|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
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
public class FloydWarshallMap
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.
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 |
---|
public static final int BAD_EDGE_FLAG
protected int badEdgeFlag
protected Map<UnrealId,Integer> navPointIndices
protected Map<Integer,NavPoint> indicesNavPoints
WILL BE NULL AFTER CONSTRUCTION! SERVES AS A TEMPORARY "GLOBAL VARIABLE" DURING FLOYD-WARSHALL COMPUTATION AND PATH RECONSTRUCTION.
protected FloydWarshallMap.PathMatrixNode[][] pathMatrix
Constructor Detail |
---|
public FloydWarshallMap(UDKBot bot)
public FloydWarshallMap(UDKBot bot, Logger log)
public FloydWarshallMap(UDKBot bot, int badEdgeFlag, Logger log)
Method Detail |
---|
protected void performFloydWarshall(MapPointListObtained map)
protected void performFloydWarshall(List<NavPoint> navPoints)
public boolean checkLink(NavPointNeighbourLink edge)
from
- Starting nav point.edge
- NeighNav object representing the edge.
protected FloydWarshallMap.PathMatrixNode getPathMatrixNode(NavPoint np1, NavPoint np2)
public boolean reachable(NavPoint from, NavPoint to)
from
- to
-
public float getDistance(NavPoint from, NavPoint to)
public List<NavPoint> getPath(NavPoint from, NavPoint to)
from
- to
-
public String toString()
toString
in class AgentModule<UDKBot>
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |