nl.tudelft.goal.unreal.floydwarshall
Class FloydWarshallMap

java.lang.Object
  nl.tudelft.goal.unreal.floydwarshall.FloydWarshallMap

All Implemented Interfaces:

cz.cuni.amis.pogamut.base.agent.navigation.IPathPlanner<NavPoint>

public class FloydWarshallMap
extends Object
implements cz.cuni.amis.pogamut.base.agent.navigation.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 FloydWarshallMap#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).

Author:

Martin Krulis, Jimmy, mpkorstanje

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 FloydWarshallMap#enabled.
protected Map<cz.cuni.amis.pogamut.unreal.communication.messages.UnrealId,Integer>	navPointIndices Hash table converting navPoint IDs to our own indices.
protected FloydWarshallMap.PathMatrixNode[][]	pathMatrix

Constructor Summary

FloydWarshallMap(int badEdgeFlag, Logger log)

FloydWarshallMap(Logger log)

Method Summary

boolean	checkLink(NavPointNeighbourLink edge) Checks whether the edge is usable.
protected void	cleanUp()
cz.cuni.amis.pogamut.base.agent.navigation.IPathFuture<NavPoint>	computePath(NavPoint from, NavPoint to) Returns path between navpoints 'from' -> 'to'.
float	getDistance(NavPoint from, NavPoint to) Calculate's distance between two nav points (using pathfinding).
List<NavPoint>	getPath(NavPoint from, NavPoint to) Returns path between navpoints 'from' -> 'to'.
protected FloydWarshallMap.PathMatrixNode	getPathMatrixNode(NavPoint np1, NavPoint np2)
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(List<NavPoint> navPoints) Force FloydWarshall to run again, useful if you modify navpoints using NavigationGraphBuilder.
String	toString()

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<cz.cuni.amis.pogamut.unreal.communication.messages.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 FloydWarshallMap#enabled.

Constructor Detail

FloydWarshallMap

public FloydWarshallMap(Logger log)

FloydWarshallMap

public FloydWarshallMap(int badEdgeFlag,
                        Logger log)

Method Detail

isWalkable

public static boolean isWalkable(int flag)

refreshPathMatrix

public void refreshPathMatrix(List<NavPoint> navPoints)

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 FloydWarshallMap#setEnabled(boolean). Note that the object is enabled by default.

Parameters:

from -

to -

Returns:

getDistance

public float getDistance(NavPoint from,
                         NavPoint to)

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

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

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 FloydWarshallMap#setEnabled(boolean). Note that the object is enabled by default.

Parameters:

from -

to -

Returns:

cleanUp

protected void cleanUp()

toString

public String toString()

Overrides:

toString in class Object

computePath

public cz.cuni.amis.pogamut.base.agent.navigation.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 FloydWarshallMap#setEnabled(boolean). Note that the object is enabled by default.

Specified by:

computePath in interface cz.cuni.amis.pogamut.base.agent.navigation.IPathPlanner<NavPoint>

Parameters:

from -

to -

Returns: