com.threerings.media.util
Class AStarPathUtil

java.lang.Object
  com.threerings.media.util.AStarPathUtil

public class AStarPathUtil
extends Object

The AStarPathUtil class provides a facility for finding a reasonable path between two points in a scene using the A* search algorithm.

See the path-finding article on Gamasutra for more detailed information.

Nested Class Summary

static interface	AStarPathUtil.ExtendedTraversalPred Provides extended traversibility information when computing paths.
protected static class	AStarPathUtil.Info A holding class to contain the wealth of information referenced while performing an A* search for a path through a tile array.
static class	AStarPathUtil.Node A class that represents a single traversable node in the tile array along with its current A*-specific search information.
static class	AStarPathUtil.Stepper Considers all the possible steps the piece in question can take.
static interface	AStarPathUtil.TraversalPred Provides traversibility information when computing paths.

Field Summary

protected static int	_considered The number of nodes considered in computing our path.
static int	ADJACENT_COST The standard cost to move between nodes.
static int	DIAGONAL_COST The cost to move diagonally.

Constructor Summary

AStarPathUtil()

Method Summary

protected static void	considerStep(AStarPathUtil.Info info, AStarPathUtil.Node n, int x, int y, int cost) Consider the step (n.x, n.y) to (x, y) for possible inclusion in the path.
static int	getConsidered() Returns the number of nodes considered in computing the most recent path.
protected static int	getDistanceEstimate(int ax, int ay, int bx, int by) Return a heuristic estimate of the cost to get from (ax, ay) to (bx, by).
protected static List<Point>	getNodePath(AStarPathUtil.Node n) Return a list of Point objects detailing the path from the first node (the given node's ultimate parent) to the ending node (the given node itself.)
static List<Point>	getPath(AStarPathUtil.TraversalPred tpred, AStarPathUtil.Stepper stepper, Object trav, int longest, int ax, int ay, int bx, int by, boolean partial) Return a list of Point objects representing a path from coordinates (ax, by) to (bx, by), inclusive, determined by performing an A* search in the given scene's base tile layer.
static List<Point>	getPath(AStarPathUtil.TraversalPred tpred, Object trav, int longest, int ax, int ay, int bx, int by, boolean partial) Gets a path with the default stepper which assumes the piece can move one in any of the eight cardinal directions.

Methods inherited from class java.lang.Object

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

Field Detail

ADJACENT_COST

public static final int ADJACENT_COST

The standard cost to move between nodes.

See Also:

Constant Field Values

DIAGONAL_COST

public static final int DIAGONAL_COST

The cost to move diagonally.

_considered

protected static int _considered

The number of nodes considered in computing our path.

Constructor Detail

AStarPathUtil

public AStarPathUtil()

Method Detail

getPath

public static List<Point> getPath(AStarPathUtil.TraversalPred tpred,
                                  AStarPathUtil.Stepper stepper,
                                  Object trav,
                                  int longest,
                                  int ax,
                                  int ay,
                                  int bx,
                                  int by,
                                  boolean partial)

Return a list of Point objects representing a path from coordinates (ax, by) to (bx, by), inclusive, determined by performing an A* search in the given scene's base tile layer. Assumes the starting and destination nodes are traversable by the specified traverser.

Parameters:

tpred - lets us know what tiles are traversible.

stepper - enumerates the possible steps.

trav - the traverser to follow the path.

longest - the longest allowable path in tile traversals. This arg must be less than Integer.MAX_VALUE / ADJACENT_COST, even if your stepper uses a different fucking adjacent cost.

ax - the starting x-position in tile coordinates.

ay - the starting y-position in tile coordinates.

bx - the ending x-position in tile coordinates.

by - the ending y-position in tile coordinates.

partial - if true, a partial path will be returned that gets us as close as we can to the goal in the event that a complete path cannot be located.

Returns:

the list of points in the path, or null if no path could be found.

getPath

public static List<Point> getPath(AStarPathUtil.TraversalPred tpred,
                                  Object trav,
                                  int longest,
                                  int ax,
                                  int ay,
                                  int bx,
                                  int by,
                                  boolean partial)

Gets a path with the default stepper which assumes the piece can move one in any of the eight cardinal directions.

getConsidered

public static int getConsidered()

Returns the number of nodes considered in computing the most recent path.

considerStep

protected static void considerStep(AStarPathUtil.Info info,
                                   AStarPathUtil.Node n,
                                   int x,
                                   int y,
                                   int cost)

Consider the step (n.x, n.y) to (x, y) for possible inclusion in the path.

Parameters:

info - the info object.

n - the originating node for the step.

x - the x-coordinate for the destination step.

y - the y-coordinate for the destination step.

getNodePath

protected static List<Point> getNodePath(AStarPathUtil.Node n)

Return a list of Point objects detailing the path from the first node (the given node's ultimate parent) to the ending node (the given node itself.)

Parameters:

n - the ending node in the path.

Returns:

the list detailing the path.

getDistanceEstimate

protected static int getDistanceEstimate(int ax,
                                         int ay,
                                         int bx,
                                         int by)

Return a heuristic estimate of the cost to get from (ax, ay) to (bx, by).