vanetsim.routing.A_Star
Class A_Star_Algorithm
java.lang.Object
vanetsim.routing.A_Star.A_Star_Algorithm
- All Implemented Interfaces:
- RoutingAlgorithm
public final class A_Star_Algorithm
- extends java.lang.Object
- implements RoutingAlgorithm
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.
Method Summary |
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)
Gets a routing result. |
Methods inherited from class java.lang.Object |
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
A_Star_Algorithm
public A_Star_Algorithm()
- Instantiates a new A_Star_Algo.
getRouting
public 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)
- Gets a routing result.
- Specified by:
getRouting
in interface RoutingAlgorithm
- Parameters:
mode
- The mode in which to operate. 0
means calculating with street lengths, 1
means calculating based on speed/timedirection
- 0
=don't care about direction, -1
=from startNode to endNode, 1
=from endNode to startNodestartX
- the x coordinate of the start pointstartY
- the y coordinate of the start pointstartStreet
- the street on which the start point liesstartStreetPos
- the position measured in cm from the startNode of the startStreet
targetX
- the x coordinate of the target pointtargetY
- the y coordinate of the target pointtargetStreet
- the street on which the target point liestargetStreetPos
- 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 endNodepenalties
- 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
- 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:
RoutingAlgorithm.getRouting(int, int, int, int, Street, double, int, int, Street, double, Street[], int[], int[], int, int)