## grid_pathfinding

Pathfinding using JPS and connected components on a grid

### 5 releases

 new 0.2.1 Aug 7, 2024 Jul 30, 2024 Apr 11, 2024 Aug 15, 2022 Aug 15, 2022

#243 in Algorithms

43KB
772 lines

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

~5.5MB
~95K SLoC