shortestpath 0.3.0

Shortest Path is an experimental library finding the shortest path from A to B.
Documentation

Shortest Path

Shortest Path is an experimental library finding the shortest path from A to B, implemented in Rust.

It aims primarily at powering Liquid War 7 but could be of wider use. Who knows.

Shortest Path icon

Status

For now this is a toy project, clearly NOT suitable for production use.

Build Status

Usage

Add this to your Cargo.toml:

[dependencies]
shortestpath = "0.3"

Optional Features

Enable optional features for additional input sources:

[dependencies]
shortestpath = { version = "0.3", features = ["image-reader"] }

Available features:

  • image-reader: Load 2D/3D volumes from images (PNG, JPEG)

Quick Example

Here's a simple 2D pathfinding example with walls:

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-reader feature)
    • Extensible via Source2D and Source3D traits for custom sources

Creating Meshes from Text

You can create meshes directly from ASCII art maps:

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-reader feature, you can load meshes directly from images (dark pixels become walls, light pixels become walkable):

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():

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.

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.

This implementation tries to make it independant from the Liquid War game 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 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 license.