seastar is a dependency-free, non-generic implementation of the A*
pathfinding algorithm. It
is specifically designed to operate over a 2D grid of tiles in cardinal
directions (North, East, South, West).
I can't necessarily recommend using this over the pathfinding crate, but I wanted a different API for my own use-case, as well as a deeper understanding of the algorithm.
sh
cargo add seastar
```rust
fn main() {
// A grid needs to be a 2D vector of Options. None represents an
// empty tile, while Some(()) represents a blocked tile.
let grid = vec![
vec![None, None, Some(())],
vec![Some(()), None, None],
vec![None, None, None],
]
let start = Point { x: 0, y: 0 }; // top left corner
let end = Point { x: 2, y: 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!
}
}
```
If you have cloned the seastar repository, you can run an example with the
command cargo run --example <example_name>.
| Example | File | Description |
|---------|-----------------------------------------|--------------------------------------------------------------------------|
| random30 | random30.rs | Generate a 30x30 map with random walls and find the path from top left to bottom right. |
| random100 | random100.rs | Generate a 100x100 map with random walls and find the path from top left to bottom right. |
| random256 | random256.rs | Generate a 256x256 map with random walls and find the path from top left to bottom. |
You can run benchmarks with the command cargo bench.
NOTE: A word of caution about benchmarks here: because the maps are randomly generated in the bench tests, the results will vary greatly from run to run. Maps without valid paths are often outliers that can skew the results heavily, especially on larger grids.
Seastar is dual-licensed under either
at your option.