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.

Constructor Summary

A_Star_Algorithm()
Instantiates a new A_Star_Algo.

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

Constructor Detail

A_Star_Algorithm

public A_Star_Algorithm()

Instantiates a new A_Star_Algo.

Method Detail

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

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)