A rogue-like game requires its levels to be randomly generated. Obtaining levels that are playable (I do not dare to add “and interesting”) is not an easy feat. Especially on an 8-bit computer such as the Apple II. But, hey, that’s what make this project interesting!

All the code presented here is available on the public repository of the project.

Hot topic

Random level generation is a hot topic for rogue-like developers, as it can make or break a game. Sources abound, such as r/roguelikedev, gamedev.net or the Procedural Content Generation Wiki. Interesting articles are countless, such as this one or this one.

But I did not find any that resulted in interesting results and that I considered feasible on the venerable 1 MHz 6502 of the Apple II.

Until I stumbled on this blog post: Rooms and Mazes: A Procedural Dungeon Generator.

This article presents everything I need: an algorithm leading to interesting level layout, fine details about implementation, along with nice animations and the source code! Thus my only task was to concentrate on porting that into a relatively optimized 6502 assembly code.

The level generator in action The level generator in action

The algorithm

Goals

A randomly generated dungeon shall have

  • Rooms. Who wants to spend days in corridors?
  • Tortuous corridors. Some game designers choose to compose their dungeon only of adjacent rooms. But I think that corridors can increase the sense of loneliness and disorientation of the player.
  • Multiple ways to go from one room to another.
  • All rooms shall be connected to every other ones. If there are isolated parts, the game-play will be broken.
  • The generator should be able to generate levels of various sizes. Indeed, I intend my levels to get bigger and more complex as the player progresses.
  • The generation of a level shall be fast enough. Some of the speed will be achieved by optimizing the implementation, but most of it will be achieved by being clever and not too “brute force”.

The generation can be decomposed in four independent steps.

Step 1 – Generate rooms

We want to generate rooms of various shapes, then to place them into the maze. They shall not overlap and the generator has to leave enough tiles to “carve” corridors between the rooms.

Depending on the size of the level, if we try to pack too much rooms, the algorithm may have an impossible problem to solve and will be stuck. Even if some solutions do exist, the algorithm may spend too much time before coming across randomly on one of them.

Thus, the solution is not to fix the number of rooms to place, but the number of attempts. The time will become predictable, at the expense of the number of rooms effectively placed in the level. But this is less important.

fig1 1. The rooms are generated and placed in the level

Step 2 – Grow the Maze

Once the rooms are in place, we fill the remaining space with a perfect maze. A maze is said to be perfect when it contains no loop: it is only a collection of dead ends. Pretty boring isn’t it? Well, yes. But it is only a small step in the whole process.

A constrained Drunkard Walk

Generating a perfect maze is rather easy. A well-known algorithm is the “drunkard walk”. Given a starting point, we choose a random direction to “carve” a tile. And repeat. Quite simple? Not so fast.

We want a perfect maze, one with no loop. So, we have to check that the tile to be carved won’t create a loop: we won’t carve a tile adjacent to a room or a corridor. If no direction is possible we try with the previously carved title and continue to grow the maze from there.

Concerning the implementation, we use a stack of successfully carved tiles. When it’s impossible to carve from the current tile, because it is surrounded by other tiles already opened, we simply pop from the stack and try again with the previous one. The stack then grows again with each new tile that we can open. And so on.
When the stack becomes empty, the job is finished: all the space has been filled with corridors.

fig2 2. Filling the empty space with mazes

Step 3 – Open doors

We then connect the rooms to the maze. At least one opening is carved on a randomly chosen suitable tile. All other walling tiles have a small chance to be opened if they are adjacent to a corridor. Thus, more openings may be added, increasing the diversity of the rooms. But every room is connected to the maze by at least one door, which is essential for the level to be playable.

fig3 3. The rooms are now connected to the maze

Step 4 – Remove dead ends

There are too many corridors in the maze: we have to do some cleaning. The maze was perfect until we connected the rooms, so there are still many dead ends. We will remove them all.
This algorithm is quite simple. For each tile we test if it is a dead end: is it a passage, with only one carved neighbor? If so, we change it into a wall and repeat the process with the neighbor. Thus, we will follow the corridor until we come across a tile with two opened neighbors.

fig4 4. Removing the dead ends, from top to bottom

Implementation tricks in 6502 assembly

All those algorithms are rather simple. But the 1 MHz 6502 inside the Apple II is quite modest and we don’t want forcing the player to stare at the screen for too long before the level becomes playable. It requires an efficient implementation!

Two field of interest are most rewarding: randomness and testing the suitability of a tile. Indeed, most operations involve generating random numbers and testing if a “neighbor” tile is opened. Those will be the most profitable areas to optimize.

Randomness

Writing a fast, and good, random generator can be tricky. So I pasted the code of a function freely available and already proven. At around 100 cycles per run, it proved fast enough.

But this random generator requires a seed. How to get one on the Apple II?
Simple: we ask a question to the player, such as his name, and increment a counter between each keystroke! Remember that a bare Apple II comes with no timer. So, we literally have to count.

; wait for keyboard
cin_str_kbd_loop:
  INC_SEED
  lda KEYBD
  bpl cin_str_kbd_loop  ; bit #8 is set when a character is present (thus A < 0)
sta KEYBD_STROBE
 
; increment 32-bit seed
.macro INC_SEED
  clc 
  lda SEED0
  adc #1
  sta SEED0
  lda SEED1
  adc #0
  sta SEED1
  lda SEED2
  adc #0
  sta SEED2
  lda SEED3
  adc #0
  sta SEED3
.endmacro

Using typing speed as a source of randomness Using typing speed as a source of randomness

Some quick math: a 64*64 maze means 4096 tiles. Growing the maze roughly requires three random attempts per cell in order to find a suitable direction in which to carve the next tile. That’s 1200000 cycles using the random generator. More than one second, only to draw the numbers.

Not bad. But still a bit too long. We need a trick.

As often when coding for such old machines, it will require a small pre-computed table. We store all the 24 direction “quartets” that are possible.

For instance: UP, LEFT, RIGHT, DOWN or UP, LEFT, DOWN, RIGHT.

So instead of calling the Random routine every time to get one direction (which also would have the inconvenience to possibly return a direction already tested as non-suitable), we only randomly pick one of the quartets. Then we test each of its directions in order.

This implementation provides more than a 4X speedup.

; 24 direction quartets
RandomDirection:
.byte EUP,ERIGHT,EDOWN,ELEFT,EUP,ERIGHT,ELEFT,EDOWN,EUP,EDOWN,ERIGHT,ELEFT,EUP,EDOWN,ELEFT,ERIGHT,EUP,ELEFT,ERIGHT,EDOWN,EUP,ELEFT,EDOWN,ERIGHT
.byte ERIGHT,EUP,EDOWN,ELEFT,ERIGHT,EUP,ELEFT,EDOWN,ERIGHT,EDOWN,EUP,ELEFT,ERIGHT,EDOWN,ELEFT,EUP,ERIGHT,ELEFT,EUP,EDOWN,ERIGHT,ELEFT,EDOWN,EUP
.byte EDOWN,ERIGHT,EUP,ELEFT,EDOWN,ERIGHT,ELEFT,EUP,EDOWN,ELEFT,EUP,ERIGHT,EDOWN,ELEFT,ERIGHT,EUP,EDOWN,EUP,ELEFT,ERIGHT,EDOWN,EUP,ERIGHT,ELEFT
.byte ELEFT,ERIGHT,EDOWN,EUP,ELEFT,ERIGHT,EDOWN,EUP,ELEFT,EDOWN,ERIGHT,EUP,ELEFT,EDOWN,EUP,ERIGHT,ELEFT,EUP,ERIGHT,EDOWN,ELEFT,EUP,EDOWN,ERIGHT
 
; Uses a precomputed table to quickly return an offset to one of the direction quartets
_random_directions:
 
    jsr Random8
    and #31
    ldx #24
    jsr Modulus
    asl
    asl     ; offset to a direction quartet
    rts

Testing the suitability of a tile

Testing the nature (opened or walled) of the neighbors of a given tile is an operation that is used many times at many stages of the level generations. It has to be efficient.

  • Growing the maze: is a tile to be carved in contact with a room or a corridor? We don’t want that.
  • Opening the room: is a tile to be carved in contact with a corridor? We want that.
  • Removing dead ends: is an opened tile in contact with more than one other opened tile? If yes, it is not a dead end.

Testing the nature of tiles means reading their content in the “World” table that describes the level. Each tile is represented by an 8-bit value that give its nature. So, for any given tile, testing its surroundings means computing their address, read their value and perform the test.
On an 8-bit 6502 CPU, computing a 16-bit address before accessing its content is slow. Fortunately the 6502 offers the wonderful indirect addressing modes. They allow to access the content of a memory given an address stored in the Zero page plus an 8-bit offset stored in X or Y.
So, instead of computing the four 16-bit addresses surrounding the center tile, we only compute the upper one. It is the one that has the smallest address. Then we can access the content of all the tiles of interest by applying constant offsets: 0 (upper tile), WIDTH_WORLD-1 (left tile), WIDTH_WORLD+1 (right tile), 2*WIDTH_WORLD (bottom tile). The only restriction is that WIDTH_WORLD shall be <= 128 as the offset is an 8-bit value.

.define ADD_FACTOR  ZERO_4_1
; REM: PTR_TILE is already offsetted by -WIDTH_WORLD
; for easy access to adjacent tiles by indirect indexing
; Returns : NB_WALLS >= 3 if it is a dead end
_is_tile_dead_end:
    
    lda #0
    sta NB_WALLS
    ldy #WIDTH_WORLD
    sty ADD_FACTOR
 
    ; Returns if the tile is a wall
    lda #ACTORS::WALKABLE
    cmp (PTR_TILE), Y
    bcc end_tst_up_tile
 
    tst_up_tile:
        ldy #0
        cmp (PTR_TILE), Y
        bcc up_non_walkable                
        sty ADD_FACTOR
        bcs tst_right_tile
        up_non_walkable:
        inc NB_WALLS
    tst_right_tile:
        ldy #(WIDTH_WORLD + 1)
        cmp (PTR_TILE), Y
        bcc right_non_walkable
        sty ADD_FACTOR
        bcs tst_down_tile
        right_non_walkable:
        inc NB_WALLS        
    tst_down_tile:
        ldy #(2*WIDTH_WORLD)
        cmp (PTR_TILE), Y
        bcc down_non_walkable
        sty ADD_FACTOR
        bcs tst_left_tile
        down_non_walkable:
        inc NB_WALLS
    tst_left_tile:
        ldy #(WIDTH_WORLD - 1)
        cmp (PTR_TILE), Y
        bcc left_non_walkable
        sty ADD_FACTOR
        bcs end_tests
        left_non_walkable:
        inc NB_WALLS

More gains

There are many further ways to gain more time. Some follow, in no particular order.

“Fences”

Sharp readers may have noticed that, in fig 2, the level is bordered by corridors when growing the maze. When growing, the maze cannot connect to an already opened tile. This is a cheap way to constrain the maze inside the level, without resorting to specific and costly tests.

Modulo

There is no hardware division on the 6502. So the modulo routine we use will simply subtract the divisor until the rest becomes inferior.

; Returns A % X in A
; Source: http://forum.6502.org/viewtopic.php?t=130
Modulus:
        sec
        stx FAC2
lbl_modulus:
        sbc FAC2
        bcs lbl_modulus
 
        adc FAC2
 
        rts

Many time a random number modulo N is required in the various algorithm. In order to make the process faster, an AND operation with the first power of 2 superior to N, minus 1, is applied to the number. The result is not the same as without the AND operation, but it is still random.

If you loock back at the code snippet concerning the random directions, the random number shall be modulus 24. Before jumping to the modulus routine, we perform an AND #31 operation to speed things up.

Memory

The most memory hungry step is the second one: “grow the maze”. As stated, it requires to stack the address of every successfully carved tile. In theory, this stack could grow up to 4096 bytes, which is a huge amount of contiguous memory! Fortunately, HIRES graphics are not required when generating a level. We can make good use of the memory reserved for the two pages. That’s a pool of a staggering 16KB of continuous memory!

What now?

In its current state, my random level generator quickly builds great levels.

The random level generator running on the Apple II The random level generator running on the Apple II

But it won’t be enough for the final game.

First of all, there is still a slightest chance that a section will be isolated, breaking the game. There are several ways to ensure that cannot happen, but I have yet to find an implementation Apple II friendly.

I would also like to have the possibility to insert handcrafted sections in the level. That way, there could be specific rooms in each level. It could prove useful to give some consistency to each run in the game, especially during boss fights. Think about the “Butcher” in Diablo I. Even if the levels where randomly generated, you knew when you were approaching its lair.

And of course, the rooms are still a bit empty. It would be a plus to populate them with columns, fireplace, cabinets and other furniture.

Footnote

This is the third post of my series about programming a rogue-like game on the Apple II. The two previous posts are:

  1. A tile engine for the Apple II
  2. Raycasting a Line of Sight