VANET Simulator
 All Classes Functions Variables
Public Member Functions | List of all members
vanetsim.routing.A_Star.A_Star_Algorithm Class Reference
Inheritance diagram for vanetsim.routing.A_Star.A_Star_Algorithm:
vanetsim.routing.RoutingAlgorithm

Public Member Functions

 A_Star_Algorithm ()
 
ArrayDeque< NodegetRouting (int mode, int direction, int startX, int startY, Street startStreet, double startStreetPos, int targetX, int targetY, Street targetStreet, double targetStreetPos, Street[] penaltyStreets, int[] penaltyDirections, int[] penalties, int penaltySize, int additionalVar)
 

Detailed Description

An implementation of the A*-algorithm. A* uses an heuristic to limit the distance calculations and thus results in a much faster routing compared with Dijkstra. It also always finds the optimal results like Dijkstra if the heuristic is correctly chosen (which it is in this implementation). The implementation is based on the pseudocode from German Wikipedia (link last time checked on 15.08.2008). However, it is modified and expanded with performance optimizations and necessary changes for usage in a vanet-simulator (one-way-routes, barring...). An own data structure is used which is basically the official PriorityQueue implementation but with unnecessary function calls and casts removed. This uses about 25% less cpu than the original PriorityQueue and about 40% less than a TreeSet. A basic ArrayList would take about 4x the performance.

Note for developers: It makes no sense to try to process streets which only have 2 crossings (no real junctions!) as one large street. It surely saves some sqrt-operations but you trade this with lots of necessary checks and lookups and (what is a larger problem) you need to rebuild the successors later because the vehicle needs a full path! Furthermore, it's also not a real A* anymore as you traverse nodes which a real A* would not have checked because their f-value is too high. In a (not fully optimized) test scenario, this concept resulted in about 30% lower (!) performance so it's really not worth thinking about it.

Constructor & Destructor Documentation

vanetsim.routing.A_Star.A_Star_Algorithm.A_Star_Algorithm ( )
inline

Instantiates a new A_Star_Algo.

Member Function Documentation

ArrayDeque<Node> vanetsim.routing.A_Star.A_Star_Algorithm.getRouting ( int  mode,
int  direction,
int  startX,
int  startY,
Street  startStreet,
double  startStreetPos,
int  targetX,
int  targetY,
Street  targetStreet,
double  targetStreetPos,
Street[]  penaltyStreets,
int[]  penaltyDirections,
int[]  penalties,
int  penaltySize,
int  additionalVar 
)
inlinevirtual

Gets a routing result.

Parameters
modeThe mode in which to operate. 0 means calculating with street lengths, 1 means calculating based on speed/time
direction0=don't care about direction, -1=from startNode to endNode, 1=from endNode to startNode
startXthe x coordinate of the start point
startYthe y coordinate of the start point
startStreetthe street on which the start point lies
startStreetPosthe position measured in cm from the startNode of the startStreet
targetXthe x coordinate of the target point
targetYthe y coordinate of the target point
targetStreetthe street on which the target point lies
targetStreetPosthe position measured in cm from the startNode of the targetStreet
penaltyStreetsan array with all streets which have penalties.
penaltyDirectionsan array with directions corresponding to penaltyStreets. 1 in the array means from endNode to startNode, 0 means both directions and -1 means from startNode to endNode
penaltiesan array with all penalties measured in cm.
penaltySizehow many penalties exist.
additionalVarcan be used to set the maximum speed for calculations in mode=1
Returns
An ArrayDeque for returning the result. The first element will be the start node and the last will be the end node of the routing.
See Also
vanetsim.routing.RoutingAlgorithm::getRouting(int, int, int, int, Street, double, int, int, Street, double, Street[], int[], int[], int, int)

Implements vanetsim.routing.RoutingAlgorithm.


The documentation for this class was generated from the following file: