|
||||||||||
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<IGhostAgent> cz.cuni.amis.pogamut.ut2004.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.
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.
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 | ||
---|---|---|
protected void |
cleanUp()
|
|
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). |
|
|
getNearestFilteredItem(Collection<T> locations,
NavPoint target,
cz.cuni.amis.utils.IFilter<T> filter)
Returns the nearest target (distance == path distance between 'from' and 'target'). |
|
|
getNearestFilteredNavPoint(Collection<T> locations,
NavPoint target,
cz.cuni.amis.utils.IFilter<T> filter)
Returns the nearest target (distance == path distance between 'from' and 'target'). |
|
|
getNearestItem(Collection<T> locations,
NavPoint target)
Returns the nearest target (distance == path distance between 'from' and 'target'). |
|
|
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'. |
|
|
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'. |
|
|
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)
|
|
|
getSecondNearestItem(Collection<T> targets,
NavPoint from)
Returns the second nearest target (distance == path distance between 'from' and 'target'). |
|
|
getSecondNearestNavPoint(Collection<T> locations,
NavPoint target)
Returns the second nearest target (distance == path distance between 'from' and 'target'). |
|
boolean |
checkLink(NavPointNeighbourLink edge)
Checks whether the edge is usable. |
|
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 |
---|
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
protected Object mutex
enabled
.
Constructor Detail |
---|
public FloydWarshallMap(IGhostAgent bot)
public FloydWarshallMap(IGhostAgent bot, Logger log)
public FloydWarshallMap(IGhostAgent bot, int badEdgeFlag, Logger log)
Method Detail |
---|
public static boolean isWalkable(int flag)
public boolean isEnabled()
setEnabled(boolean)
for more documentation.
Default: true
public void setEnabled(boolean 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).
enabled
- public void refreshPathMatrix()
NavigationGraphBuilder
.
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)
Throws exception if object is disabled, see setEnabled(boolean)
. Note that the object
is enabled by default.
from
- to
-
public float getDistance(NavPoint from, NavPoint to)
Throws exception if object is disabled, see setEnabled(boolean)
. Note that the object
is enabled by default.
public List<NavPoint> getPath(NavPoint from, NavPoint to)
Throws exception if object is disabled, see setEnabled(boolean)
. Note that the object
is enabled by default.
from
- to
-
protected void cleanUp()
cleanUp
in class AgentModule<IGhostAgent>
public String toString()
toString
in class AgentModule<IGhostAgent>
public IPathFuture<NavPoint> computePath(NavPoint from, NavPoint to)
Throws exception if object is disabled, see setEnabled(boolean)
. Note that the object
is enabled by default.
computePath
in interface IPathPlanner<NavPoint>
from
- to
-
public <T extends NavPoint> T getNearestNavPoint(Collection<T> locations, T target)
WARNING: O(n) complexity!
T
- locations
- target
-
public <T extends NavPoint> T getNearestNavPoint(Collection<T> locations, NavPoint target, double maxDistance)
WARNING: O(n) complexity!
T
- locations
- target
- maxDistance
-
public <T extends NavPoint> T getNearestFilteredNavPoint(Collection<T> locations, NavPoint target, cz.cuni.amis.utils.IFilter<T> filter)
WARNING: O(n) complexity!
T
- locations
- target
-
public <T extends NavPoint> T getSecondNearestNavPoint(Collection<T> locations, NavPoint target)
WARNING: O(n) complexity!
T
- locations
- target
-
public <T extends Item> T getNearestItem(Collection<T> locations, NavPoint target)
WARNING: O(n) complexity!
T
- locations
- target
-
public <T extends Item> T getNearestItem(Collection<T> locations, NavPoint target, double maxDistance)
WARNING: O(n) complexity!
T
- locations
- target
- maxDistance
-
public <T extends Item> T getNearestFilteredItem(Collection<T> locations, NavPoint target, cz.cuni.amis.utils.IFilter<T> filter)
WARNING: O(n) complexity!
T
- locations
- target
-
public <T extends Item> T getSecondNearestItem(Collection<T> targets, NavPoint from)
WARNING: O(n) complexity!
T
- targets
- from
-
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |