org.generation5.ai
Class AStarPathfinder

java.lang.Object
  org.generation5.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:

Navigable

Nested Class Summary

static class

AStarPathfinder.AStarNode The pathfinder node.

Nested classes inherited from class org.generation5.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

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.