Crate seastar

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

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: 2210748027404127321	Seed: 8658502531503517188	Seed: 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

• MIT License
• Apache License, Version 2.0

at your option.

Structs

Grid

Represents a 2D grid that is backed by a 1D vector.

Node

Represents a node in the Grid to be checked. Nodes know their position, and have a g and h cost, which are used to calculate the f-cost. Additionally, each node has a parent index, which is used to reconstruct the path once the end node is found.

Point

Represents an (x, y) coordinate on a Grid.

Functions

astar

Attempts to find the shortest path from start to end using the A* algorithm. Returns None if no path is found.