cz.cuni.amis.pathfinding.alg.astar
Class AStar<NODE>

java.lang.Object
  cz.cuni.amis.pathfinding.alg.astar.AStar<NODE>

public class AStar<NODE>
extends Object

Implementation of generic A* algorithm, better refered to as A* Machine according to Dan Higgins, Generic A* Pathfind paper from AI Gaming Wisdom, 2002

What is A*

----------

A* is space-search algorithm using a custom-built heuristic. It's an improved version of well-known Dijkstra algorithm which is used to find the shortest path in weighted graphs. Instead of picking the node with the smallest path from the start node it chooses node which seems to be on the shortest path to the goal node (and this guess is based on provided heuristic).

Note

----

Insted of weights we speak about cost of the edges.

Limitation of A*

----------------

1) A* doesn't work over graphs with negative edge costs.

2) heuristic has to be correct & monotonic

First we have to specify some interfaces for A* to work

------------------------------------------------------

1. IPFMap that provides the search-space notion for the A*, this implementation should be agent-agnostic, that is it should not incorporate any particular limitations/abilities into it
2. IPFMapView that provides agent's customized view of the map (extra arc costs, node filtering, etc.)
3. IPFGoal that provides the heuristic function + the goal definition

Note about Nodes

----------------

Note that we don't need to have a Node interface so you're free to have any nodes you want (POJOs). But implementation of A* requires the nodes to have Object.hashCode() and Object#equals() implemented correctly, which should be a good practice!

Note that also means you can't have two nodes which are equals in the map!

Note that if you have "unique object" for every "node", then the Java standard Object.hashCode() and Object#equals() implementations (pointer checking) are sufficient.

Ideas behind IPFMap, IPFMapView IPFGoal

---------------------------------------------------------------

Usually you will have only one world / state space representation (that is IPFMap) but you need to change the cost of edges between nodes according to your agent (imagine a fish) for which you search the path (IPFMapView). Finally you will need to search the space for different nodes possibly using different heuristics based on the goal pursued (IPFGoal).

Imagine the situation with the lake (map) / human (one agent) / fish (another agent). Human may swim across the lake but it's faster to run around it (so you need to give the edges between water tiles an extra cost using IPFMapView.getArcExtraCost(Object, Object, int)).

Fish can swim really fast but can't get out of the water (so you need to forbid tiles around the lake and give the edges between the lakes' tiles using IPFMapView.isNodeOpened(Object)).

Finally you may have hierarchical representation of your graph that has different arc-cost for humans and fishes (taking into account the lake), thus you might need to specify different heuristic function for humans and fishes using IPFGoal.getEstimatedCostToGoal(Object).

So the AStarMap will represent the world with the lake with default cost of the edges. AStarGoal may change the edges cost / forbid some nodes completely. So you will implement one goal for a human and another for a fish.

Note about the speed

--------------------

Speed of algorithm is based upon the speed of AStarOpenList and AStarCloseList.

Constructor Summary

AStar(IPFMap<NODE> map)
AStar configured with "map" with no agent-specific view on the map, IPFMapView.DefaultView is used.

AStar(IPFMap<NODE> map, IPFMapView<NODE> view)
AStar configured with "map" and agent-specific view on the map, if "view" is null, IPFMapView.DefaultView is going to be used.

Method Summary

AStarResult<NODE>	findPath(IPFGoal<NODE> goal) Method performing an AStar search over graph defined inside IPFMap starting from 'start' node driving itself towards goal that is described by IPFGoal.
AStarResult<NODE>	findPath(IPFGoal<NODE> goal, IPFMapView<NODE> mapView) Method performing an AStar search over graph defined inside IPFMap starting from 'start' node driving itself towards goal that is described by IPFGoal.
AStarResult<NODE>	findPath(IPFGoal<NODE> goal, long iterationsMax) Method performing an AStar search over graph defined inside IPFMap starting from 'start' node driving itself towards goal that is described by AStarGoal.
IPFMap<NODE>	getMap() Map abstraction the AStar is working with.
IPFMapView<NODE>	getMapView() Returns agent-specific map view for the map.
void	setMap(IPFMap<NODE> map) Sets map abstraction into the AStar.
void	setMapView(IPFMapView<NODE> mapView) Sets agent-specific map view for the map.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AStar

public AStar(IPFMap<NODE> map)

AStar configured with "map" with no agent-specific view on the map, IPFMapView.DefaultView is used.

Parameters:

map -

AStar

public AStar(IPFMap<NODE> map,
             IPFMapView<NODE> view)

AStar configured with "map" and agent-specific view on the map, if "view" is null, IPFMapView.DefaultView is going to be used.

Parameters:

map -

view - may be null

Method Detail

getMap

public IPFMap<NODE> getMap()

Map abstraction the AStar is working with.

Returns:

setMap

public void setMap(IPFMap<NODE> map)

Sets map abstraction into the AStar.

Parameters:

map -

getMapView

public IPFMapView<NODE> getMapView()

Returns agent-specific map view for the map.

Returns:

setMapView

public void setMapView(IPFMapView<NODE> mapView)

Sets agent-specific map view for the map.

Parameters:

mapView -

findPath

public AStarResult<NODE> findPath(IPFGoal<NODE> goal,
                                  long iterationsMax)

Method performing an AStar search over graph defined inside IPFMap starting from 'start' node driving itself towards goal that is described by AStarGoal. Note that AStarGoal also contains a heuristic AStarHeuristic.

AStarMap provides informations about node neighbours and edge costs, while AStarGoal contains the definition of goal node and extra cost / extra info about map nodes.

You may also specify maxIterations - "how long the A* should search" equals to number of evaluated nodes. If it's < 0 then A* will run until the 'goal' is found all nodes are evaluated and there is nowhere to search. If it is == 0, the A* won't even start!

Parameters:

map -

start -

goal -

iterationsMax - maximum of iterations to be made by algorithm during the search (zero or negative number == infinite)

findPath

public AStarResult<NODE> findPath(IPFGoal<NODE> goal,
                                  IPFMapView<NODE> mapView)

Method performing an AStar search over graph defined inside IPFMap starting from 'start' node driving itself towards goal that is described by IPFGoal. Note that IPFGoal also contains a heuristic function.

IPFMap provides informations about node neighbours and edge costs, while IPFGoal contains the definition of goal node and extra cost / extra info about map nodes.

Does not have any cap on the number of evaluated nodes. Will run until the 'goal' is found all nodes are evaluated and there is nowhere to search.

Parameters:

goal - defines START-NODE + GOAL-NODE

mapView - use custom IPFMapView

findPath

public AStarResult<NODE> findPath(IPFGoal<NODE> goal)

Method performing an AStar search over graph defined inside IPFMap starting from 'start' node driving itself towards goal that is described by IPFGoal. Note that IPFGoal also contains a heuristic function.

IPFMap provides informations about node neighbours and edge costs, while IPFGoal contains the definition of goal node and extra cost / extra info about map nodes.

Does not have any cap on the number of evaluated nodes. Will run until the 'goal' is found all nodes are evaluated and there is nowhere to search.

Parameters:

goal - defines START-NODE + GOAL-NODE