model.agent.humanAgent.aatom.tacticalLevel.navigation.pathfinder

Class JumpPointSearchPathFinder

java.lang.Object

model.agent.humanAgent.aatom.tacticalLevel.navigation.pathfinder.PathFinder

model.agent.humanAgent.aatom.tacticalLevel.navigation.pathfinder.JumpPointSearchPathFinder

public class JumpPointSearchPathFinder
extends PathFinder

The jump point search path finder uses jump point search to determine paths. Adapted from: https://github.com/qiao/PathFinding.js/ Original paper: Online Graph Pruning for Pathfinding on Grid Maps, by Daniel Harabor and Alban Grastien.

Author:

S.A.M. Janssen

Field Summary

Fields

Modifier and Type	Field and Description
private JumpPointNode	goalNode The goal node.
private JumpPointNode[][]	graph The graph in array format.

Fields inherited from class model.agent.humanAgent.aatom.tacticalLevel.navigation.pathfinder.PathFinder

discretizedMap, map, precision

Constructor Summary

Constructors

Constructor and Description
JumpPointSearchPathFinder(Map map, double precision) Creates the path finder.

Method Summary

Modifier and Type	Method and Description
private void	doSuccessor(JumpPointNode node, java.util.ArrayList<JumpPointNode> openList) Performs the successor step in the algorithm.
private void	emptyMap() Empties the map and sets all values to null.
private float	getDistance(JumpPointNode first, JumpPointNode second) Gets the distance between two nodes.
private java.util.Collection<JumpPointNode>	getNeighbors(JumpPointNode node) Gets the neighbors of a JumpPointNode.
private JumpPointNode	getNextNode(java.util.ArrayList<JumpPointNode> openList) Gets the next node from the open list.
private JumpPointNode	getNode(int x, int y) Gets a node from its coordinates.
private JumpPointNode	getNodeFromPosition(Position position) Gets a JPS node from a Position.
java.util.List<Position>	getPath(Position start, Position goal, boolean smooth) Gets a feasible path from a specified start Position to a goal Position.
private Position	getPositionFromNode(JumpPointNode node) Gets a Position from a A Star Node.
private boolean	isTraversable(int x, int y) Determines if the graph is traversable at (x,y)
private JumpPointNode	jump(JumpPointNode child, JumpPointNode parent) Perform the jump.
private void	resetMap() Resets the map.

Methods inherited from class model.agent.humanAgent.aatom.tacticalLevel.navigation.pathfinder.PathFinder

directPathPossible, getCornerPoints2, getPath, smooth

Methods inherited from class java.lang.Object

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

Field Detail

graph

private JumpPointNode[][] graph

The graph in array format.

goalNode

private JumpPointNode goalNode

The goal node.

Constructor Detail

JumpPointSearchPathFinder

public JumpPointSearchPathFinder(Map map,
                                 double precision)

Creates the path finder.

Parameters:

map - The map.

precision - The precision.

Method Detail

doSuccessor

private void doSuccessor(JumpPointNode node,
                         java.util.ArrayList<JumpPointNode> openList)

Performs the successor step in the algorithm.

Parameters:

node - The node.

openList - The open list.

emptyMap

private void emptyMap()

Empties the map and sets all values to null. This method is used to prevent memory from large amounts of memory being stored in the agents for no reason.

getDistance

private float getDistance(JumpPointNode first,
                          JumpPointNode second)

Gets the distance between two nodes.

Parameters:

first - The first node.

second - The second node.

Returns:

The distance.

getNeighbors

private java.util.Collection<JumpPointNode> getNeighbors(JumpPointNode node)

Gets the neighbors of a JumpPointNode.

Parameters:

node - The node.

Returns:

The neighbors.

getNextNode

private JumpPointNode getNextNode(java.util.ArrayList<JumpPointNode> openList)

Gets the next node from the open list.

Parameters:

openList - The open list.

Returns:

The next node.

getNode

private JumpPointNode getNode(int x,
                              int y)

Gets a node from its coordinates.

Parameters:

x - X coordinate.

y - Y coordinate.

Returns:

The node.

getNodeFromPosition

private JumpPointNode getNodeFromPosition(Position position)

Gets a JPS node from a Position.

Parameters:

position - The position.

Returns:

The node.

getPath

public java.util.List<Position> getPath(Position start,
                                        Position goal,
                                        boolean smooth)

Description copied from class: PathFinder

Gets a feasible path from a specified start Position to a goal Position. The method returns a list of points that are the corner points of the specified path.

Specified by:

getPath in class PathFinder

Parameters:

start - The start position.

goal - The goal position.

smooth - Smooth or not.

Returns:

The path.

getPositionFromNode

private Position getPositionFromNode(JumpPointNode node)

Gets a Position from a A Star Node.

Parameters:

node - The node.

Returns:

The position.

isTraversable

private boolean isTraversable(int x,
                              int y)

Determines if the graph is traversable at (x,y)

Parameters:

x - X coordinate

y - Y coordinate

Returns:

True if it is traversable, false otherwise.

jump

private JumpPointNode jump(JumpPointNode child,
                           JumpPointNode parent)

Perform the jump.

Parameters:

child - The child.

parent - The parent.

Returns:

The jump node.

resetMap

private void resetMap()

Resets the map.