Skip to content

Latest commit

 

History

History
147 lines (101 loc) · 4.42 KB

README.md

File metadata and controls

147 lines (101 loc) · 4.42 KB
Raw

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.

terminal screenshot showing off paths from start to end

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>.

Example File Description
random_30 random_30.rs Generate a 30x30 map with random walls and a random start and end point.
random_100 random_100.rs Generate a 100x100 map with random walls and a random start and end point.

Feature Flags

Flag Default Description Dependencies
serde Disabled Adds Serialize, Deserialize derives for Point. serde

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.

Grid Size Time
30x30 4.56 µs
100x100 30.38 µs
500x500 661.94 µs
1000x1000 3.01 ms

Stable Grids (3s, 50 samples)

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

Seed: 2210748027404127321Seed: 8658502531503517188Seed: 4514647571430385868
Grid Size Time
30x30 7.15 µs
100x100 8.08 µs
500x500 64.88 µs
1000x1000 11.71 ms
Grid Size Time
30x30 1.18 µs
100x100 40.23 µs
500x500 1.60 ms
1000x1000 932.75 µs
Grid Size Time
30x30 480.84 ns
100x100 1.21 µs
500x500 16.36 µs
1000x1000 219.31 µs

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

at your option.