sourcenav/
lib.rs

1use crate::navmesh::HammerUnit;
2pub use crate::navmesh::{
3    ApproachArea, Connections, EncounterPath, LadderConnections, LadderDirection, LightIntensity,
4    NavDirection, NavHidingSpot, NavQuad, Vector3, VisibleArea,
5};
6pub use crate::parser::{read_areas, NavArea, ParseError};
7use aabb_quadtree::{ItemId, QuadTree};
8use binrw::io::{Read, Seek};
9use euclid::{TypedPoint2D, TypedRect, TypedSize2D};
10
11mod navmesh;
12mod parser;
13
14type Rect = TypedRect<f32, HammerUnit>;
15
16/// A tree of all navigation areas
17pub struct NavQuadTree(QuadTree<NavQuad, HammerUnit, [(ItemId, Rect); 4]>);
18
19/// Parse all navigation quads from a nav file
20///
21/// ## Examples
22///
23/// ```no_run
24/// use sourcenav::get_quad_tree;
25/// use std::fs::File;
26/// use std::io::BufReader;
27///
28/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
29/// let mut file = BufReader::new(File::open("path/to/navfile.nav")?);
30/// let tree = get_quad_tree(&mut file)?;
31/// # Ok(())
32/// # }
33/// ```
34pub fn get_quad_tree<R: Read + Seek>(data: &mut R) -> Result<NavQuadTree, ParseError> {
35    let areas = read_areas(data)?;
36
37    let (min_x, min_y, max_x, max_y) = areas.iter().map(|area| &area.quad).fold(
38        (f32::MAX, f32::MAX, f32::MIN, f32::MIN),
39        |(min_x, min_y, max_x, max_y), area| {
40            (
41                f32::min(min_x, area.north_west.0),
42                f32::min(min_y, area.north_west.1),
43                f32::max(max_x, area.south_east.0),
44                f32::max(max_y, area.south_east.1),
45            )
46        },
47    );
48
49    let mut tree = QuadTree::default(
50        Rect::new(
51            TypedPoint2D::new(min_x - 1.0, min_y - 1.0),
52            TypedSize2D::new(max_x - min_x + 2.0, max_y - min_y + 2.0),
53        ),
54        areas.len(),
55    );
56
57    for area in areas {
58        tree.insert(area.quad);
59    }
60
61    Ok(NavQuadTree(tree))
62}
63
64impl NavQuadTree {
65    /// Find the navigation areas at a x/y coordinate
66    ///
67    /// ## Examples
68    ///
69    /// ```no_run
70    /// use sourcenav::get_quad_tree;
71    /// use std::fs::File;
72    /// use std::io::BufReader;
73    ///
74    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
75    /// let mut file = BufReader::new(File::open("path/to/navfile.nav")?);
76    /// let tree = get_quad_tree(&mut file)?;
77    /// let areas = tree.query(150.0, -312.0);
78    /// # Ok(())
79    /// # }
80    /// ```
81    pub fn query(&self, x: f32, y: f32) -> impl Iterator<Item = &NavQuad> {
82        let query_box = Rect::new(TypedPoint2D::new(x, y), TypedSize2D::new(1.0, 1.0));
83
84        self.0.query(query_box).into_iter().map(|(area, ..)| area)
85    }
86
87    /// Find the z-height of a specific x/y coordinate
88    ///
89    /// Note that multiple heights might exist for a given x/y coordinate
90    ///
91    /// ## Examples
92    ///
93    /// ```no_run
94    /// use sourcenav::get_quad_tree;
95    /// use std::fs::File;
96    /// use std::io::BufReader;
97    ///
98    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
99    /// let mut file = BufReader::new(File::open("path/to/navfile.nav")?);
100    /// let tree = get_quad_tree(&mut file)?;
101    /// let heights = tree.find_z_height(150.0, -312.0);
102    /// # Ok(())
103    /// # }
104    /// ```
105    pub fn find_z_height(&self, x: f32, y: f32) -> impl Iterator<Item = f32> + '_ {
106        self.query(x, y).map(move |area| area.get_z_height(x, y))
107    }
108
109    /// Get the z height at a point
110    ///
111    /// A z-guess should be provided to resolve cases where multiple z values are possible
112    pub fn find_best_height(&self, x: f32, y: f32, z_guess: f32) -> Option<f32> {
113        self.find_z_height(x, y).min_by(|a, b| {
114            let a_diff = (a - z_guess).abs();
115            let b_diff = (b - z_guess).abs();
116            a_diff.total_cmp(&b_diff)
117        })
118    }
119
120    /// Get all navigation areas from the nav file
121    ///
122    /// ## Examples
123    ///
124    /// ```no_run
125    /// use sourcenav::get_quad_tree;
126    /// use std::fs::File;
127    /// use std::io::BufReader;
128    ///
129    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
130    /// let mut file = BufReader::new(File::open("path/to/navfile.nav")?);
131    /// let tree = get_quad_tree(&mut file)?;
132    /// for quad in tree.quads() {
133    ///     println!("area: {:?}", quad)
134    /// }
135    /// # Ok(())
136    /// # }
137    /// ```
138    pub fn quads(&self) -> impl Iterator<Item = &NavQuad> {
139        self.0.iter().map(|(_, (area, _))| area)
140    }
141}
142
143#[test]
144fn test_tree() {
145    use std::fs::File;
146    use std::io::BufReader;
147
148    let mut file = BufReader::new(File::open("data/pl_badwater.nav").unwrap());
149    let tree = get_quad_tree(&mut file).unwrap();
150
151    // single flat plane
152    let point1 = (1600.0, -1300.0);
153
154    assert_eq!(
155        vec![375.21506],
156        tree.find_z_height(point1.0, point1.1).collect::<Vec<f32>>()
157    );
158
159    // 2 z levels
160    let point2 = (360.0, -1200.0);
161
162    assert_eq!(
163        vec![290.2907, 108.144775],
164        tree.find_z_height(point2.0, point2.1).collect::<Vec<f32>>()
165    );
166
167    // top of slope
168    let point3 = (320.0, -1030.0);
169
170    assert_eq!(
171        vec![220.83125],
172        tree.find_z_height(point3.0, point3.1).collect::<Vec<f32>>()
173    );
174
175    // bottom of same slope
176    let point4 = (205.0, -1030.0);
177
178    assert_eq!(
179        vec![147.23126],
180        tree.find_z_height(point4.0, point4.1).collect::<Vec<f32>>()
181    );
182}
183
184#[cfg(doctest)]
185doc_comment::doctest!("../README.md");
sourcenav/lib.rs

sourcenav/
lib.rs
