bsp_pathfinding/
navigation_context.rs

1use crate::{
2    astar::{astar, Path, SearchInfo},
3    BSPNode, BSPTree, NodeIndex, NodePayload, PortalIter,
4};
5use glam::Vec2;
6use rand::Rng;
7
8use crate::{Face, Portals};
9
10/// Contains the graph and edges necessary for path finding
11#[derive(Default)]
12#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
13pub struct NavigationContext {
14    tree: Option<BSPTree>,
15    portals: Portals,
16}
17
18impl NavigationContext {
19    /// Creates a new navigation context
20    pub fn new(faces: impl IntoIterator<Item = Face>) -> Self {
21        let tree = BSPTree::new(faces.into_iter());
22        let mut portals = Portals::new();
23        if let Some(tree) = tree.as_ref() {
24            portals.generate(&tree);
25        }
26
27        Self { tree, portals }
28    }
29
30    /// Creates a new navigation context.
31    /// Shuffles the input which usually reduces the depth of the final tree.
32    pub fn new_shuffle(faces: impl IntoIterator<Item = Face>, rng: &mut impl Rng) -> Self {
33        let tree = BSPTree::new_shuffle(faces.into_iter(), rng);
34        let mut portals = Portals::new();
35        if let Some(tree) = tree.as_ref() {
36            portals.generate(&tree);
37        }
38
39        Self { tree, portals }
40    }
41    pub fn node(&self, index: NodeIndex) -> Option<&BSPNode> {
42        self.tree.as_ref()?.node(index)
43    }
44
45    /// Locate a position in the tree.
46    /// Return None if there are no faces in the scene
47    pub fn locate(&self, point: Vec2) -> Option<NodePayload> {
48        match &self.tree {
49            Some(tree) => Some(tree.locate(point)),
50            None => None,
51        }
52    }
53
54    /// Get a reference to the navigation context's tree.
55    pub fn tree(&self) -> Option<&BSPTree> {
56        self.tree.as_ref()
57    }
58
59    /// Get a reference to the navigation context's portals.
60    pub fn portals(&self) -> &Portals {
61        &self.portals
62    }
63
64    /// Get the portals associated to a node
65    pub fn get(&self, index: NodeIndex) -> PortalIter {
66        self.portals.get(index)
67    }
68
69    /// Find a path from `start` to `end`
70    /// Returns None if no path was found.
71    /// If there are no faces in the scene, a straight path will be returned.
72    pub fn find_path(
73        &self,
74        start: Vec2,
75        end: Vec2,
76        heuristic: impl Fn(Vec2, Vec2) -> f32,
77        info: SearchInfo,
78    ) -> Option<Path> {
79        let mut path = None;
80        match &self.tree {
81            Some(tree) => {
82                astar(&tree, &self.portals, start, end, heuristic, info, &mut path);
83                path
84            }
85            None => Some(Path::euclidian(start, end)),
86        }
87    }
88
89    /// Find a path from `start` to `end`
90    /// Returns None if no path was found.
91    /// If there are no faces in the scene, a straight path will be returned.
92    /// Uses an already allocated path to fill and will attempt to only update
93    /// parts of the path
94    pub fn find_path_inc<'a>(
95        &self,
96        start: Vec2,
97        end: Vec2,
98        heuristic: impl Fn(Vec2, Vec2) -> f32,
99        info: SearchInfo,
100        path: &'a mut Option<Path>,
101    ) -> Option<&'a mut Path> {
102        match &self.tree {
103            Some(tree) => astar(&tree, &self.portals, start, end, heuristic, info, path),
104            None => {
105                *path = Some(Path::euclidian(start, end));
106                path.as_mut()
107            }
108        }
109    }
110}
bsp_pathfinding/navigation_context.rs

bsp_pathfinding/
navigation_context.rs
