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 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.
|
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.