Crate bsp_pathfinding

Source
Expand description

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

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");

Re-exports§

pub use astar::*;

Modules§

astar
heuristics

Structs§

BSPNode
Represents a single node in the binary tree. The node constitutes of a splitting plane and children behind and in front of the plane.
BSPTree
Defines the tree used for navigation
Descendants
Face
A two dimensional face of two vertices. Uses counterclockwise winding order to calculate a normal
NavigationContext
Contains the graph and edges necessary for path finding
NodeIndex
Represent the index of a crate::BSPNode
NodePayload
Represents the result of crate::BSPTree::locate
Portal
Represents a surface connecting two nodes
PortalRef
References a portal
Portals
Declares portals which are surfaces connecting two partitioning planes, crate::BSPNode.
Shape
Defines a collection of faces. This struct is not neccesary to use, but helps in constructing squares and other primitives.

Enums§

Side

Constants§

TOLERANCE