Class PathfinderUtil

java.lang.Object

de.tomatengames.util.PathfinderUtil

public class PathfinderUtil
extends Object

Provides methods to find optimal paths on graphs using the A* algorithm.

Since:

1.5

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	PathfinderUtil.PathNode	A PathNode should represent a position (node in a graph) combined with the way to get there (edges) from the startpoint.
static class	PathfinderUtil.PositionMap<N extends PathfinderUtil.PathNode>	A Map-like structure specifically for PathfinderUtil.PathNodes.
static interface	PathfinderUtil.World<N extends PathfinderUtil.PathNode>	Provides several functions used by the find methods.

Method Summary

Modifier and Type	Method	Description
static <N extends PathfinderUtil.PathNode> N	find(N start, boolean all, PathfinderUtil.PositionMap<N> positionMap, PathfinderUtil.World<N> world)	Finds a goal from the provided startpoint, using the provided PathfinderUtil.World to traverse the environment.
static <N extends PathfinderUtil.PathNode> N	find(N start, PathfinderUtil.World<N> world)	Finds a goal from the provided startpoint, using the provided PathfinderUtil.World to traverse the environment.
static <N> List<N>	listPath(N node, Function<N,N> previous)	Utility to list the PathNodes from the startpoint to the provided PathNode.
static <N> void	traverseAll(N node, Function<N, Iterator<N>> neighbors, Consumer<N> output)	Utility to recursively find all PathNodes indirectly connected to the provided node.

Methods inherited from class Object

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

Method Details

find

public static <N extends PathfinderUtil.PathNode> N find(N start,
 PathfinderUtil.World<N> world)

Finds a goal from the provided startpoint, using the provided PathfinderUtil.World to traverse the environment.

Type Parameters:

N - The specific type of PathNode used

Parameters:

start - The startpoint

world - The PathfinderUtil.World

Returns:

A goal PathNode

See Also:

• PathfinderUtil.PathNode
• PathfinderUtil.World

find

public static <N extends PathfinderUtil.PathNode> N find(N start,
 boolean all,
 PathfinderUtil.PositionMap<N> positionMap,
 PathfinderUtil.World<N> world)

Finds a goal from the provided startpoint, using the provided PathfinderUtil.World to traverse the environment. Set the parameter all to true to consider all optimal paths, enabling PathfinderUtil.World.preferOrigin(PathNode, PathNode) to choose from all the optimal paths. The provided PathfinderUtil.PositionMap will be used to map any position to the cheapest PathNode that was yet found representing that position. An empty map should be provided here, but its contents may be interesting after this method returns (see PathfinderUtil.World.preferOrigin(PathNode, PathNode)).

Type Parameters:

N - The specific type of PathNode used

Parameters:

start - The startpoint

all - whether to visit all optimal paths

positionMap - The PathfinderUtil.PositionMap

world - The PathfinderUtil.World

Returns:

A goal PathNode

listPath

public static <N> List<N> listPath(N node,
 Function<N,N> previous)

Utility to list the PathNodes from the startpoint to the provided PathNode. Typically, a PathNode knows their original PathNode (previous), which this method obtains using the provided function.

Type Parameters:

N - The specific type of PathNode

Parameters:

node - The furthest PathNode, typically the found goal

previous - The function used to obtain a PathNodes previous PathNode, or null if the list is complete, which typically means that the input PathNode is the startpoint.

Returns:

A list from the startpoint (first) up to the provided PathNode (last)

traverseAll

public static <N> void traverseAll(N node,
 Function<N, Iterator<N>> neighbors,
 Consumer<N> output)

Utility to recursively find all PathNodes indirectly connected to the provided node. This may be useful for collecting all PathNodes involved in any path from start to goal when multiple possible paths were recorded.

Type Parameters:

N - The specific type of PathNode

Parameters:

node - The initial PathNode to start searching from

neighbors - The function providing the PathNodes directly connected to the input PathNode

output - The Consumer that all found PathNodes will be put into