Metadata-Version: 2.1
Name: nano-astar
Version: 0.1.2
Summary: Tiny, fast A* pathfinding on occupancy grids: C++ core, bucket queue for integer costs, nanobind bindings, GIL-free.
Keywords: a-star,astar,pathfinding,grid,occupancy-grid,robotics
Author: nano-astar authors
License: MIT
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: C++
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Software Development :: Libraries
Project-URL: Homepage, https://github.com/ygxiuming/nano-astar
Project-URL: Repository, https://github.com/ygxiuming/nano-astar
Requires-Python: >=3.9
Requires-Dist: numpy>=1.22
Provides-Extra: dev
Requires-Dist: pytest>=7; extra == "dev"
Requires-Dist: pytest-benchmark>=4; extra == "dev"
Requires-Dist: matplotlib>=3.7; extra == "dev"
Requires-Dist: pillow>=9; extra == "dev"
Requires-Dist: networkx>=3.0; extra == "dev"
Requires-Dist: build>=1; extra == "dev"
Requires-Dist: twine>=4; extra == "dev"
Description-Content-Type: text/markdown

# nano-astar

English | [中文](README.zh.md)

[![CI](https://github.com/ygxiuming/nano-astar/actions/workflows/ci.yml/badge.svg)](https://github.com/ygxiuming/nano-astar/actions/workflows/ci.yml)
[![PyPI](https://img.shields.io/pypi/v/nano-astar.svg)](https://pypi.org/project/nano-astar/)
[![Python](https://img.shields.io/badge/python-3.9%20–%203.12-blue.svg)](https://www.python.org)

**A* pathfinding on occupancy grids with a C++ core — measured 14–18× faster than networkx search alone, 52–63× faster including graph construction, and up to 464× on 4-connected integer grids** (exact numbers, environment and reproduction script in [BENCH.md](BENCH.md)).

![A* exploring a maze](https://raw.githubusercontent.com/ygxiuming/nano-astar/main/docs/demo.gif)

## Why nano-astar

- **Fast where it matters.** The search core is C++17 with cache-friendly flat arrays: one byte per cell for the closed bitmap, intrusive per-node links — no hash maps, no per-node allocation.
- **Two open lists, chosen automatically.** 4-connected integer grids run on a **bucket queue** with O(1) amortized push/pop and true decrease-key; float costs (8-connected `sqrt(2)` diagonals) fall back to a **4-ary heap**. Measured on identical integer workloads the bucket queue is **1.3–2.4× faster** than the heap ([BENCH.md](BENCH.md)).
- **Real multithreading.** The GIL is released for the entire search (`nb::call_guard<nb::gil_scoped_release>`), so threads truly run in parallel — measured **2.9× on 4 threads** ([test_gil_released_under_threads](tests/test_api.py)).
- **Zero-copy numpy in, numpy out.** A contiguous `uint8` grid is passed to C++ without copying; the path comes back as an `(n, 2)` `int32` array.
- **One dependency.** Runtime: `numpy` only. Bindings via [nanobind](https://github.com/wjakob/nanobind), build via scikit-build-core.
- **Differentially tested against a reference implementation.** 200 randomized grids are checked against networkx A* — reachability and optimal cost must match exactly (integer) or within 1e-6 (float) ([tests/test_correctness.py](tests/test_correctness.py)).

## Install & 30-second quickstart

```bash
pip install nano-astar
```

From a source checkout: `pip install .`

```python
import numpy as np
from nano_astar import astar

grid = np.zeros((100, 100), dtype=np.uint8)
grid[20:80, 50] = 1                       # a wall

result = astar(grid, (0, 0), (99, 99), heuristic="octile", diagonal=True)
if result is None:
    print("unreachable")
else:
    path, cost = result                   # path: (n, 2) int32 (row, col)
    print(f"{len(path)} cells, cost {cost:.3f}")

# exploration history for animations:
path, cost, history = astar(grid, (0, 0), (99, 99), return_history=True)
```

Terminal demo: `python examples/demo.py`

## Benchmarks

Random grids with 30% obstacles, medians after warmup, costs cross-checked
against networkx on every run (identical within 1e-6). Full methodology —
repetition counts, seeds, fairness notes — and the reproduction script:
[BENCH.md](BENCH.md). Environment: Python 3.11.15, networkx 3.6.1,
numpy 2.4.6, MSVC 19.51 (`/O2`), Windows 11.

8-connected grids, octile heuristic on both sides:

| grid | nano-astar | networkx (search only) | networkx (build + search) | speedup (search) | speedup (incl. build) |
|---|---|---|---|---|---|
| 100×100 | 0.66 ms | 9.3 ms | 40.2 ms | 14× | 61× |
| 500×500 | 24.4 ms | 360.0 ms | 1273.4 ms | 15× | 52× |
| 1000×1000 | 115.9 ms | 2030.3 ms | 7304.9 ms | 18× | 63× |

4-connected integer grids, manhattan heuristic on both sides — the bucket
queue's home turf:

| grid | nano-astar | networkx (search only) | networkx (build + search) | speedup (search) | speedup (incl. build) |
|---|---|---|---|---|---|
| 100×100 | 0.07 ms | 3.1 ms | 289.2 ms | 43× | 4037× |
| 500×500 | 4.02 ms | 109.3 ms | 718.4 ms | 27× | 179× |
| 1000×1000 | 7.65 ms | 124.3 ms | 3546.6 ms | 16× | 464× |

![benchmark chart](https://raw.githubusercontent.com/ygxiuming/nano-astar/main/docs/benchmark.png)

Reproduce:

```bash
python tests/bench_vs_networkx.py   # rewrites BENCH.md + docs/bench_results.json
python tools/make_plots.py          # regenerates the charts
```

## Heuristics, visualized

Same map, four built-in heuristics (4-connected). Blue = cells explored,
red = final path. A tighter heuristic explores less — all four still return
the same optimal cost.

![heuristic comparison](https://raw.githubusercontent.com/ygxiuming/nano-astar/main/docs/heuristics.png)

## When NOT to use nano-astar

- **General graphs.** Nodes with attributes, edge weights, or non-grid
  topology are out of scope — the input is a binary occupancy grid, period.
  Use networkx, rustworkx, or a graph library.
- **Custom Python heuristics.** There is no callback interface: the four
  built-in heuristics run inline in C++, which is exactly where the speed
  comes from. If you need a domain-specific heuristic, fork and add it in
  `src/cpp/heuristics.hpp`.
- **Weighted terrain.** All free cells cost the same (1 orthogonally,
  `sqrt(2)` diagonally). Costmaps with per-cell traversal costs need a
  different engine.
- **When the bucket queue won't help you.** The bucket queue only engages
  for 4-connected integer-cost grids (`diagonal=False`). With
  `diagonal=True`, costs are irrational multiples of `sqrt(2)` and the
  engine uses the 4-ary heap instead — by design, not by accident. On
  integer grids the bucket queue is 1.3–2.4× faster than the heap
  (measured, [BENCH.md](BENCH.md)); if your workload is 8-connected, that
  is the number you give up.
- **`manhattan` with `diagonal=True`.** Manhattan overestimates on
  8-connected grids and would return suboptimal paths, so nano-astar emits
  a `RuntimeWarning`. Use `octile` (the default) there.

## API

```python
astar(grid, start, goal, heuristic="octile", diagonal=True,
      return_history=False) -> (path, cost) | (path, cost, history) | None
```

| parameter | meaning |
|---|---|
| `grid` | 2-D array-like; `0` = free, nonzero = obstacle. Contiguous `uint8` is zero-copy; other dtypes are converted once via `grid != 0`. |
| `start`, `goal` | `(row, col)` cell indices. |
| `heuristic` | `"octile"` (default, tightest for 8-conn), `"manhattan"` (tightest for 4-conn), `"euclidean"`, `"diagonal"`. All inline C++, no Python callback. |
| `diagonal` | `True`: 8-connected, diagonal steps cost `sqrt(2)`, no corner cutting. `False`: 4-connected unit costs → integer bucket-queue engine. |
| `return_history` | Also return the closed cells in pop order as `(m, 2)` int32 — what the GIF above is made of. |

- **Returns** `None` when no path exists (never raises for that).
- **Raises `ValueError`** for out-of-bounds or on-obstacle `start`/`goal`,
  non-2-D grids, and unknown heuristic names.
- Path cost is exact: integer grids return integer-valued floats, 8-connected
  grids return exact sums of `1`/`sqrt(2)` terms.
- Thread-safe and GIL-free: no Python objects are touched while the GIL is
  released, and concurrent calls from multiple threads run truly in parallel.

## Development

```bash
uv venv --python 3.11 .venv
uv pip install --python .venv -e ".[dev]"
pytest tests/                          # 220 tests, differential vs networkx
python tests/bench_vs_networkx.py      # regenerate BENCH.md
python tools/make_gif.py               # regenerate docs/demo.gif
```

Layout:

```
src/cpp/astar.cpp         engine + nanobind bindings
src/cpp/bucket_queue.hpp  ring bucket queue (integer costs, O(1) decrease-key)
src/cpp/heap4.hpp         4-ary heap (float/general costs)
src/cpp/heuristics.hpp    octile / manhattan / euclidean / diagonal, inline
src/python/nano_astar/    Python wrapper (validation, dtype normalization)
tests/                    differential tests, API tests, benchmark
tools/                    smoke test (pure C++), GIF/chart generators
```

## License

MIT
