com.b3dgs.lionengine.game.pathfinding
Class AStarPathFinder

java.lang.Object
  extended by com.b3dgs.lionengine.game.pathfinding.AStarPathFinder
All Implemented Interfaces:
PathFinder

public class AStarPathFinder
extends java.lang.Object
implements PathFinder

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


Constructor Summary
AStarPathFinder(PathBasedMap<? extends AbstractPathTile> map, int maxSearchDistance, boolean allowDiagMovement)
          Create a path finder with the default heuristic - closest to target.
AStarPathFinder(PathBasedMap<? extends AbstractPathTile> map, int maxSearchDistance, boolean allowDiagMovement, AStarHeuristic heuristic)
          Create a path finder.
 
Method Summary
protected  void addToClosed(Node node)
          Add a node to the closed list.
protected  void addToOpen(Node node)
          Add a node to the open list.
 Path findPath(Pathfindable mover, int sx, int sy, int tx, int ty, boolean ignoreRef)
          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.
protected  Node getFirstInOpen()
          Get the first element from the open list.
 float getHeuristicCost(Pathfindable mover, int x, int y, int tx, int ty)
          Get the heuristic cost for the given location.
 float getMovementCost(Pathfindable mover, int sx, int sy, int tx, int ty)
          Get the cost to move through a given location.
protected  boolean inClosedList(Node node)
          Check if the node supplied is in the closed list.
protected  boolean inOpenList(Node node)
          Check if a node is in the open list.
protected  boolean isValidLocation(Pathfindable mover, int sx, int sy, int x, int y, boolean ignoreRef)
          Check if a given location is valid for the supplied mover.
protected  void removeFromClosed(Node node)
          Remove a node from the closed list.
protected  void removeFromOpen(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(PathBasedMap<? extends AbstractPathTile> map,
                       int maxSearchDistance,
                       boolean allowDiagMovement)
Create a path finder with the default heuristic - closest to target.

Parameters:
map - map to be searched.
maxSearchDistance - maximum depth we'll search before giving up.
allowDiagMovement - true if the search should try diaganol movement.

AStarPathFinder

public AStarPathFinder(PathBasedMap<? extends AbstractPathTile> map,
                       int maxSearchDistance,
                       boolean allowDiagMovement,
                       AStarHeuristic heuristic)
Create a path finder.

Parameters:
heuristic - heuristic used to determine the search order of the map.
map - map to be searched.
maxSearchDistance - maximum depth we'll search before giving up.
allowDiagMovement - if the search should try diaganol movement.
Method Detail

findPath

public Path findPath(Pathfindable mover,
                     int sx,
                     int sy,
                     int tx,
                     int ty,
                     boolean ignoreRef)
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 - entity that will be moving along the path.
sx - x coordinate of the start location.
sy - y coordinate of the start location.
tx - x coordinate of the target location.
ty - y coordinate of the target location.
ignoreRef - ignore map array ref checking.
Returns:
path found from start to end, or null if no path can be found.

getFirstInOpen

protected Node getFirstInOpen()
Get the first element from the open list. This is the next one to be searched.

Returns:
first element in the open list.

addToOpen

protected void addToOpen(Node node)
Add a node to the open list.

Parameters:
node - node to be added to the open list.

inOpenList

protected boolean inOpenList(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(Node node)
Remove a node from the open list.

Parameters:
node - node to remove from the open list.

addToClosed

protected void addToClosed(Node node)
Add a node to the closed list.

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

inClosedList

protected boolean inClosedList(Node node)
Check if the node supplied is in the closed list.

Parameters:
node - node to search for.
Returns:
true if the node specified is in the closed list.

removeFromClosed

protected void removeFromClosed(Node node)
Remove a node from the closed list.

Parameters:
node - the node to remove from the closed list.

isValidLocation

protected boolean isValidLocation(Pathfindable mover,
                                  int sx,
                                  int sy,
                                  int x,
                                  int y,
                                  boolean ignoreRef)
Check if a given location is valid for the supplied mover.

Parameters:
mover - mover that would hold a given location.
sx - starting x coordinate.
sy - starting y coordinate.
x - x coordinate of the location to check.
y - y coordinate of the location to check.
ignoreRef - ignore map ref array checking.
Returns:
true if the location is valid for the given mover.

getMovementCost

public float getMovementCost(Pathfindable mover,
                             int sx,
                             int sy,
                             int tx,
                             int ty)
Get the cost to move through a given location.

Parameters:
mover - entity that is being moved.
sx - x coordinate of the tile whose cost is being determined.
sy - y coordiante of the tile whose cost is being determined.
tx - x coordinate of the target location.
ty - y coordinate of the target location.
Returns:
cost of movement through the given tile.

getHeuristicCost

public float getHeuristicCost(Pathfindable 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 - entity that is being moved
x - x coordinate of the tile whose cost is being determined
y - y coordiante of the tile whose cost is being determined
tx - x coordinate of the target location
ty - y coordinate of the target location
Returns:
heuristic cost assigned to the tile