How Dr. Mario (NES) creates its levels

Back when I was making Snake in 500 characters, I was wondering how small I could make a decent Dr. Mario clone. I had gotten an incomplete proof-of-concept down to 1,122 characters before I gave up. But it got me thinking: how exactly does Dr. Mario create its levels?

Fortunately, there’s enough interest in Dr. Mario that quite a few people have looked at this question before. There’s a good description of the level generation algorithm on tetris.wiki, and a few people have even reverse-engineered the game well enough that you can check out the code behind it. Using these resources, I decided to implement this algorithm in PICO-8, and get it to work just like the NES version.¹

Random number generation

Although the levels in Dr. Mario are “random”, the same exact level will be generated given the same initial conditions. This is because the game uses a PRNG (pseudo-random number generator), which is usually an adequate source of randomness for things like video games.

Specifically, Dr. Mario uses an LFSR (linear-feedback shift register). An LFSR works by taking an input number, shifting its bits over by one bit, and shifting in a new bit which is some combination of the other bits. These are very simple to implement in code, and the relevant function is only 23 bytes in assembly.

For the curious, here’s how I recreated Dr. Mario’s PRNG in PICO-8, using its builtin bitwise operators. Don’t worry if you don’t understand what’s going on; the point is, the NES could run something like this extremely quickly.

function roll_rng()
    local bit=(seed>>>9^^seed>>>1)&1
    seed=(seed>>>1|bit<<15)&0xffff
    rng0,rng1=seed>>8&255,seed&255
end

The only seeds that are never used with this PRNG are 0x0000 and 0x0001,² because this algorithm will only ever result in a seed of 0x0000 with this input. If this ever happened, the only pills it would generate would be all yellow, and the playfield generation would softlock the game. Otherwise, this algorithm will eventually loop through 32,767 different states.

Playfield representation

For each of the player’s playfields, Dr. Mario reserves 128 bytes of RAM – one for each cell on the playfield – and represents different types of cells with different numbers. The important thing to know is that it represents an empty cell as 0xFF, a yellow virus as 0xD0, a red virus as 0xD1, and a blue virus as 0xD2.

virus=0xd0
empty=0xff

yellow=0x00
red=0x01
blue=0x02

The game represents the playfield as a series of contiguous bytes in RAM. To make it easier to reason about, however, I’m representing the playfield as a 2D table called bottle, and defining a few helper functions for using it.³

bottle={}
for r=0,15 do
    bottle[r]={}
    for c=0,7 do
        bottle[r][c]=empty
    end
end

function next_bottle_pos(r,c)
    if (c<7) return r,c+1
    if (r<15) return r+1,0
end
function prev_bottle_pos(r,c)
    if (c>0) return r,c-1
    if (r>0) return r-1,7
end
function bottle_pos_is_valid(r,c)
    return r>=0 and r<=15 and c>=0 and c<=7
end

Pill generation

Before the level generation starts, a fixed sequence of 128 pills is generated, and the pills for the level will come from this sequence. This means that the pill sequence and series of levels will not be affected by player action after the game starts.⁴

The pills are generated in backwards order (to make for shorter assembly code), and given IDs from 0 to 8.

For each pill, a random number from 0 to 15 is chosen using the PRNG from earlier, and this number is added to the ID of the last pill to be generated to get the next pill’s ID. (If the ID is out of range, 9 is subtracted until it’s in range.)

function generate_pills()
    pills={}
    last_pill=0
    for i=127,0,-1 do
        roll_rng()
        last_pill=(rng0%16+last_pill)%9
        pills[i]=last_pill
    end
end

Playfield generation

The number of viruses in a level starts at 4 viruses for level 0, and goes up by 4 viruses each level, until 84 viruses is reached at level 20. The maximum height of any virus in a level comes from a lookup table of possible values (which are defined up to level 34, even though the possible levels only go up to 24).

virus_color_random={
    [0]=yellow,red,blue,blue,red,
    yellow,yellow,red,blue,blue,
    red,yellow,yellow,red,blue,
    red,
}
virus_max_height={
    [0]=9,9,9,9,9,9,9,9,9,9,9,9,9,
    9,9,10,10,11,11,12,12,12,12,
    12,12,12,12,12,12,12,12,12,12,
    12,12,
}

One virus is added to the playfield at a time, subject to certain constraints. A random virus position is generated until it’s within the allowed level height, and the virus color cycles between yellow, red, blue, and a random color from another lookup table. (Note that the position and color may change later.)

function add_virus(v_left)
    if (v_left<=0) return v_left

    --randomize virus position
    local r,c
    repeat
        roll_rng()
        r,c=rng0%16,rng1%8
    until r<=virus_max_height[level]
    --convert rows from bottom to
    --rows from top
    r=15-r

    --choose virus color
    --sequence: yel,red,blu,random
    local v=v_left%4
    if v>=3 then
        roll_rng()
        v=virus_color_random[rng1%16]
    end

If you’ve ever seen a Dr. Mario playfield, you may notice that viruses are never placed in lines of three or more. This is because of the next constraint: viruses of the same color can never be placed two cells away. This constraint is enforced by checking all cells that are two away from the current cell.

    local nbors
    repeat
        --go to next open position
        while bottle[r][c]!=empty do
            r,c=next_bottle_pos(r,c)
            if (not r) return v_left
        end

        nbors={}
        --check all positions 2 away
        for nbor_pos in all({
            {r,c-2},{r,c+2},
            {r-2,c},{r+2,c},
        }) do
            local nr,nc=unpack(nbor_pos)
            if bottle_pos_is_valid(nr,nc) then
                local nbor=bottle[nr][nc]
                --if a virus is here
                if nbor!=empty then
                    --keep track of its color
                    nbors[nbor&0x0f]=true
                end
            end
        end

If all three colors of virus appear in those cells, then no virus can be placed there that fits this constraint, and the next empty cell is tried; otherwise, the colors are cycled through (in the order blue, red, yellow) until a color is found that’s not in those two-away cells, and that color virus is placed there.

(If this function can’t find a valid virus placement before reaching the last cell, it places no virus and gives up.)

        --placement is valid if not
        --all colors are neighbors
        local valid_placement=not (
            nbors[yellow]
            and nbors[red]
            and nbors[blue]
        )

        --if placement is invalid,
        --try the next position
        if not valid_placement then
            r,c=next_bottle_pos(r,c)
            if (not r) return v_left
        end
    until valid_placement

    --find next color that's not a
    --neighbor
    while nbors[v] do
        v=(v-1)%3
    end
    --place this virus color here
    bottle[r][c]=v|virus
    return v_left-1
end

Flaws in the algorithm

While the algorithm works well in practice for generating levels, it has some theoretical flaws, which are touched upon in this paper on the subject by Aaron Williams.

Williams found a playfield state with only 60 viruses which would lead to this algorithm getting stuck in an infinite loop. This happens because of the two-away constraint, which ends up disallowing every single empty cell to have a virus of any color. In practice, this kind of playfield state never happens to be generated, because the PRNG is so limited in the kinds of playfields it can generate.

If the game is made to generate more viruses per playfield with cheat codes, however, Williams also discovered that the algorithm can fail in this way. In fact, it’s possible for the algorithm to fail after generating as few as 89 viruses! In practice, the game only adds up to 84 viruses per level, so this will never happen in-game either.

Williams speculates that the limit of 84 viruses is due to the problem of the game freezing if even a few more viruses are added. Apparently, the prototypes of Dr. Mario (called “Virus” at the time) allowed for up to 96 viruses on the playfield, but with a larger maximum height. I haven’t checked these versions out, but I suspect that they’re using the same playfield generation algorithm, and that the larger maximum height is what keeps the game from freezing with this amount of viruses.⁵

Testing suite

The PICO-8 cartridge I created is available in this forum post on the Lexaloffle website. Although the online source code viewer is broken at the time of posting, you can still view and edit the source code if you own PICO-8 (or use the online educational version) by typing load #miyiyupaba on the console. The controls should be pretty self-explanatory.

Oh, and happy Tau Day!