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.

Status

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

Usage

Add this to your Cargo.toml:

[dependencies]
shortestpath = "0.10"

Optional Features

Enable optional features for additional input sources:

[dependencies]
shortestpath = { version = "0.10", 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:

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);

// Query distance from any position
let start = mesh.xy_to_index(0, 0)?;
let distance = gradient.get_distance(start);
println!("Distance from start to goal: {:.2}", distance);

// Follow the gradient from start
let path = gradient.follow(&mesh, start, false);
if !path.is_empty() {
    println!("Path found with {} steps", path.len());
    for (i, gate) in path.iter().enumerate() {
        println!("  Step {}: move to node {}", i + 1, gate.target);
    }
}

// Or use find() to do everything in one call (resets and computes gradient)
let mut gradient2 = Gradient::from_mesh(&mesh);
if let Some(path) = gradient2.find(&mesh, start, target, false) {
    println!("Path found with {} steps", path.len());
}

// Or get just the best next move from any position
if let Some(best_move) = gradient.best(&mesh, start, false) {
    println!("Best move from start: to node {}", best_move.target);
}
# Ok::<(), shortestpath::Error>(())

Pathfinding Methods

The library provides two main approaches for pathfinding:

Complete Pathfinding (find)

• find(mesh, start, target, backward): All-in-one method that resets the gradient, sets the target, spreads the distances, and returns the complete path. This modifies the gradient but is the simplest way to find a path. Returns Option<Vec<Gate>>.

Manual Gradient Control (follow)

For more control or when reusing gradients:

1. reset(): Resets all distances to DISTANCE_MAX
2. set_distance(target, 0.0): Sets the target distance to 0
3. spread(mesh): Computes the gradient across the mesh
4. follow(mesh, start, backward): Follows the pre-computed gradient from start, moving to better positions until no improvement is available. Does not check if a target was reached. Returns Vec<Gate> (may be empty if no moves improve the position).

Single-Step Methods

After spreading the gradient, you can also query individual moves:

• best(mesh, node, backward): Returns Option<Gate> with the best next move from a given node. Returns None if all neighbors are farther from the target.

• worst(mesh, node, backward): Returns Option<Gate> with the worst next move (highest distance to target). Useful for debugging or exploring suboptimal paths.

• moves(mesh, node, backward): Returns a sorted Vec<Gate> of all possible moves from a node, ordered by distance to target.

All methods support the backward parameter for deterministic tie-breaking. In follow() and find(), this parameter alternates automatically at each step for path stability.

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.)
• Zone filtering: unique() method to keep only the connected zone reachable from the origin
• 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:

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

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.