Repository files navigation

Pathfinding3D

Pathfinding algorithms in 3D for python3 born from the fork ofpython-pathfinding by@brean.

Pathfinding3D is a comprehensive library designed for 3D pathfinding applications.

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

• A*: Versatile and most widely used algorithm.
• Dijkstra: A* without heuristic.
• Best-First
• Bi-directional A*: Efficient for large graphs with a known goal.
• Breadth First Search (BFS)
• Iterative Deeping A* (IDA*): Memory efficient algorithm for large graphs.
• Minimum Spanning Tree (MSP)
• Theta*: Almost A* with path smoothing.

Dijkstra, A* and Bi-directional A* take the weight of the fields on the map into account.Theta* is a variant of A* but with any angle of movement allowed.

• python >= 3.8
• numpy

To install Pathfinding3D, use pip:

pip install pathfinding3d

For more details, seepathfinding3d on pypi

For a quick start, here's a basic example:

importnumpyasnpfrompathfinding3d.core.diagonal_movementimportDiagonalMovementfrompathfinding3d.core.gridimportGridfrompathfinding3d.finder.a_starimportAStarFinder# Create a 3D numpy array with 0s as obstacles and 1s as walkable pathsmatrix=np.ones((10,10,10),dtype=np.int8)# mark the center of the grid as an obstaclematrix[5,5,5]=0# Create a grid object from the numpy arraygrid=Grid(matrix=matrix)# Mark the start and end pointsstart=grid.node(0,0,0)end=grid.node(9,9,9)# Create an instance of the A* finder with diagonal movement allowedfinder=AStarFinder(diagonal_movement=DiagonalMovement.always)path,runs=finder.find_path(start,end,grid)# Path will be a list with all the waypoints as nodes# Convert it to a list of coordinate tuplespath= [p.identifierforpinpath]print("operations:",runs,"path length:",len(path))print("path:",path)

For usage examples with detailed descriptions take a look at theexamples folder or at thedocumentation.

You can visualize the grid along with the path by calling thevisualize method of theGrid class. This method can take path as an optional argument and generate a plotly figure. You can install pathfinding3d with theplotly to use this feature with the following command:

pip install pathfinding3d[vis]

The path produced in the previous example can be visualized by adding the following code to the end of the example:

grid.visualize(path=path,# optionally visualize the pathstart=start,end=end,visualize_weight=True,# weights above 1 (default) will be visualizedsave_html=True,# save visualization to html filesave_to="path_visualization.html",# specify the path to save the html filealways_show=True,# always show the visualization in the browser)

This will generate a visualization of the grid and the path and save it to the filepath_visualization.html and also open it in your default browser.

When rerunning the algorithm, remember to clean the grid first usingGrid.cleanup. This will reset the grid to its original state.

grid.cleanup()

Please note that this operation can be time-consuming but is usally faster than creating a new grid object.

All pathfinding algorithms in this library inherit from theFinder class. This class provides common functionality that can be overridden by specific pathfinding algorithm implementations.

General Process:

1. You callfind_path on one of your finder implementations.
2. init_find instantiates theopen_list and resets all values and counters. Theopen_list is a priority queue that keeps track of nodes to be explored.
3. The main loop starts on theopen_list which contains all nodes to be processed next (e.g. all current neighbors that are walkable). You need to implementcheck_neighbors in your finder implementation to fill this list.
4. For example in A* implementation (AStarFinder),check_neighbors pops the node with the minimum 'f' value from the open list and marks it as closed. It then either returns the path (if the end node is reached) or continues processing neighbors.
5. If the end node is not reached,check_neighbors callsfind_neighbors to get all adjacent walkable nodes. For most algorithms, this callsgrid.neighbors.
6. If none of the neighbors are walkable, the algorithm terminates. Otherwise,check_neighbors callsprocess_node on each neighbor. It calculates the costf for each neighbor node. This involves computingg (the cost from the start node to the current node) andh (the estimated cost from the current node to the end node, calculated byapply_heuristic).
7. Finallyprocess_node updates the open list sofind_path with new or updated nodes. This allowsfind_path to continue the process with the next node in the subsequent iteration.

The following diagram illustrates the process:

  graph TD;      style find_path stroke:#333,stroke-width:2px      style init_find stroke:#333,stroke-width:2px      style while_open_list_not_empty stroke:#333,stroke-width:2px      style check_neighbors stroke:#333,stroke-width:2px      style pop_node stroke:#333,stroke-width:2px      style find_neighbors stroke:#333,stroke-width:2px      style process_node stroke:#333,stroke-width:2px      style return_empty_list stroke:#333,stroke-width:2px      style return_path stroke:#333,stroke-width:2px      find_path["find_path"] --> init_find["init_find\n(re)set global values\nand open list"];      init_find --> while_open_list_not_empty["while open_list not empty"];      while_open_list_not_empty --> check_neighbors["check_neighbors\n(for node with min 'f' value)"];      check_neighbors --> pop_node["pop_node\n(node with min 'f' value)"];      pop_node --> find_neighbors["find_neighbors\n(get neighbors)"];      find_neighbors --> process_node["process_node\n(calculate new cost)"];      process_node --> while_open_list_not_empty;      while_open_list_not_empty -- "open list empty" --> return_empty_list["return empty list"];      while_open_list_not_empty -- "path found" --> return_path["return path"];

Run the tests locally using pytest. For detailed instructions, see thetest folder:

pytesttest

We welcome contributions of all sizes and levels! For bug reports and feature requests, please use theissue tracker to submit bug reports and feature requests. Please Follow the guidelines inCONTRIBUTING.md for submitting merge requests.

Pathfinding3D is distributed under theMIT license.

Find a list of contributorshere.