Seastar

seastar is a dependency-free implementation of the A* pathfinding algorithm. It is specifically designed to operate over uniform-cost, 2D grids in cardinal directions.

You can check out the library in action at seastar.sombia.com.

Usage

cargo add seastar

use seastar::{astar, Point, Grid};

let grid = Grid::new(3, 3);

let start = Point::new(0, 0); // top left corner
let end = Point::new(2, 2); // bottom right corner

// Assuming a path is found, `path` will be a `Vec<Point>` where each point is
// a step in the path from `start` to `end`.
if let Some(path) = astar(&grid, start, end) {
    // ...do whatever you want with the path!
}

Examples

If you have cloned the seastar repository, you can run an example with the command cargo run --release --example <example_name>.

Feature Flags

Benchmarks

You can run benchmarks with the command cargo bench.

As usual, take into account that benchmarks will vary wildly depending on the grid size, the distance between the start and end points, and the distribution of walls. Don't take these as perfect indicators of performance given a specific grid size.

Grids are built with a 20% density of obstacles, with randomized start and end points. This results in fairly chaotic grids, which may challenge the algorithms performance.

Unstable Grids (30s, 50 samples)

Uses random seeds to give a better indicator of average execution time.

Stable Grids (3s, 50 samples)

Uses fixed seeds to ensure consistent results for cross-run comparisons.

Note: Benchmarks run on Intel i9-9900K (16) @ 5.000GHz.

Comparison Notes

cargo bench -- --save-baseline before

cargo bench -- --load-baseline after

critcmp before after

Requires critcmp to be installed.

Motivation

The full-featured pathfinding crate exists, and should probably be your first choice if you need a pathfinding implementation. However, I wanted to implement the A* algorithm to actually understand how it works, and I desired a simpler API for my game design needs.

License

Seastar is dual-licensed under either

• MIT License
• Apache License, Version 2.0

at your option.