cz.cuni.amis.pogamut.udk.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<UDKBot>
          cz.cuni.amis.pogamut.udk.agent.navigation.floydwarshall.FloydWarshallMap

All Implemented Interfaces:

IComponent

public class FloydWarshallMap
extends SensorModule<UDKBot>

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.

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 maps have 3000 navpoints max). If you are going to use more than one bot in your simulation, we advise you to create a singleton that will provide an instance for all your bots.

Author:

Martin Krulis, Jakub Gemrot

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 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(UDKBot bot)

FloydWarshallMap(UDKBot bot, int badEdgeFlag, Logger log)

FloydWarshallMap(UDKBot bot, Logger log)

Method Summary

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)
boolean	checkLink(NavPointNeighbourLink edge) Checks whether the edge is usable.
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'.
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 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

Constructor Detail

FloydWarshallMap

public FloydWarshallMap(UDKBot bot)

FloydWarshallMap

public FloydWarshallMap(UDKBot bot,
                        Logger log)

FloydWarshallMap

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

Method Detail

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

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 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 String toString()

Overrides:

toString in class AgentModule<UDKBot>