banished_game/behaviour/
character_tree.rs

1//! The characters' spatial tree: a loose quadtree of the CharacterComponents, which the
2//! tornado's victims and the hunters' prey are searched in.
3//!
4//! - **Built**: a world of 2048 units centred on the map (offset 1024, 1024), 8
5//!   levels, node `base[level] + Morton(x, y)` with the bases 0, 1, 5, 0x15, … 0x1555 (0x5555
6//!   nodes). Each node keeps a circular list of its slots (the head) and the count of slots in it
7//!   and below (carried up `parent = (i − 1) >> 2`).
8//! - **Insert** (when a character starts or is loaded): the last freed slot, else a new one; then
9//!   placed.
10//! - **Remove** (when a character ends): unlinked, the slot freed.
11//! - **Place** (at every character update): the level from the character's
12//!   square (its position ± the description's radius), the cell its centre falls in at that level;
13//!   a slot that changes node goes to the end of the new node's list.
14//! - **Search**: a stack from the root; a node with nothing in or below it, or whose loose box (its
15//!   square doubled, z from −1 to 1) misses the query's box (the point ± the radius on every axis),
16//!   is dropped; otherwise its slots are visited from the head and it is replaced by its four
17//!   children (pushed 1 to 4, so the fourth comes off first). The z bounds mean nothing is found
18//!   while the point stands more than the radius + 1 from height 0.
19//!
20//! Original: built by `FUN_140018cc0`; insert `FUN_14010ee90` (start) and `FUN_14010ef80` (load);
21//! remove `FUN_14010ee50`; place `FUN_14010e990`; and `FUN_140097e60`, `FUN_140097730`, `FUN_140097d50`, `FUN_140018e00`, `FUN_140018f70`, `FUN_140019070`, `FUN_140019710`, `FUN_140019650`, `FUN_1400197e0`, `FUN_140019290`.
22// Game +0x88; +0x30; +0x50; +0x20
23
24/// `DAT_140178958`: the world's side.
25const WORLD: f32 = 2048.0;
26/// `FUN_140018cc0`: the levels and the first node of each.
27const LEVELS: i32 = 8;
28const BASES: [i32; 8] = [0, 1, 5, 0x15, 0x55, 0x155, 0x555, 0x1555];
29const NODES: usize = 0x5555;
30
31/// What a slot holds: the owner of the CharacterComponent.
32#[derive(Debug, Clone, Copy, PartialEq, Eq)]
33pub enum Who {
34    /// A citizen.
35    Citizen(usize),
36    /// An animal.
37    Animal(usize),
38    /// A trader boat.
39    Boat(usize),
40    /// A nomad.
41    Nomad(usize),
42}
43
44#[derive(Debug, Clone, Copy)]
45struct Slot {
46    who: Option<Who>,
47    /// `+0x08`, `+0x0c`: the node list's next and previous slots.
48    next: i32,
49    prev: i32,
50    /// `+0x10`: the node, −1 when in none.
51    node: i32,
52    position: [f32; 3],
53    /// The component's walking direction (`+0x2c`), as of its last update.
54    direction: [f32; 3],
55    /// When it was put in, standing in for the component's address in `FUN_1400cde40`.
56    serial: u64,
57}
58
59/// The characters' spatial tree. See the [module documentation](self).
60#[derive(Debug, Clone)]
61pub struct CharacterTree {
62    slots: Vec<Slot>,
63    free: Vec<i32>,
64    heads: Vec<i32>,
65    counts: Vec<i32>,
66    serials: u64,
67}
68
69impl Default for CharacterTree {
70    fn default() -> Self {
71        CharacterTree {
72            slots: Vec::new(),
73            free: Vec::new(),
74            heads: vec![-1; NODES],
75            counts: vec![0; NODES],
76            serials: 0,
77        }
78    }
79}
80
81/// `FUN_140019070`'s bit interleave: x in the even bits, y in the odd.
82fn morton(x: u32, y: u32) -> u32 {
83    let spread = |mut v: u32| {
84        v = (v << 8 | v) & 0x00ff_00ff;
85        v = (v << 4 | v) & 0x0f0f_0f0f;
86        v = (v << 2 | v) & 0x3333_3333;
87        (v << 1 | v) & 0x5555_5555
88    };
89    spread(x) | spread(y) << 1
90}
91
92/// The node a character at `position` with `radius` belongs in (`FUN_140019070`).
93fn node_of(position: [f32; 3], radius: f32) -> i32 {
94    // FUN_140097d90: the square position ± radius; its centre and half its size.
95    let (x0, y0) = (position[0] - radius, position[1] - radius);
96    let (x1, y1) = (radius + position[0], radius + position[1]);
97    let (cx, cy) = ((x0 + x1) * 0.5, (y0 + y1) * 0.5);
98    let half = ((x1 - x0) * 0.5).max((y1 - y0) * 0.5);
99    let q = WORLD / (half + 0.001);
100    let level = ((q.to_bits() >> 23) as i32 - 127).clamp(0, LEVELS - 1);
101    let side = 1i32 << level;
102    let scale = 1.0 / (WORLD / side as f32);
103    let (cx, cy) = (cx + WORLD * 0.5, cy + WORLD * 0.5);
104    let x = ((cx * scale) as i32).clamp(0, side - 1) as u32;
105    let y = ((cy * scale) as i32).clamp(0, side - 1) as u32;
106    morton(x, y) as i32 + BASES[level as usize]
107}
108
109impl CharacterTree {
110    /// A slot for `who`, placed at once. Returns the slot.
111    ///
112    /// Original: `FUN_140018e00`.
113    pub fn insert(&mut self, who: Who, position: [f32; 3], radius: f32) -> i32 {
114        self.serials += 1;
115        let blank = Slot {
116            who: Some(who),
117            next: 0,
118            prev: 0,
119            node: -1,
120            position,
121            direction: [0.0; 3],
122            serial: self.serials,
123        };
124        let slot = match self.free.pop() {
125            Some(s) => {
126                self.slots[s as usize] = blank;
127                s
128            }
129            None => {
130                self.slots.push(blank);
131                self.slots.len() as i32 - 1
132            }
133        };
134        self.place(slot, position, radius);
135        slot
136    }
137
138    /// Out of its node; the slot goes on the free list. The slot holding `who`, if it is in the
139    /// tree.
140    ///
141    /// Original: `FUN_140018f70`.
142    pub fn slot_of(&self, who: Who) -> Option<i32> {
143        self.slots
144            .iter()
145            .position(|s| s.who == Some(who))
146            .map(|i| i as i32)
147    }
148
149    /// Remove a character's slot.
150    pub fn remove(&mut self, slot: i32) {
151        if slot < 0
152            || self
153                .slots
154                .get(slot as usize)
155                .is_none_or(|s| s.who.is_none())
156        {
157            return;
158        }
159        if 0 <= self.slots[slot as usize].node {
160            self.unlink(slot);
161        }
162        let s = &mut self.slots[slot as usize];
163        s.who = None;
164        s.next = 0;
165        s.node = -1;
166        self.free.push(slot);
167    }
168
169    /// Where the character stands now; a new node puts it at the end of that node's list.
170    ///
171    /// Original: `FUN_140019070`.
172    pub fn place(&mut self, slot: i32, position: [f32; 3], radius: f32) {
173        if slot < 0
174            || self
175                .slots
176                .get(slot as usize)
177                .is_none_or(|s| s.who.is_none())
178        {
179            return;
180        }
181        self.slots[slot as usize].position = position;
182        let node = node_of(position, radius);
183        if self.slots[slot as usize].node != node {
184            if 0 <= self.slots[slot as usize].node {
185                self.unlink(slot);
186            }
187            self.slots[slot as usize].node = node;
188            self.link(slot);
189        }
190    }
191
192    // +0x2c
193    /// The walking direction the follow check reads (the component's).
194    pub fn set_direction(&mut self, slot: i32, direction: [f32; 3]) {
195        if let Some(s) = usize::try_from(slot)
196            .ok()
197            .and_then(|i| self.slots.get_mut(i))
198        {
199            s.direction = direction;
200        }
201    }
202
203    // its slot +0x30
204    /// MoveTo's notify: the nearest other character within 0.5, if it came after this one (the
205    /// original compares the components' addresses; the port, the order they were put in the tree)
206    /// and walks the same way (the directions' dot product above 0), is followed.
207    ///
208    /// Original: `FUN_1400cde40`, `FUN_140097730`.
209    pub fn follows(&self, slot: i32) -> bool {
210        let Some(me) = usize::try_from(slot).ok().and_then(|i| self.slots.get(i)) else {
211            return false;
212        };
213        let Some(who) = me.who else { return false };
214        let mut best: Option<&Slot> = None;
215        let mut most = 0.5f32 * 0.5;
216        self.visit_slots(me.position, 0.5, |s| {
217            if s.who != Some(who) {
218                let d = dist2(s.position, me.position);
219                if d < most {
220                    most = d;
221                    best = Some(s);
222                }
223            }
224        });
225        let Some(other) = best else { return false };
226        let dot = other.direction[0] * me.direction[0]
227            + other.direction[1] * me.direction[1]
228            + other.direction[2] * me.direction[2];
229        // Deviation: the original follows a character whose component sits at a higher
230        // address; the port takes the one put in the tree later.
231        me.serial < other.serial && 0.0 < dot
232    }
233
234    /// `FUN_140019650`: at the end of its node's circular list.
235    fn link(&mut self, slot: i32) {
236        let node = self.slots[slot as usize].node as usize;
237        let head = self.heads[node];
238        if head < 0 {
239            self.heads[node] = slot;
240            self.slots[slot as usize].next = slot;
241            self.slots[slot as usize].prev = slot;
242        } else {
243            let last = self.slots[head as usize].prev;
244            self.slots[slot as usize].prev = last;
245            self.slots[slot as usize].next = head;
246            self.slots[last as usize].next = slot;
247            self.slots[head as usize].prev = slot;
248        }
249        let mut n = node as i32;
250        self.counts[n as usize] += 1;
251        while n != 0 {
252            n = (n - 1) >> 2;
253            self.counts[n as usize] += 1;
254        }
255    }
256
257    /// `FUN_140019710`.
258    fn unlink(&mut self, slot: i32) {
259        let node = self.slots[slot as usize].node as usize;
260        if self.heads[node] == slot {
261            self.heads[node] = self.slots[slot as usize].next;
262        }
263        let (next, prev) = (
264            self.slots[slot as usize].next,
265            self.slots[slot as usize].prev,
266        );
267        self.slots[prev as usize].next = next;
268        self.slots[next as usize].prev = prev;
269        self.slots[slot as usize].next = -1;
270        self.slots[slot as usize].prev = -1;
271        if self.heads[node] == slot {
272            self.heads[node] = -1;
273        }
274        let mut n = node as i32;
275        self.counts[n as usize] -= 1;
276        while n != 0 {
277            n = (n - 1) >> 2;
278            self.counts[n as usize] -= 1;
279        }
280    }
281
282    /// The search: every slot of the nodes whose loose box meets `point ± radius`, in the
283    /// original's order, with where it stands.
284    ///
285    /// Original: `FUN_1400197e0`, `FUN_140019290`.
286    pub fn visit(&self, point: [f32; 3], radius: f32, mut each: impl FnMut(Who, [f32; 3])) {
287        self.visit_slots(point, radius, |s| {
288            if let Some(who) = s.who {
289                each(who, s.position);
290            }
291        });
292    }
293
294    fn visit_slots<'a>(&'a self, point: [f32; 3], radius: f32, mut each: impl FnMut(&'a Slot)) {
295        let qmin = [point[0] - radius, point[1] - radius, point[2] - radius];
296        let qmax = [radius + point[0], radius + point[1], radius + point[2]];
297        // (centre, half, node, level)
298        let mut stack: Vec<([f32; 3], [f32; 3], i32, i32)> =
299            vec![([0.0; 3], [WORLD * 0.5, WORLD * 0.5, 0.0], 0, 0)];
300        while let Some(&(c, h, node, level)) = stack.last() {
301            if self.counts[node as usize] <= 0 {
302                stack.pop();
303                continue;
304            }
305            // The loose box: the square doubled, the iterator's z from −1 to 1.
306            let e = [2.0 * h[0], 2.0 * h[1], 1.0 * h[2]];
307            let bmin = [c[0] - e[0] + 0.0, c[1] - e[1] + 0.0, c[2] - e[2] + -1.0];
308            let bmax = [e[0] + c[0] + 0.0, e[1] + c[1] + 0.0, e[2] + c[2] + 1.0];
309            let meets = (0..3).all(|k| bmin[k] <= qmax[k] && qmin[k] <= bmax[k]);
310            if !meets {
311                stack.pop();
312                continue;
313            }
314            let head = self.heads[node as usize];
315            if 0 <= head {
316                let mut s = head;
317                loop {
318                    let slot = &self.slots[s as usize];
319                    each(slot);
320                    s = slot.next;
321                    if s == head {
322                        break;
323                    }
324                }
325            }
326            // FUN_140019290: the node gives way to its children.
327            stack.pop();
328            if level + 1 < LEVELS {
329                let (hx, hy, hz) = (h[0] * 0.5, h[1] * 0.5, h[2]);
330                let child = |dx: f32, dy: f32| [c[0] + dx, c[1] + dy, c[2] + hz];
331                let half = [hx, hy, hz];
332                stack.push((child(hx * -1.0, hy * -1.0), half, node * 4 + 1, level + 1));
333                stack.push((child(hx, hy * -1.0), half, node * 4 + 2, level + 1));
334                stack.push((child(hx * -1.0, hy), half, node * 4 + 3, level + 1));
335                stack.push((child(hx * 1.0, hy * 1.0), half, node * 4 + 4, level + 1));
336            }
337        }
338    }
339
340    /// The characters standing within `radius` of `point` (squared distance below `radius²`), in
341    /// the tree's order.
342    ///
343    /// Original: `FUN_140097e60`.
344    pub fn within(&self, point: [f32; 3], radius: f32, filter: impl Fn(Who) -> bool) -> Vec<Who> {
345        let mut out = Vec::new();
346        let r2 = radius * radius;
347        self.visit(point, radius, |who, p| {
348            if filter(who) && dist2(p, point) < r2 {
349                out.push(who);
350            }
351        });
352        out
353    }
354
355    /// The nearest character within `radius` of `point` that `filter` takes; the first of equals in
356    /// the tree's order.
357    ///
358    /// Original: `FUN_140097730`.
359    pub fn nearest(
360        &self,
361        point: [f32; 3],
362        radius: f32,
363        filter: impl Fn(Who) -> bool,
364    ) -> Option<Who> {
365        let mut best = None;
366        let mut most = radius * radius;
367        self.visit(point, radius, |who, p| {
368            if filter(who) {
369                let d = dist2(p, point);
370                if d < most {
371                    most = d;
372                    best = Some(who);
373                }
374            }
375        });
376        best
377    }
378}
379
380/// `Vector3::Dot` of the difference with itself.
381fn dist2(p: [f32; 3], q: [f32; 3]) -> f32 {
382    let (dx, dy, dz) = (p[0] - q[0], p[1] - q[1], p[2] - q[2]);
383    dx * dx + dy * dy + dz * dz
384}
385
386#[cfg(test)]
387mod tests {
388    use super::*;
389
390    #[test]
391    fn a_character_lands_in_the_deepest_level_cell() {
392        // Radius 0.25: level 7, 128 cells of 16 a side.
393        assert_eq!(
394            node_of([0.0, 0.0, 0.0], 0.25),
395            0x1555 + morton(64, 64) as i32
396        );
397        assert_eq!(node_of([-1024.0, -1024.0, 0.0], 0.25), 0x1555);
398        assert_eq!(
399            node_of([17.0, -3.0, 5.0], 0.25),
400            0x1555 + morton(65, 63) as i32
401        );
402    }
403
404    #[test]
405    fn slots_are_reused_last_freed_first_and_lists_keep_arrival_order() {
406        let mut t = CharacterTree::default();
407        let a = t.insert(Who::Citizen(0), [1.0, 1.0, 0.0], 0.25);
408        let b = t.insert(Who::Citizen(1), [2.0, 2.0, 0.0], 0.25);
409        let c = t.insert(Who::Citizen(2), [3.0, 3.0, 0.0], 0.25);
410        assert_eq!((a, b, c), (0, 1, 2));
411        t.remove(a);
412        t.remove(c);
413        assert_eq!(t.insert(Who::Animal(9), [1.0, 1.0, 0.0], 0.25), 2);
414        let found = t.within([2.0, 2.0, 0.0], 8.0, |_| true);
415        assert_eq!(found, vec![Who::Citizen(1), Who::Animal(9)]);
416        // Moving away and back puts it at the end of its node.
417        t.place(b, [200.0, 200.0, 0.0], 0.25);
418        t.place(b, [2.0, 2.0, 0.0], 0.25);
419        assert_eq!(
420            t.within([2.0, 2.0, 0.0], 8.0, |_| true),
421            vec![Who::Animal(9), Who::Citizen(1)]
422        );
423    }
424
425    #[test]
426    fn a_later_character_ahead_going_the_same_way_is_followed() {
427        let mut t = CharacterTree::default();
428        let a = t.insert(Who::Citizen(0), [10.0, 10.0, 0.0], 0.25);
429        let b = t.insert(Who::Citizen(1), [10.3, 10.0, 0.0], 0.25);
430        t.set_direction(a, [1.0, 0.0, 0.0]);
431        t.set_direction(b, [1.0, 0.0, 0.0]);
432        assert!(t.follows(a));
433        // The later one does not follow the earlier.
434        assert!(!t.follows(b));
435        // Opposite ways: not followed.
436        t.set_direction(b, [-1.0, 0.0, 0.0]);
437        assert!(!t.follows(a));
438    }
439
440    #[test]
441    fn nothing_is_found_far_from_height_zero() {
442        let mut t = CharacterTree::default();
443        t.insert(Who::Animal(1), [5.0, 5.0, 12.0], 0.25);
444        t.insert(Who::Animal(2), [5.0, 6.0, 8.0], 0.25);
445        // Point at 12 with radius 8: the query's lowest z (4) is above the nodes' (1).
446        assert_eq!(t.nearest([5.0, 5.5, 12.0], 8.0, |_| true), None);
447        // At 9 it reaches down to 1.
448        assert_eq!(
449            t.nearest([5.0, 5.5, 9.0], 8.0, |_| true),
450            Some(Who::Animal(2))
451        );
452    }
453}
banished_game/behaviour/character_tree.rs

banished_game/behaviour/
character_tree.rs
