org.jscience.computing.ai
Class AStarPathfinder

java.lang.Object
  extended by org.jscience.computing.ai.AStarPathfinder
All Implemented Interfaces:
Pathfinder, Steppable

public class AStarPathfinder
extends java.lang.Object
implements Pathfinder

Implements the A algorithm. Pathing can be done on any class that implements the Navigable interface.

See Also:
org.jscience.computing.ai.ai.Navigable

Nested Class Summary
static class AStarPathfinder.AStarNode
          The pathfinder node.
 
Nested classes/interfaces inherited from interface org.jscience.computing.ai.Pathfinder
Pathfinder.Node
 
Field Summary
static int IN_PROGRESS
          Returned by getStatus if the pathfinder is still running.
protected  java.util.LinkedList listClosed
          The closed list.
protected  java.util.LinkedList listOpen
          The open list.
protected  Navigable navMap
          The current navigable environment.
protected  AStarPathfinder.AStarNode nodeBest
          The current best node.
protected  AStarPathfinder.AStarNode nodeGoal
          The goal node.
protected  AStarPathfinder.AStarNode nodeStart
          The start node.
static int PATH_FOUND
          Returned by getStatus if a path has been found.
static int PATH_NOT_FOUND
          Returned by getStatus if a path cannot be found.
protected  int pathStatus
          The current status of the pathfinder.
 
Constructor Summary
AStarPathfinder()
          Creates a new instance of AStarPathfinder
 
Method Summary
protected  void addToOpen(AStarPathfinder.AStarNode node)
          Add the new child to the open list, ordering by the f-value.
protected  AStarPathfinder.AStarNode checkClosed(AStarPathfinder.AStarNode node)
          Check the closed list for the given node.
protected  AStarPathfinder.AStarNode checkOpen(AStarPathfinder.AStarNode node)
          Check the open list for a given node.
protected  void createChildren(AStarPathfinder.AStarNode node)
          Create the children surrounding the current best node.
 void doStep()
          Iterate the pathfinder through one step.
protected  AStarPathfinder.AStarNode getBest()
          Assigns the best node from the open list.
 AStarPathfinder.AStarNode getBestNode()
          Returns the current best node.
 java.util.LinkedList getClosed()
          Return the closed list.
 AStarPathfinder.AStarNode getGoal()
          Returns the goal node.
 java.util.LinkedList getOpen()
          Return the open list.
 AStarPathfinder.AStarNode getStart()
          Returns the start node.
 int getStatus()
          Return the current status of the pathfinder.
 void init()
          Initialize the pathfinder.
protected  void linkChild(AStarPathfinder.AStarNode node, int x, int y)
          Link the children to the parent node.
 void reset()
          Reset the pathfinder (just calls init).
 void setEndpoints(AStarPathfinder.AStarNode start, AStarPathfinder.AStarNode goal)
          Set the starting and goal points for the pathfinder.
 void setEndpoints(int sx, int sy, int gx, int gy)
          Sets the starting and goal points for the pathfinder.
 void setGoal(AStarPathfinder.AStarNode goal)
          Set the goal node.
 void setNavigable(Navigable map)
          Sets the navigable to use in the pathfinder.
 void setStart(AStarPathfinder.AStarNode start)
          Set the start node.
protected  void updateParents(AStarPathfinder.AStarNode node)
          Update the parents for the new route.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

PATH_NOT_FOUND

public static final int PATH_NOT_FOUND
Returned by getStatus if a path cannot be found.

See Also:
getStatus(), Constant Field Values

PATH_FOUND

public static final int PATH_FOUND
Returned by getStatus if a path has been found.

See Also:
getStatus(), Constant Field Values

IN_PROGRESS

public static final int IN_PROGRESS
Returned by getStatus if the pathfinder is still running.

See Also:
getStatus(), Constant Field Values

pathStatus

protected int pathStatus
The current status of the pathfinder.

See Also:
PATH_FOUND, PATH_NOT_FOUND, IN_PROGRESS

listOpen

protected java.util.LinkedList listOpen
The open list.


listClosed

protected java.util.LinkedList listClosed
The closed list.


nodeGoal

protected AStarPathfinder.AStarNode nodeGoal
The goal node.


nodeStart

protected AStarPathfinder.AStarNode nodeStart
The start node.


nodeBest

protected AStarPathfinder.AStarNode nodeBest
The current best node. The best node is taken from the open list after every iteration of doStep.


navMap

protected Navigable navMap
The current navigable environment.

Constructor Detail

AStarPathfinder

public AStarPathfinder()
Creates a new instance of AStarPathfinder

Method Detail

getStatus

public int getStatus()
Return the current status of the pathfinder.

Returns:
the pathfindre status.
See Also:
pathStatus

doStep

public void doStep()
Iterate the pathfinder through one step.

Specified by:
doStep in interface Steppable

init

public void init()
Initialize the pathfinder.

Specified by:
init in interface Steppable
Throws:
java.lang.IllegalArgumentException - DOCUMENT ME!

reset

public void reset()
Reset the pathfinder (just calls init).

Specified by:
reset in interface Steppable

setNavigable

public void setNavigable(Navigable map)
Sets the navigable to use in the pathfinder. The object must implement the Navigable interface.

Parameters:
map - the map (or other Navigable object) to find a path through.

setEndpoints

public void setEndpoints(int sx,
                         int sy,
                         int gx,
                         int gy)
Sets the starting and goal points for the pathfinder.

Parameters:
sx - the start x-position.
sy - the start y-position.
gx - the goal x-position.
gy - the goal y-position.

setEndpoints

public void setEndpoints(AStarPathfinder.AStarNode start,
                         AStarPathfinder.AStarNode goal)
Set the starting and goal points for the pathfinder. This method uses AStarNode's x and y variables, the pathfinder sets all the other necessary node parameters.

Parameters:
start - the start node.
goal - the goal node.

getStart

public AStarPathfinder.AStarNode getStart()
Returns the start node.

Returns:
the start node.

setStart

public void setStart(AStarPathfinder.AStarNode start)
Set the start node.

Parameters:
start - the start node.

setGoal

public void setGoal(AStarPathfinder.AStarNode goal)
Set the goal node.

Parameters:
goal - the goal node.

getGoal

public AStarPathfinder.AStarNode getGoal()
Returns the goal node.

Returns:
the goal node.

getBest

protected AStarPathfinder.AStarNode getBest()
Assigns the best node from the open list.

Returns:
the best node.

getBestNode

public AStarPathfinder.AStarNode getBestNode()
Returns the current best node.

Returns:
the best node.

createChildren

protected void createChildren(AStarPathfinder.AStarNode node)
Create the children surrounding the current best node.

Parameters:
node - the node to create the children from.

linkChild

protected void linkChild(AStarPathfinder.AStarNode node,
                         int x,
                         int y)
Link the children to the parent node. This method may also update the parent path if a shorter path is found.

Parameters:
node - the parent node.
x - the x-position of the new child.
y - the y-position of the new child.

addToOpen

protected void addToOpen(AStarPathfinder.AStarNode node)
Add the new child to the open list, ordering by the f-value.

Parameters:
node - the node to add to the open list.

updateParents

protected void updateParents(AStarPathfinder.AStarNode node)
Update the parents for the new route.

Parameters:
node - the root node.

checkOpen

protected AStarPathfinder.AStarNode checkOpen(AStarPathfinder.AStarNode node)
Check the open list for a given node.

Parameters:
node - the node to check for.
Returns:
the node, if found, otherwise null.

checkClosed

protected AStarPathfinder.AStarNode checkClosed(AStarPathfinder.AStarNode node)
Check the closed list for the given node.

Parameters:
node - the node to check for.
Returns:
the node, if found, otherwise null.

getOpen

public java.util.LinkedList getOpen()
Return the open list.

Returns:
the open list.

getClosed

public java.util.LinkedList getClosed()
Return the closed list.

Returns:
the closed list.