public class FloydWarshallMap extends SensorModule<IGhostAgent> implements IPathPlanner<NavPoint>
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.
Modifier and Type | Class and Description |
---|---|
static class |
FloydWarshallMap.PathMatrixNode |
Modifier and Type | Field and Description |
---|---|
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 |
worldView
agent, controller, eventBus, log
Constructor and Description |
---|
FloydWarshallMap(IGhostAgent bot) |
FloydWarshallMap(IGhostAgent bot,
int badEdgeFlag,
Logger log) |
FloydWarshallMap(IGhostAgent bot,
Logger log) |
Modifier and Type | Method and Description |
---|---|
boolean |
checkLink(NavPointNeighbourLink edge)
Checks whether the edge is usable.
|
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).
|
<T extends Item> |
getNearestFilteredItem(Collection<T> locations,
NavPoint target,
cz.cuni.amis.utils.IFilter<T> filter)
Returns the nearest target (distance == path distance between 'from' and 'target').
|
<T extends NavPoint> |
getNearestFilteredNavPoint(Collection<T> locations,
NavPoint target,
cz.cuni.amis.utils.IFilter<T> filter)
Returns the nearest target (distance == path distance between 'from' and 'target').
|
<T extends Item> |
getNearestItem(Collection<T> locations,
NavPoint target)
Returns the nearest target (distance == path distance between 'from' and 'target').
|
<T extends Item> |
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'.
|
<T extends NavPoint> |
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'.
|
<T extends NavPoint> |
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) |
<T extends Item> |
getSecondNearestItem(Collection<T> targets,
NavPoint from)
Returns the second nearest target (distance == path distance between 'from' and 'target').
|
<T extends NavPoint> |
getSecondNearestNavPoint(Collection<T> locations,
NavPoint target)
Returns the second nearest target (distance == path distance between 'from' and 'target').
|
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() |
getComponentId, getLog, getState, initComponentId, isRunning, kill, pause, reset, resume, start, stop
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
public FloydWarshallMap(IGhostAgent bot)
public FloydWarshallMap(IGhostAgent bot, Logger log)
public FloydWarshallMap(IGhostAgent bot, int badEdgeFlag, Logger log)
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)
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
- Copyright © 2012 AMIS research group, Faculty of Mathematics and Physics, Charles University in Prague, Czech Republic. All Rights Reserved.