implementing pathfinding in uxntal

deluge subpost it is not coming out for a very long time

but it's also kind of its own thing so i decided to split out

algorithm

breadth-first search (BFS): simplest good pathfinding algorithm

it explores the area around the start til it finds the end (solved!) or can't explore any further (no path)

here's an interactive intro from redblobgames

constraints

• 65536 bytes total with up to 15 more banks, but constant memcpy is a bad idea  
• max room size is 256x256
• tiles have different accessibility (floor, pole, wall, air) per creature

size

what data structures do we need?

• queue of nodes to visit (worst-case: all the nodes (n*n) i suspect it's closer to 4(n-1) (max frontier on empty map) but better safe than sorry )
• map of directions to visited tiles (n*n)
  • 4 cardinal directions (no diagonals) so we can pack 1 tile into 2 bits (4 tiles per byte)
  • but we also need to flag that the tile has been visited
  • in theory, this would be 5 possible values
  • in practice, that would be silly to decode
  • round up to 4 bits so 2 tiles per byte
  • why not use a separate "visited" map for 3 bits per tile?

    using a separate map means extra code to access the map, which takes away from the memory savings. ultimately i decided it wasn't worth the complexity

dimensions should be a nice power of two

• 256x256 is ideal (covers maximum room size) but takes up too much space
• 16x16 covers 1/4 of an average room, good enough!

prototype

i like to use Scratch as a visual playground, nothing beats the interactivity

main downside is that it doesn't translate well to lower-level stuff (datatypes/overflow/bit-operations)

Tbh I think scratch is hard mode - bullno1

visualizations are cool :D

this implementation is slightly different from what i explained earlier, it uses a map of distance rather than direction to give us those pretty gradients
this is less efficient because the path backtracker must compare distances of each neighbouring tile to find the correct direction

now that we understand how BFS works, let's implement it in uxntal!

data structures

• queue of nodes to visit
• map of directions to visited tiles

queue shall be a circular buffer, we don't even need to worry about the "circular" part because the range is 0-255 like a byte, so our index will just wrap around :D

as for the map, 1 tile is half a byte or 1 nybl, so map shall be a simple nyblmap (map of nybls!)

how about returning the path?

the path is actually calculated backwards, we backtrack from the goal and collect directions along the way

so the last direction we collect is the starting direction -- this is a stack!

fortunately our circular buffer impl can also behave like a stack, and since the node queue is temporary storage that won't be used after a path has been found, we can reuse it to store the path result!

algorithm

16x16 = 256, we can store nodes in a single byte (y is higher nybl and x is lower nybl)

i want the search area to be centered on a tile so make it 15x15

that'll lose us 16 + 15 = 31 tiles but it compensates by allowing us to detect wraparound easily :D

put the search origin in the middle: (8,8)
range is ±7 so 0x1 - 0xf
if we're on the low edge 0x1 and try to move even lower, it'll become 0x0
if we're on the high edge 0xf and try to move even higher, it'll wrap around to 0x0 too!

so detecting wraparound is as simple as checking if either x or y nybl is 0! no need to care which direction we're coming from because either way falls into the 0x0 gutter

%guttered ( index -- guttered? ) {
	DUP #0004 SFT2 #04 SFT MUL #00 EQU
}

this part actually tripped me up twice

original impl: #0f AND #00 EQU ?&skip DUP #f0 AND #00 EQU ?&skip (31 bytes)

if x is 0 then skip; if y is 0 then skip
if x OR y is 0 then skip

round 1: #0f AND ?&no-skip DUP #f0 AND ?&no-skip !&skip &no-skip (24 bytes)

rawra
rawra	Isnt this a bug or am I tripping
notchoc	oh yea that is definitely a bug
notchoc	wow how did you break it so fast HAHAHA
rawra	im a very skilled destroyer of software

if x is not 0 then do not skip; if y is not 0 then do not skip
if x AND y are 0 then skip

see the difference?

yeah, i sure didn't, classic case of confusing AND with OR (which would catch only the corner gutters)

round 2: #0004 SFT2 MUL #00 EQU ?&skip (17 bytes) 🥹

#0004 SFT2 splits yx into their own bytes 0y and x0, then the MUL acts as an integer AND (if either byte is 0 then the result will be 0)

rawra
rawra	cursed position lmao
notchoc	reproducible
notchoc
notchoc	... it happens on the + tooo

here's a map of all the "cursed" positions:

interesting pattern...

#0004 SFT2 splits yx into their own bytes 0y and x0, then the MUL acts as an integer AND (if either byte is 0 then the result will be 0)

let's take the top left diagonal (4,4), index is 44

#0004 SFT2 ( 44 -- 04 40 )
MUL ( 04 40 -- 00 )

huh?? both values are clearly nonzero, so why is the MUL giving us 0?

calculating 0x04 * 0x40 gives us 0x100... which gets truncated to 0x00

let's try the axes, (8,6) -> 68

#0004 SFT2 ( 68 -- 06 80 )
MUL ( 06 80 -- 00 )

0x06 * 0x80 = 0x300 which is again truncated to 0x00

the x nybl is leftshifted by 4 bits, if the result of x*y would have been a multiple of 0x10, then it would also be leftshifted into 0x00 and return a false positive

solution: #0004 SFT2 #04 SFT MUL #00 EQU ?&skip (20 bytes)

solution? un-leftshift the x nybl

so

#0004 SFT2 splits yx into their own bytes 0y and x0,

becomes

#0004 SFT2 #04 SFT splits yx into their own bytes 0y and 0x,

since x and y can never exceed 0x0f, multiplying them will always give a value within 0x100

no more false positives :D

and our pathfinding impl works perfectly!

source on codeberg

• core library is in main.tal
• maze UI thing is in maze.tal

some custom syntax here, maybe in a future blogpost...