1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
//! Provides a path finding search space generation and A* search algorithm
//! using Binary Spatial Partitioning.
//!
//! The navigable space is defined by polygons delimiting the space. A graph of
//! navigable nodes and edges will be generated.
//!
//! The algorithm does not impose any constraints on size or angle of the scene
//! as is the case for grid or quadtree based approaches.
//!
//! # Usage
//! ```rust
//! use bsp_pathfinding::*;
//! use glam::*;
//! // Define a simple scene
//! let square = Shape::rect(Vec2::new(50.0, 50.0), Vec2::new(0.0, 0.0));
//! let left = Shape::rect(Vec2::new(10.0, 200.0), Vec2::new(-200.0, 10.0));
//! let right = Shape::rect(Vec2::new(10.0, 200.0), Vec2::new(200.0, 10.0));
//! let bottom = Shape::rect(Vec2::new(200.0, 10.0), Vec2::new(10.0, -200.0));
//! let top = Shape::rect(Vec2::new(200.0, 10.0), Vec2::new(10.0, 200.0));
//!
//! // Create navigational context from the scene
//! let nav = NavigationContext::new([square, left, right, top, bottom].iter().flatten());
//!
//! // Find a path
//! let start = Vec2::new(-100.0, 0.0);
//! let end = Vec2::new(100.0, 30.0);
//!
//! let path = nav
//! .find_path(start, end, heuristics::euclidiean, SearchInfo::default())
//! .expect("Failed to find a path");
//! ```
//!
pub mod astar;
pub mod heuristics;
mod navigation_context;
mod shape;
mod tree;
mod util;
pub use astar::*;
pub use navigation_context::*;
pub use shape::*;
pub use tree::*;
pub const TOLERANCE: f32 = 0.01;