cz.cuni.amis.pogamut.ut2004.agent.navigation.floydwarshall
Class FloydWarshallMap

java.lang.Object
  cz.cuni.amis.pogamut.base.agent.module.AgentModule<AGENT>
      cz.cuni.amis.pogamut.base.agent.module.SensorModule<IGhostAgent>
          cz.cuni.amis.pogamut.ut2004.agent.navigation.floydwarshall.FloydWarshallMap

All Implemented Interfaces:

IPathPlanner<NavPoint>, IComponent

public class FloydWarshallMap
extends SensorModule<IGhostAgent>
implements IPathPlanner<NavPoint>

Private map using Floyd-Warshall for path-finding.

It should be initialized upon receiving MapPointListObtained event. It precomputes all the paths inside the environment using Floyd-Warshall algorithm (O(n^3)). Use getReachable(), getDistance(), getPath() to obtain the info about the path.

If needed you may call refreshPathMatrix() to recompute Floyd-Warshall. Especially useful if you're using NavigationGraphBuilder to modify the underlying navpoints/edges.

Based upon the implementation from Martin Krulis with his kind consent - Thank you!

NOTE: requires O(navpoints.size^3) of memory ~ which is 10000^3 at max for UT2004 (usually the biggest maps have 3000 navpoints max, but small maps, e.g., DM-1on1-Albatross has 200 navpoints).

Because the algorithm is so space-hungery-beast, there is option to disable it by calling setEnabled(boolean) with 'false' argument. See the method for further documentation about the object behavior.

Author:

Martin Krulis, Jimmy

Nested Class Summary

static class

FloydWarshallMap.PathMatrixNode

Field Summary

static int	BAD_EDGE_FLAG Flag mask representing unusable edge.
protected int	badEdgeFlag Prohibited edges.
protected Map<Integer,NavPoint>	indicesNavPoints Mapping indices to nav points.
protected Object	mutex Synchronizing access to object with respect to enabled.
protected Map<UnrealId,Integer>	navPointIndices Hash table converting navPoint IDs to our own indices.
protected FloydWarshallMap.PathMatrixNode[][]	pathMatrix

Fields inherited from class cz.cuni.amis.pogamut.base.agent.module.SensorModule

worldView

Fields inherited from class cz.cuni.amis.pogamut.base.agent.module.AgentModule

agent, controller, eventBus, log

Constructor Summary

FloydWarshallMap(IGhostAgent bot)

FloydWarshallMap(IGhostAgent bot, int badEdgeFlag, Logger log)

FloydWarshallMap(IGhostAgent bot, Logger log)

Method Summary

boolean	checkLink(NavPointNeighbourLink edge) Checks whether the edge is usable.
protected void	cleanUp()
IPathFuture<NavPoint>	computePath(NavPoint from, NavPoint to) Returns path between navpoints 'from' -> 'to'.
double	getDistance(NavPoint from, NavPoint to) Calculate's distance between two nav points (using pathfinding).
<T extends Item> T	getNearestFilteredItem(Collection<T> locations, NavPoint target, cz.cuni.amis.utils.IFilter<T> filter) Returns the nearest target (distance == path distance between 'from' and 'target').
<T extends NavPoint> T	getNearestFilteredNavPoint(Collection<T> locations, NavPoint target, cz.cuni.amis.utils.IFilter<T> filter) Returns the nearest target (distance == path distance between 'from' and 'target').
<T extends Item> T	getNearestItem(Collection<T> locations, NavPoint target) Returns the nearest target (distance == path distance between 'from' and 'target').
<T extends Item> T	getNearestItem(Collection<T> locations, NavPoint target, double maxDistance) Returns the nearest target (distance == path distance between 'from' and 'target') that is not further than 'maxDistance'.
<T extends NavPoint> T	getNearestNavPoint(Collection<T> locations, NavPoint target, double maxDistance) Returns the nearest target (distance == path distance between 'from' and 'target') that is not further than 'maxDistance'.
<T extends NavPoint> T	getNearestNavPoint(Collection<T> locations, T target) Returns the nearest target (distance == path distance between 'from' and 'target').
List<NavPoint>	getPath(NavPoint from, NavPoint to) Returns path between navpoints 'from' -> 'to'.
protected FloydWarshallMap.PathMatrixNode	getPathMatrixNode(NavPoint np1, NavPoint np2)
<T extends Item> T	getSecondNearestItem(Collection<T> targets, NavPoint from) Returns the second nearest target (distance == path distance between 'from' and 'target').
<T extends NavPoint> T	getSecondNearestNavPoint(Collection<T> locations, NavPoint target) Returns the second nearest target (distance == path distance between 'from' and 'target').
boolean	isEnabled() Whether the object is active, see setEnabled(boolean) for more documentation.
static boolean	isWalkable(int flag)
protected void	performFloydWarshall(List<NavPoint> navPoints)
protected void	performFloydWarshall(MapPointListObtained map)
boolean	reachable(NavPoint from, NavPoint to) Whether navpoint 'to' is reachable from the navpoint 'from'.
void	refreshPathMatrix() Force FloydWarshall to run again, useful if you modify navpoints using NavigationGraphBuilder.
void	setEnabled(boolean enabled) Enables/disables object.
String	toString()

Methods inherited from class cz.cuni.amis.pogamut.base.agent.module.AgentModule

getComponentId, getLog, getState, initComponentId, isRunning, kill, pause, reset, resume, start, stop

Methods inherited from class java.lang.Object

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

Field Detail

BAD_EDGE_FLAG

public static final int BAD_EDGE_FLAG

Flag mask representing unusable edge.

badEdgeFlag

protected int badEdgeFlag

Prohibited edges.

navPointIndices

protected Map<UnrealId,Integer> navPointIndices

Hash table converting navPoint IDs to our own indices.

indicesNavPoints

protected Map<Integer,NavPoint> indicesNavPoints

Mapping indices to nav points.

WILL BE NULL AFTER CONSTRUCTION! SERVES AS A TEMPORARY "GLOBAL VARIABLE" DURING FLOYD-WARSHALL COMPUTATION AND PATH RECONSTRUCTION.

pathMatrix

protected FloydWarshallMap.PathMatrixNode[][] pathMatrix

mutex

protected Object mutex

Synchronizing access to object with respect to enabled.

Constructor Detail

FloydWarshallMap

public FloydWarshallMap(IGhostAgent bot)

FloydWarshallMap

public FloydWarshallMap(IGhostAgent bot,
                        Logger log)

FloydWarshallMap

public FloydWarshallMap(IGhostAgent bot,
                        int badEdgeFlag,
                        Logger log)

Method Detail

isWalkable

public static boolean isWalkable(int flag)

isEnabled

public boolean isEnabled()

Whether the object is active, see setEnabled(boolean) for more documentation.

Default: true

Returns:

setEnabled

public void setEnabled(boolean enabled)

Enables/disables object. As default, object is initialized as 'enabled'.

If you "disable" the object (passing 'false' as an argument), it will cleanUp() itself dropping any info it has about paths, i.e., method computePath(NavPoint, NavPoint) will start throwing exceptions at you.

Note that if you "enable" the object (passing 'true' as an argument), it won't AUTOMATICALLY trigger the computation of the algorithm, you should manually refreshPathMatrix() when it is appropriate (unless you enable it before list of navpoints is received, in that case the path will get computed automatically).

Parameters:

enabled -

refreshPathMatrix

public void refreshPathMatrix()

Force FloydWarshall to run again, useful if you modify navpoints using NavigationGraphBuilder.

performFloydWarshall

protected void performFloydWarshall(MapPointListObtained map)

performFloydWarshall

protected void performFloydWarshall(List<NavPoint> navPoints)

checkLink

public boolean checkLink(NavPointNeighbourLink edge)

Checks whether the edge is usable.

Parameters:

from - Starting nav point.

edge - NeighNav object representing the edge.

Returns:

boolean

getPathMatrixNode

protected FloydWarshallMap.PathMatrixNode getPathMatrixNode(NavPoint np1,
                                                            NavPoint np2)

reachable

public boolean reachable(NavPoint from,
                         NavPoint to)

Whether navpoint 'to' is reachable from the navpoint 'from'.

Throws exception if object is disabled, see setEnabled(boolean). Note that the object is enabled by default.

Parameters:

from -

to -

Returns:

getDistance

public double getDistance(NavPoint from,
                          NavPoint to)

Calculate's distance between two nav points (using pathfinding).

Throws exception if object is disabled, see setEnabled(boolean). Note that the object is enabled by default.

Specified by:

getDistance in interface IPathPlanner<NavPoint>

Returns:

Distance or POSITIVE_INFINITY if there's no path.

getPath

public List<NavPoint> getPath(NavPoint from,
                              NavPoint to)

Returns path between navpoints 'from' -> 'to'. The path begins with 'from' and ends with 'to'. If such path doesn't exist, returns null.

Throws exception if object is disabled, see setEnabled(boolean). Note that the object is enabled by default.

Parameters:

from -

to -

Returns:

cleanUp

protected void cleanUp()

Overrides:

cleanUp in class AgentModule<IGhostAgent>

toString

public String toString()

Overrides:

toString in class AgentModule<IGhostAgent>

computePath

public IPathFuture<NavPoint> computePath(NavPoint from,
                                         NavPoint to)

Returns path between navpoints 'from' -> 'to'. The path begins with 'from' and ends with 'to'. If such path does not exist, it returns zero-sized path.

Throws exception if object is disabled, see setEnabled(boolean). Note that the object is enabled by default.

Specified by:

computePath in interface IPathPlanner<NavPoint>

Parameters:

from -

to -

Returns:

getNearestNavPoint

public <T extends NavPoint> T getNearestNavPoint(Collection<T> locations,
                                                 T target)

Returns the nearest target (distance == path distance between 'from' and 'target').

WARNING: O(n) complexity!

Type Parameters:

T -

Parameters:

locations -

target -

Returns:

nearest object from collection of objects

getNearestNavPoint

public <T extends NavPoint> T getNearestNavPoint(Collection<T> locations,
                                                 NavPoint target,
                                                 double maxDistance)

Returns the nearest target (distance == path distance between 'from' and 'target') that is not further than 'maxDistance'.

WARNING: O(n) complexity!

Type Parameters:

T -

Parameters:

locations -

target -

maxDistance -

Returns:

nearest object from collection of objects that is not further than 'maxDistance'.

getNearestFilteredNavPoint

public <T extends NavPoint> T getNearestFilteredNavPoint(Collection<T> locations,
                                                         NavPoint target,
                                                         cz.cuni.amis.utils.IFilter<T> filter)

Returns the nearest target (distance == path distance between 'from' and 'target').

WARNING: O(n) complexity!

Type Parameters:

T -

Parameters:

locations -

target -

Returns:

nearest object from collection of objects

getSecondNearestNavPoint

public <T extends NavPoint> T getSecondNearestNavPoint(Collection<T> locations,
                                                       NavPoint target)

Returns the second nearest target (distance == path distance between 'from' and 'target').

WARNING: O(n) complexity!

Type Parameters:

T -

Parameters:

locations -

target -

Returns:

nearest object from collection of objects

getNearestItem

public <T extends Item> T getNearestItem(Collection<T> locations,
                                         NavPoint target)

Returns the nearest target (distance == path distance between 'from' and 'target').

WARNING: O(n) complexity!

Type Parameters:

T -

Parameters:

locations -

target -

Returns:

nearest object from collection of objects

getNearestItem

public <T extends Item> T getNearestItem(Collection<T> locations,
                                         NavPoint target,
                                         double maxDistance)

Returns the nearest target (distance == path distance between 'from' and 'target') that is not further than 'maxDistance'.

WARNING: O(n) complexity!

Type Parameters:

T -

Parameters:

locations -

target -

maxDistance -

Returns:

nearest object from collection of objects that is not further than 'maxDistance'.

getNearestFilteredItem

public <T extends Item> T getNearestFilteredItem(Collection<T> locations,
                                                 NavPoint target,
                                                 cz.cuni.amis.utils.IFilter<T> filter)

Returns the nearest target (distance == path distance between 'from' and 'target').

WARNING: O(n) complexity!

Type Parameters:

T -

Parameters:

locations -

target -

Returns:

nearest object from collection of objects

getSecondNearestItem

public <T extends Item> T getSecondNearestItem(Collection<T> targets,
                                               NavPoint from)

Returns the second nearest target (distance == path distance between 'from' and 'target').

WARNING: O(n) complexity!

Type Parameters:

T -

Parameters:

targets -

from -

Returns:

nearest object from collection of objects