cz.cuni.astar
Class AStar

java.lang.Object
  cz.cuni.astar.AStar

public class AStar
extends java.lang.Object

======================================================== This file holds implementation of generic A* algorithm, better refered to as A* Machine according to Dan Higgins, Generic A* Pathfind, 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 -> it has to be lower estimation of the cost to the goal node (in 2D, 3D an euklidian metric will do the job). First we have to specify some interfaces for A* ----------------------------------------------- we will need a few things: Open List Class Close List Class Goal (which can tell us about extra costs, when work is done, etc) Map (which tells us about travel cost between nodes and can return node's neighbours) Note about Nodes ---------------- Note that we don't need to have a Node interface so you're free to have any nodes you want. But implementation of A* requires the nodes to have hashCode() and 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!) Idea behind AStarGoal / AStarMap -------------------------------- Usually you will have only one world / state space representation but you need to change the cost of edges between nodes according to let say creature for which you search the path. Imagine the situation with the lake / human / fish. 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). 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 an negative extra cost). 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. If you have a better example send it to jakub.gemrot@gmail.com ;-) Note about the speed -------------------- Speed of algorithm is based upon the speed of AStarOpenList and AStarCloseList.

Constructor Summary

AStar()

Method Summary

static AStarResult	aStar(AStarGoal goal, AStarMap map, java.lang.Object start) For A* to run you have to provide AStarGoal and AStarMap and startNode.
static AStarResult	aStar(AStarGoal goal, AStarMap map, java.lang.Object start, long iterationsMax) For A* to run you have to provide AStarGoal and AStarMap and startNode.

Methods inherited from class java.lang.Object

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

Constructor Detail

AStar

public AStar()

Method Detail

aStar

public static AStarResult aStar(AStarGoal goal,
                                AStarMap map,
                                java.lang.Object start,
                                long iterationsMax)

For A* to run you have to provide AStarGoal and AStarMap and startNode. AStarMap provides informations about node neighbours and edge costs, whil 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* won't even start! If it's negative number then it will run until the goalNode is found or all nodes is evaluated.

Parameters:

goal -

map -

start - the node from which A* begins the search

iterationsMax -

aStar

public static AStarResult aStar(AStarGoal goal,
                                AStarMap map,
                                java.lang.Object start)

For A* to run you have to provide AStarGoal and AStarMap and startNode. AStarMap provides informations about node neighbours and edge costs, whil AStarGoal contains the definition of goal node and extra cost / extra info about map nodes. Calls aStar(goal, map, start, -1) -> run without the constrain on number of interations.

Parameters:

goal -

map -

start - the node from which A* begins the search