hierarchical_pathfinding/

lib.rs

#![deny(
    missing_docs,
    // missing_doc_code_examples,
    missing_debug_implementations,
    missing_copy_implementations,
    trivial_casts,
    trivial_numeric_casts,
    unsafe_code,
    unstable_features,
    unused_import_braces,
    unused_qualifications
)]
#![allow(clippy::upper_case_acronyms)]

//! A crate to quickly approximate Paths on a Grid.
//!
//! # Use Case
//!
//! Finding Paths on a Grid is an expensive Operation. Consider the following Setup:
//!
//! ![The Setup](https://github.com/mich101mich/hierarchical_pathfinding/blob/master/img/problem.png?raw=true)
//!
//! In order to calculate a Path from Start to End using regular A*, it is necessary to check a
//! lot of Tiles:
//!
//! ![A*](https://github.com/mich101mich/hierarchical_pathfinding/blob/master/img/a_star.png?raw=true)
//!
//! (This is simply a small example, longer Paths require a quadratic increase in Tile checks,
//! and unreachable Goals require the check of _**every single**_ Tile)
//!
//! The Solution that Hierarchical Pathfinding provides is to divide the Grid into Chunks and
//! cache the Paths between Chunk entrances as a Graph of Nodes:
//!
//! ![The Graph](https://github.com/mich101mich/hierarchical_pathfinding/blob/master/img/hpa.png?raw=true)
//!
//! This allows Paths to be generated by connecting the Start and End to the Nodes within the
//! Chunk and using the Graph for the rest:
//!
//! ![The Solution](https://github.com/mich101mich/hierarchical_pathfinding/blob/master/img/hpa_solution.png?raw=true)
//!
//! Since the Graph is not an exact representation of the Grid, **the resulting Paths will
//! be slightly worse than the actual best Path** (unless [`config.perfect_paths`](PathCacheConfig::perfect_paths)
//! is set to `true`). This is usually not a problem, since the purpose of Hierarchical Pathfinding
//! is to quickly find the next direction to go in or a Heuristic for the Cost and existence
//! of a Path.
//!
//! The only time where the actual best Path would noticeably differ is in the case of short Paths.
//! That is why this crate calls the regular A* search after HPA* confirmed the length and
//! existence. (This behavior can be turned of using the Config).
//!
//! This crate provides an implementation of a Hierarchical Pathfinding Algorithm for any generic Grid.
//! Paths can be searched using either A* for a Path to a single Tile, or Dijkstra for searching
//! multiple Targets. It handles solid walls in the Grid and actually finding a Path to a wall.
//!
//! # Examples
//! ##### Creating the Cache
//! First is the Grid itself. **How it is stored doesn't matter**, but lookup has to be fast.
//!
//! For this example, we shall use a 2D-Array:
//! ```ignore
//! // 0 = empty, 1 = swamp, 2 = wall
//! let mut grid = [
//!     [0, 2, 0, 0, 0],
//!     [0, 2, 2, 2, 0],
//!     [0, 1, 0, 0, 0],
//!     [0, 1, 0, 2, 0],
//!     [0, 0, 0, 2, 0],
//! ];
//! let (width, height) = (grid.len(), grid[0].len());
//!
//! let cost_map = [
//!     1,  // empty
//!     10, // swamp
//!     -1, // wall = solid
//! ];
//! ```
//! Now for creating the [`PathCache`]:
//! ```
//! # let mut grid = [
//! #     [0, 2, 0, 0, 0],
//! #     [0, 2, 2, 2, 0],
//! #     [0, 1, 0, 0, 0],
//! #     [0, 1, 0, 2, 0],
//! #     [0, 0, 0, 2, 0],
//! # ];
//! # let (width, height) = (grid.len(), grid[0].len());
//! # let cost_map = [
//! #     1,  // empty
//! #     10, // swamp
//! #     -1, // wall. Negative number == solid
//! # ];
//! use hierarchical_pathfinding::prelude::*;
//!
//! let mut pathfinding = PathCache::new(
//!     (width, height),   // the size of the Grid
//!     |(x, y)| cost_map[grid[y][x]],   // get the cost for walking over a Tile
//!     ManhattanNeighborhood::new(width, height),   // the Neighborhood
//!     PathCacheConfig::with_chunk_size(3),   // config
//! );
//! ```
//! The [`PathCache`] never takes the actual Grid, to allow for any storage format to be used
//! (`Array`, `Vec`, `HashMap`, `kd-tree`, ...). Instead, it takes a callback function that
//! indicates, how "expensive" walking across a Tile is (negative numbers for solid obstacles).
//!
//! Unfortunately, it is necessary to provide this function to every method of PathCache, since
//! storing it would make the Grid immutable. See also [Updating the PathCache](#updating-the-pathcache).
//!
//! [Currying](https://en.wikipedia.org/wiki/Currying) can be used to reduce duplication:
//! ```
//! # use hierarchical_pathfinding::prelude::*;
//! # // 0 = empty, 1 = swamp, 2 = wall
//! # let mut grid = [
//! #     [0, 2, 0, 0, 0],
//! #     [0, 2, 2, 2, 0],
//! #     [0, 1, 0, 0, 0],
//! #     [0, 1, 0, 2, 0],
//! #     [0, 0, 0, 2, 0],
//! # ];
//! # let (width, height) = (grid.len(), grid[0].len());
//! # type Grid = [[usize; 5]; 5];
//! const COST_MAP: [isize; 3] = [1, 10, -1]; // now const for ownership reasons
//!
//! // only borrows the Grid when called
//! fn cost_fn(grid: &Grid) -> impl '_ + Sync + Fn((usize, usize)) -> isize {
//!     move |(x, y)| COST_MAP[grid[y][x]]
//! }
//!
//! let mut pathfinding = PathCache::new(
//!     (width, height), // the size of the Grid
//!
//!     // simply call the creator function to take a reference of the Grid
//!     cost_fn(&grid),
//!     // ...
//! #     ManhattanNeighborhood::new(width, height), // the Neighborhood
//! #     PathCacheConfig::with_chunk_size(3), // config
//! # );
//! ```
//!
//! ##### Pathfinding
//! Finding the Path to a single Goal:
//! ```
//! # use hierarchical_pathfinding::prelude::*;
//! # let mut grid = [
//! #     [0, 2, 0, 0, 0],
//! #     [0, 2, 2, 2, 2],
//! #     [0, 1, 0, 0, 0],
//! #     [0, 1, 0, 2, 0],
//! #     [0, 0, 0, 2, 0],
//! # ];
//! # let (width, height) = (grid.len(), grid[0].len());
//! # fn cost_fn(grid: &[[usize; 5]; 5]) -> impl '_ + Sync + Fn((usize, usize)) -> isize {
//! #     move |(x, y)| [1, 10, -1][grid[y][x]]
//! # }
//! # let mut pathfinding = PathCache::new(
//! #     (width, height),
//! #     cost_fn(&grid),
//! #     ManhattanNeighborhood::new(width, height),
//! #     PathCacheConfig::with_chunk_size(3),
//! # );
//! #
//! let start = (0, 0);
//! let goal = (4, 4);
//!
//! // find_path returns Some(Path) on success
//! let path = pathfinding.find_path(
//!     start,
//!     goal,
//!     cost_fn(&grid),
//! );
//!
//! assert!(path.is_some());
//! let path = path.unwrap();
//!
//! assert_eq!(path.cost(), 12);
//! ```
//! For more information, see [`find_path`](PathCache::find_path).
//!
//! Finding multiple Goals:
//! ```
//! # use hierarchical_pathfinding::prelude::*;
//! # let mut grid = [
//! #     [0, 2, 0, 0, 0],
//! #     [0, 2, 2, 2, 2],
//! #     [0, 1, 0, 0, 0],
//! #     [0, 1, 0, 2, 0],
//! #     [0, 0, 0, 2, 0],
//! # ];
//! # let (width, height) = (grid.len(), grid[0].len());
//! # fn cost_fn(grid: &[[usize; 5]; 5]) -> impl '_ + Sync + Fn((usize, usize)) -> isize {
//! #     move |(x, y)| [1, 10, -1][grid[y][x]]
//! # }
//! # let mut pathfinding = PathCache::new(
//! #     (width, height),
//! #     cost_fn(&grid),
//! #     ManhattanNeighborhood::new(width, height),
//! #     PathCacheConfig::with_chunk_size(3),
//! # );
//! #
//! let start = (0, 0);
//! let goals = [(4, 4), (2, 0)];
//!
//! // find_paths returns a HashMap<goal, Path> for all successes
//! let paths = pathfinding.find_paths(
//!     start,
//!     &goals,
//!     cost_fn(&grid),
//! );
//!
//! // (4, 4) is reachable
//! assert!(paths.contains_key(&goals[0]));
//!
//! // (2, 0) is not reachable
//! assert!(!paths.contains_key(&goals[1]));
//! ```
//! For more information, see [`find_paths`](PathCache::find_paths).
//!
//! ##### Using a Path
//! - Path exists: `path.is_some()` | `paths.contains_key()`
//!   - Useful as a Heuristic for other Algorithms
//!   - **100% correct** (`true` if and only if path can be found)
//! - Total Cost of the Path: [`path.cost()`](internals::AbstractPath::cost)
//!   - Correct for this Path, may be slightly larger than for optimal Path
//!   - The cost is simply returned; `cost()` does no calculations
//! - Total Length of the Path: [`path.length()`](internals::AbstractPath::length)
//!   - Correct for this Path, may be slightly longer than the optimal Path
//!   - The length is simply returned; `length()` does no calculations
//! - Next Position: [`path.next()`](internals::AbstractPath::next) | [`path.safe_next(cost_fn)`](internals::AbstractPath::safe_next)
//!   - [`safe_next`](internals::AbstractPath::safe_next) is needed if [`config.cache_paths`](crate::PathCacheConfig::cache_paths) is set to `false`
//!   - can be called several times to iterate Path
//!   - path implements `Iterator<Item = (usize, usize)>`
//! - Entire Path: `path.collect::<Vec<_>>()` | [`path.resolve(cost_fn)`](internals::AbstractPath::resolve)
//!   - [`resolve`](internals::AbstractPath::resolve) is needed if [`config.cache_paths`](crate::PathCacheConfig::cache_paths) is set to `false`
//!   - Returns a `Vec<(usize, usize)>`
//!
//! Note that [`resolve`](internals::AbstractPath::resolve) calculates any missing segments (if [`config.cache_paths`](crate::PathCacheConfig::cache_paths) ` == false`)
//! and allocates a [`Vec`](std::vec::Vec) with the resulting Points. Not recommended if only the
//! beginning of the Path is needed.
//! ```
//! # use hierarchical_pathfinding::prelude::*;
//! # let mut grid = [
//! #     [0, 2, 0, 0, 0],
//! #     [0, 2, 2, 2, 2],
//! #     [0, 1, 0, 0, 0],
//! #     [0, 1, 0, 2, 0],
//! #     [0, 0, 0, 2, 0],
//! # ];
//! # let (width, height) = (grid.len(), grid[0].len());
//! # fn cost_fn(grid: &[[usize; 5]; 5]) -> impl '_ + Sync + Fn((usize, usize)) -> isize {
//! #     move |(x, y)| [1, 10, -1][grid[y][x]]
//! # }
//! # let mut pathfinding = PathCache::new(
//! #     (width, height),
//! #     cost_fn(&grid),
//! #     ManhattanNeighborhood::new(width, height),
//! #     PathCacheConfig::with_chunk_size(3),
//! # );
//! # struct Player{ pos: (usize, usize) }
//! # impl Player {
//! #     pub fn move_to(&mut self, pos: (usize, usize)) {
//! #         self.pos = pos;
//! #     }
//! # }
//! #
//! let mut player = Player {
//!     pos: (0, 0),
//!     //...
//! };
//! let goal = (4, 4);
//!
//! let mut path = pathfinding.find_path(
//!     player.pos,
//!     goal,
//!     cost_fn(&grid),
//! ).unwrap();
//!
//! player.move_to(path.next().unwrap());
//! assert_eq!(player.pos, (0, 1));
//!
//! // wait for next turn or whatever
//!
//! player.move_to(path.next().unwrap());
//! assert_eq!(player.pos, (0, 2));
//!
//! // iterating is possible
//! for new_pos in path {
//!     player.move_to(new_pos);
//! }
//! assert_eq!(player.pos, goal);
//! ```
//!
//! ##### Updating the PathCache
//! The PathCache does not contain a copy or reference of the Grid for mutability and Ownership reasons.
//! This means however, that the user is responsible for storing and maintaining both the Grid and the PathCache.
//! It is also necessary to update the PathCache when the Grid has changed to keep it consistent:
//! ```should_panic
//! # use hierarchical_pathfinding::prelude::*;
//! # let mut grid = [
//! #     [0, 2, 0, 0, 0],
//! #     [0, 2, 2, 2, 2],
//! #     [0, 1, 0, 0, 0],
//! #     [0, 1, 0, 2, 0],
//! #     [0, 0, 0, 2, 0],
//! # ];
//! # let (width, height) = (grid.len(), grid[0].len());
//! # fn cost_fn(grid: &[[usize; 5]; 5]) -> impl '_ + Sync + Fn((usize, usize)) -> isize {
//! #     move |(x, y)| [1, 10, -1][grid[y][x]]
//! # }
//! # let mut pathfinding = PathCache::new(
//! #     (width, height),
//! #     cost_fn(&grid),
//! #     ManhattanNeighborhood::new(width, height),
//! #     PathCacheConfig::with_chunk_size(3),
//! # );
//! #
//! let (start, goal) = ((0, 0), (2, 0));
//!
//! let path = pathfinding.find_path(start, goal, cost_fn(&grid));
//! assert!(path.is_none()); // from previous example
//!
//! // Clear a way to the goal
//! grid[1][2] = 0; // at (2, 1): the wall below the goal
//!
//! let path = pathfinding.find_path(start, goal, cost_fn(&grid));
//! assert!(path.is_some()); // there should be a Path now!
//! ```
//! [`tiles_changed`](PathCache::tiles_changed) must be called with all changed Tiles:
//! ```
//! # use hierarchical_pathfinding::prelude::*;
//! # let mut grid = [
//! #     [0, 2, 0, 0, 0],
//! #     [0, 2, 2, 2, 2],
//! #     [0, 1, 0, 0, 0],
//! #     [0, 1, 0, 2, 0],
//! #     [0, 0, 0, 2, 0],
//! # ];
//! # let (width, height) = (grid.len(), grid[0].len());
//! # fn cost_fn(grid: &[[usize; 5]; 5]) -> impl '_ + Sync + Fn((usize, usize)) -> isize {
//! #     move |(x, y)| [1, 10, -1][grid[y][x]]
//! # }
//! # let mut pathfinding = PathCache::new(
//! #     (width, height),
//! #     cost_fn(&grid),
//! #     ManhattanNeighborhood::new(width, height),
//! #     PathCacheConfig::with_chunk_size(3),
//! # );
//! #
//! let (start, goal) = ((0, 0), (2, 0));
//!
//! let path = pathfinding.find_path(start, goal, cost_fn(&grid));
//! assert!(path.is_none());
//!
//! // Clear a way to the goal
//! grid[1][2] = 0; // at (2, 1): the wall below the goal
//!
//! pathfinding.tiles_changed(
//!     &[(2, 1)],
//!     cost_fn(&grid),
//! );
//!
//! let path = pathfinding.find_path(start, goal, cost_fn(&grid));
//! assert!(path.is_some());
//! ```
//! `tiles_changed` takes a slice of Points, and it is recommended to bundle changes together for
//! performance reasons.
//!
//! ##### Configuration
//! The last parameter for PathCache::new is a [`PathCacheConfig`] object with different options to have more control over the generated PathCache.
//! These options are mostly used to adjust the balance between Performance and Memory Usage, with the default values aiming more at Performance.
//! ```
//! # use hierarchical_pathfinding::prelude::*;
//! # let mut grid = [
//! #     [0, 2, 0, 0, 0],
//! #     [0, 2, 2, 2, 2],
//! #     [0, 1, 0, 0, 0],
//! #     [0, 1, 0, 2, 0],
//! #     [0, 0, 0, 2, 0],
//! # ];
//! # let (width, height) = (grid.len(), grid[0].len());
//! # fn cost_fn(grid: &[[usize; 5]; 5]) -> impl '_ + Sync + Fn((usize, usize)) -> isize {
//! #     move |(x, y)| [1, 10, -1][grid[y][x]]
//! # }
//!
//! let mut pathfinding = PathCache::new(
//!     (width, height), // the size of the Grid
//!     cost_fn(&grid), // get the cost for walking over a Tile
//!     ManhattanNeighborhood::new(width, height), // the Neighborhood
//!     PathCacheConfig {
//!         chunk_size: 3,
//!         ..PathCacheConfig::LOW_MEM
//!     }
//! );
//!
//! assert_eq!(pathfinding.config().chunk_size, 3);
//! ```
//! # Cargo Features
//! ##### parallel
//! Enabled by default.
//!
//! The parallel feature causes [`PathCache`] creation and updates to be multithreaded using [Rayon](https://crates.io/crates/rayon), making them significantly faster.
//! This feature has no effect on the speed of finding paths (_yet_).
//!
//! ##### log
//! Disabled by default.
//!
//! The log feature is used to enable internal timings on some functions.
//!
//! You probably shouldn't enable this feature unless you are working on improvments to hierarchical_pathfinding.
//! In order to comsume the logs, you need a logger setup to show trace! level logs.
//! See the [log](https://crates.io/crates/log) crate for more details.
//!

/// Shorthand for a 2D Point
type Point = (usize, usize);

/// A convenience type for a [`HashMap`](hashbrown::HashMap) using Points as the key
type PointMap<V> = hashbrown::HashMap<Point, V>;
/// A convenience type for a [`HashSet`](hashbrown::HashSet) with Points
type PointSet = hashbrown::HashSet<Point>;

/// The Type used to reference a Node in the abstracted Graph
type NodeID = u32;

/// A convenience type for a [`HashMap`](hashbrown::HashMap) using NodeIDs as the key
type NodeIDMap<V> = hashbrown::HashMap<NodeID, V>;
/// A convenience type for a [`HashSet`](hashbrown::HashSet) with NodeIDs
type NodeIDSet = hashbrown::HashSet<NodeID>;

mod path_cache;
pub use self::path_cache::{PathCache, PathCacheConfig};

mod path;

mod utils;
pub(crate) use utils::*;

pub mod neighbors;

mod graph;
mod grid;

/// Internal stuff that is returned by other function
pub mod internals {
    pub use crate::path::AbstractPath;
    pub use crate::path_cache::{CacheInspector, NodeInspector};
}

/// The prelude for this crate.
pub mod prelude {
    pub use crate::{
        neighbors::{ManhattanNeighborhood, MooreNeighborhood, Neighborhood},
        PathCache, PathCacheConfig,
    };
}