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!
Tags: Pastime, Technology // Add Comment »
Today, I release another arcade classic clone for the venerable Commodore VIC 20. This time it is based on the 1980 Stern hit, Berzerk. It did not take 24-years to complete like Quikman possessed me, just a mere couple of months between commuter rail rides and some weekend tinkering. Still, it came out pretty good because of my improved software sprite stack and floor generator.
