cz.cuni.amis.utils.astar

Class AStar<NODE>

java.lang.Object

cz.cuni.amis.utils.astar.AStar<NODE>

public class AStar<NODE>
extends 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 (POJOs). 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.

Note about the speed

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

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

Constructor Summary

Constructors

Constructor and Description
AStar()

Method Summary

Methods

Modifier and Type	Method and Description
static <NODE> AStarResult<NODE>	aStar(AStarMap<NODE> map, AStarEvaluator<NODE> evaluator, NODE start, NODE goal) Method performing an AStar search over graph defined inside AStarMap starting from 'start' node driving itself towards 'goal' using heuristic and extra costs defined by AStarEvaluator.
static <NODE> AStarResult<NODE>	aStar(AStarMap<NODE> map, AStarEvaluator<NODE> evaluator, NODE start, NODE goal, int maxIterations) Method performing an AStar search over graph defined inside AStarMap starting from 'start' node driving itself towards 'goal' using heuristic and extra costs defined by AStarEvaluator.
static <NODE> AStarResult<NODE>	aStar(AStarMap<NODE> map, AStarHeuristic<NODE> heuristic, NODE start, NODE goal) Method performing an AStar search over graph defined inside AStarMap starting from 'start' node driving itself towards 'goal' using heuristic defined by AStarHeuristic.
static <NODE> AStarResult<NODE>	aStar(AStarMap<NODE> map, AStarHeuristic<NODE> heuristic, NODE start, NODE goal, int maxIterations) Method performing an AStar search over graph defined inside AStarMap starting from 'start' node driving itself towards 'goal' using heuristic defined by AStarHeuristic.
static <NODE> AStarResult<NODE>	aStar(AStarMap<NODE> map, NODE start, AStarGoal<NODE> goal) Method performing an AStar search over graph defined inside AStarMap starting from 'start' node driving itself towards goal that is described by AStarGoal.
static <NODE> AStarResult<NODE>	aStar(AStarMap<NODE> map, NODE start, AStarGoal<NODE> goal, long iterationsMax) Method performing an AStar search over graph defined inside AStarMap starting from 'start' node driving itself towards goal that is described by AStarGoal.

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 <NODE> AStarResult<NODE> aStar(AStarMap<NODE> map,
                             NODE start,
                             AStarGoal<NODE> goal,
                             long iterationsMax)

Method performing an AStar search over graph defined inside AStarMap 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* won't even start! If it is < 0 it will run until the 'goal' is found all nodes are evaluated.

Parameters:

map -

start -

goal -

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

aStar

public static <NODE> AStarResult<NODE> aStar(AStarMap<NODE> map,
                             NODE start,
                             AStarGoal<NODE> goal)

Method performing an AStar search over graph defined inside AStarMap 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.

This method performs 'unbounded' AStar search, i.e., it does not limit a number of iterations the algorithm will perform.

Type Parameters:

NODE -

Parameters:

map -

start -

goal -

Returns:

aStar

public static <NODE> AStarResult<NODE> aStar(AStarMap<NODE> map,
                             AStarEvaluator<NODE> evaluator,
                             NODE start,
                             NODE goal,
                             int maxIterations)

Method performing an AStar search over graph defined inside AStarMap starting from 'start' node driving itself towards 'goal' using heuristic and extra costs defined by AStarEvaluator.

AStarMap provides informations about node neighbours and edge costs, while AStarEvaluator contains definition of the heuristic + extra edge 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 is < 0 it will run until the 'goal' is found all nodes are evaluated.

WARNING: Class that is used for NODE must have correctly defined Object.equals(Object) because it will be used to recognized whether the current evaluated node is the same as the goal or not!

Type Parameters:

NODE -

Parameters:

map -

evaluator -

start -

goal -

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

Returns:

aStar

public static <NODE> AStarResult<NODE> aStar(AStarMap<NODE> map,
                             AStarEvaluator<NODE> evaluator,
                             NODE start,
                             NODE goal)

Method performing an AStar search over graph defined inside AStarMap starting from 'start' node driving itself towards 'goal' using heuristic and extra costs defined by AStarEvaluator.

AStarMap provides informations about node neighbours and edge costs, while AStarEvaluator contains definition of the heuristic + extra edge info about map nodes.

This method performs 'unbounded' AStar search, i.e., it does not limit a number of iterations the algorithm will perform.

WARNING: Class that is used for NODE must have correctly defined Object.equals(Object) because it will be used to recognized whether the current evaluated node is the same as the goal or not!

Type Parameters:

NODE -

Parameters:

map -

evaluator -

start -

goal -

Returns:

aStar

public static <NODE> AStarResult<NODE> aStar(AStarMap<NODE> map,
                             AStarHeuristic<NODE> heuristic,
                             NODE start,
                             NODE goal,
                             int maxIterations)

Method performing an AStar search over graph defined inside AStarMap starting from 'start' node driving itself towards 'goal' using heuristic defined by AStarHeuristic.

AStarMap provides informations about node neighbours and edge costs, while AStarHeuristic contains definition of the heuristic.

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 is < 0 it will run until the 'goal' is found all nodes are evaluated.

WARNING: Class that is used for NODE must have correctly defined Object.equals(Object) because it will be used to recognized whether the current evaluated node is the same as the goal or not!

Type Parameters:

NODE -

Parameters:

map -

evaluator -

start -

goal -

maxIterations -

Returns:

aStar

public static <NODE> AStarResult<NODE> aStar(AStarMap<NODE> map,
                             AStarHeuristic<NODE> heuristic,
                             NODE start,
                             NODE goal)

Method performing an AStar search over graph defined inside AStarMap starting from 'start' node driving itself towards 'goal' using heuristic defined by AStarHeuristic.

AStarMap provides informations about node neighbours and edge costs, while AStarHeuristic contains definition of the heuristic.

This method performs 'unbounded' AStar search, i.e., it does not limit a number of iterations the algorithm will perform.

WARNING: Class that is used for NODE must have correctly defined Object.equals(Object) because it will be used to recognized whether the current evaluated node is the same as the goal or not!

Type Parameters:

NODE -

Parameters:

map -

heuristic -

start -

goal -

Returns: