words.rsThe goals the bot could pursue, said as sentences a person would say, from
nothing but the bot's own records of them (zbanks::GoalOption), and
collapsed so that no two options in one question read alike.
Every sentence carries what the bot knows that tells a goal apart from its
neighbours: what it is, which screen it is on and where on that screen,
which way it lies from Link, the exit the bot's own path leaves by and how
many screens that path crosses, whether it is on the way to another option,
what the bot expects there, failures so far, and the path length. Two goals
that differ in none of those things except distance are the same choice as
far as anyone could tell from the words, so they are one [Offer] - Jev
is never asked to split what it cannot tell apart (user, on "use door use
door use door"), and never asked to break a tie the planner's own scoring
already settles: distance is not a difference in KIND, so it is never a
reason to keep two same-kind, same-place goals as separate offers, however
far apart the two distances are (frame 14674, two pots 27 and 45 steps
apart, asked anyway - the fix this note describes).
19use zbanks::{GoalOption, Situation};
The bot's screen names carry their bounds and level after the name
("Well Uncle ^ 0 6a00,a00 x 6bff,aff", "Castle Yard 600,600 x 9ff,9ff");
unnamed screens are their id ("0x0c50 v 0 (20480 ...)"). The name alone,
with the bot's abbreviations spelled out, or None for an unnamed one.
25pub fn screen_name(screen: &str) -> Option<String> { 26 let mut words = Vec::new(); 27 for word in screen.split_whitespace() { 28 let marker = word == "^" || word == "v" || word.starts_with('(') || word.contains(','); 29 if marker { 30 break; 31 } 32 words.push(word); 33 } 34 if words.is_empty() || words[0].starts_with("0x") { 35 return None; 36 } 37 let name = words 38 .iter() 39 .map(|w| match *w { 40 "HC" => "Hyrule Castle", 41 "EP" => "Eastern Palace", 42 "DP" => "Desert Palace", 43 "Kak" => "Kakariko", 44 "DM" => "Death Mountain", 45 "ToH" => "Tower of Hera", 46 other => other, 47 }) 48 .collect::<Vec<_>>() 49 .join(" "); 50 Some(name.trim_end_matches(';').to_owned()) 51}
A direction index as the bot keeps it (ap_map.h:9: 1 U, 2 D, 3 L, 4 R).
An exit's direction: the bot's own, else the letter in its node name ("door U 0x84 ...").
Which way to lies from from, in eight compass points (y grows south),
or None when they are within a couple of tiles of each other.
80pub fn bearing(from: (u16, u16), to: (u16, u16)) -> Option<&'static str> { 81 let dx = i32::from(to.0) - i32::from(from.0); 82 let dy = i32::from(to.1) - i32::from(from.1); 83 if dx.abs().max(dy.abs()) < 24 { 84 return None; 85 } 86 let ns = if dy < 0 { "north" } else { "south" }; 87 let ew = if dx < 0 { "west" } else { "east" }; 88 Some(if dx.abs() > 2 * dy.abs() { 89 ew 90 } else if dy.abs() > 2 * dx.abs() { 91 ns 92 } else { 93 match (dy < 0, dx < 0) { 94 (true, true) => "north-west", 95 (true, false) => "north-east", 96 (false, true) => "south-west", 97 (false, false) => "south-east", 98 } 99 }) 100}
Where on its screen a point is, by thirds of the screen's width and height.
103pub fn zone(at: (u16, u16), bounds: ((u16, u16), (u16, u16))) -> Option<&'static str> { 104 let ((x0, y0), (x1, y1)) = bounds; 105 if x1 <= x0 || y1 <= y0 { 106 return None; 107 } 108 let third = |v: u16, lo: u16, hi: u16| { 109 let f = f64::from(v.saturating_sub(lo)) / f64::from(hi - lo); 110 if f < 1.0 / 3.0 { 0 } else if f < 2.0 / 3.0 { 1 } else { 2 } 111 }; 112 Some(match (third(at.1, y0, y1), third(at.0, x0, x1)) { 113 (0, 0) => "north-west corner", 114 (0, 1) => "north side", 115 (0, _) => "north-east corner", 116 (1, 0) => "west side", 117 (1, 1) => "middle", 118 (1, _) => "east side", 119 (_, 0) => "south-west corner", 120 (_, 1) => "south side", 121 (_, _) => "south-east corner", 122 }) 123}
125fn person(option: &GoalOption) -> &'static str { 126 match (option.sprite_type, option.sprite_subtype) { 127 (0x73, 0x100) => "Link's wounded uncle", 128 (0x73, _) => "the sage", 129 (0x16, _) => "Sahasrahla, the village elder", 130 (0x2C, _) => "the lumberjacks", 131 (0x31, _) => "the fortune teller", 132 _ => "the person", 133 } 134} 135 136fn on_links_screen(option: &GoalOption, here: &Situation) -> bool { 137 !here.link_screen.is_empty() && option.screen == here.link_screen 138}
The screen a goal is on, as a noun phrase.
141fn screen_phrase(option: &GoalOption, here: &Situation) -> String { 142 if on_links_screen(option, here) { 143 return "this screen".to_owned(); 144 } 145 match screen_name(&option.screen) { 146 Some(name) => name, 147 None if option.indoors => "an unnamed room".to_owned(), 148 None => "an unnamed stretch of overworld".to_owned(), 149 } 150}
An exit by the bot's own node name (ap_map.c:2737-3308) and direction: "north door" (a dungeon door, "door U 0x84 ..."), "entrance" (an overworld door into a building or cave, "door 0x3f"), "stairs up", "hole", "ledge", "north edge" (a screen edge, "0x148 U 1").
156fn exit_phrase(node: &str, direction: Option<&str>) -> String { 157 let mut words = node.split_whitespace(); 158 let first = words.next().unwrap_or(""); 159 let second = words.next().unwrap_or(""); 160 let lettered = matches!(second, "U" | "D" | "L" | "R"); 161 match (first, direction) { 162 ("door", Some(dir)) if lettered => format!("{dir} door"), 163 ("door", _) => "entrance".to_owned(), 164 ("stairs", _) if second == "U" => "stairs up".to_owned(), 165 ("stairs", _) => "stairs down".to_owned(), 166 ("hole", _) => "hole in the ground".to_owned(), 167 ("ledge", Some(dir)) => format!("{dir} ledge"), 168 ("ledge", None) => "ledge".to_owned(), 169 ("keyblock", _) => "locked block".to_owned(), 170 (_, Some(dir)) => format!("{dir} edge"), 171 (_, None) => "passage".to_owned(), 172 } 173}
The thing itself: "the pot", "the chest", "the north door", "Link's wounded uncle". Short enough to name one option inside another's sentence.
177fn thing(option: &GoalOption) -> String { 178 let node = option.node.as_str(); 179 let first = node.split_whitespace().next().unwrap_or(""); 180 match option.kind.as_str() { 181 "CHEST" if first == "big" => "the unopened big chest".to_owned(), 182 "CHEST" => "the unopened chest".to_owned(), 183 "PICKUP" => match (first, option.sprite_type) { 184 ("pot", _) => "the pot".to_owned(), 185 (_, 0xE4) => "the small key lying".to_owned(), 186 (_, 0xE5) => "the big key lying".to_owned(), 187 (_, 0xEB) => "the piece of heart lying".to_owned(), 188 _ => "the item lying".to_owned(), 189 }, 190 "NPC" => person(option).to_owned(), 191 "ITEM" if option.item.is_empty() => "the item".to_owned(), 192 "ITEM" => format!("the {}", option.item.to_lowercase()), 193 "SCRIPT" => format!("the known routine \"{}\"", node.strip_prefix("Script: ").unwrap_or(node)), 194 "EXPLORE" => format!("the {}", exit_phrase(node, direction(option))), 195 other => format!("the {other} goal \"{node}\""), 196 } 197}
The verb for doing it, and what doing it is for.
200fn verb(option: &GoalOption) -> (&'static str, &'static str) { 201 let first = option.node.split_whitespace().next().unwrap_or(""); 202 match option.kind.as_str() { 203 "CHEST" => ("Open", ""), 204 "PICKUP" if first == "pot" => ("Lift", " to see what is under it"), 205 "PICKUP" => ("Pick up", ""), 206 "NPC" => ("Talk to", ""), 207 "ITEM" => ("Collect", ""), 208 "SCRIPT" => ("Carry out", ""), 209 "EXPLORE" => ("Go through", ""), 210 _ => ("Pursue", ""), 211 } 212}
"the pot in the north-west corner of this screen": enough to name another option from inside a sentence.
Where a point on Link's screen is from him, in steps (16 pixels) along each axis: "6 steps west and 2 steps north of Link".
226pub fn offset(from: (u16, u16), to: (u16, u16)) -> Option<String> { 227 let dx = (i32::from(to.0) - i32::from(from.0)) / 16; 228 let dy = (i32::from(to.1) - i32::from(from.1)) / 16; 229 let axis = |d: i32, neg: &str, pos: &str| match d { 230 0 => None, 231 1 | -1 => Some(format!("1 step {}", if d < 0 { neg } else { pos })), 232 d => Some(format!("{} steps {}", d.abs(), if d < 0 { neg } else { pos })), 233 }; 234 match (axis(dx, "west", "east"), axis(dy, "north", "south")) { 235 (None, None) => None, 236 (Some(a), None) | (None, Some(a)) => Some(format!("{a} of Link")), 237 (Some(a), Some(b)) => Some(format!("{a} and {b} of Link")), 238 } 239}
Everything said about a goal except its distance. fine places a goal
on Link's screen by its offset from him in steps; otherwise by compass
point. Look-alikes are judged on the coarse form (a pot one tile from
another is the same choice), and the question carries the fine one.
245fn describe(options: &[GoalOption], i: usize, here: &Situation, fine: bool) -> String { 246 let option = &options[i]; 247 let (verb, purpose) = verb(option); 248 let mut s = format!("{verb} {}{purpose}", short(option, here)); 249 // Which way it lies from Link: only when both are in the same space (the 250 // bot keeps indoors and outdoors in different coordinate ranges). 251 if option.indoors == here.link_indoors { 252 let near = if fine && on_links_screen(option, here) { offset(here.link, option.at) } else { bearing(here.link, option.at).map(|b| format!("{b} of Link")) }; 253 match near { 254 Some(b) => s.push_str(&format!(", {b}")), 255 None if on_links_screen(option, here) => s.push_str(", right beside Link"), 256 None => {} 257 } 258 } 259 if !on_links_screen(option, here) && !option.via.is_empty() { 260 let dir = compass_of(option.via_direction); 261 s.push_str(&format!(", reached by leaving this screen through its {}", exit_phrase(&option.via, dir))); 262 match option.screens_on_path { 263 0 | 1 => {} 264 n => s.push_str(&format!(" and crossing {} screens", n)), 265 } 266 } 267 if option.kind == "EXPLORE" { 268 s.push_str(if option.adjacent_known { ", to somewhere already mapped" } else { ", to somewhere never visited" }); 269 } 270 if !option.item.is_empty() && option.kind != "ITEM" { 271 s.push_str(&format!("; the bot expects it holds the {}", option.item.to_lowercase())); 272 } 273 let ways: Vec<String> = (0..options.len()) 274 .filter(|&j| j != i && option.on_way_to & (1 << j) != 0) 275 .take(2) 276 .map(|j| short(&options[j], here)) 277 .collect(); 278 if !ways.is_empty() { 279 s.push_str(&format!("; it is on the way to {}", ways.join(" and to "))); 280 } 281 match option.attempts { 282 0 => {} 283 1 => s.push_str("; already tried once and failed"), 284 n => s.push_str(&format!("; already tried {n} times and failed")), 285 } 286 if !option.needs.is_empty() && option.needs != "[Any]" { 287 let needs = option.needs.trim_matches(|c| c == '[' || c == ']').to_lowercase().replace('_', " "); 288 s.push_str(&format!("; it needs the {needs}, which Link has")); 289 } 290 s 291}
The bot's path cost in Link-sized steps (16 pixels).
One option as Jev sees it: its sentence, and the bot's goals it stands for (indices into the offered goals; the first is the one pursued if it is chosen, and is always the lowest index, so upstream's pick stays 0).
The offered goals as distinct options. Goals that are the same kind of
thing on the same screen, said identically but for distance, collapse
into one offer REGARDLESS of how far apart their distances are: the
planner's own scoring already weighs distance, so asking Jev to break a
tie between two same-kind, same-place goals spends a question on
something the scorer already knows (frame 14674, two pots 27 and 45
steps apart, asked anyway - the same kind of goal, so nothing but
distance separated them, and distance is not Jev's to weigh). The
group's own representative (goals[0], the one pursued if this offer is
picked) is always the NEAREST of the merged goals, kept up to date as
each candidate streams in - "not asked: same kind, nearest taken". The
result's sentences are still pairwise different.
327pub fn offers(options: &[GoalOption], here: &Situation) -> Vec<Offer> { 328 struct Group { 329 description: String, 330 screen_id: u16, 331 steps: i32, 332 goals: Vec<usize>, 333 } 334 let mut groups: Vec<Group> = Vec::new(); 335 for i in 0..options.len() { 336 let description = describe(options, i, here, false); 337 let steps = steps(&options[i]); 338 let screen_id = options[i].screen_id; 339 match groups.iter_mut().find(|g| g.description == description && g.screen_id == screen_id) { 340 Some(g) => { 341 g.goals.push(i); 342 if steps < g.steps { 343 g.steps = steps; 344 let pos = g.goals.len() - 1; 345 g.goals.swap(0, pos); 346 } 347 } 348 None => groups.push(Group { description, screen_id, steps, goals: vec![i] }), 349 } 350 } 351 let mut out: Vec<Offer> = groups 352 .iter() 353 .map(|g| Offer { 354 sentence: format!("{}{}", describe(options, g.goals[0], here, true), distance_clause(g.steps)), 355 goals: g.goals.clone(), 356 }) 357 .collect(); 358 // Same coarse words and same screen were merged above regardless of 359 // distance, and the fine words only add to the coarse ones, so equal 360 // sentences can only be the same description on two different screens 361 // the words cannot name (two unnamed rooms): name them by the bot's own 362 // screen number. 363 let clashing: Vec<usize> = (0..out.len()) 364 .filter(|&i| out.iter().enumerate().any(|(j, o)| j != i && o.sentence == out[i].sentence)) 365 .collect(); 366 for i in clashing { 367 let id = options[out[i].goals[0]].screen_id; 368 out[i].sentence = format!("{} (It is on the bot's screen {id:#06x}.)", out[i].sentence.trim_end_matches('.')); 369 } 370 out 371}
373#[cfg(test)] 374mod tests { 375 use super::*; 376 377 const YARD: &str = "Castle Yard 600,600 x 9ff,9ff"; 378 379 fn here() -> Situation { 380 Situation { 381 link_screen: YARD.into(), 382 link_indoors: false, 383 has_sword: true, 384 link: (0x7f8, 0x832), 385 screen: ((0x600, 0x600), (0x9ff, 0x9ff)), 386 } 387 } 388 389 fn option(kind: &str, node: &str, screen: &str, at: (u16, u16), distance: i32) -> GoalOption { 390 GoalOption { 391 kind: kind.into(), 392 node: node.into(), 393 screen: screen.into(), 394 screen_id: 0x0606, 395 indoors: false, 396 direction: 0, 397 sprite_type: 0, 398 sprite_subtype: 0, 399 item: String::new(), 400 needs: "[Any]".into(), 401 score: distance, 402 distance, 403 attempts: 0, 404 adjacent_known: false, 405 at, 406 screen_bounds: ((0x600, 0x600), (0x9ff, 0x9ff)), 407 via: String::new(), 408 via_direction: 0, 409 screens_on_path: 0, 410 on_way_to: 0, 411 } 412 } 413 414 fn distinct(offers: &[Offer]) { 415 let set: std::collections::BTreeSet<_> = offers.iter().map(|o| &o.sentence).collect(); 416 assert_eq!(set.len(), offers.len(), "{offers:#?}"); 417 } 418 419 #[test] 420 fn screen_names_lose_their_bounds() { 421 assert_eq!(screen_name("Well Uncle ^ 0 6a00,a00 x 6bff,aff").as_deref(), Some("Well Uncle")); 422 assert_eq!(screen_name("Castle Yard 600,600 x 9ff,9ff").as_deref(), Some("Castle Yard")); 423 assert_eq!(screen_name("HC First Key ^ 5200,e00 x 53ff,eff").as_deref(), Some("Hyrule Castle First Key")); 424 assert_eq!(screen_name("0x0c50 v 0 (20480 0x5000, 3072 0x0c00) x (20991"), None); 425 }
The question in run/window/jev-5.png: two pots side by side, 62 steps
away, which read identically. They are one choice, and with nothing
else on offer there is no question at all.
430 #[test] 431 fn two_pots_side_by_side_are_one_choice() { 432 let a = option("PICKUP", "pot 0x7e0,0x6f0", YARD, (0x7e0, 0x6f0), 990); 433 let b = option("PICKUP", "pot 0x7f0,0x6f0", YARD, (0x7f0, 0x6f0), 1000); 434 let offers = offers(&[a, b], &here()); 435 assert_eq!(offers.len(), 1, "{offers:#?}"); 436 assert_eq!(offers[0].goals, vec![0, 1]); 437 assert!(offers[0].sentence.starts_with("Lift the pot in the north side of this screen"), "{}", offers[0].sentence); 438 assert!(offers[0].sentence.contains("north of Link"), "{}", offers[0].sentence); 439 }
441 #[test] 442 fn pots_in_different_places_are_told_apart() { 443 let a = option("PICKUP", "pot a", YARD, (0x640, 0x640), 1000); 444 let b = option("PICKUP", "pot b", YARD, (0x9c0, 0x640), 1000); 445 let offers = offers(&[a, b], &here()); 446 assert_eq!(offers.len(), 2); 447 assert!(offers[0].sentence.contains("north-west corner") && offers[1].sentence.contains("north-east corner"), "{offers:#?}"); 448 distinct(&offers); 449 } 450 451 #[test] 452 fn pots_close_together_are_placed_by_steps() { 453 let a = option("PICKUP", "pot a", YARD, (0x7c0, 0x800), 300); 454 let b = option("PICKUP", "pot b", YARD, (0x790, 0x820), 500); 455 let offers = offers(&[a, b], &here()); 456 assert_eq!(offers.len(), 2); 457 assert!(offers[0].sentence.contains("3 steps west and 3 steps north of Link"), "{}", offers[0].sentence); 458 assert!(offers[1].sentence.contains("6 steps west and 1 step north of Link"), "{}", offers[1].sentence); 459 } 460 461 #[test] 462 fn exits_are_named_by_kind() { 463 assert_eq!(exit_phrase("door U 0x84 DOOR|NODE NORM", Some("north")), "north door"); 464 assert_eq!(exit_phrase("door 0x3f", None), "entrance"); 465 assert_eq!(exit_phrase("0x148 U 1", Some("north")), "north edge"); 466 assert_eq!(exit_phrase("stairs U 0x1f", Some("north")), "stairs up"); 467 assert_eq!(exit_phrase("hole 0x05", None), "hole in the ground"); 468 }
The scorer already weighs distance, so two same-kind, same-place goals collapse to one offer no matter HOW far apart their distances are - only a different kind or place is worth a question. Order doesn't matter: the nearer one is always the representative.
474 #[test] 475 fn same_place_far_apart_in_distance_is_still_collapsed_and_the_nearer_is_taken() { 476 let a = option("PICKUP", "pot a", YARD, (0x640, 0x640), 900); 477 let b = option("PICKUP", "pot b", YARD, (0x650, 0x650), 200); 478 let offers = offers(&[a, b], &here()); 479 assert_eq!(offers.len(), 1, "{offers:#?}"); 480 assert_eq!(offers[0].goals, vec![1, 0], "the nearer goal (b, index 1) must be the representative"); 481 }
483 #[test] 484 fn two_unnamed_rooms_are_named_by_number() { 485 let mut a = option("CHEST", "chest 0", "0x0c50 v 0 (1", (0x5100, 0xc80), 3000); 486 let mut b = option("CHEST", "chest 0", "0x0c52 v 0 (1", (0x5100, 0xc80), 3000); 487 for (o, id) in [(&mut a, 0x0c50), (&mut b, 0x0c52)] { 488 o.indoors = true; 489 o.screen_id = id; 490 o.screen_bounds = ((0x5000, 0xc00), (0x51ff, 0xcff)); 491 } 492 let offers = offers(&[a, b], &here()); 493 assert_eq!(offers.len(), 2, "{offers:#?}"); 494 distinct(&offers); 495 assert!(offers[1].sentence.contains("0x0c52"), "{}", offers[1].sentence); 496 } 497 498 #[test] 499 fn sentences_say_what_where_and_the_way() { 500 let mut uncle = option("NPC", "sprite 0x73.0x100 TALK|NODE", "Well Uncle ^ 0 6a00,a00 x 6bff,aff", (0x6b00, 0xa80), 3000); 501 uncle.indoors = true; 502 uncle.sprite_type = 0x73; 503 uncle.sprite_subtype = 0x100; 504 uncle.item = "SWORD".into(); 505 uncle.screen_id = 0x0a6a; 506 uncle.screen_bounds = ((0x6a00, 0xa00), (0x6bff, 0xaff)); 507 uncle.via = "door U 0x84 DOOR|NODE NORM".into(); 508 uncle.via_direction = 1; 509 uncle.screens_on_path = 3; 510 let mut door = option("EXPLORE", "door U 0x84 DOOR|NODE NORM", YARD, (0x800, 0x610), 700); 511 door.direction = 1; 512 door.attempts = 2; 513 door.on_way_to = 0b1; 514 let said = offers(&[uncle, door], &here()); 515 let s0 = &said[0].sentence; 516 assert!(s0.starts_with("Talk to Link's wounded uncle in the"), "{s0}"); 517 assert!(s0.contains("of Well Uncle") && s0.contains("sword"), "{s0}"); 518 assert!(s0.contains("leaving this screen through its north door and crossing 3 screens"), "{s0}"); 519 let s1 = &said[1].sentence; 520 assert!(s1.starts_with("Go through the north door in the north side of this screen, 34 steps north of Link"), "{s1}"); 521 assert!(s1.contains("on the way to Link's wounded uncle") && s1.contains("tried 2 times"), "{s1}"); 522 distinct(&said); 523 }
Every question the window and the headless runs have logged: the options reconstructed from the log cannot be, but the rule can - no two offers built from any set of goals share a sentence. Exercised over a grid of look-alike goals.
529 #[test] 530 fn no_two_offers_ever_read_alike() { 531 let kinds = [("PICKUP", "pot x"), ("PICKUP", "bush x"), ("CHEST", "chest 0"), ("EXPLORE", "door U 0x84")]; 532 let mut all = Vec::new(); 533 for (k, (kind, node)) in kinds.iter().enumerate() { 534 for d in [100, 104, 500, 520, 2000] { 535 for (x, y) in [(0x640u16, 0x640u16), (0x648, 0x640), (0x800, 0x800)] { 536 let mut o = option(kind, node, YARD, (x, y), d); 537 o.screen_id = 0x0606 + (k as u16 % 2); 538 all.push(o); 539 } 540 } 541 } 542 for window in all.windows(6) { 543 distinct(&offers(window, &here())); 544 } 545 for chunk in all.chunks(6) { 546 distinct(&offers(chunk, &here())); 547 } 548 } 549}