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

Nested Classes

Modifier and Type	Class and Description
static interface	AStarPathUtil.ExtendedTraversalPred Provides extended traversibility information when computing paths.
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

Fields

Modifier and Type	Field and Description
static int	ADJACENT_COST The standard cost to move between nodes.
static int	DIAGONAL_COST The cost to move diagonally.

Constructor Summary

Constructors

Constructor and Description
AStarPathUtil()

Method Summary

Modifier and Type	Method and Description
static int	getConsidered() Returns the number of nodes considered in computing the most recent path.
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

equals, 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.

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.