Skip to main content

Path finding algorithms (based on Pathfinding.JS)

Project description

python-pathfinding

Pathfinding algorithms for python 3.

Currently there are 7 path-finders bundled in this library, namely:

  • A*
  • Dijkstra
  • Best-First
  • Bi-directional 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.

MIT License PyPI

If you are still using python 2 take a look at the (unmaintained) python2-branch.

Installation

This library is provided by pypi, so you can just install the current stable version using pip:

pip install pathfinding

see pathfinding on pypi

Usage examples

For usage examples with detailed descriptions take a look at the docs folder, also take a look at the test/ folder for more examples, e.g. how to use pandas.

image_pathfinding.py in the examples/-folder provides an example how to load an image with a start and goal point. You can all it with an input and output file like this:

cd examples/
python3 image_pathfinding.py -i map.png -o foo.png

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:

  1. You call find_path on one of your finder implementations.
  2. init_find instantiates the open_list and resets all values and counters.
  3. The main loop starts on the open_list. This list gets filled with all nodes that will be processed next (e.g. all current neighbors that are walkable). For this you need to implement check_neighbors in your own finder implementation.
  4. 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. the next_node method in Finder does this by giving you the node with a minimum f-value from the open list, it closes it and removes it from the open_list.
  5. if this node is not the end node we go on and get its neighbors by calling find_neighbors. This just calls grid.neighbors for most algorithms.
  6. If none of the neighbors are the end node we want to process the neighbors to calculate their distances in process_node
  7. process_node calculates the cost f from the start to the current node using the calc_cost method and the cost after calculating h from apply_heuristic.
  8. finally process_node updates the open list so find_path can run check_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

Testing

You can run the tests locally using pytest. Take a look at the test-folder

You can follow below steps to setup your virtual environment and run the tests.

# Go to repo
cd python-pathfinding

# Setup virtual env and activate it - Mac/Linux for windows use source venv/Scripts/activate
python3 -m venv venv
source venv/bin/activate

# Install test requirements
pip install -r test/requirements.txt

# Run all the tests
pytest

Contributing

Please use the issue tracker to submit bug reports and feature requests. Please use merge requests as described here to add/adapt functionality.

License

python-pathfinding is distributed under the MIT license.

Maintainer

Andreas Bresser, self@andreasbresser.de

Authors / Contributers

Authors and contributers are listed on github.

Inspired by Pathfinding.JS

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pathfinding-1.0.17.tar.gz (22.4 kB view details)

Uploaded Source

Built Distribution

pathfinding-1.0.17-py3-none-any.whl (23.3 kB view details)

Uploaded Python 3

File details

Details for the file pathfinding-1.0.17.tar.gz.

File metadata

  • Download URL: pathfinding-1.0.17.tar.gz
  • Upload date:
  • Size: 22.4 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/6.1.0 CPython/3.12.8

File hashes

Hashes for pathfinding-1.0.17.tar.gz
Algorithm Hash digest
SHA256 73ad00daf31e6b71080774e7aa3f68c88524cf4604f2769ead3bfef428cbb5f1
MD5 bff441842dbd838555741fbca62575c8
BLAKE2b-256 119e3adfd01dc368112a72709458055cc7c1f236f0a0bbf01e36c22f4d1564e6

See more details on using hashes here.

File details

Details for the file pathfinding-1.0.17-py3-none-any.whl.

File metadata

  • Download URL: pathfinding-1.0.17-py3-none-any.whl
  • Upload date:
  • Size: 23.3 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/6.1.0 CPython/3.12.8

File hashes

Hashes for pathfinding-1.0.17-py3-none-any.whl
Algorithm Hash digest
SHA256 4ed4d9cd51b470dacf7a5bf21555c93b27e5536836d17bf7d4c95c0fadce1fca
MD5 54f6933ed852c8426df45087d7a74a6a
BLAKE2b-256 0169ba483e0a7716e388cd39f4a5870369cbea966fed8fe1dbcc40bed7b6e083

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page