org.newdawn.slick.util.pathfinding
Class AStarPathFinder

java.lang.Object
  org.newdawn.slick.util.pathfinding.AStarPathFinder

All Implemented Interfaces:

PathFinder, PathFindingContext

public class AStarPathFinder
extends java.lang.Object
implements PathFinder, PathFindingContext

A path finder implementation that uses the AStar heuristic based algorithm to determine a path.

Author:

Kevin Glass

Constructor Summary

AStarPathFinder(TileBasedMap map, int maxSearchDistance, boolean allowDiagMovement)
Create a path finder with the default heuristic - closest to target.

AStarPathFinder(TileBasedMap map, int maxSearchDistance, boolean allowDiagMovement, AStarHeuristic heuristic)
Create a path finder

Method Summary

protected void	addToClosed(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node) Add a node to the closed list
protected void	addToOpen(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node) Add a node to the open list
Path	findPath(Mover mover, int sx, int sy, int tx, int ty) Find a path from the starting location provided (sx,sy) to the target location (tx,ty) avoiding blockages and attempting to honour costs provided by the tile map.
int	getCurrentX() Get the X coordinate of the node currently being evaluated
int	getCurrentY() Get the Y coordinate of the node currently being evaluated
protected org.newdawn.slick.util.pathfinding.AStarPathFinder.Node	getFirstInOpen() Get the first element from the open list.
float	getHeuristicCost(Mover mover, int x, int y, int tx, int ty) Get the heuristic cost for the given location.
float	getMovementCost(Mover mover, int sx, int sy, int tx, int ty) Get the cost to move through a given location
Mover	getMover() Get the object being moved along the path if any
int	getSearchDistance() Get the distance that has been searched to reach this point
int	getSourceX() Get the x coordinate of the source location
int	getSourceY() Get the y coordinate of the source location
protected boolean	inClosedList(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node) Check if the node supplied is in the closed list
protected boolean	inOpenList(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node) Check if a node is in the open list
protected boolean	isValidLocation(Mover mover, int sx, int sy, int x, int y) Check if a given location is valid for the supplied mover
protected void	removeFromClosed(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node) Remove a node from the closed list
protected void	removeFromOpen(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node) Remove a node from the open list

Methods inherited from class java.lang.Object

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

Constructor Detail

AStarPathFinder

public AStarPathFinder(TileBasedMap map,
                       int maxSearchDistance,
                       boolean allowDiagMovement)

Create a path finder with the default heuristic - closest to target.

Parameters:

map - The map to be searched

maxSearchDistance - The maximum depth we'll search before giving up

allowDiagMovement - True if the search should try diaganol movement

AStarPathFinder

public AStarPathFinder(TileBasedMap map,
                       int maxSearchDistance,
                       boolean allowDiagMovement,
                       AStarHeuristic heuristic)

Create a path finder

Parameters:

heuristic - The heuristic used to determine the search order of the map

map - The map to be searched

maxSearchDistance - The maximum depth we'll search before giving up

allowDiagMovement - True if the search should try diaganol movement

Method Detail

findPath

public Path findPath(Mover mover,
                     int sx,
                     int sy,
                     int tx,
                     int ty)

Description copied from interface: PathFinder

Find a path from the starting location provided (sx,sy) to the target location (tx,ty) avoiding blockages and attempting to honour costs provided by the tile map.

Specified by:

findPath in interface PathFinder

Parameters:

mover - The entity that will be moving along the path. This provides a place to pass context information about the game entity doing the moving, e.g. can it fly? can it swim etc.

sx - The x coordinate of the start location

sy - The y coordinate of the start location

tx - The x coordinate of the target location

ty - Teh y coordinate of the target location

Returns:

The path found from start to end, or null if no path can be found.

See Also:

PathFinder.findPath(Mover, int, int, int, int)

getCurrentX

public int getCurrentX()

Get the X coordinate of the node currently being evaluated

Returns:

The X coordinate of the node currently being evaluated

getCurrentY

public int getCurrentY()

Get the Y coordinate of the node currently being evaluated

Returns:

The Y coordinate of the node currently being evaluated

getFirstInOpen

protected org.newdawn.slick.util.pathfinding.AStarPathFinder.Node getFirstInOpen()

Get the first element from the open list. This is the next one to be searched.

Returns:

The first element in the open list

addToOpen

protected void addToOpen(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node)

Add a node to the open list

Parameters:

node - The node to be added to the open list

inOpenList

protected boolean inOpenList(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node)

Check if a node is in the open list

Parameters:

node - The node to check for

Returns:

True if the node given is in the open list

removeFromOpen

protected void removeFromOpen(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node)

Remove a node from the open list

Parameters:

node - The node to remove from the open list

addToClosed

protected void addToClosed(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node)

Add a node to the closed list

Parameters:

node - The node to add to the closed list

inClosedList

protected boolean inClosedList(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node)

Check if the node supplied is in the closed list

Parameters:

node - The node to search for

Returns:

True if the node specified is in the closed list

removeFromClosed

protected void removeFromClosed(org.newdawn.slick.util.pathfinding.AStarPathFinder.Node node)

Remove a node from the closed list

Parameters:

node - The node to remove from the closed list

isValidLocation

protected boolean isValidLocation(Mover mover,
                                  int sx,
                                  int sy,
                                  int x,
                                  int y)

Check if a given location is valid for the supplied mover

Parameters:

mover - The mover that would hold a given location

sx - The starting x coordinate

sy - The starting y coordinate

x - The x coordinate of the location to check

y - The y coordinate of the location to check

Returns:

True if the location is valid for the given mover

getMovementCost

public float getMovementCost(Mover mover,
                             int sx,
                             int sy,
                             int tx,
                             int ty)

Get the cost to move through a given location

Parameters:

mover - The entity that is being moved

sx - The x coordinate of the tile whose cost is being determined

sy - The y coordiante of the tile whose cost is being determined

tx - The x coordinate of the target location

ty - The y coordinate of the target location

Returns:

The cost of movement through the given tile

getHeuristicCost

public float getHeuristicCost(Mover mover,
                              int x,
                              int y,
                              int tx,
                              int ty)

Get the heuristic cost for the given location. This determines in which order the locations are processed.

Parameters:

mover - The entity that is being moved

x - The x coordinate of the tile whose cost is being determined

y - The y coordiante of the tile whose cost is being determined

tx - The x coordinate of the target location

ty - The y coordinate of the target location

Returns:

The heuristic cost assigned to the tile

getMover

public Mover getMover()

Description copied from interface: PathFindingContext

Get the object being moved along the path if any

Specified by:

getMover in interface PathFindingContext

Returns:

The object being moved along the path

See Also:

PathFindingContext.getMover()

getSearchDistance

public int getSearchDistance()

Description copied from interface: PathFindingContext

Get the distance that has been searched to reach this point

Specified by:

getSearchDistance in interface PathFindingContext

Returns:

The distance that has been search to reach this point

See Also:

PathFindingContext.getSearchDistance()

getSourceX

public int getSourceX()

Description copied from interface: PathFindingContext

Get the x coordinate of the source location

Specified by:

getSourceX in interface PathFindingContext

Returns:

The x coordinate of the source location

See Also:

PathFindingContext.getSourceX()

getSourceY

public int getSourceY()

Description copied from interface: PathFindingContext

Get the y coordinate of the source location

Specified by:

getSourceY in interface PathFindingContext

Returns:

The y coordinate of the source location

See Also:

PathFindingContext.getSourceY()