seastar
| Crates.io | seastar |
| lib.rs | seastar |
| version | |
| source | src |
| created_at | 2023-03-23 04:57:05.564501 |
| updated_at | 2024-11-02 17:12:45.193678 |
| description | Dependency-free implementation of the A* pathfinding algorithm for uniform-cost, 2D grids in cardinal directions. |
| homepage | |
| repository | https://github.com/robertwayne/seastar |
| max_upload_size | |
| id | 817835 |
| Cargo.toml error: | TOML parse error at line 18, column 1 | 18 | autolib = false | ^^^^^^^ unknown field `autolib`, expected one of `name`, `version`, `edition`, `authors`, `description`, `readme`, `license`, `repository`, `homepage`, `documentation`, `build`, `resolver`, `links`, `default-run`, `default_dash_run`, `rust-version`, `rust_dash_version`, `rust_version`, `license-file`, `license_dash_file`, `license_file`, `licenseFile`, `license_capital_file`, `forced-target`, `forced_dash_target`, `autobins`, `autotests`, `autoexamples`, `autobenches`, `publish`, `metadata`, `keywords`, `categories`, `exclude`, `include` |
| size | 0 |
Rob (robertwayne)
documentation
README
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 | ||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
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.