tbvanderwoude/grid_pathfinding

Pathfinding on grids using jumping point search and connected components.

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 behavior if no path exists. Both 4-neighborhood and 8-neighborhood grids are supported and a custom variant of JPS is implemented for the 4-neighborhood.

Example

Below a simple 8-grid example is given, illustrating 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);
 }
}

This assumes an 8-neighborhood, which is the default grid type. The same problem can be solved for a 4-neighborhood, disallowing diagonal moves, by adding the line

pathing_grid.allow_diagonal_move = false;

before component generation, which is done in example simple_4.

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

Benchmarks

The system can be benchmarked using scenarios from the Moving AI 2D pathfinding benchmarks. The grid_pathfinding_benchmark utility crate provides general support for loading these files. The default benchmark executed using cargo bench runs three scenario sets from the Dragon Age: Origins: dao/arena, dao/den312 and dao/arena2 (or dao/den009d when using the rectilinear algorithm). Running these requires the corresponding map and scenario files to be saved in folders called maps/dao and scenarios/dao.

A baseline can be set using

cargo bench -- --save-baseline main

New runs can be compared to this baseline using

cargo bench -- --baseline main

Performance

Using an i5-6600 quad-core running at 3.3 GHz, running the dao/arena2 set takes 134 ms using JPS allowing diagonals and with improved pruning disabled. Using default neighbor generation as in normal A* (enabled by setting GRAPH_PRUNING = false) makes this take 1.37 s, a factor 10 difference. As a rule, the relative difference increases as maps get larger, with the dao/arena set (a smaller map) taking 846 us and 1.34 ms respectively with and without pruning.

An existing C++ JPS implementation runs the same scenarios in about 60 ms. The fastest known solver is the l1-path-finder (implemented in Javascript) which can do this in only 38 ms using A* with landmarks (for a 4-neighborhood). This indicates that there is still a lot of room for improvement in terms of search speed.

Goal of crate

The long-term goal of this crate is to provide a fast off-the-shelf pathfinding implementation for grids.