Pathfinding algorithms (based on Pathfinding.JS)
Project description
pythonpathfinding
Pathfinding algorithms for python 2 and 3.
Currently there are 7 pathfinders bundled in this library, namely:
 A*
 Dijkstra
 BestFirst
 Bidirectional A*
 Breadth First Search (BFS)
 Iterative Deeping A* (IDA*)
 Minimum Spanning Tree (MSP)
Dijkstra and A* take the weight of the fields on the map into account.
Inspired by Pathfinding.JS
Installation
This library is provided by pypi, so you can just install the current stable version using pip:
pip install pathfinding
Usage example
A simple usage example to find a path using A*.

import the required libraries:
from pathfinding.core.diagonal_movement import DiagonalMovement from pathfinding.core.grid import Grid from pathfinding.finder.a_star import AStarFinder

Create a map using a 2Dlist. Any value smaller or equal to 0 describes an obstacle. Any number bigger than 0 describes the weight of a field that can be walked on. The bigger the number the higher the cost to walk that field. In this example we like the algorithm to create a path from the upper left to the bottom right. To make it not to easy for the algorithm we added an obstacle in the middle, so it can not use the direct way. We ignore the weight for now, all fields have the same cost of 1. Feel free to create a more complex map or use some sensor data as input for it.
matrix = [ [1, 1, 1], [1, 0, 1], [1, 1, 1] ]
Note: you can use negative values to describe different types of obstacles. It does not make a difference for the path finding algorithm but it might be useful for your later map evaluation.

we create a new grid from this map representation. This will create Node instances for every element of our map. It will also set the size of the map. We assume that your map is a square, so the size height is defined by the length of the outer list and the width by the length of the first list inside it.
grid = Grid(matrix=matrix)

we get the start (topleft) and endpoint (bottomright) from the map:
start = grid.node(0, 0) end = grid.node(2, 2)

create a new instance of our finder and let it do its work. We allow diagonal movement. The
find_path
function does not only return you the path from the start to the end point it also returns the number of times the algorithm needed to be called until a way was found.finder = AStarFinder(diagonal_movement=DiagonalMovement.always) path, runs = finder.find_path(start, end, grid)

thats it. We found a way. Now we can print the result (or do something else with it). Note that the start and end points are part of the path.
print('operations:', runs, 'path length:', len(path)) print(grid.grid_str(path=path, start=start, end=end))
The result should look like this:
('operations:', 5, 'path length:', 4) ++ sx   #x  e ++
You can ignore the +,  and  characters, they just show the border around your map, the blank space is a free field, 's' marks the start, 'e' the end and '#' our obstacle in the middle. You see the path from start to end marked by 'x' characters. We allow horizontal movement, so it is not using the upperright corner. You can access
print(path)
to get the specific list of coordinates.
Here The whole example if you just want to copyandpaste the code and play with it:
from pathfinding.core.diagonal_movement import DiagonalMovement from pathfinding.core.grid import Grid from pathfinding.finder.a_star import AStarFinder matrix = [ [1, 1, 1], [1, 0, 1], [1, 1, 1] ] grid = Grid(matrix=matrix) start = grid.node(0, 0) end = grid.node(2, 2) finder = AStarFinder(diagonal_movement=DiagonalMovement.always) path, runs = finder.find_path(start, end, grid) print('operations:', runs, 'path length:', len(path)) print(grid.grid_str(path=path, start=start, end=end))
Take a look at the test/
folder for more examples.
Rerun the algorithm
While running the pathfinding algorithm it might set values on the nodes. Depending on your path finding algorithm things like calculated distances or visited flags might be stored on them. So if you want to run the algorithm in a loop you need to clean the grid first (see Grid.cleanup
). Please note that because cleanup looks at all nodes of the grid it might be an operation that can take a bit of time!
Implementation details
All pathfinding algorithms in this library are inheriting the Finder class. It has some common functionality that can be overwritten by the implementation of a path finding algorithm.
The normal process works like this:
 You call
find_path
on one of your finder implementations init_find
instantiatesopen_list
and resets all values and counters. The main loop starts on the
open_list
. This list gets filled with all nodes that will be processed next (e.g. all neighbors that are walkable). For this you need to implementcheck_neighbors
in your own finder implementation.  For example in A*s implementation of
check_neighbors
you first want to get the next node closest from the current starting point from the open list. thenext_node
method in Finder does this by giving you the node with a minimumf
value from the open list, it closes it and removes it from theopen_list
.  if this node is not the end node we go on and get its neighbors by calling
find_neighbors
. This just callsgrid.neighbors
for most algorithms.  If none of the neighbors are the end node we want to process the neighbors to calculate their distances in
process_node
process_node
calculates the costf
from the start to the current node using thecalc_cost
method and the cost after calculatingh
fromapply_heuristic
. finally
process_node
updates the open list sofind_path
can runcheck_neighbors
on it in the next node in the next iteration of the main loop.
flow:
find_path init_find # (re)set global values and open list check_neighbors # for every node in open list next_node # closest node to start in open list find_neighbors # get neighbors process_node # calculate new cost for neighboring node
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size pathfinding1.0.1py3.9.egg (18.2 kB)  File type Egg  Python version 3.9  Upload date  Hashes View 
Filename, size pathfinding1.0.1py3noneany.whl (19.8 kB)  File type Wheel  Python version py3  Upload date  Hashes View 
Filename, size pathfinding1.0.1.tar.gz (15.7 kB)  File type Source  Python version None  Upload date  Hashes View 
Hashes for pathfinding1.0.1py3noneany.whl
Algorithm  Hash digest  

SHA256  911a5f8b8fbbdb8c4c8b804501b3a4107595d07663f496f7f3bd9ec87513196a 

MD5  f04bcbe646a97ae2e15f50162ceb2eae 

BLAKE2256  37831c9a87fbfe53eed24f8003a0f5fc70a6d3958e723a773e35f5ee8ee5399f 