During the Amiga heyday in the early 1990s, I wrote a standalone BBS program called ‘Hack & Slash’. It was a port from an Apple ][ BASIC program, but heavily customized and enhanced using C and “modern” telecommunications and protocols for color, graphics, and sound.
I thought I was really clever at the time writing my random dungeon level generator — it was my first practical use outside of a classroom to implement a recursive function. Because the dungeon ‘walls’ were probability driven, a function was needed to validate that every ’tile’ in the arbitrarily-sized dungeon floor was accessible by the hero. Without this kind of validation, the hero would eventually find himself ‘trapped’ on a floor with no means to escape.
The recursive function was simply invoked as chkroom(0,0), whereas the 0,0 passed were parameters to the starting point in the dungeon map matrix. Upon entering each tile, a flag is cleared for that element in the matrix. Next, a condition is checked if the tile to its right is accessible. If it is, call chkroom() with +1 added to X. If not, do the same condition checks for down, left, and up directions calling chkroom() passing values Y+1, X-1, and Y-1 respectively.
And at the conclusion of all this recursion, do a loop through the dungeon matrix to check if ALL of the flags had been cleared. If any persist, do the dungeon regeneration and this validation again until it has passed. The higher the frequency of random walls generated increases the pattern complexity of the floor, which exponentially increases the probability that the floor will not pass with an ‘all clear’.
Today, I am working on a port of an old arcade favorite, Berzerk, for the Commodore VIC 20. The playfield for the game is a fixed 3-row by 5-column matrix for each floor. Given that the game needs to be written using 8-bit assembler, I quickly dismissed the idea that using my C algorithm to validate a floor could be feasible. After all, VIC 20 is a relic machine running at 1mHz and limited memory of only a few thousand bytes available for the program, graphics, and sound all the while using a 256-byte system stack. Ah, but the challenge by it all . . .
Generating the random walls for each floor is a simple matter, but validating that all its ‘rooms’ are accessible was turning out to be very problematic. Every time I thought I could solve this puzzle using bit operators (OR, AND, XOR) to assure that its rooms and corridors could not trap the hero, I would only later stumble upon an instance where even my most elaborate of schemes failed. This was getting a bit frustrating, pun intended.
So I wandered back to my dungeon floor validation and decided it was so simple of an algorithm that it may be possible to translate it to assembler and still keep it within reason of the machine’s constraints. After some writing and whittling, the resulting code turned out perfect! It is called by simply zero-ing the starting cell (R0) and invoking CRAWL. Here is its listing:
CRAWL: LDX R0 LDA MAZE,X CMP #$80 BCC @fini ; been here? AND #$7F ; clear accessible bit STA MAZE,X @right: LSR BCS @down ; right wall? PHA ;++ push walls LDA R0 PHA ;++ push cell INC R0 JSR CRAWL ; explore right cell PLA ;-- pop cell STA R0 PLA ;-- pop walls @down: LSR BCS @left ; bottom wall? PHA ;++ push walls LDA R0 PHA ;++ push cell CLC ADC #5 STA R0 JSR CRAWL ; explore cell below PLA ;-- pop cell STA R0 PLA ;-- pop walls @left: LSR BCS @up PHA ;++ push walls LDA R0 PHA ;++ push cell DEC R0 JSR CRAWL ; explore left cell PLA ;-- pop cell STA R0 PLA ;-- pop walls @up: LSR BCS @fini ; top wall? PHA ;++ push walls LDA R0 PHA ;++ push cell SEC SBC #5 STA R0 JSR CRAWL ; explore cell above PLA ;-- pop cell STA R0 PLA ;-- pop walls @fini: RTS
This old dog is always happy to re-implement an old trick!
