org.newdawn.slick.util.pathfinding
Class AStarPathFinder

java.lang.Object
  extended by 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()


Copyright © 2006 New Dawn Software. All Rights Reserved.