An Old Trick for a New Game for an even Older Computer

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!