The planners: search, greedy, type 1, type 15, random walk, spiral and the rest
Purpose
Section titled “Purpose”A planner takes the context PathPlan built and writes the path’s points. Its input is the live grid and the context; its output is the
point list and a count. This page holds each planner a stock caller reaches, and the others in short, as pseudocode with its cell reads and its draws. Which caller
reaches which type, what each count tests and the grid they read are the overview.
What the tags cover. A [C] by emulation covers the code’s map from the bytes it reads, not what the game stores there or when it runs: compare the record byte for byte against each model over declared images, with controls. A [C] by the game’s plans covers the types and outcomes overview § G1 lists, given the live cells. A branch that only the emulation reached says so.
Entry points
Section titled “Entry points”| Type | Tag |
|---|---|
| 2, 5, 6, 13 | [C] |
| 7 | [C] |
| 8 | [C] |
| 9 | [C] |
| 1 | [C]; in the game through type 7’s switch |
| 15 | [C] |
| 4, 10, 14 | [C] |
| 10 | [C] |
| 14 | [C] |
| 4 | [C] |
| 0, 16 | [C] by emulation only |
| 3, 11, 12, client only | [C] by emulation only |
Inputs
Section titled “Inputs”Tables
Section titled “Tables”These sit in the image’s data. A planner can’t be written without them: the values or their exact rules, widths and index forms are in PathDirTables, except g_PathSearchStep8 (the same 16 values as g_PathStep8Long), g_PathSearchDrawAdd and g_SineTable, which the rows below state.
| Shape | Used for |
|---|---|
i32[25][3] by PathDirCell |
the three directions to a target; column 0 is the octant |
| 8 × (dx, dy) i32, read as words | one step: (1,0), (1,1), (0,1), (−1,1), (−1,0), (−1,−1), (0,−1), (1,−1) |
| 8 × (dx, dy) i32, read as words | the same steps |
i32[64] by dx + 8 dy |
the near distance (A3) |
i32[8][8] |
the search’s turns (L3) |
i32[32]: −2..2 six times, then −1, 1 |
type 16’s addend (L4) |
| 16 × (dx, dy) i32, read as words: (0,−1), (1,−1), … twice | a follower’s step |
centred i32, index 3 dy + dx |
a follower’s first direction |
i32[16] each |
the followers’ turns and next directions |
f32[512], within 1.8e-07 of sin(2πk/512) |
the spiral |
Runtime state
Section titled “Runtime state”The context ctx and the record path are overview § Runtime state. A planner returns its count; PathPlan stores it in +0x28.
What decides each planner, [C] by emulation against the whole record. An undeclared field has no traced read: ctx +0x0C, +0x10, +0x1C, +0x20, +0x24 in the short planners, ctx.limit, ctx.size and +0x10 in the search, ctx.limit, ctx.refresh and +0x91 in type 1. The table doesn’t list the asserts’ reads.
| Planner | Cells read under | Limit | Other |
|---|---|---|---|
| Greedy’s first line (A4, A5) | path +0x1C, +0x48, +0x50, from the position |
— | +0x7C, +0x3C, the unit’s type |
| Greedy’s walk (A6) | ctx.room, ctx.pattern, ctx.testMask, from ctx.start |
ctx.limit |
ctx.refresh, +0x98 |
| Knockback | as the first line, but from ctx.start |
— | +0x90, +0x58 |
| Type 1 | ctx.room, ctx.pattern, ctx.testMask |
none | +0x58 |
| Type 15 | ctx.room, ctx.pattern, ctx.testMask |
the byte +0x91, not ctx.limit |
+0x58 |
| Search | ctx.room, ctx.pattern, ctx.testMask |
none: ctx.b1C is the bound |
ctx.refresh, ctx.type, ctx.b1C, ctx.troom, and path +0x30 under type 16 |
| Random walk, spiral | no cell | the byte +0x91; the spiral neither |
the position; the target (walk) |
PathPlan writes both sets from the same fields, and a planner does not change +0x48 or +0x50, so in the game the line’s and the walk’s inputs differ only in where they start. [I]
Constants
Section titled “Constants”| Name | Value | Tag |
|---|---|---|
| straight step, diagonal step | 2, 3 | [C] (controls cost) |
h |
2 max(|dx|, |dy|) + min(|dx|, |dy|) |
[C] (controls h, the same runs) |
| type 1 switch | dx² + dy² ≤ 324 |
[C] (control le325 18 cases) |
| type 1 pool | 200 nodes | [C] (control pool) |
| search store | 900 nodes, 10 000 tries a pass, 50 000 cells | [C] (controls nodes, passes, families grid, over) |
| type 15 minimum limit under a target unit | 40 | [C] (control lim40) |
| random walk step | 2 subtiles | [C] (control step1) |
| spiral | r += 0x2580, a += 16, 77 points |
[C] (the structure reproduces all 260 stock type-14 plans; steps 0x2500, 0x2600 and angles 15, 17 each fail all 260; it agrees under the emulator’s rounding too, control swap) |
Algorithm
Section titled “Algorithm”A. What the planners share
Section titled “A. What the planners share”A1. A cell read: Blocked
Section titled “A1. A cell read: Blocked”Blocked(hint, x, y, pattern, mask) ← COLL_PatternTestBool(hint, x, y, pattern, mask) [C] pattern 0: the cell (x, y) & mask; no room: blocked pattern 1, 3, 5: the plus, each cell looked up with the centre's room as hint; no centre room, or a room one cell wide or high: blocked pattern 2, 4: the 3×3 rectangle, split across rooms any other: blocked- A1. [C] The cells and masks are drlg/collision §§ D, E. The room is a hint for every step of a plan, so a cell in a room outside that room’s near list is “no room” and blocked, however large the search’s rectangle.
- A1. [C] The grid is the live one, with the unit’s own marks already off: overview § F1.
A2. Directions
Section titled “A2. Directions”PathDirCell(a, b) → i32: [C] (control sign 60) dx: i32 ← b.x − a.x; dy: i32 ← b.y − a.y if |dx| ≥ 2|dy|: dy ← (dy < 0) ? −1 : dy & 1 ; & 1, not a sign else if |dy| ≥ 2|dx|: dx ← (dx < 0) ? −1 : dx & 1 dx ← clamp(dx, −2, 2); dy ← clamp(dy, −2, 2) return 5 dx + dy + 12
PathDirRow(a, b) ← the three of g_DirOctant[PathDirCell(a, b)] [C]PathDirOctant(a, b) ← the first of them [C]-
A2. [C]
g_DirOctantholds 0..7 only (75 dwords, read with a second tool), so the assert 0x4C of a third direction 255 cannot fire from these callers. -
A2. [C] The octant by cases.
PathDirOctant(a, b)equals the following description on all 25 cells, compared element by element with column 0 ofg_DirOctantas the image holds it (25 of 25): withdx'anddy'the cell’s two terms after the cut and clamp ofPathDirCell(each −2..2), a term whose double is at most the other term’s size is set to 0; the octant is then the index of the step ofg_PathSearchStep8whose(dx, dy)has the signs of what is left, in the steps’ order under Inputs (0 for(1,0), 1 for(1,1), on to 7 for(1,−1)); the cell(0, 0)gives 6. So(±2, ±1)and(±1, ±2)take the straight direction (at 2 : 1 the straight step wins), and(±1, ±1)and(±2, ±2)the diagonal. The equality holds on the image’s elements and says nothing of how the table was made; the table stays listed, and columns 1 and 2 (the other two directions ofPathDirRow) are not described here.
A3. Distances
Section titled “A3. Distances”PathOctile(a, b): dx, dy absolute; 2 max(dx, dy) + min(dx, dy) [C]PathDistNear(a, b): [C] (control dist 7) dx, dy absolute if dx < 8 and dy < 8: v ← g_PathDistNear[dx + 8 dy]; return (v < 0) ? 0 : v + 1 return (dx > dy) ? dy + 2 dx : dx + 2 dyA4. The line: PathLineFree
Section titled “A4. The line: PathLineFree”PathLineFree(path, s, t) → (free, point): [C] (all of A4) Blocked here is under path.room, path.pattern, path.testMask dx: i32 ← t.x − s.x; dy ← t.y − s.y; ax ← |dx| + 1; ay ← |dy| + 1 px ← (dx ≥ 0) ? 1 : −1; py ← (dy ≥ 0) ? 1 : −1 (x, y) ← s; last ← s if ax > ay: err ← ay loop: x += px; if Blocked(x, y): return (0, last) err += ay if err ≥ ax: y += py; err −= ax if err > 0 and Blocked(x, y): return (0, last) last ← (x, y) if x = t.x: return (1, t) if ax < ay: the same with the axes swapped if s.x = t.x: return (1, t) loop: ; a diagonal x += px; y += py; if Blocked(x, y): return (0, last) last ← (x, y) if x = t.x: return (1, t)Coordinates are u16. point is the last point wholly free.
A5. The first line: PathFirstLine
Section titled “A5. The first line: PathFirstLine”PathFirstLine(path, pt) → (reached, pt): [C] unit neither player nor monster: assert 0x144; path type 4: assert 0x145 ; [C] 43 and 25 cases, at their return site pt.x = 0: assert 0x146; pt.y = 0: assert 0x147 ; [I] read, not run if path +0x7C = 0: return (0, the position's subtile) PathAimNextPoint(path, 1; 1) ; over the record, points[0] the target, +0x28 = 0 if path +0x7C = 0: return (0, the position's subtile) ; the target is the position return PathLineFree(path, the position's subtile, pt)- A5. [C] The planner aims the path before its own points exist, which writes the vector, the step and the facing, and the speed gates the line. (path/overview § H has the aim and the facing, anim/movement § B the step that follows;
PathAimNextPoint)
A6. Three directions: PathTry3Dirs
Section titled “A6. Three directions: PathTry3Dirs”PathTry3Dirs(ctx, cur, dirs) → d or none: [C] (control order) for d in dirs, in order: if not Blocked(ctx.room, cur + g_PathStep8Long[d], ctx.pattern, ctx.testMask): return d return noneB. The greedy planner: types 2 and 13
Section titled “B. The greedy planner: types 2 and 13”PathPlanGreedy(ctx) → n: [C] (greedy 600, gbound 30; all of B) 1. +0x24 ← 0; +0x28 ← 0 2. if path.+0x98 ≠ 0: return PathWalkParam98(ctx) 3. points[0] ← ctx.target 4. (reached, pt) ← PathFirstLine(path, ctx.target) 5. if reached or PathDistNear(pt, ctx.target) ≤ ctx.refresh: points[0] ← pt; +0x28 ← 1; return 1 6. cur ← ctx.start; n: i32 ← 0 7. if pt ≠ ctx.start: points[0] ← pt; n ← 1; cur ← pt 8. limit: i32 ← ctx.limit; prev ← 0xFF; turned ← 0; i: i32 ← 0 9. while i < limit: ; the test is once at entry and at step 1610. if cur = ctx.target: if not turned and i ≠ 0: points[n++] ← cur break11. turned ← 012. d ← PathTry3Dirs(ctx, cur, PathDirRow(cur, ctx.target))13. if d is none or ((d − 4) & 7) = prev: ; blocked, or a reversal if i ≠ 0: points[n++] ← cur break14. next ← cur + g_PathStep8Long[d] ; u16 adds if d ≠ prev: if cur ≠ ctx.start: points[n++] ← cur turned ← 115. cur ← next; prev ← d; i ← i + 116. if i ≥ limit: if not turned: points[n++] ← cur break17. +0x28 ← n; return n- B. [C] A walk whose last step turned ends one step short: when the step that reaches the target or the limit changed direction, only the corner is written. (control
noflag) - B. [C] The first point is written twice when the walk turns at once, since
curequals it and is not the start. - B. [C] A reversal ends the walk, with the point reached written. (control
rev, 2 cases; 6; 1) - B. [C] Limit 0 writes nothing past the line’s end. At most
ctx.limit + 1points: 78 at limit 77, every slot used, no write past it. (familygbound) - B. [C] Types 2 and 13 are one plan.
C. The +0x98 walk: types 5 and 6
Section titled “C. The +0x98 walk: types 5 and 6”PathWalkParam98(ctx) → n: [C] (g98 300, values 2, −2, −4, 1; all of C) n: i32 ← +0x28 ; appends cur ← ctx.start; prev ← 0xFF; turned ← 0; i: i32 ← 0; limit: i32 ← ctx.limit while i < limit: if cur = ctx.target: if not turned and i ≠ 0: points[n++] ← cur break dirs ← (PathDirRow(cur, ctx.target)[k] + path.+0x98) & 7, k = 0, 1, 2 turned ← 0 d ← PathTry3Dirs(ctx, cur, dirs) if d is none or ((d − 4) & 7) = prev: if i ≠ 0: points[n++] ← cur break next ← cur + g_PathStep8Long[d] if d ≠ prev: points[n++] ← cur; turned ← 1 ; always, so the first point is the start cur ← next; prev ← d; i ← i + 1 if i ≥ limit: if not turned: points[n++] ← cur break +0x28 ← n; return n- C. [C] No line first and no refresh test: unlike § B it starts at
ctx.start, and the start is its first point. At mostctx.limitpoints from an empty list. (controlsparam0164,order158) - C. [I] With
+0x98= 2 or −2 the three directions are the row’s turned by 90°: the walk goes sideways to the line to the target rather than to it. - C. [C] In the game these plans hold 6 points at most; the walk’s other branches rest on the emulation. (
2026-11-04-path-2-check.txt)
D. Greedy-near: type 7
Section titled “D. Greedy-near: type 7”PathPlanGreedyNear(ctx) → n: [C] (near 480; all of D) 1. +0x24 ← 0; +0x28 ← 0 2. n ← PathPlanGreedy(ctx) 3. if n ≠ 0: p ← points[n − 1] if PathDistNear(p, ctx.target) ≤ ctx.refresh and p ≠ ctx.start: return n 4. d2: i32 ← (s.x − t.x)² + (s.y − t.y)² ; ctx.start to ctx.target if d2 > 324: return n 5. r ← PathPlanType1(ctx); if r ≠ 0: return r 6. if n = 0: return 0 7. return PathPlanGreedy(ctx) ; rewrites the list; repeats the first greedy's aim- D. [C] A player plans this type, and when greedy stops short within the bound the walk falls to type 1: of the players’ type-7 plans greedy stopped short in 462, the 461 at
d²≤ 324 (all ≤ 317) switched to type 1, the 1 atd²> 360 did not. [I] 324 is 18 subtiles on an axis: (18, 0) passes, (18, 1) at 325 doesn’t; no short plan fell atd²318–360, so the edge itself is read, not logged. - D. [C] In the game: 270 + 554 plans took the switch, of 2 725 + 4 355 that reached the planner. The 324 boundary and the retry at step 7 separate no plan in either run (
le325,noretry): they rest on the emulation.
E. The knockback planner: type 8
Section titled “E. The knockback planner: type 8”PathPlanKnockback(ctx) → 0 or 1: [C] (knock 300, controls k 124, floor 41; all of E) 1. k: i32 ← (path.+0x90 >> 1) + 1 2. if t ← path.+0x58: (tx, ty) ← t's static dwords +0x0C, +0x10 for types 2, 4, 5; else its path words +0x02, +0x06, 0 without a path dx: i32 ← s.x − tx; dy ← s.y − ty; m ← max(|dx|, |dy|) if m ≠ 0: dx ← k × dx ÷ m; dy ← k × dy ÷ m ; signed idiv, truncating toward zero pt ← (s.x + dx, s.y + dy) ; u16 adds else: pt ← ctx.target 3. points[0] ← pt 4. (free, q) ← PathLineFree(path, ctx.start, pt); if not free: pt ← q ; from ctx.start, not the position 5. PathSetTargetPoint(path, pt); path.+0x58 ← 0 ; on either outcome 6. if pt = ctx.start: return 0 7. points[0] ← pt; +0x28 ← 1; return 1- E. [C] The plan clears the path’s target unit and leaves the point as its target. It doesn’t write
+0x24;PathPlanhas. - E. [I] A unit standing on its target has
m= 0, andptis the start: a return of 0.k≤ 128 and the pushed point are not tested beyond the line. - E. [C] The
+0x90values and the start are anim/movement § E; its adjustment is A4. In the game, monsters’ plans with 2 player plans in the second run.
F. The one point: type 9
Section titled “F. The one point: type 9”PathPlanOnePoint(ctx) → 0 or 1: [C] (onept 200, 62 one point, 70 refused, 68 at the asserts) +0x24 ← 0; points[0] ← ctx.target (_, pt) ← PathFirstLine(path, ctx.target) if pt = ctx.start: return 0 ; +0x28 untouched points[0] ← pt; +0x28 ← 1; return 1- F. [C] In the game 54 + 346 plans of the player’s own Leap or Leap Attack, one branch, one point, no grid needed in the first run’s 54. The refusal branch rests on the emulation.
G. Type 1: best-first over a pool of 200
Section titled “G. Type 1: best-first over a pool of 200”Reach and evidence: overview § G2. Emulated to its return (t1real 400, t1syn 240, t1stair 40), in the game through type 7’s switch.
PathPlanType1(ctx) → n: [C] (all of G) 1. if path.+0x58 ≠ 0: ; control nostart test (±2, ±2) then the axes, from the target, in this order: (−2,−2), (−2,+2), (+2,−2), (+2,+2), (−2,0), (0,−2), (+2,0), (0,+2) if all 8 are Blocked: return 0 ; nothing else written 2. root: pt ← ctx.start, g ← 0, h ← f ← PathOctile(start, target), no parent; count: i32 ← 1; open ← [root] 3. best ← none 4. while open not empty: 5. n ← the head of open; move it to closed 6. if best is none or (s16)n.h < (s16)best.h or (n.h = best.h and (s16)n.g > (s16)best.g + 5): best ← n 7. if n.h = 0: break 8. for (a, b) in (−1,−1), (−1,+1), (+1,−1), (+1,+1), (−1,0), (0,−1), (+1,0), (0,+1): 9. p ← n.pt + (a, b) ; u1610. if Blocked(ctx.room, p, ctx.pattern, ctx.testMask): continue11. g: u16 ← n.g + ((p.x = n.x or p.y = n.y) ? 2 : 3)12. o ← the open node at p13. if o exists: if n has fewer than 8 links: link n → o if (s16)g < (s16)o.g: o.parent ← n; o.g ← g; o.f ← g + o.h ; o stays where it lies in the list continue14. o ← the closed node at p15. if o exists: if n has fewer than 8 links: link n → o if (s16)g < (s16)o.g: o.parent ← n; o.g ← g; o.f ← g + o.h; Propagate(o) continue16. if count ≥ 200: end the search now ; the 201st request; go to 19 with best17. count ← count + 1 o ← new: parent n, g, pt p, h ← PathOctile(p, target), f ← g + h18. insert o into open before the first node with (s16)f not less than its own; link n → o19. return Reduce(best)
Propagate(o): ; a LIFO stack, 200 slots push o while the stack is not empty: u ← pop for each link u → v, in link order: gg: u16 ← u.g + cost(u.pt, v.pt) ; 2 or 3 as step 11 if (s16)gg < (s16)v.g: v.parent ← u; v.g ← gg; v.f ← gg + v.h; push v
Reduce(best) → n: buf ← []; prev ← (−2, −2); m ← best while m and |buf| < 78: if m.parent: step ← m.pt − m.parent.pt; if step ≠ prev: append m.pt to buf; prev ← step m ← m.parent if |buf| is not in 1..77: return 0 ; the list untouched copy buf reversed to points; return |buf| ; neither +0x24 nor +0x28- G. [C] The diagonals come first and no corner test applies: a diagonal between two blocked cells is taken. (control
offs) - G. [C] Among equal
fthe newest comes first, and an open node given a bettergis not moved. (controlresort19 and 103) - G. [C] A plan past the pool ends short with what it has,
bestincluded, even when no route reached the target: 60 oft1realend at the pool, 2 of them returning 0, and 108 oft1syn. (controlpool) - G. [C]
bestis the leasth, and on equalha later node withgmore than 5 above replaces it. Controlgt0separates only 4 cases of each family. - G. [C] The start is never kept; a single-segment route gives one point, unlike the search. A raw 78 returns 0 (
t1stair: 15 cases past 77,maxret77). (controlsmax77,min2) - G. [C] Not read:
ctx.limit,ctx.refresh,+0x91. A type-1 route has no length limit but its pool. The two hash tables only place nodes in buckets: the model holds no hash and matches. (data) - G. [I] A node is expanded once and has 8 neighbours, so the code’s silent drop of a ninth link is not reached.
- G. [I] The model’s propagation stack reached 3 on the first run’s 270 plans and 23 on the emulation’s cases, against 200 slots; neither is the game’s own depth, which nothing logs.
H. Type 15: a line with two wall followers
Section titled “H. Type 15: a line with two wall followers”PathPlanType15(ctx) → n: [C] (t15real 400, t15syn 300, t15stair 40; all of H unless noted) 1. unit neither player nor monster: assert 0x2AD ; [I] read, not run 2. lim: i32 ← the byte path.+0x91; if path.+0x58 ≠ 0 and lim < 40: lim ← 40 3. (L, axis) ← T15Line(ctx.start, ctx.target, lim); n ← |L| 4. if n ≤ 2: return 0 5. cur ← ctx.start; i ← 0 6. loop: if Blocked(ctx.room, L[i], ctx.pattern, ctx.testMask): r ← T15Follow(ctx, L, cur, &i, &n, lim − i, axis) if r = 0: return T15Reduce(ctx.start, L, i) cur ← L[i]; i ← i + 1 ; at i = n after a follow, a read past the written list, without effect if i ≥ n: break 7. return (n ≠ 0) ? T15Reduce(ctx.start, L, n) : 0
T15Line(a, b, lim) → (cells after a, axis): dx ← b.x − a.x; dy ← b.y − a.y; px, py their signs (≥ 0 → +1); dx, dy absolute; err ← 0 axis: y major: 2 for increasing, 0 decreasing; x major: 1 for increasing, 3 decreasing x is major when dy = 0, or dx ≠ 0 and dx ≥ dy ; equal dx, dy takes x no cells when the major difference is 0, or above lim − 1 (the axis still set) for each major step: major += sign; err += minor difference if err ≥ major difference: err −= it; minor += sign append (x, y)
T15Follow(ctx, L, cur, &i, &n, lim4, axis) → r: p ← L[i]; q ← g_T15DirFromStep[3 (p.y − cur.y) + (p.x − cur.x)] w0: dir q + 1, Turn g_T15TurnA, Next g_T15NextA; w1: dir q + 7, Turn g_T15TurnB, Next g_T15NextB ; not masked: up to 14, the tables have 16 each: pos ← cur, cnt ← 0, list empty, mark ← 0, stop ← 0; a ← w0; b ← w1 loop: if a.stop = 0 and not WalkStep(a): a.stop ← 1 if a.stop = 0: v ← a.next's advance along axis from cur, when a.cnt ≥ 1 ; axis 0: cur.y − next.y; 1: next.x − cur.x; 2: next.y − cur.y; 3: cur.x − next.x if v > 0 and i + v − 1 < n and L[i + v − 1] = a.next: ; back on the line: the splice lim4 ≤ a.cnt: assert 0x1BB ; [I] read, not reached append a.next to a.list; a.cnt += 1 idx ← i + v − 1; d ← i − idx − 1 + a.cnt; new ← idx + d move L[idx + 1 ..< n] to start at new + 1; copy a.list to L[i ..< i + a.cnt] n ← n + d; i ← new + 1; return a.cnt if b.cnt > 1: if a.mark ≠ 0: if a.next = b.list[a.mark − 2]: n ← i; return 0 ; met the other's trail again: the line before the block a.mark ← 0 if a.next = b.pos: a.mark ← b.cnt append a.next to a.list; a.cnt += 1; a.pos ← a.next; a.dir ← a.Next[a.dir] if (lim4 − n) − 1 ≤ a.cnt: a.stop ← 1 if a.mark = 0: swap a, b ; they alternate, except while one holds its mark if w0.stop or w1.stop: break if lim4 > 80: n ← i; return 0 last(w) ← w.list[w.cnt − 1] when w.cnt ≠ 0, else w.stop read as a point d0, d1, dq ← the squared distances to ctx.target of last(w0), last(w1), ctx.start w ← (d0 < d1) ? w0 : w1 if dq < the chosen d: return 0 ; nothing changed copy w.list to L[i ..< i + w.cnt]; i ← i + w.cnt; n ← i return a.cnt
WalkStep(w) → free: up to four tries: w.next ← w.pos + g_T15Step[w.dir]; if not Blocked(w.next): return 1 before tries 2, 3, 4: w.dir ← w.Turn[w.dir] return 0
T15Reduce(start, L, n) → count: n = 0: return 0; n = 1: points[0] ← L[0]; return 1 (lx, ly) ← L[0] − start; o ← 0; run ← 0 for j in 0 ..< n − 1: (dx, dy) ← L[j + 1] − L[j] if dx = lx and dy = ly: run ← run + 1; lx ← dx ; dropped else if run < 1 and lx ≠ dx and ly ≠ dy: run ← 1; lx ← −2 ; one kink dropped else: points[o++] ← L[j]; run ← 0; lx ← dx ly ← dy points[o++] ← L[n − 1]; return o- H. [C] The outcomes are by
OUTCOMES: clear line, refused at 2 points or fewer, follow, follow with splice, truncation, loop. Controlslim4032 and 7,lim18120 and 150,min24 and 1,reduce171, 230, 34,wswap29, 99, 2,noswap28, 66, 18. In the gamewswap627,noswap498,reduce858 on the second run. - H. [C] Most plans end at 0: 2 273 of the second run’s 3 309, the planner’s own refusal or a free line of too few cells. (
2026-11-04-path-2-check.txt) - H. [C]
T15Reducedrops a point whose step equals the last, and, with nothing dropped since, a point where both coordinates of the step change, after which the next point is kept. So E, S, E, S loses every other corner, and E, SE, E, SE, a line’s own steps, which share a coordinate, loses none (review-s54/literal.txt). (controlreduce) - H. [I] A follower count of 0 reads as a point:
lastis then the stop word, as a point of (1, 0) or (0, 0). No control separates it. - H. [C]
limabove 80 is reached only with bytes no path-module writer gives (lim50, 4 emulated cases): every path-module writer of+0x91and every immediate gives at most 77. [I] That the 13 register dword stores at+0x90outside the path module (bases not traced) give no more is not read. A target unit with+0x91below 40 is a monster with its creation’s 14, so its line reaches 39 subtiles where its other plans have 14.
I. The random walk: type 10
Section titled “I. The random walk: type 10”PathPlanRandomWalk(path, seed) → n + 1: [C] (rwalk 300, 5 092 draws, controls shr 279, n1 300, step1 258, accum 204, noadd 238; all of I) 1. add: i32[32] ← { −1, 0, 1 } ten times, then −1, 1 2. n: i32 ← path.+0x91 >> 1 3. cur ← the position's subtile words (+0x02, +0x06) 4. d ← PathDirRow(cur, (path.+0x10, path.+0x12))[0] ; once 5. for k in 0 ..< n: lo, hi ← the seed's halves; v: u64 ← 0x6AC690C5 × lo + hi; seed ← (low 32 of v, high 32 of v) ; draw#(k+1), the LCG inline; see rng dir ← (d + add[low 32 of v & 31]) & 7 points[k] ← cur cur ← cur + 2 × g_PathStep8Long[dir] ; u16 adds 6. points[n] ← cur; +0x28 ← n + 1; return n + 1- I. [C] It is not a walk of accumulating turns: every step is the first direction ±1 or straight. The first point is the position itself. No grid and no room are read: the missile’s collision is its own. (control
accum) - I. [C]
+0x91of 0 or 1 draws nothing and has one point. (familyrwalk,draws:042) - I. [C] A straight step has chance 10/32, each side 11/32: the turn map reproduces all 946 type-10 plans’ points and seeds, a 12/32-straight variant fails all 851 it separates, and the game’s steps are 10 616 straight of 33 500 (31.7 %).
- I. [C] In the game: 698 + 248 plans, return 39 in all at
+0x91= 77, 654 creations of the skills runs. Worked example: overview. - I. [I] At limit 77 the walk reaches 76 subtiles on an axis, so its u16 adds wrap only within 76 subtiles of 0 or 65 535.
J. The spiral: type 14
Section titled “J. The spiral: type 14”PathPlanSpiral(path) → 77: [C] the structure, over all 260 stock type-14 plans, and the products and the list below (all of J) 1. (fx, fy): u32 ← the 16.16 position; (lx, ly) ← (fx, fy); r: u32 ← 0; a: i32 ← 0; k: i32 ← 0 2. loop: 3. r ← r + 0x2580; a ← a + 16 4. R: f32 ← r ; fstp, exact for these values 5. X: i32 ← trunc(g_SineTable[(a + 0x80) & 0x1FF] × R) ; toward zero 6. Y: i32 ← trunc(g_SineTable[a & 0x1FF] × R) ; toward zero 7. x: u32 ← X + fx; y: u32 ← Y + fy 8. if x >> 16 ≠ lx >> 16 or y >> 16 ≠ ly >> 16: points[k] ← (x >> 16, y >> 16); k ← k + 1; (lx, ly) ← (x, y) 9. if k ≥ 77: break10. +0x28 ← 77; return 77- J. [C] Truncation toward zero: overview § G4.
- J. [C] The point list reproduces in 27 stock plans of the first run, which at a start fraction of
0x8000on both axes are one list relative to the start, and in 233 natural plans of the second;swapseparates them. - J. [I]
g_SineTableandRgo on the x87 stack as f32, so the product has at most 48 mantissa bits and is exact in a double;XandYare the low dwords of a 64-bitFISTP. The game’s stored integers agree with the exact product (overview § G4’s 43 804). - J. [C] No draw, no grid, neither
+0x90nor+0x91: the seed, the grid (no dump) and both bytes unchanged in 260 of 260 plans. 94 iterations at the kept start(0x8000, 0x8000)in 233 of 233 plans, at most 95 in the emulator’s cases;rwould wrap at iteration 223 697 (the kept bound line). - J. [I] The emulator’s x87 can’t test this: the p-code
FISTPignores the rounding field. So the list’s tag rests on the game’s plans. - J. [C] The hammer at a wall: this plan reads no grid (no grid dump in 260 of 260 plans, 123 of them passing through cells with the wall bit
0x04). [I] The end at a wall is the missile’s own step, skills/missiles § D3, with P12’s entry.
K. The straight planner and type 4
Section titled “K. The straight planner and type 4”PathPlanStraight(path, unit): [C] to the boundaries of 10 and 14 type 4: n ← PathPlanToUnit(path); flag 0x20 set when n ≠ 0, cleared when 0; return n type 10: PathPlanRandomWalk(path, &unit.seed); flag 0x20 set; return +0x28 ; [I] past the boundary type 14: PathPlanSpiral(path); flag 0x20 set; return +0x28 ; [I] past the boundary else: fatal 0x207 ; [I] not run
PathPlanToUnit(path) → 0 or 1: [C] (47 cases, 35 one point, 12 refused) +0x24 ← 0 if a target unit: (+0x10, +0x12) ← its position if |sx − tx| ≥ 100 or |sy − ty| ≥ 100 or tx = 0 or ty = 0: return 0 ; +0x28 kept points[0] ← (tx, ty); +0x28 ← 1; +0x38 ← 0 PathAimNextPoint(path, 1; 1) flag bit 0 when the path has no room or the point lies outside its rectangle return 1- K. [C] No collision test: a type-4 path is one straight segment. The refusal is at 100 where
PathPlan’s window passes 100, and these paths skip that window. In the game all 2 740 + 3 713 plans are this one point.
L. The search: types 0 and 16
Section titled “L. The search: types 0 and 16”[C] Evidence: 2 116 cases of families real0, real16, stair, corr, open, rect, 0 mismatches, plus the 120 boundary cases of grid and over. No game plan: no type 0 or 16 in 46 sessions. Everything in § L is that emulation’s, with the frame compared as scratch, unless tagged otherwise.
It is an iterative-deepening depth-first walk, not best-first: no open list and no priority. Each node takes the first direction of a fixed fan that passes the tests, so the fan’s order is the tie-break.
L1. The rectangle
Section titled “L1. The rectangle”PathPlanSearch(ctx): [C] (controls union 11 of rect, margin 10 and 37) ctx.refresh ← ctx.refresh + ctx.refresh ; u8 own ← the unit's room's rectangle (x, y, w, h); r ← own ; DungeonRoom +0x4C if ctx.troom ≠ 0 and ctx.troom ≠ ctx.room: o ← its rectangle if o.x < own.x: r.x ← o.x; r.w ← own.w − o.x + own.x ; own's right end else: r.x ← own.x; r.w ← o.w − own.x + o.x ; o's right end, even when own's lies further if o.y < own.y: r.y ← o.y; r.h ← own.h − o.y + own.y else: r.y ← own.y; r.h ← o.h − own.y + o.y if r.w = own.w: r.x −= 10; r.w += 20 else: r.x −= 10; r.w += 20 if r.h = own.h: r.y −= 10; r.h += 20 return PathSearchRun(r, ctx)- L1. [C] It is not the true union. A target room right of or below the unit’s, with the same left or top edge or one inside, and a smaller far end, shrinks the rectangle below the unit’s room; a start beyond it ends the walk at the root: return 0. (family
rect,startout24, all count 0) - L1. [I] Rooms on one row with equal rectangles get the margin only across, since
r.wdiffers.x1 = x + wandy1 = y + hare both inside, one column and row past the room’s own end.
L2. The run
Section titled “L2. The run”PathSearchRun(r, ctx) → n: [C] (controls step, half, regrid) 1. if (i32)(r.w × r.h) > 50000: assert line 0x171 ; 50 000 passes 2. the store: 900 nodes of 0x1C bytes, x0, y0, x1, y1, stride ← r.w + 6, offsets 3 − x0, 3 − y0 clear (r.w + 6)(r.h + 6) i32 cells to 0 ; once a search; every pass reuses them cell(x, y) ← cells[(y + 3 − y0) × stride + 3 − x0 + x] ; 0 unseen, 1 blocked, else the least g written 3. drawing ← (ctx.type = 16); seed ← path.unit + 0x20 under type 16 4. h0: u16 ← PathOctile(start, target); first: i16 ← h0 if type = 0: last ← max(first, ctx.b1C) else if type = 16: first ← (i16)(h0 + h0 ÷ 2); last ← max(first, ctx.b1C) else: last ← first 5. root: pt ← start, f ← h ← h0, g ← 0, tries ← −3, turn row 0 at entry 0, dir ← PathDirOctant(start, target) & 7 6. do: nodes[0] ← root; node ← Walk(first, ctx); first ← first + 5 if node is none and nNodes = 900: break nNodes ← 1 while node is none and first < last 7. n ← node ? Reduce(node, ctx) : 0 8. return (n ≥ 78) ? 0 : n
Reduce(node, ctx) → n: ; controls min2, max77 buf ← []; prev ← (−2, −2) while node and |buf| < 78: if node.parent: step ← node.pt − node.parent.pt; if step ≠ prev: append node.pt; prev ← step node ← node.parent if |buf| < 2 or |buf| > 77: return 0 ; the list untouched copy buf reversed to points; return |buf|- L2. [C] With
b1Cat or belowh0, type 0 has one pass at exactlyh0: only a route of the unblocked octile length is found. - L2. [C] A route of one segment returns 0, so a straight or exactly diagonal free line is refused by this planner (
points<2:target9 ofreal0, 1 ofreal16, 3 ofstair). The list ends at the node the walk ended on; the start is not in it. - L2. [C] Neither planner reads
ctx.limit,ctx.sizeor+0x10, and neither reads the path but+0x30under type 16. (traced=0over 2 116 cases) - L2. [C] Bounds: at most 51 passes for any
h0(checked overh00..599 andb1C0..255, types 0 and 16), each at most 10 000 tries; the loop also ends at a found node or a full node pool.
L3. The walk and the fan
Section titled “L3. The walk and the fan”Walk(bound, ctx) → node or none: [C] (controls h, cost, fgt, cellle, rectend, radius, passes, nodes) 1. node ← root; tries: i32 ← 0 2. loop: 3. if node.pt = ctx.target: return node 4. tries ← tries + 1; if tries > 10000: return none ; a refused try and a passing one both count 5. if node.pt is outside x0..x1, y0..y1: return node ; u16 compares, both ends inside; returned as found 6. n ← node.pt + g_PathSearchStep8[node.dir] ; u16 adds 7. c ← cell(n) 8. if c = 0 and Blocked(ctx.room, n, ctx.pattern, ctx.testMask): cell(n) ← 1; goto next 9. g: u16 ← node.g + ((n.x ≠ node.x and n.y ≠ node.y) ? 3 : 2)10. if c ≠ 0 and (u32)c < (u32)(i32)(i16)g: goto next ; 1, blocked, is below every g11. cell(n) ← (i16)g ; written before the bound test12. h: u16 ← PathOctile(n, target); f: u16 ← g + h13. if (i16)f > bound: goto next14. child ← node.child if child is none: if nNodes = 900: return none ; ends the whole search child ← the zeroed nodes[nNodes]; nNodes += 1; child.parent ← node; node.child ← child15. child.h ← h; child.g ← g; child.f ← f; child.tries ← 016. want ← PathDirOctant(n, target)17. child.turn ← the row (want − node.dir) & 7 of g_PathSearchTurnRows, at entry 018. child.dir ← (node.dir + child.turn[0] + A) & 7 ; type 16: draw, A ← g_PathSearchDrawAdd[low & 31]; else A ← 019. child.pt ← n; node ← child20. if (i16)node.h < ctx.refresh: return node ; ctx.refresh already doubled21. continue22. next: node ← Advance(node); if none: return none
Advance(node) → node or none: [C] if node.tries < 4: next entry of node.turn; Turn(node) node.tries += 1 if node.tries ≠ 5: return node loop: if node is the root: return none node ← node.parent next entry of node.turn; Turn(node) ; a backtrack's turn, unconditional node.tries += 1 if node.tries ≠ 5: return node
Turn(node): node.dir ← (node.dir + the turn entry + A) & 7 ; A as step 18: a draw under type 16The fan, as offsets from d, the parent’s direction when the child was made (for the root: from want). The row index is (want − d) & 7. A child tries 5, the root 8.
| Row | Turn entries used | Tries, from d |
|---|---|---|
| root (0) | 0, 1, 6, 3, 4, 5, 2, 7 | 0, +1, −1, +2, −2, +3, −3, +4 |
| 0 | 0, 1, 6, 3, 4 | 0, +1, −1, +2, −2 |
| 1 | 0, 1, 6, 3, 1 | 0, +1, −1, +2, +3 |
| 2 | 0, 1, 1, 1, 1 | 0, +1, +2, +3, +4 |
| 3 | 1, 1, 1, 1, 1 | +1, +2, +3, +4, +5 |
| 4 | 6, 4, 3, 6, 1 | −2, +2, −3, +3, +4 |
| 5 | 7, 7, 7, 7, 7 | −1, −2, −3, −4, −5 |
| 6 | 0, 7, 7, 7, 7 | 0, −1, −2, −3, −4 |
| 7 | 0, 7, 2, 5, 7 | 0, −1, +1, −2, −3 |
- L3. [C] Under type 0 the fan’s order rests on 5 cases of
openand 5 ofrectthatrowandtriesseparate; under a tight bound the order doesn’t show, and none ofreal0’s separates. - L3. [C] A node has one child slot, kept across a backtrack, so the allocated count is the deepest chain of the pass + 1. Reaching a node outside the rectangle returns a route one step outside it, short of the target. (family
corr) - L3. [C] The first try keeps the parent’s direction in rows 0, 1, 2, 6 and 7 (entry 0 is 0 in those rows): under the non-drawing types the walk runs straight until the bound or a wall turns it; under type 16 the turn adds a draw (step 18).

The search of type 0 on a toy room of 16 by 9 subtiles: click cells to put up or take down walls, and move the start, the target and the last bound. The first bound is the octile length h0 and the walk runs again at bounds 5 higher while they stay below the last bound given (§ L2). Each pass is a depth-first walk in which a node takes the first direction of the fan that passes the tests (the fan table above, over the eight steps of the Tables under Inputs), a straight step costs 2 and a diagonal 3, and a cell that already holds a lower cost is not entered again, the cell store being kept from one pass to the next (§ L3). The direction toward the target that picks the root’s direction and each child’s row of the fan is the octant, which § A2 states cell by cell: a term whose double is at most the other’s size counts as 0, and a target on the node itself gives direction 6. The list returned keeps the corner points, with the start not among them, and a route of one segment returns nothing (§ L2). A cell with no room around it is blocked (§ A1). Not shown: type 16’s draws, real rooms and their masks. Computed by our model of the rule, not observed in the game; the starting values are illustrative.
L4. Type 16’s draws
Section titled “L4. Type 16’s draws”- L4. [C] The step is the game’s LCG, inlined at three sites, step 18,
Advance’s first line and its loop:v = 0x6AC690C5 · lo + hi.dir = (dir + turn entry + g_PathSearchDrawAdd[lo & 31]) & 7with the new low word. Controldrawseparates all 400 ofreal16; the exit seed is compared in every type-16 case, 994 022 draws there. A node’s fifth try draws nothing. Type 0 draws nothing. - L4. [C] Type 16’s reach: two unreferenced functions.
L5. The limits
Section titled “L5. The limits”- L5. [C] Points: at most 77, against 78 slots. A route of 78 corners fits
PathPlan’s window: a staircase ofdx78,dy39 hasg = h0 = 195.stair: 77 returned, 78 refused. - L5. [I] The node store is out of reach under
PathPlan’s window:|dx|, |dy| ≤ 100givesh0 ≤ 300, the last bound at most 300 (type 0) or 450 (type 16), the depth at most 150 or 225, so at most 151 or 226 nodes of 900. Past the window,corrreaches it: 899 steps fit, the 900th step’s child returns 0 and ends the search. - L5. [C] The assert and the frame. 50 000 passes; 50 001 asserts. But the clear covers
(w + 6)(h + 6)cells and the frame holds 50 010 before the savedEBP: a clear of 50 011 cells zeroes the savedEBP, 50 012 the return address, 50 013 the context argument. So a rectangle can pass the assert and overrun: 217 × 217 fits, 218 × 218 overruns. The signed product wraps from 46 341². (familiesgrid,over) - L5. [C] No single stock room overruns: the largest is 60 × 60 subtiles, a same-room rectangle 80 × 80, a clear of 7 396 cells. A pair on the near list’s gap rule has a side of at most 145, a clear of at most 22 801. (Levels § Largest room, rerun byte-identical,
LvlMaze.txtagreeing) [I] That the builders make no room outside these extents (their room rule is not read). - L5. [I]
gandfare u16 read as i16; under the storeg ≤ 2 697, and no wrap is reached.
M. The client-only slots: types 3, 11, 12
Section titled “M. The client-only slots: types 3, 11, 12”No server code sets them. The maps are [C] by emulation (family client, 60 cases each, control order 49). That they run in the client is out of scope.
PathPlanType3(ctx): +0x24 ← 0; then PathPlanGreedy's body [C]PathPlanType11(ctx): +0x24 ← 0; points[0] ← target; [C] (_, pt) ← PathFirstLine(path, target); points[0] ← pt; return 1 ; +0x28 never written, even when pt = startPathPlanType12(ctx): +0x24 ← 0; +0x98 ← −4; n ← PathWalkParam98(ctx); n = 0: return 0 [C] +0x28 ← n; +0x98 ← −2; v ← PathWalkParam98(ctx) if v = n: +0x98 ← 2; v ← PathWalkParam98(ctx) +0x98 ← −4; return v- M. [I] Type 12’s total can be
2 × limit, past 78 from limit 40, though only cases of limit 38 or less ran. Client only.
N. Points against the 78 slots
Section titled “N. Points against the 78 slots”| Planner | Most points | Reached | Tag |
|---|---|---|---|
Greedy, +0x98 0 |
ctx.limit + 1, 78 at limit 77 |
gbound 78; game 21 (type 7, run 1), 27 |
[C] |
The +0x98 walk |
ctx.limit |
g98 76; game 6 |
[C] (p3-bounds.txt) |
| Knockback, one point, type 11 | 1 | 1 | [C] |
| Type 1 | 77; a raw 78 returns 0 | t1stair 77 |
[C] |
| Type 15 | lim − 1 = 76 |
maxret 56; game 29 |
[I] the bound |
| Random walk | (+0x91 >> 1) + 1, 39 at 77 |
39 | [C] |
| Spiral | 77, always | 77 | [C] |
| Search | 77 | stair 77 |
[C] |
- N. [C] Limit 77 is the most any path-module writer or immediate gives:
PathSetByte90caps at 77, creation gives 73 or 14. [I] That the 13 register dword stores at+0x90outside the path module (bases not traced) give no more is not read. Limit 78 would write+0x1D4; no server code path sets it, and the quest byte stores at the same offsets are not paths. - N. [C]
PathPlanhas no test of a count above 78: the return is stored and none of the tail’s 8 compares holds 77 or 78, so a planner returning one would overrun the record. [I] No server planner passes 78: it rests on the limits above, whose register stores outside the path module are not read.
Outputs
Section titled “Outputs”The point list at +0x9C (u32 words x | y << 16, in walking order), the return, and each planner’s side writes: +0x24, +0x28, the aim of A5, knockback’s target point and target unit, the seed under types 10 and 16. PathPlan’s tail then acts on them: overview § C. [C] the points, the return, +0x24, +0x28, the aim and the target words, and type 10’s seed (946 plans). [I] the search’s and type 16’s side writes (no server plan) and knockback’s own target point (not compared).
Worked example
Section titled “Worked example”The draws of a type-10 plan, with its entry, each point and its exit seed from a kept log, are in overview § Worked example.
Reimplementation notes
Section titled “Reimplementation notes”- [C] The search refuses a free straight line (L2), and type 1 accepts one (§ G). Don’t merge their reductions.
- [C] The line reads the path’s fields and the walk the context’s (Inputs); knockback’s line starts at
ctx.start, greedy’s at the position. - [C] Type 15 reads the byte
+0x91, notctx.limit, andlimis 40 at least under a target unit. (controllim18) - [C]
PathDirCell’s& 1is not a sign: it changes the cell only for an even non-zero minor term. (controlsign) - [C] A greedy walk’s quirks are behaviour to keep: the doubled first point, the point short at a turned last step, the reversal’s end.
- [C]
cell(n)takesgbefore the bound test, and the cells survive between passes, so a later pass can refuse a cell an earlier one wrote. (controlregrid)
Evidence
Section titled “Evidence”- Tools (the models, kept): runs §§ G and H as written against the models.
- Specs: the overview, drlg/collision, anim/movement, rng.