Public Member Functions  
A_Star_Algorithm ()  
ArrayDeque< Node >  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) 
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 vanetsimulator (onewayroutes, 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 sqrtoperations 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 fvalue 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.

inline 
Instantiates a new A_Star_Algo.

inlinevirtual 
Gets a routing result.
mode  The mode in which to operate. 0 means calculating with street lengths, 1 means calculating based on speed/time 
direction  0 =don't care about direction, 1 =from startNode to endNode, 1 =from endNode to startNode 
startX  the x coordinate of the start point 
startY  the y coordinate of the start point 
startStreet  the street on which the start point lies 
startStreetPos  the position measured in cm from the startNode of the startStreet 
targetX  the x coordinate of the target point 
targetY  the y coordinate of the target point 
targetStreet  the street on which the target point lies 
targetStreetPos  the position measured in cm from the startNode of the targetStreet 
penaltyStreets  an array with all streets which have penalties. 
penaltyDirections  an 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 
penalties  an array with all penalties measured in cm. 
penaltySize  how many penalties exist. 
additionalVar  can be used to set the maximum speed for calculations in mode=1 
ArrayDeque
for returning the result. The first element will be the start node and the last will be the end node of the routing.Implements vanetsim.routing.RoutingAlgorithm.