Metadata-Version: 2.4
Name: cstar-pathfinding
Version: 0.1.0
Summary: Fast search algorithms for grid-based pathfinding
Author: Tim Schönbrod
License-Expression: CC-BY-4.0
Project-URL: Repository, https://github.com/FraunhoferIVI/cstar
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=2.0.2
Provides-Extra: dev
Requires-Dist: exceptiongroup; extra == "dev"
Requires-Dist: ImageIO; extra == "dev"
Requires-Dist: iniconfig; extra == "dev"
Requires-Dist: packaging; extra == "dev"
Requires-Dist: pathfinding; extra == "dev"
Requires-Dist: pillow; extra == "dev"
Requires-Dist: pluggy; extra == "dev"
Requires-Dist: pyastar2d; extra == "dev"
Requires-Dist: pybind11; extra == "dev"
Requires-Dist: Pygments; extra == "dev"
Requires-Dist: pytest; extra == "dev"
Requires-Dist: tomli; extra == "dev"
Requires-Dist: typing_extensions; extra == "dev"
Requires-Dist: cibuildwheel; extra == "dev"
Dynamic: license-file

# cstar – A Fast C++ Pathfinding Wrapper for Python

`cstar` provides a simple Python interface to high-performance C++ implementations of A*, WA*, Focal Search, and MHA*. It supports fast 2D/3D grid pathfinding with diagonal movement.

---

## Features

- Core A*, WA*, Focal Search, and MHA* implementations in C++ for speed  
- Clean Python API with 2D and 3D wrappers  
- Supports 8-direction (2D) and 26-direction (3D) movement
- Works with 2D and 3D NumPy arrays  
- Benchmark script included in `/benchmarks`

---

## Installation

**Basic:**
```bash
uv sync
```

**Dev:**
```bash
uv sync --extra dev
```

## Usage

```python
import numpy as np
from cstar.pathfinding import (
	run_astar_2D,
	run_wastar_2D,
	run_astar_3D,
	run_wastar_3D,
	run_mhastar_2D,
	run_mhastar_3D,
)

grid = np.ones((10, 10), dtype=bool)
path, cost, expansions, expanded = run_astar_2D(grid, 0, 0, 9, 9)

h2d = np.zeros((10, 10), dtype=float)
path_h, cost_h, expansions_h, expanded_h = run_wastar_2D(
	grid, 0, 0, 9, 9, w=1.2
)

path_mha, cost_mha, expansions_mha, expanded_mha = run_mhastar_2D(
	grid, h2d, 0, 0, 9, 9, w1=1.0, w2=1.0
)

print(path)
print(cost)
print(expansions)
print(expanded)

grid3d = np.ones((10, 10, 5), dtype=bool)
path3d, cost3d, expansions3d, expanded3d = run_astar_3D(grid3d, 0, 0, 0, 9, 9, 4)

h3d = np.zeros((10, 10, 5), dtype=float)
path3d_h, cost3d_h, expansions3d_h, expanded3d_h = run_astar_3D_heuristic_grid(
	grid3d, 0, 0, 0, 9, 9, 4, heuristic_grid=h3d, w=1.2
)

path3d_mha, cost3d_mha, expansions3d_mha, expanded3d_mha = run_mhastar_3D(
	grid3d, h3d, 0, 0, 0, 9, 9, 4, w1=1.0, w2=1.0
)
```

## API: pathfinding wrappers

Parameters

- 2D wrappers:
	- `run_astar_2D`
	- `run_wastar_2D`
	- `run_focal_search_2D`
	- `run_mhastar_2D`
- 3D wrappers:
	- `run_astar_3D`
	- `run_wastar_3D`
	- `run_focal_search_3D`
	- `run_mhastar_3D`

Common parameters

- grid: 2D/3D boolean NumPy array with True = walkable, False = obstacle (autoconverted to bool if necessary and possible)
- x_start, y_start (, z_start): start coordinates
- x_target, y_target (, z_target): target coordinates

Returns

- path: NumPy array [N, 2] or [N, 3] of path waypoints
- cost: float total path cost
- expansions: int number of nodes expanded during the search
- expanded: boolean grid matching input shape with expanded nodes marked True

## Edge behavior:

- The default assumes non uniform step costs (octile distance based), 2D functions have an optional parameter for uniform step costs
- The model can always move diagonal if the diagonal cell is free, even if all other neighboring cells of the current node and diagonal node are blocked. This is mostly standard, can however be undesired for some real world applications. 

## Benchmarks

A benchmark script is available in the /benchmarks directory, showing performance comparisons with the python based pathfinding2D library and the C++ based pyastar library.
