Skip to content

A* pathfinding algorithm implementation for uniform-cost grids.

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT
Notifications You must be signed in to change notification settings

robertwayne/seastar

Repository files navigation

Seastar


terminal screenshot showing off paths from start to end

seastar is a dependency-free, non-generic implementation of the A* pathfinding algorithm. It is specifically designed to operate over unform-cost, 2D grids.

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

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.

Usage

cargo add seastar
use seastar::{astar, Point};

fn main() {
    // A grid needs to be a 2D vector of `Option`s. `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!
    }
}

Examples

If you have cloned the seastar repository, you can run an example with the command cargo run --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.

Features

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

Benchmarks

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.

License

Seastar is dual-licensed under either

at your option.

About

A* pathfinding algorithm implementation for uniform-cost grids.

Topics

Resources

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT

Stars

Watchers

Forks

Languages