Explore.rs

This package is a collection of various algorithms and utilities for pathing and planning.

Astar

The explorers::astar module provides an implementation of the A* pathfinding algorithm.

use explorers::astar::{astar, EdgeToNodeWithCost};

#[derive(Debug, Clone, Copy)]
enum Edges {
    AddOne,
    SubtractOne,
    SubtractTwo,
    AddTwo,
}

// Set up the search using the builder pattern
let result = astar()
    // We provide a function to check if we've reached the goal
    .is_goal(|n: &i32, goal: &i32| n == goal)
    // We define the traversibility of the graph
    .get_neighbors(|i: &i32| {
        vec![
            EdgeToNodeWithCost::new(Edges::AddOne, i + 1, 1),
            EdgeToNodeWithCost::new(Edges::SubtractOne, i - 1, 1),
            EdgeToNodeWithCost::new(Edges::SubtractTwo, i - 2, 1),
            EdgeToNodeWithCost::new(Edges::AddTwo, i + 2, 1),
        ]
    })
    // Provide the distance heuristic to guide the search
    .heuristic(|i: &i32, g: &i32| (g - i).abs())
    // Limit the search depth to prevent infinite searching
    .max_nodes_searched(1_000_000)
    .plan_path(&0i32, &10i32);
// Check we found a path
assert!(result.is_ok_and(|r| r.path[r.path.len() - 1].1 == goal));

Benchmarking

I've not set up a robust benchmarking process - instead using a combination of the hyperfine CLI and examples. For example:

hyperfine 'cargo run --release --example astar_benchmark'

Ensuring that you have already built the package with the release flag. Improvements will eventually come, if needed!

Planning

Goal-Oriented Action Planning

We can leverage the above a-star implementation as the backbone for action planning. This is implemented in the explorers::goap module.

Note that the implementation is highly flexible (read, it's just a skin on A-star), and therefore it is up to you to adopt good practises. We suggest reading the Nyx planner paper alongside other documentation (such as pyperplan).

To view an example of action planning using this library, see the simple_goap example.

To view an example of incorporating time in action planning, see the goap_time example.

Monte-Carlo Tree Search

We've also provided a very basic implementation of Monte-Carlo Tree Search (MCTS) in the explorers::mcts module. An example of using MCTS to play Tic-Tac-Toe can be found in the mcts_tic_tac_toe example.

Pathfinding

Beyond the A-star implementation, we also provide simple implementations of RRT and RRT-star inside the explorers::pathing module, and adopt the excellent h3o crate as a navmesh to enable geospatial pathfinding using A-star and a string pulling algorithm.