# Shortest Path
[Shortest Path](https://gitlab.com/ufoot/shortestpath) is an experimental library finding
the shortest path from A to B, implemented in [Rust](https://www.rust-lang.org/).
It aims primarily at powering [Liquid War 7](https://gitlab.com/ufoot/liquidwar7)
but could be of wider use. Who knows.
# Status
For now this is a toy project, clearly *NOT* suitable for production use.
[](https://gitlab.com/ufoot/shortestpath/pipelines)
# Usage
Add this to your `Cargo.toml`:
```toml
[dependencies]
shortestpath = "0.4"
```
### Optional Features
Enable optional features for additional input sources:
```toml
[dependencies]
shortestpath = { version = "0.4", features = ["image"] }
```
Available features:
- `image`: Load 2D/3D volumes from images (PNG, JPEG)
- `serde`: Enable serialization/deserialization support for all types
## Quick Example
Here's a simple 2D pathfinding example with walls:
```rust
use shortestpath::{Mesh, Gradient, mesh_2d::{Compact2D, Index2D}};
// Create a 5x5 grid with walls (#) and walkable cells (.)
let map = "\
.....
.###.
.#...
...#.
.....";
let mesh = Compact2D::from_text(map)?;
// Create a gradient and set the target (bottom-right corner)
let mut gradient = Gradient::from_mesh(&mesh);
let target = mesh.xy_to_index(4, 4)?;
gradient.set_distance(target, 0.0);
gradient.spread(&mesh);
// Find the path from top-left corner
let start = mesh.xy_to_index(0, 0)?;
let distance = gradient.get_distance(start);
println!("Distance from start to goal: {:.2}", distance);
// Get the next step from any position
let next = gradient.get_best_successor(&mesh, start);
println!("First step from (0,0): {:?}", next);
# Ok::<(), shortestpath::Error>(())
```
## Features
The library supports:
- **2D grids** (`mesh_2d`): Classic grid-based pathfinding with 8-way movement
- **2.5D layers** (`mesh_25d`): Stacked 2D grids with vertical movement between layers (10 neighbors: 8 in-layer + 2 vertical)
- **True 3D volumes** (`mesh_3d`): Full 26-neighbor volumetric pathfinding with diagonal transitions
- **Dynamic topology** (`mesh_topo`): Conditional connectivity (doors, one-way passages, etc.)
- **Flexible input sources** (`mesh_source`):
- Parse maps from ASCII text (`.` = walkable, `#` = wall)
- Load 2D/3D volumes from images (optional `image` feature)
- Extensible via `Source2D` and `Source3D` traits for custom sources
### Creating Meshes from Text
You can create meshes directly from ASCII art maps:
```rust
use shortestpath::mesh_2d::Compact2D;
use shortestpath::mesh_3d::Compact3D;
// 2D from text (. = walkable, # = wall)
let mesh_2d = Compact2D::from_text("...\n.#.\n...")?;
// 3D from text (layers separated by ---)
let map_3d = "\
...
.#.
...
---
...
...
...";
let mesh_3d = Compact3D::from_text(map_3d)?;
# Ok::<(), shortestpath::Error>(())
```
### Creating Meshes from Images
With the optional `image` feature, you can load meshes directly from images (dark pixels become walls, light pixels become walkable):
```rust
use shortestpath::mesh_2d::Compact2D;
use shortestpath::mesh_3d::Compact3D;
// 2D from image file (uses default 0.5 brightness threshold)
let mesh_2d = Compact2D::from_path("map.png")?;
// 2D with custom brightness threshold (0.0-1.0)
let mesh_2d = Compact2D::from_path_with_threshold("map.png", 0.3)?;
// 3D from stack of images (each image = one z-layer)
let paths = vec!["layer0.png", "layer1.png", "layer2.png"];
let mesh_3d = Compact3D::from_paths(&paths)?; // Uses default 0.5 threshold
// 3D with custom threshold
let mesh_3d = Compact3D::from_paths_with_threshold(&paths, 0.7)?;
// You can also use pre-loaded images
use image::DynamicImage;
let img = image::open("map.png")?;
let mesh_2d = Compact2D::from_image(&img)?;
# Ok::<(), Box<dyn std::error::Error>>(())
```
### Extensibility
For custom input sources, you can implement the `Source2D` or `Source3D` traits from the `mesh_source` module and use them with `from_source()`:
```rust
use shortestpath::mesh_source::{Source2DFromText, Source3DFromText};
use shortestpath::mesh_2d::Compact2D;
// The mesh_source module provides low-level sources
let source = Source2DFromText::from_text("...\n.#.\n...");
let mesh = Compact2D::from_source(&source)?;
// Or use the FromStr trait for parsing
let mesh: Compact2D = "...\n.#.\n...".parse()?;
# Ok::<(), shortestpath::Error>(())
```
## Performance
The library is optimized for many-to-one pathfinding scenarios where multiple agents need to find paths to a common target. Performance scales based on mesh dimensionality and neighbor count:
- **2D meshes** (8 neighbors) provide the fastest pathfinding
- **2.5D meshes** (10 neighbors: 8 in-layer + 2 vertical) offer a middle ground for layered environments
- **3D meshes** (26 neighbors with full diagonal connectivity) handle true volumetric pathfinding
The `Compact` mesh variants pre-compute neighbor relationships and support walls, making them more memory-efficient for sparse environments. The `Full` variants compute successors on-the-fly and work best for fully-connected grids.
Below is the result of a bench executed on a standard CI runner:
```
running 6 tests
test tests::bench_compact_25d_160x90x3 ... bench: 2,680,485.75 ns/iter (+/- 901,204.19)
test tests::bench_compact_2d_160x90 ... bench: 676,991.05 ns/iter (+/- 22,940.60)
test tests::bench_compact_3d_160x90x3 ... bench: 4,960,161.85 ns/iter (+/- 1,297,727.76)
test tests::bench_full_25d_160x90x3 ... bench: 4,823,626.70 ns/iter (+/- 151,326.60)
test tests::bench_full_2d_160x90 ... bench: 750,262.20 ns/iter (+/- 9,177.50)
test tests::bench_full_3d_160x90x3 ... bench: 5,390,642.50 ns/iter (+/- 145,018.10)
test result: ok. 0 passed; 0 failed; 0 ignored; 6 measured; 0 filtered out; finished in 14.22s
```
# History
Technically, this is a variant of [Dijkstra's Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm).
A famous, classical algorithm which we re-discovered (as in, re-invent the wheel) with my friend Thomas Colcombet back in 1995.
Back in those days we did not have access to Internet and never stumbled on that great work by Dijkstra but
somehow managed to use its main idea. First code snippets in [Liquid War 3](https://gitlab.com/ufoot/liquidwar3).
This implementation tries to make it independant from the [Liquid War game](https://ufoot.org/liquidwar/) and
offer a multi-purpose version. It still aims at speed execution rather than exactness, in the context of
many agents trying to find the shortest point to a single target.
# Similar packages
The [pathfinding](https://crates.io/crates/pathfinding) crate has a multi-purpose,
very likely stricter version of this, along with many other path finding algorithms.
It has been a great source of inspiration.
# License
Shortest Path is licensed under the [MIT](https://gitlab.com/ufoot/shortestpath/blob/main/LICENSE) license.
