grid_pathfinding

A grid-based pathfinding system. Implements Jump Point Search with improved pruning rules for speedy pathfinding. Pre-computes connected components to avoid flood-filling behaviour if no path exists.

Example

Below a simple example is given which illustrates how to set a basic problem and find a path.

use grid_pathfinding::PathingGrid;
use grid_util::grid::Grid;
use grid_util::point::Point;

// In this example a path is found on a 3x3 grid with shape
//  ___
// |S  |
// | # |
// |  E|
//  ___
// where
// - # marks an obstacle
// - S marks the start
// - E marks the end

fn main() {
    let mut pathing_grid: PathingGrid = PathingGrid::new(3, 3, false);
    pathing_grid.set(1, 1, true);
    pathing_grid.generate_components();
    println!("{}", pathing_grid);
    let start = Point::new(0, 0);
    let end = Point::new(2, 2);
    let path = pathing_grid
        .get_path_single_goal(start, end, false)
        .unwrap();
    println!("Path:");
    for p in path {
        println!("{:?}", p);
    }
}

See examples for finding paths with multiple goals and generating waypoints instead of full paths.

Goal of crate

The long-term goal of this crate is to provide a fast pathfinding implementation for grids as well as support for features like multi-tile pathfinding and multi-agent pathfinding.