bsp_pathfinding/tree/
mod.rs

1use std::ops::Index;
2
3use glam::Vec2;
4use rand::{prelude::SliceRandom, Rng};
5use slotmap::*;
6
7use crate::Face;
8
9pub use node::*;
10pub use portal::*;
11pub use portals::*;
12
13mod node;
14mod portal;
15mod portals;
16
17type Nodes = SlotMap<NodeIndex, BSPNode>;
18
19new_key_type! {
20    /// Represent the index of a [crate::BSPNode]
21    pub struct NodeIndex;
22}
23/// Defines the tree used for navigation
24#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
25pub struct BSPTree {
26    nodes: Nodes,
27    root: NodeIndex,
28    // Bounds
29    l: Vec2,
30    r: Vec2,
31}
32
33impl BSPTree {
34    /// Constructs a new tree.
35    /// Returns None if there are not faces, and root construction was not possible
36    pub fn new(faces: impl Iterator<Item = Face>) -> Option<Self> {
37        let faces: Vec<_> = faces.collect();
38
39        Self::new_inner(faces)
40    }
41
42    pub fn new_shuffle(faces: impl Iterator<Item = Face>, rng: &mut impl Rng) -> Option<Self> {
43        let mut faces: Vec<_> = faces.collect();
44        faces.shuffle(rng);
45
46        Self::new_inner(faces)
47    }
48
49    fn new_inner(faces: Vec<Face>) -> Option<Self> {
50        let mut l = Vec2::new(f32::MAX, f32::MAX);
51        let mut r = Vec2::new(f32::MIN, f32::MIN);
52
53        faces.iter().flatten().for_each(|val| {
54            l = l.min(val);
55            r = r.max(val);
56        });
57
58        let mut nodes = SlotMap::with_key();
59        let root = BSPNode::from_faces(&mut nodes, &faces, 0)?;
60
61        Some(Self { nodes, root, l, r })
62    }
63
64    pub fn node(&self, index: NodeIndex) -> Option<&BSPNode> {
65        self.nodes.get(index)
66    }
67
68    /// Returns the root index
69    pub fn root(&self) -> NodeIndex {
70        self.root
71    }
72
73    /// Returns a reference to the root node
74    pub fn root_node(&self) -> &BSPNode {
75        self.node(self.root).expect("Root is always present")
76    }
77
78    pub fn descendants(&self) -> Descendants {
79        BSPNode::descendants(self.root, &self.nodes)
80    }
81
82    /// Returns the containing node and if the point is covered
83    pub fn locate(&self, point: Vec2) -> NodePayload {
84        let mut index = self.root;
85
86        loop {
87            let node = &self.nodes[index];
88            let rel = point - node.origin();
89            let dot = rel.dot(node.normal());
90
91            let (next, covered) = if dot >= 0.0 {
92                (node.front(), false)
93            } else {
94                (node.back(), true)
95            };
96
97            if let Some(next) = next {
98                index = next
99            } else {
100                return NodePayload {
101                    index,
102                    node,
103                    covered,
104                    depth: if covered {
105                        -node.normal() * dot
106                    } else {
107                        Vec2::ZERO
108                    },
109                };
110            }
111        }
112    }
113
114    /// Get a mutable reference to the bsptree's root.
115    pub fn root_mut(&mut self) -> &mut NodeIndex {
116        &mut self.root
117    }
118
119    /// Get a reference to the bsptree's nodes.
120    pub fn nodes(&self) -> &Nodes {
121        &self.nodes
122    }
123
124    /// Returns clipping planes which contain the scene
125    pub fn clipping_planes(&self) -> [Face; 4] {
126        [
127            Face::new([Vec2::new(self.l.x, self.r.y), self.l]),
128            Face::new([self.l, Vec2::new(self.r.x, self.l.y)]),
129            Face::new([Vec2::new(self.r.x, self.l.y), self.r]),
130            Face::new([self.r, Vec2::new(self.l.x, self.r.y)]),
131        ]
132    }
133
134    pub fn generate_portals(&self) -> Vec<ClippedFace> {
135        let clipping_planes = self.clipping_planes().into_iter().collect();
136
137        let mut portals = Vec::new();
138        BSPNode::generate_portals(self.root, &self.nodes, &clipping_planes, &mut portals);
139        portals
140    }
141}
142
143/// Represents the result of [crate::BSPTree::locate]
144#[derive(Clone, Debug)]
145pub struct NodePayload<'a> {
146    pub index: NodeIndex,
147    pub node: &'a BSPNode,
148    pub covered: bool,
149    pub depth: Vec2,
150}
151
152impl<'a> NodePayload<'a> {
153    /// Get the node payload's node.
154    pub fn node(&self) -> &BSPNode {
155        self.node
156    }
157
158    /// Get the node payload's index.
159    pub fn index(&self) -> NodeIndex {
160        self.index
161    }
162
163    /// Get the node payload's covered.
164    pub fn covered(&self) -> bool {
165        self.covered
166    }
167
168    /// Get the node payload's depth.
169    pub fn depth(&self) -> Vec2 {
170        self.depth
171    }
172}
173
174impl Index<NodeIndex> for BSPTree {
175    type Output = BSPNode;
176
177    fn index(&self, index: NodeIndex) -> &Self::Output {
178        self.node(index).unwrap()
179    }
180}
bsp_pathfinding/tree/mod.rs

bsp_pathfinding/tree/
mod.rs
