Crate seastar

Seastar

---

Features

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

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.

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

• MIT License
• Apache License, Version 2.0

at your option.

Modules

• node

Structs

• Point
  Represents an (x, y) coordinate in a grid.

Functions

• astar
  Attempts to find the shorest path from start to end using the A* algorithm. Returns None if no path is found.
• get_neighbors
  Returns all of the non-colliding neighbors of the given node. Neighbors are defined as colliding if they are Some, and empty if they are None.

Type Definitions

• Grid
  Alias for a 2D vector of Option<()>’s.