The Pathfinder can be used straight away with a map of Nodes built by the internal map maker. Variations on the standard map can be achieved by setting flags in the Pathfinder before calling setCuboidNodes(). Or the user can make their own map and add it to the Pathfinder.
The following is a quick program to show you Pathfinder at it's most basic. It's based on the Dijkstra example. With the library installed you can copy and paste this program straight into Processing:
| Field Summary | |
| ArrayList | nodes A storage array for the Nodes used in the AStar algorithm. |
| ArrayList | open An array used to collect information on possible routes. |
| ArrayList | closed An array of nodes forming possible routes. |
| boolean | wrap Setting for createCuboidNodes() and setCuboidNodes() as to whether a web of Nodes wraps around at its edges. Initially set to false. |
| boolean | corners Setting for createCuboidNodes() and setCuboidNodes() as to whether a web of Nodes links at the corners of nodes. Initially set to true. |
| boolean | manhattan Sets the Pathfinder to use an overestimate of distance called the Manhattan method. This encourages straight paths and is useful when corner nodes are not available. Initially set to false. |
| float | offsetX Setting applied to all Nodes generated with createCuboidNodes() and setCuboidNodes(). Refers to the top left most point in generating the web. |
| float | offsetY Setting applied to all Nodes generated with createCuboidNodes() and setCuboidNodes(). Refers to the top left most point in generating the web. |
| float | offsetZ Setting applied to all Nodes generated with createCuboidNodes() and setCuboidNodes(). Refers to the top left most point in generating the web. |
| Constructor Summary |
| Pathfinder () Creates a Pathfinder object without nodes and set to initial state. |
| Pathfinder(ArrayList
nodes) Creates a Pathfinder object using the nodes given in the parameters. |
| Pathfinder(int
width, int height, float scale) Creates a Pathfinder object and sends a call to the setCuboidNodes() method with the given parameters. |
| Pathfinder(int
width, int height, int depth, float scale) Creates a Pathfinder object and sends a call to the setCuboidNodes() method with the given parameters. |
| Method Summary | |
| ArrayList | aStar (Node start, Node finish) Returns an ArrayList containing the shortest route from the start Node to the finish Node. Nodes are connected by their 'parent' property from start to finish. |
| ArrayList | bfs (Node start, Node finish) Returns an ArrayList containing a greedy route from the start Node to the finish Node. This method is however very fast. Nodes are connected by their 'parent' property from start to finish. |
| void | dijkstra (Node start) Configures the parent value of all Nodes in the Pathfinder to point towards the shortest route to the start Node. |
| ArrayList | dijkstra (Node start, Node finish) Configures the parent value of all Nodes in the Pathfinder to point towards the shortest route to the start Node, but halts the search when the finish Node is encountered. Returns an ArrayList of Nodes from start to finish connected by their 'parent' property. |
| ArrayList | getPath (Node pathNode) If pathNode's 'parent' property is not null, then this method will follow the path suggested by the chain of parent Nodes and return an ArrayList of Nodes. |
| void | setCuboidNodes (int width,
int height, float scale) Sets the Nodes in the Pathfinder to a plane grid of connected Nodes according to the flags set in the Pathfinder. |
| void | setCuboidNodes (int
width, int height, int depth, float scale) Sets the Nodes in the Pathfinder to a cuboid grid of connected Nodes according to the flags set in the Pathfinder. |
| void | addNodes (ArrayList nodes) Adds the Nodes given in the parameters to the 'nodes' property of the Pathfinder. |
| ArrayList | createCuboidNodes (int
width, int height, float scale) Returns an ArrayList containing a plane grid of connected Nodes of cuboid dimensions to the scale and dimensions offered. |
| ArrayList | createCuboidNodes (int
width, int height, int depth, float scale) Returns an ArrayList containing a cuboid grid of connected Nodes of cuboid dimensions to the scale and dimensions offered. |
| void | disconnectUnwalkables () Disconnects the links to all of the nodes whose walkable field is set to false. |
| void | radialDisconnectUnwalkables () |
| int | indexOf (Node n) Returns the index in the ArrayList field 'nodes' of Node 'n'. Computes result faster than ArrayList.indexOf(). |
| boolean | arrayListContains (ArrayList
c, Node n) Returns true if Node 'n' is in ArrayList 'c'. Computes result faster than ArrayList.contains(). |
| int [] | getFolded (int n, int []
d) Returns an n-dimensional vector in the form of an array assuming that n is a unit in a list folded into a cuboid of the dimensions given. |
| int | getUnfolded (int [] p,
int [] d) Returns a point in a list from a point in a list folded into a cuboid of the dimensions given. |
| Constructor Detail |
public Pathfinder ()
Creates an object that can be used to find routes through Nodes. Nodes are objects that contain an ArrayList of Connector objects that provide a reference to another Node and the distance between them. They also have a spatial coordinates and a 'parent' field that is set by the search algorithms to imply a path. This constructor is advised in generating custom searches, allowing one to set flags and generate a web of nodes offering the best search.
public Pathfinder (ArrayList Nodes)
Creates an object that can be used to find routes through Nodes. Nodes are objects that contain an ArrayList of Connector objects that provide a reference to another Node and the distance between them. They also have a spatial coordinates and a 'parent' field that is set by the search algorithms to imply a path. This constructor assumes either the presence of another Pathfinder object from which a web of Nodes has been generated or a user made world of Nodes has been generated.
Parameters:
Nodes - an ArrayList of Nodes to be used in a search.
public Pathfinder (int width, int height, float scale)
Creates an object that can be used to find routes through Nodes. Nodes are objects that contain an ArrayList of Connector objects that provide a reference to another Node and the distance between them. They also have a spatial coordinates and a 'parent' field that is set by the search algorithms to imply a path. This constructor creates the Pathfinder object with a plane grid of Nodes connected at the corners.
Parameters:
width - the width of the plane grid of Nodes.
height - the height of the plane grid of Nodes.
scale - the spacing of Nodes in the grid.
public Pathfinder (int width, int height, int depth, float scale)
Creates an object that can be used to find routes through Nodes. Nodes are objects that contain an ArrayList of Connector objects that provide a reference to another Node and the distance between them. They also have a spatial coordinates and a 'parent' field that is set by the search algorithms to imply a path. This constructor creates the Pathfinder object with a cuboid grid of Nodes connected at the corners.
Parameters:
width - the width of the plane grid of Nodes.
height - the height of the plane grid of Nodes.
depth - the depth of the plane grid of Nodes.
scale - the spacing of Nodes in the grid.
| Method Detail |
public ArrayList aStar (Node start, Node finish)
This method returns an ArrayList of Node objects that refer to a path found from Node 'finish' to Node 'start'. Each Node's 'parent' property leads to the next Node in the list and is the means by which the path is extrapolated from the map. The Node at index 0 will be the finish Node and the last Node will be the start Node. Thus the next move a bot would take would be path.size()-2, the Node reached in the chain of parents before start.
The aStar method searches from the start Node to every connecting Node evaluating a score for each Node and developing the search based on the best score. The formula for this score is:
f = g + h
f is the score applied to the Node, g is the cost of reaching the goal and h is the heuristic distance to the goal. This creates the shortest route to the finish Node and is the fastest method Pathfinder offers for this task. If the aStar() method cannot complete its route to the finish node a compromise path is offered that leads to the closest available Node from the finish Node. Note that the compromise is not always efficacious but provides activity for bots engaged in a pursuit.
Parameters:
start - the starting Node for the search.
finish - the goal to reach in the search.
public ArrayList bfs (Node start, Node finish)
This method returns an ArrayList of Node objects that refer to a path found from Node 'start' to Node 'finish'. Each Node's 'parent' property leads to the next Node in the list and is the means by which the path is extrapolated from the map. The Node at index 0 will be the finish Node and the last Node will be the start Node. Thus the next move a bot would take would be path.size()-2, the Node reached in the chain of parents before start.
The bfs method searches from the start Node to every connecting Node evaluating a score for each Node and developing the search based on the best score. The formula for this score is simply the distance to the target.
Since bfs only cares about which Node is nearest to the goal it does away with much of the calculation that slows aStar down. bfs will not get you home any faster, it will run into alley ways on route. But it is a serious consideration for projects with a high frame rate which could be choked by aStar or dijkstra. If the bfs() method cannot complete its route to the finish node a compromise path is offered that leads to the closest available Node from the finish Node. Note that the compromise is not always efficacious but provides activity for bots engaged in a pursuit.
Parameters:
start - the starting Node for the search.
finish - the goal to reach in the search.
public void dikjstra (Node start)
The dijkstra method searches from the start Node to every connecting Node evaluating a score for each Node and developing the search based on the best score. The formula for this score is the distance travelled to reach the node through the Connectors.
This search differs from the other two in that it works across the whole map pointing the 'parent' property of every Node to the shortest route discovered to the 'start' Node. A path can be extrapolated by following the parent Node of each Node or by using the getPath() method. This is the only search that is ignorant of the spatial coordinates of the Node. This means you can perform a search purely based on values separating the Nodes or searches where Nodes on opposite sides of the map are connected. The dijkstra method will not resolve paths to Nodes walled off by unwalkable Nodes or are otherwise unreachable.
Parameters:
start - the starting Node for the search.
public ArrayList dikjstra (Node start, Node finish)
This method returns an ArrayList of Node objects that refer to a path found from Node 'start' to Node 'finish'. Each Node's 'parent' property leads to the next Node in the list and is the means by which the path is extrapolated from the map. The Node at index 0 will be the finish Node and the last Node will be the start Node. Thus the next move a bot would take would be path.size()-2, the Node reached in the chain of parents before start.
The dijkstra method searches from the start Node to every connecting Node evaluating a score for each Node and developing the search based on the best score. The formula for this score is the distance travelled to reach the node through the Connectors.
This search differs from the other two in that it works across the whole map pointing the 'parent' property of every Node to the shortest route discovered to the 'start' Node but quits this operation upon finding the Node 'finish'. This is the only search that is ignorant of the spatial coordinates of the Node. This means you can perform a search purely based on values separating the Nodes or searches where Nodes on opposite sides of the map are connected. The dijkstra method will not resolve paths to Nodes walled off by unwalkable Nodes or are otherwise unreachable. A search that cannot be completed will return an ArrayList with only the 'finish' Node.
Parameters:
start - the starting Node for the search.
finish - the goal to reach in the search or the
point at which the search should be abandoned.
public ArrayList getPath (Node pathNode)
This method returns an ArrayList of Node objects that refer to a path. It is assumed the user has already performed a search and as a result the map will be populated with Nodes leading toward a common goal. This method can be used after any of the searches provided the pathNode leads somewhere. Each Node's 'parent' property leads to the next Node in the list and is the means by which the path is extrapolated from the map. The Node at index 0 will be the pathNode in the parameters and the last Node will be the start Node offered from the last search algorithm. Thus the next move a bot would take would be path.size()-2, the Node reached in the chain of parents before start.
Parameters:
start - the final Node of a chain of Nodes leading to a Node with no parent.
public void setCuboidNodes (int width, int height, float scale)
This method resets the nodes field and fills it with a plane grid of Nodes of the width and height specified in Nodes. The Nodes are regularly spaced apart according to the scale parameter. The Nodes are automatically linked according to the flag settings of the Pathfinder object.
Parameters:
width - the width of the grid of Nodes.
height - the height
of the grid of Nodes.
scale - the distance
between the Nodes excluding diagonal distances.
public void setCuboidNodes (int width, int height, int depth, float scale)
This method resets the nodes field and fills it with a cuboid grid of Nodes of the width, height and depth specified in Nodes. The Nodes are regularly spaced apart according to the scale parameter. The Nodes are automatically linked according to the flag settings of the Pathfinder object.
Parameters:
width - the width of the grid of Nodes.
height - the height
of the grid of Nodes.
depth -
the depth of the grid of Nodes.
scale - the distance
between the Nodes excluding diagonal distances.
public void addNodes (ArrayList nodes)
Adds the ArrayList given to the nodes field. This method can be used after generating custom node environments to add said environments to a Pathfinder object. It will not resolve connections to existing Nodes and anyone wishing to replace the contents of 'nodes' should call the ArrayList method clear() on 'nodes' before adding the new map.
Parameters:
nodes - a Vector of Nodes.
public ArrayList createCuboidNodes (int width, int height, scale)
This method returns an ArrayList containing a plane grid of Nodes of the width and height specified in Nodes. The Nodes are regularly spaced apart according to the scale parameter. The Nodes are automatically linked according to the flag settings of the Pathfinder object.
Parameters:
width - the width of the grid of Nodes.
height - the height
of the grid of Nodes.
scale - the distance
between the Nodes excluding diagonal distances.
public ArrayList createCuboidNodes (int width, int height, scale)
This method returns an ArrayList containing a cuboid grid of Nodes of the width, height and depth specified in Nodes. The Nodes are regularly spaced apart according to the scale parameter. The Nodes are automatically linked according to the flag settings of the Pathfinder object.
Parameters:
width - the width of the grid of Nodes.
height - the height
of the grid of Nodes.
depth -
the depth of the grid of Nodes.
scale - the distance
between the Nodes excluding diagonal distances.
public void disconnectUnwalkables ()
This method iterates through the whole 'nodes' field and disconnects the incoming Connectors to all Nodes whose 'walkable' field is set to false.
public void radialDisconnectUnwalkables ()
This method iterates through the whole nodes field and disconnects all Connectors in a sphere around all Nodes whose 'walkable' field is set to false. The range of effect is determined by the shortest link. This method is supplied as a solution to removing the links on corner connected Nodes that will overlap an unwalkable Node but not pass through it. Search paths thus will walk around the physical size of the Node. The measuring in this method ignores settings on the Connectors of any Node, using spatial mesurements between the Nodes instead.
public int indexOf(Node n)
This method returns the index within the ArrayList 'nodes' of Node 'n'. It is supplied as a faster alternative to ArrayList.indexOf() for the 'nodes' property and is also used in the Pathfinder's search algorithms to improve their performance. If the Node is not in 'nodes' the value -1 is returned.
Parameters:
n - the Node for which an index is to be found.
public boolean arrayListContains(ArrayList c, Node n)
This method returns true if Node 'n' is within the ArrayList 'c'. It is supplied as a faster alternative to ArrayList.contains() for Nodes and is also used in the Pathfinder's search algorithms to improve their performance.
Parameters:
c - an ArrayList populated with Nodes.
n -
the Node to be found.
public int [] getFolded (int n, int [] d)
This method returns a point in a cuboid. The point will have as many dimensions as the cuboid. The cuboid is defined by the array given and the point is a unit on a line folded into the cuboid given. This method is supplied as part of the calculations used in generating the cuboid maps and may be deprecated in future.
Parameters:
n - a unit in list or an array of a singular dimension.
d -
the dimensions of a cuboid that it is assumed the aforementioned list has been
folded into.
public int getUnfolded (int [] p, int [] d)
This method returns a point on a line or list that has a length equal to the dimensions of a cuboid given in the parameters multiplied together. This method is supplied as part of the calculations used in generating the cuboid maps and may be deprecated in future.
Parameters:
p - a location in a cuboid to be turned into a
unit on a list.
d - the dimensions of said cuboid which is actually a list assuming
the shape of a cuboid.