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).

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 java.util.Map<java.lang.Integer,NavPoint>	indicesNavPoints Mapping indices to nav points.
protected java.util.Map<UnrealId,java.lang.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, java.util.logging.Logger log)

FloydWarshallMap(IGhostAgent bot, java.util.logging.Logger log)

Method Summary

boolean	checkLink(NavPointNeighbourLink edge) Checks whether the edge is usable.
IPathFuture<NavPoint>	computePath(NavPoint from, NavPoint to) Returns a future where the path planner will set the result of its computation.
float	getDistance(NavPoint from, NavPoint to) Calculate's distance between two nav points (using pathfinding).
java.util.List<NavPoint>	getPath(NavPoint from, NavPoint to) Returns path between navpoints 'from' -> 'to'.
protected FloydWarshallMap.PathMatrixNode	getPathMatrixNode(NavPoint np1, NavPoint np2)
protected void	performFloydWarshall(java.util.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.
java.lang.String	toString()

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

cleanUp, 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 java.util.Map<UnrealId,java.lang.Integer> navPointIndices

Hash table converting navPoint IDs to our own indices.

indicesNavPoints

protected java.util.Map<java.lang.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

Constructor Detail

FloydWarshallMap

public FloydWarshallMap(IGhostAgent bot)

FloydWarshallMap

public FloydWarshallMap(IGhostAgent bot,
                        java.util.logging.Logger log)

FloydWarshallMap

public FloydWarshallMap(IGhostAgent bot,
                        int badEdgeFlag,
                        java.util.logging.Logger log)

Method Detail

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(java.util.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'.

Parameters:

from -

to -

Returns:

getDistance

public float getDistance(NavPoint from,
                         NavPoint to)

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

Returns:

Distance or POSITIVE_INFINITY if there's no path.

getPath

public java.util.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.

Parameters:

from -

to -

Returns:

toString

public java.lang.String toString()

Overrides:

toString in class AgentModule<IGhostAgent>

computePath

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

Description copied from interface: IPathPlanner

Returns a future where the path planner will set the result of its computation.

Note that the IPathFuture might already contain the path (i.e., the returned path was computed inside this method or it was a precomputed result). Always examine status of the future before attaching listeners to it.

Specified by:

computePath in interface IPathPlanner<NavPoint>

Returns: