cz.cuni.amis.pathfinding.alg.floydwarshall
Class FloydWarshall<NODE>

java.lang.Object
  cz.cuni.amis.pathfinding.alg.floydwarshall.FloydWarshall<NODE>

public class FloydWarshall<NODE>
extends Object

Floyd-Warshall algorithm for precomputing all-possible paths within the IPFKnownMap.

It precomputes all the paths inside the environment using Floyd-Warshall algorithm (time: O(n^3)) in the form of matrix.

Use isReachable(Object, Object), getPathCost(Object, Object) and getPath(Object, Object) to obtain information about computed paths. the info about the path.

getPath(Object, Object) is caching retrieved paths using SoftReferences.

If needed you may call compute() to recompute paths, this call is needed if you set new map / agent view using setMap(IPFKnownMap) or FloydWarshall#setMapView(IPFMapView).

Based upon the implementation from Martin Krulis with his kind consent, thank you! Even though it was heavily recreated by now ;-)

NOTE: requires O(map.nodes.size^2) of memory! So be careful.

NOTE: you should read javadocs for IPFMap, IPFKnownMap and IPFMapView to understand how you can separate your map representation from various agent "views on the map" (i.e., how to provide customized path finding for different agents, e.g., fish vs. human)

Author:

Jimmy

Nested Class Summary

static class

FloydWarshall.PathMatrixNode<N> Class describing cell inside the FloydWarshall matrix holding additional informations relating to the path between two nodes.

Constructor Summary

FloydWarshall(IPFKnownMap<NODE> map)
FloydWarshall configured with "map" with no agent-specific view on the map, IPFMapView.DefaultView is used.

FloydWarshall(IPFKnownMap<NODE> map, IPFKnownMapView<NODE> view)
FloydWarshall configured with "map" and agent-specific view on the map, if "view" is null, IPFMapView.DefaultView is going to be used.

FloydWarshall(IPFKnownMap<NODE> map, IPFKnownMapView<NODE> view, Logger log)
FloydWarshall configured with "map" and agent-specific view on the map, if "view" is null, IPFMapView.DefaultView is going to be used.

FloydWarshall(IPFKnownMap<NODE> map, Logger log)
FloydWarshall configured with "map" with no agent-specific view on the map, IPFMapView.DefaultView is used.

Method Summary

void	cacheAllPaths()
void	compute() Force FloydWarshall to refresh its path matrix, useful if you modify the map or view using setMap(IPFKnownMap) or setMapView(IPFKnownMapView).
long	getAproxMemory() Returns approximation of memory consumption of this object in bytes for 32-bit JVM, might be as twice for 64-bit JVM!
Logger	getLog() Returns logger used by this object.
IPFKnownMap<NODE>	getMap() Map abstraction the FloydWarshall is working with.
IPFKnownMapView<NODE>	getMapView() Returns agent-specific map view for the map.
FloydWarshall.PathMatrixNode<NODE>[][]	getMatrix() Returns matrix of nodes as computed by FloydWarshall algorithm.
Integer	getNodeIndex(NODE node) Returns index of the node inside getMatrix().
List<NODE>	getPath(NODE from, NODE to) Returns path between navpoints 'from' -> 'to'.
int	getPathCost(NODE from, NODE to) Calculate's distance between two nav points (using pathfinding).
FloydWarshall.PathMatrixNode<NODE>	getPathMatrixNode(NODE nodeFrom, NODE nodeTo) Returns PathMatrixNode describing path from "nodeFrom" to "nodeTo".
boolean	isReachable(NODE from, NODE to) Whether node 'to' is reachable (path exists) from the node 'from'.
void	setLog(Logger log) Sets logger used by this object.
void	setMap(IPFKnownMap<NODE> map) Sets map abstraction into the FloydWarshall.
void	setMapView(IPFKnownMapView<NODE> mapView) Sets agent-specific map view for the map.
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

FloydWarshall

public FloydWarshall(IPFKnownMap<NODE> map)

FloydWarshall configured with "map" with no agent-specific view on the map, IPFMapView.DefaultView is used.

compute() method is immediately called from within this constructor.

Parameters:

map -

FloydWarshall

public FloydWarshall(IPFKnownMap<NODE> map,
                     IPFKnownMapView<NODE> view)

FloydWarshall configured with "map" and agent-specific view on the map, if "view" is null, IPFMapView.DefaultView is going to be used.

compute() method is immediately called from within this constructor.

Parameters:

map -

view - may be null

FloydWarshall

public FloydWarshall(IPFKnownMap<NODE> map,
                     Logger log)

FloydWarshall configured with "map" with no agent-specific view on the map, IPFMapView.DefaultView is used.

compute() method is immediately called from within this constructor.

Parameters:

map -

log - may be null

FloydWarshall

public FloydWarshall(IPFKnownMap<NODE> map,
                     IPFKnownMapView<NODE> view,
                     Logger log)

FloydWarshall configured with "map" and agent-specific view on the map, if "view" is null, IPFMapView.DefaultView is going to be used.

compute() method is immediately called from within this constructor.

Parameters:

map -

view - may be null

log - may be null

Method Detail

getLog

public Logger getLog()

Returns logger used by this object.

Returns:

setLog

public void setLog(Logger log)

Sets logger used by this object.

Parameters:

log -

getMap

public IPFKnownMap<NODE> getMap()

Map abstraction the FloydWarshall is working with.

Returns:

setMap

public void setMap(IPFKnownMap<NODE> map)

Sets map abstraction into the FloydWarshall.

Parameters:

map -

getMapView

public IPFKnownMapView<NODE> getMapView()

Returns agent-specific map view for the map.

Returns:

setMapView

public void setMapView(IPFKnownMapView<NODE> mapView)

Sets agent-specific map view for the map.

Parameters:

mapView -

compute

public void compute()

Force FloydWarshall to refresh its path matrix, useful if you modify the map or view using setMap(IPFKnownMap) or setMapView(IPFKnownMapView).

Called automatically from constructors!

cacheAllPaths

public void cacheAllPaths()

getAproxMemory

public long getAproxMemory()

Returns approximation of memory consumption of this object in bytes for 32-bit JVM, might be as twice for 64-bit JVM!

Returns:

getPathMatrixNode

public FloydWarshall.PathMatrixNode<NODE> getPathMatrixNode(NODE nodeFrom,
                                                            NODE nodeTo)

Returns PathMatrixNode describing path from "nodeFrom" to "nodeTo".

Parameters:

nodeFrom -

nodeTo -

Returns:

isReachable

public boolean isReachable(NODE from,
                           NODE to)

Whether node 'to' is reachable (path exists) from the node 'from'.

Parameters:

from -

to -

Returns:

getPathCost

public int getPathCost(NODE from,
                       NODE 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 Integer.MAX_VALUE if there's no path.

getPath

public List<NODE> getPath(NODE from,
                          NODE to)

Returns path between navpoints 'from' -> 'to'. The path begins with 'from' and ends with 'to'. If such path doesn't exist, returns null.

Path is automatically cached using SoftReference.

Parameters:

from -

to -

Returns:

getMatrix

public FloydWarshall.PathMatrixNode<NODE>[][] getMatrix()

Returns matrix of nodes as computed by FloydWarshall algorithm. You should not alter it by hand!

Returns:

getNodeIndex

public Integer getNodeIndex(NODE node)

Returns index of the node inside getMatrix(). Note that if node that is not inside the matrix is passed, this will return null!

Parameters:

node -

Returns:

toString

public String toString()

Overrides:

toString in class Object