com.threerings.tudey.server.util
Class Pathfinder

java.lang.Object
  com.threerings.tudey.server.util.Pathfinder

All Implemented Interfaces:

TudeySceneModel.Observer, ActorLogic.CollisionFlagObserver, Logic.ShapeObserver, TudeySceneManager.ActorObserver

public class Pathfinder
extends Object
implements TudeySceneModel.Observer, TudeySceneManager.ActorObserver, Logic.ShapeObserver, ActorLogic.CollisionFlagObserver

A helper class for pathfinding. Currently the pathfinding strategy is to divide the world up into unit cells and track the collision flags of all scene entries and actors whose shapes intersect those cells. An alternate method that may be worth exploring would be to have the traversal predicate perform a full intersection query (it seems likely that this would be more expensive than maintaining the collision map for all actors, but it's not entirely clear).

Field Summary

protected IntMap<List<Integer>>	_actorFlagLists Maps encoded coordinates to lists of separate sets of actor flags.
protected CoordIntMap	_actorFlags The collision flags corresponding to the scene entries and the actors.
protected List<SpaceElement>	_elements Holds elements during intersection testing.
protected CoordIntMap	_entryFlags The collision flags corresponding to the scene entries.
protected Polygon	_quad Used to store tile shapes for intersecting testing.
protected Rectangle	_region Region object to reuse.
protected TudeySceneManager	_scenemgr The owning scene manager.
protected Shape	_sweptShape Swept shape to reuse.
protected Transform2D	_transform Transform to reuse.
protected Vector2f	_translation Translation vector to reuse.
protected List<Vector2f>	_waypoints Holds waypoints during shortcut processing.
protected Shape	_worldShape World shape to reuse.
protected static int	SUBDIVISION The subdivision of the actor collision map.

Constructor Summary

Pathfinder(TudeySceneManager scenemgr)
Creates a new pathfinder.

Method Summary

void	actorAdded(ActorLogic logic) Notes that an actor has been added.
void	actorRemoved(ActorLogic logic) Notes that an actor has been removed.
protected void	addFlags(ActorLogic logic) Adds the flags for the specified actor.
protected void	addFlags(Shape shape, int flags, boolean entry) Adds the specified flags to the flag map(s).
protected void	addFlags(TudeySceneModel.Entry entry) Adds the specified entry's flags to the flag maps.
void	collisionFlagsChanged(ActorLogic logic, int oflags) Notes that the actor's collision flags have changed.
void	entryAdded(TudeySceneModel.Entry entry) Notes that an entry has been added to the scene.
void	entryRemoved(TudeySceneModel.Entry oentry) Notes that an entry has been removed from the scene.
void	entryUpdated(TudeySceneModel.Entry oentry, TudeySceneModel.Entry nentry) Notes that an entry has been updated within the scene.
Vector2f[]	getEntryPath(ActorLogic actor, float longest, float bx, float by, boolean partial, boolean shortcut) Computes a path for the specified actor from its current location, considering only the scene entries (not the actors).
Vector2f[]	getEntryPath(ActorLogic actor, float longest, float ax, float ay, float bx, float by, boolean partial, boolean shortcut) Computes a path for the specified actor, considering only the scene entries (not the actors).
Vector2f[]	getPath(ActorLogic actor, float longest, float bx, float by, boolean partial, boolean shortcut) Computes a path for the specified actor from its current location.
Vector2f[]	getPath(ActorLogic actor, float longest, float ax, float ay, float bx, float by, boolean partial, boolean shortcut) Computes a path for the specified actor.
protected Vector2f[]	getPath(boolean collideActor, ActorLogic logic, float longest, float ax, float ay, float bx, float by, boolean partial, boolean shortcut) Computes a path for the specified actor.
protected void	removeFlags(ActorLogic logic) Removes the flags for the specified actor.
protected void	removeFlags(Shape shape, int flags, boolean entry, SpaceElement skip) Removes the flags for the specified shape.
protected void	removeFlags(TudeySceneModel.Entry entry) Removes the flags for the specified entry.
void	shapeDidChange(Logic logic) Notes that the logic's shape has changed.
void	shapeWillChange(Logic logic) Notes that the logic's shape is about to change.
void	shutdown() Shuts down the pathfinder.
protected boolean	sweptShapeCollides(boolean collideActor, ActorLogic logic, Vector2f start, Vector2f end) Determines whether the swept shape of the specified actor collides with anything.
protected void	updateEntryFlags(int x, int y, SpaceElement skip) Updates the entry flags at the specified location (_quad should be set to the cell boundaries).
protected void	updateQuad(float lx, float ly, float ux, float uy) Updates the coordinates of the quad.
protected void	updateQuad(int x, int y) Updates the coordinates of the quad to encompass the specified grid cell.
protected void	updateQuadSubdivision(int x, int y, int xs, int ys) Updates the coordinates of the quad to encompass the subdivided section of the specified grid cell.

Methods inherited from class java.lang.Object

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

Field Detail

_scenemgr

protected TudeySceneManager _scenemgr

The owning scene manager.

_entryFlags

protected CoordIntMap _entryFlags

The collision flags corresponding to the scene entries.

_actorFlags

protected CoordIntMap _actorFlags

The collision flags corresponding to the scene entries and the actors.

_actorFlagLists

protected IntMap<List<Integer>> _actorFlagLists

Maps encoded coordinates to lists of separate sets of actor flags.

_quad

protected Polygon _quad

Used to store tile shapes for intersecting testing.

_elements

protected List<SpaceElement> _elements

Holds elements during intersection testing.

_waypoints

protected List<Vector2f> _waypoints

Holds waypoints during shortcut processing.

_region

protected Rectangle _region

Region object to reuse.

_transform

protected Transform2D _transform

Transform to reuse.

_worldShape

protected Shape _worldShape

World shape to reuse.

_translation

protected Vector2f _translation

Translation vector to reuse.

_sweptShape

protected Shape _sweptShape

Swept shape to reuse.

SUBDIVISION

protected static final int SUBDIVISION

The subdivision of the actor collision map.

See Also:

Constant Field Values

Constructor Detail

Pathfinder

public Pathfinder(TudeySceneManager scenemgr)

Creates a new pathfinder.

Method Detail

shutdown

public void shutdown()

Shuts down the pathfinder.

getEntryPath

public Vector2f[] getEntryPath(ActorLogic actor,
                               float longest,
                               float bx,
                               float by,
                               boolean partial,
                               boolean shortcut)

Computes a path for the specified actor from its current location, considering only the scene entries (not the actors).

Parameters:

longest - the maximum path length.

partial - if true, return a partial path even if the destination is unreachable.

shortcut - if true, use swept shapes to find path shortcuts.

Returns:

the computed path, or null if unreachable.

getEntryPath

public Vector2f[] getEntryPath(ActorLogic actor,
                               float longest,
                               float ax,
                               float ay,
                               float bx,
                               float by,
                               boolean partial,
                               boolean shortcut)

Computes a path for the specified actor, considering only the scene entries (not the actors).

Parameters:

longest - the maximum path length.

partial - if true, return a partial path even if the destination is unreachable.

shortcut - if true, use swept shapes to find path shortcuts.

Returns:

the computed path, or null if unreachable.

getPath

public Vector2f[] getPath(ActorLogic actor,
                          float longest,
                          float bx,
                          float by,
                          boolean partial,
                          boolean shortcut)

Computes a path for the specified actor from its current location.

Parameters:

longest - the maximum path length.

partial - if true, return a partial path even if the destination is unreachable.

shortcut - if true, use swept shapes to find path shortcuts.

Returns:

the computed path, or null if unreachable.

getPath

public Vector2f[] getPath(ActorLogic actor,
                          float longest,
                          float ax,
                          float ay,
                          float bx,
                          float by,
                          boolean partial,
                          boolean shortcut)

Computes a path for the specified actor.

Parameters:

longest - the maximum path length.

partial - if true, return a partial path even if the destination is unreachable.

shortcut - if true, use swept shapes to find path shortcuts.

Returns:

the computed path, or null if unreachable.

entryAdded

public void entryAdded(TudeySceneModel.Entry entry)

Description copied from interface: TudeySceneModel.Observer

Notes that an entry has been added to the scene.

Specified by:

entryAdded in interface TudeySceneModel.Observer

entryUpdated

public void entryUpdated(TudeySceneModel.Entry oentry,
                         TudeySceneModel.Entry nentry)

Description copied from interface: TudeySceneModel.Observer

Notes that an entry has been updated within the scene.

Specified by:

entryUpdated in interface TudeySceneModel.Observer

entryRemoved

public void entryRemoved(TudeySceneModel.Entry oentry)

Description copied from interface: TudeySceneModel.Observer

Notes that an entry has been removed from the scene.

Specified by:

entryRemoved in interface TudeySceneModel.Observer

actorAdded

public void actorAdded(ActorLogic logic)

Description copied from interface: TudeySceneManager.ActorObserver

Notes that an actor has been added.

Specified by:

actorAdded in interface TudeySceneManager.ActorObserver

actorRemoved

public void actorRemoved(ActorLogic logic)

Description copied from interface: TudeySceneManager.ActorObserver

Notes that an actor has been removed.

Specified by:

actorRemoved in interface TudeySceneManager.ActorObserver

shapeWillChange

public void shapeWillChange(Logic logic)

Description copied from interface: Logic.ShapeObserver

Notes that the logic's shape is about to change.

Specified by:

shapeWillChange in interface Logic.ShapeObserver

shapeDidChange

public void shapeDidChange(Logic logic)

Description copied from interface: Logic.ShapeObserver

Notes that the logic's shape has changed.

Specified by:

shapeDidChange in interface Logic.ShapeObserver

collisionFlagsChanged

public void collisionFlagsChanged(ActorLogic logic,
                                  int oflags)

Description copied from interface: ActorLogic.CollisionFlagObserver

Notes that the actor's collision flags have changed.

Specified by:

collisionFlagsChanged in interface ActorLogic.CollisionFlagObserver

getPath

protected Vector2f[] getPath(boolean collideActor,
                             ActorLogic logic,
                             float longest,
                             float ax,
                             float ay,
                             float bx,
                             float by,
                             boolean partial,
                             boolean shortcut)

Computes a path for the specified actor.

Parameters:

longest - the maximum path length.

partial - if true, return a partial path even if the destination is unreachable.

shortcut - if true, use swept shapes to compute shortcuts in the path.

Returns:

the computed path, or null if unreachable.

sweptShapeCollides

protected boolean sweptShapeCollides(boolean collideActor,
                                     ActorLogic logic,
                                     Vector2f start,
                                     Vector2f end)

Determines whether the swept shape of the specified actor collides with anything.

addFlags

protected void addFlags(TudeySceneModel.Entry entry)

Adds the specified entry's flags to the flag maps.

removeFlags

protected void removeFlags(TudeySceneModel.Entry entry)

Removes the flags for the specified entry.

addFlags

protected void addFlags(ActorLogic logic)

Adds the flags for the specified actor.

removeFlags

protected void removeFlags(ActorLogic logic)

Removes the flags for the specified actor.

addFlags

protected void addFlags(Shape shape,
                        int flags,
                        boolean entry)

Adds the specified flags to the flag map(s).

removeFlags

protected void removeFlags(Shape shape,
                           int flags,
                           boolean entry,
                           SpaceElement skip)

Removes the flags for the specified shape.

updateQuad

protected void updateQuad(int x,
                          int y)

Updates the coordinates of the quad to encompass the specified grid cell.

updateQuadSubdivision

protected void updateQuadSubdivision(int x,
                                     int y,
                                     int xs,
                                     int ys)

Updates the coordinates of the quad to encompass the subdivided section of the specified grid cell.

updateQuad

protected void updateQuad(float lx,
                          float ly,
                          float ux,
                          float uy)

Updates the coordinates of the quad.

updateEntryFlags

protected void updateEntryFlags(int x,
                                int y,
                                SpaceElement skip)

Updates the entry flags at the specified location (_quad should be set to the cell boundaries).

Parameters:

skip - an element to skip, or null for none.