<div align="center">
# Pathfinding3D
[](LICENSE)
[](https://pypi.org/project/pathfinding3d/)
[](https://github.com/harisankar95/pathfinding3D/actions/workflows/run-tests.yml)
[](https://codecov.io/gh/harisankar95/pathfinding3D)
[](https://github.com/psf/black)
[](https://harisankar95.github.io/pathfinding3D/INTRO.html)
<img src="https://raw.githubusercontent.com/harisankar95/pathfinding3D/main/assets/logo.png" width="224" title="Pathfinding3D logo">
</div>
Pathfinding algorithms in 3D for python3 born from the fork of [python-pathfinding](https://github.com/brean/python-pathfinding) by [@brean](https://github.com/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.
## Installation
### Requirements
- python >= 3.8
- numpy
To install Pathfinding3D, use pip:
```bash
pip install pathfinding3d
```
For more details, see [pathfinding3d on pypi](https://pypi.org/project/pathfinding3d/)
## Usage examples
For a quick start, here's a basic example:
```python
import numpy as np
from pathfinding3d.core.diagonal_movement import DiagonalMovement
from pathfinding3d.core.grid import Grid
from pathfinding3d.finder.a_star import AStarFinder
# Create a 3D numpy array with 0s as obstacles and 1s as walkable paths
matrix = np.ones((10, 10, 10), dtype=np.int8)
# mark the center of the grid as an obstacle
matrix[5, 5, 5] = 0
# Create a grid object from the numpy array
grid = Grid(matrix=matrix)
# Mark the start and end points
start = grid.node(0, 0, 0)
end = grid.node(9, 9, 9)
# Create an instance of the A* finder with diagonal movement allowed
finder = 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 tuples
path = [p.identifier for p in path]
print("operations:", runs, "path length:", len(path))
print("path:", path)
```
For usage examples with detailed descriptions take a look at the [examples](examples/) folder or at the [documentation](https://harisankar95.github.io/pathfinding3D/USAGE.html).
## Visualization of the path
You can visualize the grid along with the path by calling the `visualize` method of the `Grid` class. This method can take path as an optional argument and generate a plotly figure. You can install pathfinding3d with the `plotly` to use this feature with the following command:
```bash
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:
```python
grid.visualize(
path=path, # optionally visualize the path
start=start,
end=end,
visualize_weight=True, # weights above 1 (default) will be visualized
save_html=True, # save visualization to html file
save_to="path_visualization.html", # specify the path to save the html file
always_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 file `path_visualization.html` and also open it in your default browser.
<p align="center">
<img src="https://raw.githubusercontent.com/harisankar95/pathfinding3D/main/assets/path_visualization.png" width="95%" title="Path visualization">
<p align="center">
## Rerun the Algorithm
When rerunning the algorithm, remember to clean the grid first using `Grid.cleanup`. This will reset the grid to its original state.
```python
grid.cleanup()
```
Please note that this operation can be time-consuming but is usally faster than creating a new grid object.
## Implementation details
All pathfinding algorithms in this library inherit from the `Finder` class. This class provides common functionality that can be overridden by specific pathfinding algorithm implementations.
General Process:
1. You call `find_path` on one of your finder implementations.
2. `init_find` instantiates the `open_list` and resets all values and counters. The `open_list` is a priority queue that keeps track of nodes to be explored.
3. The main loop starts on the `open_list` which contains all nodes to be processed next (e.g. all current neighbors that are walkable). You need to implement `check_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` calls `find_neighbors` to get all adjacent walkable nodes. For most algorithms, this calls `grid.neighbors`.
6. If none of the neighbors are walkable, the algorithm terminates. Otherwise, `check_neighbors` calls `process_node` on each neighbor. It calculates the cost `f` for each neighbor node. This involves computing `g` (the cost from the start node to the current node) and `h` (the estimated cost from the current node to the end node, calculated by `apply_heuristic`).
7. Finally `process_node` updates the open list so `find_path` with new or updated nodes. This allows `find_path` to continue the process with the next node in the subsequent iteration.
The following diagram illustrates the process:
<div align="center">
```mermaid
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"];
```
</div>
## Testing
Run the tests locally using pytest. For detailed instructions, see the `test` folder:
```bash
pytest test
```
## Contributing
We welcome contributions of all sizes and levels! For bug reports and feature requests, please use the [issue tracker](https://github.com/harisankar95/pathfinding3D/issues) to submit bug reports and feature requests. Please Follow the guidelines in [CONTRIBUTING.md](/CONTRIBUTING.md) for submitting merge requests.
## License
Pathfinding3D is distributed under the [MIT license](https://opensource.org/licenses/MIT).
## Authors / Contributers
Find a list of contributors [here](https://github.com/harisankar95/pathfinding3D/graphs/contributors).
Raw data
{
"_id": null,
"home_page": "https://github.com/harisankar95/pathfinding3D",
"name": "pathfinding3d",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.8",
"maintainer_email": null,
"keywords": "pathfinding, pathplanning, python, 3D, A*, Dijkstra, Theta*",
"author": "Harisankar Babu",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/98/c1/67dcddcc647f8cef6c9096e9d249f9e3255918046e25fbdd3e6aa4fc9053/pathfinding3d-0.7.2.tar.gz",
"platform": "any",
"description": "<div align=\"center\">\n\n# Pathfinding3D\n\n[](LICENSE)\n[](https://pypi.org/project/pathfinding3d/)\n[](https://github.com/harisankar95/pathfinding3D/actions/workflows/run-tests.yml)\n[](https://codecov.io/gh/harisankar95/pathfinding3D)\n[](https://github.com/psf/black)\n[](https://harisankar95.github.io/pathfinding3D/INTRO.html)\n\n<img src=\"https://raw.githubusercontent.com/harisankar95/pathfinding3D/main/assets/logo.png\" width=\"224\" title=\"Pathfinding3D logo\">\n\n</div>\n\nPathfinding algorithms in 3D for python3 born from the fork of [python-pathfinding](https://github.com/brean/python-pathfinding) by [@brean](https://github.com/brean).\n\nPathfinding3D is a comprehensive library designed for 3D pathfinding applications.\n\nCurrently there are 8 path-finders bundled in this library, namely:\n\n- A\\*: Versatile and most widely used algorithm.\n- Dijkstra: A\\* without heuristic.\n- Best-First\n- Bi-directional A\\*: Efficient for large graphs with a known goal.\n- Breadth First Search (BFS)\n- Iterative Deeping A\\* (IDA\\*): Memory efficient algorithm for large graphs.\n- Minimum Spanning Tree (MSP)\n- Theta\\*: Almost A\\* with path smoothing.\n\nDijkstra, A\\* and Bi-directional A\\* take the weight of the fields on the map into account.\nTheta\\* is a variant of A\\* but with any angle of movement allowed.\n\n## Installation\n\n### Requirements\n\n- python >= 3.8\n- numpy\n\nTo install Pathfinding3D, use pip:\n\n```bash\npip install pathfinding3d\n```\n\nFor more details, see [pathfinding3d on pypi](https://pypi.org/project/pathfinding3d/)\n\n## Usage examples\n\nFor a quick start, here's a basic example:\n\n ```python\n import numpy as np\n\n from pathfinding3d.core.diagonal_movement import DiagonalMovement\n from pathfinding3d.core.grid import Grid\n from pathfinding3d.finder.a_star import AStarFinder\n\n # Create a 3D numpy array with 0s as obstacles and 1s as walkable paths\n matrix = np.ones((10, 10, 10), dtype=np.int8)\n # mark the center of the grid as an obstacle\n matrix[5, 5, 5] = 0\n\n # Create a grid object from the numpy array\n grid = Grid(matrix=matrix)\n\n # Mark the start and end points\n start = grid.node(0, 0, 0)\n end = grid.node(9, 9, 9)\n\n # Create an instance of the A* finder with diagonal movement allowed\n finder = AStarFinder(diagonal_movement=DiagonalMovement.always)\n path, runs = finder.find_path(start, end, grid)\n\n # Path will be a list with all the waypoints as nodes\n # Convert it to a list of coordinate tuples\n path = [p.identifier for p in path]\n\n print(\"operations:\", runs, \"path length:\", len(path))\n print(\"path:\", path)\n ```\n\nFor usage examples with detailed descriptions take a look at the [examples](examples/) folder or at the [documentation](https://harisankar95.github.io/pathfinding3D/USAGE.html).\n\n## Visualization of the path\n\nYou can visualize the grid along with the path by calling the `visualize` method of the `Grid` class. This method can take path as an optional argument and generate a plotly figure. You can install pathfinding3d with the `plotly` to use this feature with the following command:\n\n ```bash\n pip install pathfinding3d[vis]\n ```\n\nThe path produced in the previous example can be visualized by adding the following code to the end of the example:\n\n ```python\n grid.visualize(\n path=path, # optionally visualize the path\n start=start,\n end=end,\n visualize_weight=True, # weights above 1 (default) will be visualized\n save_html=True, # save visualization to html file\n save_to=\"path_visualization.html\", # specify the path to save the html file\n always_show=True, # always show the visualization in the browser\n )\n ```\n\nThis will generate a visualization of the grid and the path and save it to the file `path_visualization.html` and also open it in your default browser.\n\n<p align=\"center\">\n<img src=\"https://raw.githubusercontent.com/harisankar95/pathfinding3D/main/assets/path_visualization.png\" width=\"95%\" title=\"Path visualization\">\n<p align=\"center\">\n\n## Rerun the Algorithm\n\nWhen rerunning the algorithm, remember to clean the grid first using `Grid.cleanup`. This will reset the grid to its original state.\n\n ```python\n grid.cleanup()\n ```\n\nPlease note that this operation can be time-consuming but is usally faster than creating a new grid object.\n\n## Implementation details\n\nAll pathfinding algorithms in this library inherit from the `Finder` class. This class provides common functionality that can be overridden by specific pathfinding algorithm implementations.\n\nGeneral Process:\n\n1. You call `find_path` on one of your finder implementations.\n2. `init_find` instantiates the `open_list` and resets all values and counters. The `open_list` is a priority queue that keeps track of nodes to be explored.\n3. The main loop starts on the `open_list` which contains all nodes to be processed next (e.g. all current neighbors that are walkable). You need to implement `check_neighbors` in your finder implementation to fill this list.\n4. 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.\n5. If the end node is not reached, `check_neighbors` calls `find_neighbors` to get all adjacent walkable nodes. For most algorithms, this calls `grid.neighbors`.\n6. If none of the neighbors are walkable, the algorithm terminates. Otherwise, `check_neighbors` calls `process_node` on each neighbor. It calculates the cost `f` for each neighbor node. This involves computing `g` (the cost from the start node to the current node) and `h` (the estimated cost from the current node to the end node, calculated by `apply_heuristic`).\n7. Finally `process_node` updates the open list so `find_path` with new or updated nodes. This allows `find_path` to continue the process with the next node in the subsequent iteration.\n\nThe following diagram illustrates the process:\n\n<div align=\"center\">\n\n```mermaid\n graph TD;\n style find_path stroke:#333,stroke-width:2px\n style init_find stroke:#333,stroke-width:2px\n style while_open_list_not_empty stroke:#333,stroke-width:2px\n style check_neighbors stroke:#333,stroke-width:2px\n style pop_node stroke:#333,stroke-width:2px\n style find_neighbors stroke:#333,stroke-width:2px\n style process_node stroke:#333,stroke-width:2px\n style return_empty_list stroke:#333,stroke-width:2px\n style return_path stroke:#333,stroke-width:2px\n\n find_path[\"find_path\"] --> init_find[\"init_find\\n(re)set global values\\nand open list\"];\n init_find --> while_open_list_not_empty[\"while open_list not empty\"];\n while_open_list_not_empty --> check_neighbors[\"check_neighbors\\n(for node with min 'f' value)\"];\n check_neighbors --> pop_node[\"pop_node\\n(node with min 'f' value)\"];\n pop_node --> find_neighbors[\"find_neighbors\\n(get neighbors)\"];\n find_neighbors --> process_node[\"process_node\\n(calculate new cost)\"];\n process_node --> while_open_list_not_empty;\n while_open_list_not_empty -- \"open list empty\" --> return_empty_list[\"return empty list\"];\n while_open_list_not_empty -- \"path found\" --> return_path[\"return path\"];\n```\n\n</div>\n\n## Testing\n\nRun the tests locally using pytest. For detailed instructions, see the `test` folder:\n\n```bash\npytest test\n```\n\n## Contributing\n\nWe welcome contributions of all sizes and levels! For bug reports and feature requests, please use the [issue tracker](https://github.com/harisankar95/pathfinding3D/issues) to submit bug reports and feature requests. Please Follow the guidelines in [CONTRIBUTING.md](/CONTRIBUTING.md) for submitting merge requests.\n\n## License\n\nPathfinding3D is distributed under the [MIT license](https://opensource.org/licenses/MIT).\n\n## Authors / Contributers\n\nFind a list of contributors [here](https://github.com/harisankar95/pathfinding3D/graphs/contributors).\n\n\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Pathfinding algorithms in 3D grids (based on python-pathfinding)",
"version": "0.7.2",
"project_urls": {
"Homepage": "https://github.com/harisankar95/pathfinding3D"
},
"split_keywords": [
"pathfinding",
" pathplanning",
" python",
" 3d",
" a*",
" dijkstra",
" theta*"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "f12c1972b527e0120ca32540ab389b82dabd787fd4221fcb991aee51473e9695",
"md5": "686fddb21192fa47b4f54e4238c4d618",
"sha256": "e7c9286a504607a12e89f5c43d6e973480a3ed81952e148f7934f0a9b3a0bbc9"
},
"downloads": -1,
"filename": "pathfinding3d-0.7.2-py3-none-any.whl",
"has_sig": false,
"md5_digest": "686fddb21192fa47b4f54e4238c4d618",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.8",
"size": 31470,
"upload_time": "2024-03-21T13:18:33",
"upload_time_iso_8601": "2024-03-21T13:18:33.251329Z",
"url": "https://files.pythonhosted.org/packages/f1/2c/1972b527e0120ca32540ab389b82dabd787fd4221fcb991aee51473e9695/pathfinding3d-0.7.2-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "98c167dcddcc647f8cef6c9096e9d249f9e3255918046e25fbdd3e6aa4fc9053",
"md5": "8d0e2cd206390ee2ab8903bb69eeca96",
"sha256": "5dfa91b2d248357f41d451f5167d2079901156c0bb8a1193d2cf630d7e8810e8"
},
"downloads": -1,
"filename": "pathfinding3d-0.7.2.tar.gz",
"has_sig": false,
"md5_digest": "8d0e2cd206390ee2ab8903bb69eeca96",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.8",
"size": 30039,
"upload_time": "2024-03-21T13:18:34",
"upload_time_iso_8601": "2024-03-21T13:18:34.562277Z",
"url": "https://files.pythonhosted.org/packages/98/c1/67dcddcc647f8cef6c9096e9d249f9e3255918046e25fbdd3e6aa4fc9053/pathfinding3d-0.7.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-03-21 13:18:34",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "harisankar95",
"github_project": "pathfinding3D",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "pathfinding3d"
}
JSON
