banished_game/people/
names.rs

1//! Names for citizens and towns, made from the name databases (`Game/Names/*`). See
2//! docs/TOWN-NAME-DATABASE.md.
3//!
4//! Original: `FUN_1400a9d50` (one candidate), `FUN_1400aa000` (try again
5//! while the candidate is a name the game ships), `FUN_1400aa130` (citizens), `FUN_14009ef90`
6//! (towns).
7
8use banished_formats::names::NameDatabase;
9
10use crate::random::Random;
11
12/// Bit 26 of a transition mask: the name may end here.
13const END: u32 = 26;
14
15fn key(window: [u8; 4]) -> u32 {
16    // Bytes are sign-extended (`movsbl`); names are ASCII, so this is a plain big-endian key.
17    let b = |c: u8| c as i8 as i32 as u32;
18    (((b(window[0]) << 8 | b(window[1])) << 8 | b(window[2])) << 8) | b(window[3])
19}
20
21/// Binary search of the transition table as the original does it (unsigned keys).
22fn find(db: &NameDatabase, k: u32) -> Option<usize> {
23    let n = db.transitions.len() as i32;
24    let (mut lo, mut hi) = (0i32, n);
25    loop {
26        let mid = (hi + lo) >> 1;
27        if mid < 0 || n <= mid {
28            return None;
29        }
30        let rec = key(db.transitions[mid as usize].prefix);
31        if k == rec {
32            return Some(mid as usize);
33        }
34        if k <= rec {
35            hi = mid - 1;
36        } else {
37            lo = mid + 1;
38        }
39        if hi < lo {
40            return None;
41        }
42    }
43}
44
45/// Compose one candidate of roughly `min..max` letters.
46///
47/// Original: `FUN_1400a9d50`.
48pub fn candidate(db: &NameDatabase, rng: &mut Random, min: i32, max: i32) -> String {
49    let mut out = [0u8; 0x100];
50    let start = rng.rand_below(db.starting_transitions.len() as u32) as usize;
51    let first = db.transitions[db.starting_transitions[start] as usize];
52    out[..4].copy_from_slice(&first.prefix);
53    out[0] = out[0].wrapping_sub(0x20);
54    let mut window = first.prefix;
55    let limit = rng.rand_range(min, max - 4) as i64;
56    let steps = (max * 2 - 3) as i64;
57    let mut written = 0usize; // r14
58    let mut last_boundary: i32 = -1; // r15
59    let mut pos: i64 = 0; // rbp
60    let finish = |out: &[u8; 0x100]| {
61        let len = out.iter().position(|&c| c == 0).unwrap_or(out.len());
62        String::from_utf8_lossy(&out[..len]).into_owned()
63    };
64    if steps <= 0 {
65        return finish(&out);
66    }
67    loop {
68        let Some(i) = find(db, key(window)) else {
69            return finish(&out);
70        };
71        let rec = db.transitions[i];
72        window = rec.prefix;
73        let mask = rec.next_characters;
74        if mask == 0 {
75            return finish(&out);
76        }
77        if pos >= max as i64 && rec.boundary != 0 {
78            return finish(&out);
79        }
80        if rec.boundary != 0 {
81            last_boundary = written as i32 + 4;
82        }
83        let total = (mask & 0x7ff_ffff).count_ones();
84        let pick = rng.rand_below(total);
85        let mut chosen = total;
86        let mut seen = 0;
87        for bit in 0..=END {
88            if mask >> bit & 1 != 0 {
89                if seen == pick {
90                    chosen = bit;
91                    break;
92                }
93                seen += 1;
94            }
95        }
96        if (pos >= limit && mask >> END & 1 != 0) || chosen == END {
97            out[written + 4] = 0;
98            return finish(&out);
99        }
100        let c = chosen as u8 + b'a';
101        pos += 1;
102        written += 1;
103        out[3 + pos as usize] = c;
104        window = [window[1], window[2], window[3], c];
105        if pos >= steps {
106            break;
107        }
108    }
109    if last_boundary > 0 {
110        out[last_boundary as usize] = 0;
111    }
112    finish(&out)
113}
114
115/// Up to 50 candidates, keeping the first of at least `min` letters that is not a shipped name (or
116/// the last one tried).
117///
118/// Original: `FUN_1400aa000`.
119pub fn generate(db: &NameDatabase, rng: &mut Random, min: i32, max: i32) -> String {
120    let mut name = String::new();
121    for _ in 0..50 {
122        name = candidate(db, rng, min, max);
123        if name.len() as i32 >= min && !is_shipped(db, &name) {
124            break;
125        }
126    }
127    name
128}
129
130/// Binary search of the sorted accepted-name pool (`String::StrCompare`).
131fn is_shipped(db: &NameDatabase, name: &str) -> bool {
132    let n = db.names.len() as i32;
133    let (mut lo, mut hi) = (0i32, n);
134    loop {
135        let mid = (hi + lo) >> 1;
136        if mid < 0 || n <= mid {
137            return false;
138        }
139        match name.as_bytes().cmp(db.names[mid as usize].as_bytes()) {
140            std::cmp::Ordering::Equal => return true,
141            std::cmp::Ordering::Less => hi = mid - 1,
142            std::cmp::Ordering::Greater => lo = mid + 1,
143        }
144        if hi < lo {
145            return false;
146        }
147    }
148}
149
150/// A citizen's first name, 3 to 10 letters.
151///
152/// Original: `FUN_1400aa130`.
153pub fn citizen_name(db: &NameDatabase, rng: &mut Random) -> String {
154    generate(db, rng, 3, 10)
155}
156
157/// A town name of at least five letters; `…vill` becomes `…ville`.
158///
159/// Original: `FUN_14009ef90`.
160pub fn town_name(db: &NameDatabase, rng: &mut Random, max: i32) -> String {
161    let mut name = generate(db, rng, 5, max);
162    if name.len() > 4 && name.ends_with("vill") {
163        name.push('e');
164    }
165    name
166}
banished_game/people/names.rs

banished_game/people/
names.rs
