• Stars
    star
    267
  • Rank 153,621 (Top 4 %)
  • Language
    Python
  • License
    MIT License
  • Created over 9 years ago
  • Updated almost 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Implementation of common pathfinding algorithms

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.

Build Status Coverage Status MIT License PyPI

If you are still using python 2 take a look at the 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

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

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, [email protected]

Authors / Contributers

Authors and contributers are listed on github.

Inspired by Pathfinding.JS

More Repositories

1

python-ifc-model

helper classes to load and store data from IFC into a smaller JSON for easier access across different platforms
Python
28
star
2

python-ifc-blender

import and manipulate an IFC in Blender based on IFCOpenShell
Python
26
star
3

Non-Military-Open-Source-License

Non-Military Open Source License
13
star
4

arduino-kivy-bluetooth

control an arduino board via bluetooth in a kivy-app using firmata
Python
13
star
5

robotlegs2-starling-clock-example

ActionScript
12
star
6

godot-robotics-sources

Sources, Links and Information on using the Godot Game Engine in Robotics
7
star
7

geometry_position_Unity3D_WebGL

Create and move cubes in WebGL and see them moving in Mixed Reality (using Meteor)
C#
6
star
8

cpp-socket-server

configurable C/C++ multi-threaded socket server template for Unix-based systems with logging as basis for different projects to get data from different clients and process it directly in C/C++
C++
6
star
9

jbla

Json to BLender Animation
Python
5
star
10

ros2-turtlebot3-gazebo-docker

ROS 2 docker image using the Gazebo simulation
Shell
5
star
11

godot-robotics

Godot as robotics simulation using ROS 2 humble
GDScript
4
star
12

CirqueDuSoleilDemo

A small project inspired by the Build 2017 Cirque du Soleil Demo
C#
4
star
13

docker-ros2-lidar-scanner

run rviz2 and ROS2 inside docker to show/process an rplidar-scan.
Dockerfile
4
star
14

MonsterFight

Godot Monster Fighting Game
GDScript
4
star
15

gz-sim-docker

Base docker container for newer Gazebo versions ontop of ROS 2
Dockerfile
4
star
16

Game-Dev-Intro

Explainations on how to generally create a game for a Game Jam... from inside a game engine.
GDScript
3
star
17

ubuntu-setup

Setup scripts for setting up my initial Ubuntu system
Shell
3
star
18

UltimateSuperSmashSibs

Global Game Jam Game 2019
C#
3
star
19

pybullet_ros_environment

Development environment for pybullet using Docker
Dockerfile
3
star
20

discord-bot-cud

Simple Discord but that creates voice channels for pairs of 2
Python
2
star
21

mobipick_labs_docker

Docker (compose) environment for the DFKI MobiPick lab (https://github.com/DFKI-NI/mobipick_labs)
Dockerfile
2
star
22

cozmo_ros

COZMO driver for ROS-2 using pycozmo
Python
2
star
23

MauzillaDespair

Global Game Jam 2020 Game
C#
2
star
24

mir-simulation

docker-compose file and run script for MIR-100 robot simulation
Dockerfile
2
star
25

colyseus-lobby-babylon

colyseus.io and babylon.js based game using kay-kit assets
TypeScript
2
star
26

robot-design-lab-latex-template

LaTeX template for the course "Robot Design Lab".
TeX
1
star
27

roslibjs-react-typescript-docker

Minimal Example using ROS noetic with libjs and a React-based frontend for debugging of action execution.
TypeScript
1
star
28

hospital-world-docker

Dockerfile
1
star
29

urdf-editor

parse robot URDF and show it in svelte using threlte.xyz
Svelte
1
star
30

my-robot-fleet

Information of the robots (and useful robotic hardware) I privately own.
1
star
31

simple_planning

Run planning algorithms in docker
C
1
star
32

react-sc2

React.js frontend to see results of StarCraft 2 matches played by AI.
HTML
1
star
33

ros2-turtlebot3-remote-pc-docker

ROS 2 docker image of the "REMOTE-PC" to connect to a turtlebot in simulation or on real hardware
Shell
1
star
34

my_mindstorms_scripts

LEGO Mindstorms scripts
Python
1
star
35

pixi-shapes-editor

Simple Editor for PIXI.shapes (which is part of GOWN)
JavaScript
1
star
36

aiohttp_dev_docker

Docker-Environment running aiohttp for easy development.
Python
1
star
37

robot_design_lab_20_21

Material for the Robot Design Lab lecture at University Bremen Winter semester 2020/2021
CMake
1
star
38

worktime

Python program to get my timesheet from an owncloud-calendar
Python
1
star
39

docker-sc2

Docker environment for StarCraft II bots.
Python
1
star
40

python-txtrpacker

Texture Packer (based on http://www.executionunit.com/blog/2013/04/12/python-script-to-build-a-texture-page-or-sprite-sheet/ by Execution Unit Ltd.)
Python
1
star
41

robotlegs2-clock-example

robotlegs 2 clock example that shows all parts of the MVCS bundle
ActionScript
1
star
42

ClumsyWizardBros

Hangover: Magic Edition - Global Game Jam 2018 Game
C#
1
star
43

roslibpy_bridge_test

Example project to connect two ros instances using roslibpy
Python
1
star
44

procvis

JavaScript process visualization (and manipulation) library
CSS
1
star
45

brean

About me
1
star
46

quest-boxes

Draw Boxes to create Quests for learning apps or games.
Vue
1
star
47

Game-Dev-Intro-3D

Game Development Introduction using Godot in 3D
1
star
48

vue-web-infrastructure

Basic docker-based infrastructure for Web Projects
Vue
1
star
49

javascript-karma-webpack-coverage-sample

Basic example for an ECMAScript 6-project using Webpack, Karma and Istanbul (automatic unit testing with coverage report) and JSDoc - feel free to use this as boilerplate for your next professional JavaScript application
JavaScript
1
star
50

ros-gazebo-colcon-docker

Build docker container using ros:noetic with gazebo and colcon installed
Dockerfile
1
star
51

moon_mission

A Moon Mission selection screen in svelte using threlte and smui
Svelte
1
star