wyvern.kernel.monsters
Class AStarSearch

java.lang.Object
  wyvern.kernel.monsters.AStarSearch

public class AStarSearch

extends java.lang.Object

Implements the standard A* algorithm. Each location visited in the search is assigned a cost and a heuristic value. The nodes are pushed onto a priority queue, and popped off in most-desirable order. The heuristic is customizable.

Version:

1.0, Dec 14, 1999

Author:

Steve Yegge

Nested Class Summary

class

AStarSearch.Node A node in the search graph.

Field Summary

static int	BASE_DEPTH
static int	CANT_MOVE
static int	DEFAULT_COST
static int	DIGGABLE_WALL_COST
static int	LOCKED_DOOR_COST
static int	MAX_DEPTH
static int	MAX_INTELLIGENCE
static int	MAX_SEARCH_NODES
static int	PLAYER_MAX_DEPTH
static int	TRAP_COST
static int	UNLOCKED_DOOR_COST

Constructor Summary

AStarSearch()
Constructs a new AStarSearch

Method Summary

java.lang.String	computeDirection(int x, int y) Quickly computes the direction from the move offsets.
java.util.List	constructPath(AStarSearch.Node node) Returns a list of (String) directions to move to get to the desired player.
static java.lang.String	getProfilingInfo() Returns detailed profiling info.
boolean	isGoalNode(AStarSearch.Node node) Returns true if this is a goal node.
void	pushSuccessorNodes(AStarSearch.Node parent) Generates successors to passed node, computes their costs, and pushes them onto the OPEN list.
protected void	reset() Resets the internal variables so you can call search() again.
java.util.List	search(Commandable agent, GameMap map, Commandable[] targets) Executes the A* search to a list of possible targets.
java.util.List	search(Commandable agent, GameMap map, Point dest) Executes the A* search to a given destination point.

Methods inherited from class java.lang.Object

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

Field Detail

BASE_DEPTH

public static final int BASE_DEPTH

See Also:

Constant Field Values

MAX_DEPTH

public static final int MAX_DEPTH

See Also:

Constant Field Values

PLAYER_MAX_DEPTH

public static final int PLAYER_MAX_DEPTH

See Also:

Constant Field Values

MAX_INTELLIGENCE

public static final int MAX_INTELLIGENCE

See Also:

Constant Field Values

MAX_SEARCH_NODES

public static final int MAX_SEARCH_NODES

See Also:

Constant Field Values

DEFAULT_COST

public static final int DEFAULT_COST

See Also:

Constant Field Values

UNLOCKED_DOOR_COST

public static final int UNLOCKED_DOOR_COST

See Also:

Constant Field Values

TRAP_COST

public static final int TRAP_COST

See Also:

Constant Field Values

DIGGABLE_WALL_COST

public static final int DIGGABLE_WALL_COST

See Also:

Constant Field Values

LOCKED_DOOR_COST

public static final int LOCKED_DOOR_COST

See Also:

Constant Field Values

CANT_MOVE

public static final int CANT_MOVE

See Also:

Constant Field Values

Constructor Detail

AStarSearch

public AStarSearch()

Constructs a new AStarSearch

Method Detail

reset

protected void reset()

Resets the internal variables so you can call search() again.

search

public final java.util.List search(Commandable agent,
                                   GameMap map,
                                   Point dest)

Executes the A* search to a given destination point. Used for MouseCommand (run-to-mouse), among other things.

Parameters:

agent - the player or monster

map - the monster's map

dest - the desired destination

Returns:

a List of moves to make (string dirs) to get to the target, or null if no path was found.

search

public final java.util.List search(Commandable agent,
                                   GameMap map,
                                   Commandable[] targets)

Executes the A* search to a list of possible targets.

Parameters:

agent - the monster

map - the monster's map

targets - the list of targets under consideration

Returns:

a List of moves to make (string dirs) to get to one of the targets, or null if no path was found. Side effect: the monster gets a "@a*-hunt" property with a reference to the player we're going after.

pushSuccessorNodes

public final void pushSuccessorNodes(AStarSearch.Node parent)

Generates successors to passed node, computes their costs, and pushes them onto the OPEN list.

Parameters:

parent - the node for which to generate successors

isGoalNode

public boolean isGoalNode(AStarSearch.Node node)

Returns true if this is a goal node.

Returns:

true if we're adjacent to the player nearest the node.

constructPath

public final java.util.List constructPath(AStarSearch.Node node)

Returns a list of (String) directions to move to get to the desired player.

Parameters:

node - the goal node

Returns:

a list of moves

computeDirection

public final java.lang.String computeDirection(int x,
                                               int y)

Quickly computes the direction from the move offsets.

Parameters:

x - x offset (-1, 0, 1)

y - y offset (-1, 0, 1)

Returns:

the direction string

getProfilingInfo

public static java.lang.String getProfilingInfo()

Returns detailed profiling info.