Using the Path finding Module

This page explains to use the Pathfinding module found in the path_planning module (currently only on the pathfinding_api branch). The purpose of this module is to make a convenient way to run different pathing algorithms. It is also written in C++ so it should be much faster than a pure python implementation. This is important as these pathing algorithms will be run very often.

---

Currently, the pathfinding algorithm really only has one functional method: search. search returns the optimal path via the given map of nodes. This method takes arguments to understand the map, start position, goal position, and type of algorithm to run.

The implementation is as such:

pathfinding.search(<list_of_nodes>, <list_of_edges>, <start_pos>, <end_pos>, <algorithm_type>, <heuristic_function>)

I'll go through and explain each of these parameters and the structure they should be in.

---

<list_of_nodes>

This is a list containing lists of two pairs, representing points. Essentially, it is a list containing x,y coordinates. An example of this could be

nodes = [
            [0,0],
            [1,0],
            [2,0]
        ]

In this case, there are three mappable locations, (0,0), (1,0), and (2,0).

---

<list_of_edges>

This is a list specifying which positions are connected. In other words, if you can go from one node to another. Every single value represents the corresponding (order matters) node in the nodes list. It is also a list of lists, but each sublist's length is equal to the number of nodes. Following our example above:

edges = [
            [0,0,1],
            [1,0,0],
            [1,1,0]
          ]

This would mean the following connections are possible:
(0,0) -> (2,0)
(1,0) -> (0,0)
(2,0) -> (0,0)
(2,0) -> (1,0)

---

<start_pos> and <end_pos>

This is just a point to start from and try and reach, respectively. For example

start_pos = [0,0]
end_pos = [1,0]

NOTE: The both of these MUST be a node in the graph (eg, also inside <list_of_nodes>)

---

<algorithm_type>

This is the type of pathing algorithm to run pathfinding with. This is an optional keyword argument, the default is the A* algorithm. The currently supported algorithms are:

Type	Parameter Passed
A*	'A*'
Breadth-First Search	'bfs'

So to run using the Breadth-First algorithm, you would do:

pathfinding.search(nodes, edges, [0,0], [1,0], algorithm='bfs')

---

<heuristic_function>

This is the type of heuristic (distance) function to use. This is an optional keyword argument, the default is Euclidean distance. The currently supported functions are:

Type	Parameter Passed
Euclidean	'euclid'
Manhattan	'man'
GPS	'gps'

So to run using the manhattan distance heuristic (this would run A* since that is the default algorithm), you would do:

pathfinding.search(nodes, edges, [0,0], [1,0], cost_function='man')

---

As a final example, all of the above put together, here is some example code:

#!/usr/bin/env python
import pathfinding

nodes = [[0,0],[1,0],[2,0]]
edges = [[0,0,1],[1,1,0],[0,1,0]]

print pathfinding.search(nodes, edges, [0,0], [1,0], algorithm='bfs', cost_function='man')

Output:

[[0.0, 0.0], [2.0, 0.0], [1.0, 0.0]]

---

Some Notes:

• If a path does not exist, currently it will simply return the start node, I plan on changing this to return the closest path very soon.
• If you pass the points inside nodes and edges as tuples it will fail (eg nodes = [(0,0)...]). I also plan on fixing this soon so both tuples and lists will work interchangably