<Work in Progress>

Study of Berzerk and Maze Generation with Classic Developer- Alan McNeil

After reading the Edge article on the Making of Berzerk, you’ll learn from Mr. McNeil that the game went through 2 earlier phases before acquiring Mazes.

  • “I figured I’d need barriers between the robots and the human.  So I started looking at maze generators, and devised a super-simple scheme.  To make the maze non-random, I used the XY coordinate of the room as a 16bit number to seed my random number generator.  That way you could exit, run back and see the same room.  It makes the universe more real if you leave a room with a box in the middle and return to a room with box in the middle.  Totally random rooms are not immersive:  your brain goes ‘huh?’ and the fantasy collapses.”

Any student of the sciences or math, knows a core truth- within the most simple and elegant design lies the essence of genius.   So how does this “super-simple scheme” work?  Let’s find out from the quintessential master of maze generation himself, Alan McNeil.

  • Sean R- the way it’s done you don’t need to keep a map of the rooms- the room # gives you the info to construct the walls. Necessity is the mother of invention- the entire program, including speech, is only 16K! Speech and text for multiple languages takes up a significant portion of that. So there wasn’t room to store a big map.

BerzerkMazeGeneratorPerAlanMcNeil

OVERVIEW of the Maze Generator

  • The information below may become over-technical for the average reader so here is a summary of the content
  • There are 65,536 rooms in Berzerk.  Think of it like a large rectangle, 256 rooms wide and 256 rooms tall
  • The mazes are built from 8 pillars that have arms extending from them in a North, South, East or West direction.
  • Due to the limitations of the random number generation process, there are only 1024 maze layouts created, some of which will appear to be identical to other rooms!
  • If you start a game immediately after starting up Berzerk, you will be placed in a room with coordinates of 251-123 (251 vertical – 123 horizontal).
  • The basic concept of the maze process is that the program takes the room coordinates, does a math equation on the room number, then evaluates the number as binary 1’s and 0’s to decide which direction to create arms off of the 8 pillars in the room.  The arms will swing North, South, East or West depending on the number generated by the math equation.

Digging just a little deeper

  • If you are still curious after reading the above information…The arms are generated in “random” directions off of the 8 pillars using the following process:
  • Take the room number coordinates; multiply the coordinates 7 times with itself; add a specific value to that number; break out a few bits of the number, then evaluate the binary 1’s and 0’s from the resulting number.  The binary value decides if a pillar goes North, South, East, or West.  The process is repeated 8 times to make the arms for 8 pillars in any given room.
  • This is why Alan states that the same maze layout will be generated every time for the same room coordinates!

65,536 rooms, but not that many mazes!

  • Alan- “The 16 bit XY location is the basis for the Wikipedia note of 64K rooms. There are 64K rooms but I think the generator will make some duplicate layouts.”
  • You can think of Berzerk as a grid of 65,536 rooms. Horizontally the rooms are in rows from 0 to 255 (00 to FF in hexadecimal).  Vertically the rooms are in columns from 0 to 255 (00 to FF hex).
  • Mathematically 256 x 256 leads to 65, 536 rooms!
  • Using the 8 pillars and 4 directions used to make mazes, the math equation that leads to the POTENTIAL number of different maze styles/layouts: 4 directions and 8 pillars = 4x4x4x4x4x4x4x4=65,536
  • In theory that means that there would be a possibility of 65,536 different maze layouts spread amongst the 65,536 different rooms.  BUT the amount of DIFFERENT maze layouts in each room is much less than sixty-five thousand. Due to limitations of the random number generation process the actual number is 1024.  Taking note that the mazes generated in each different room will have many repeated layouts and some layouts which it isn’t possible to be generate.
  • In Summary- Maze grid is 256×256 (65,536).  Random Number Generator (RNG) turns that into a set of 64 duplicaterooms 32×32 (1024).  In the 1024 maze grid, only 888 are unique layouts.  Taking out a few more similar wall layouts.  The final tally of UNIQUE mazes is 876! 
  • Spoiler Alert- Click HERE if you want to see the exact map of mazes!
  • Sean R- The code I wrote only generated 1024 unique random #s, so I thought something
    was wrong.  $3153 isn’t prime (see Detailed Technical section below for explanation), so I tried a few different primes for B, but they all only returned 1024 unique random #s.

BerzerkMazeGridOverview

Scenarios which create maze layout duplication:

  • Examples of duplication would be situations where one pillar arm could be flipped in multiple directions without affecting the appearance of the maze. so one maze style might have multiple scenarios that could generate the same layout
  • In the example below, the corner pillar outlined in green can swing either direction and have no effect on the appearance of the maze, therefore 2 different random maze scenarios exist for that particular pillar anytime you see the setup.
  • In the second example, the green pillar can swing in any of 3 directions without affecting the maze appearance.  So for that situation there are 3 different number scenarios for that particular pillar setup.
  • But if pillar 1 arm is N or W, that pillar won’t be in a situation to create a duplicate maze layout
  • So in summary, you can see how the total number of 1024 maze layouts is reduced due to pillar values which don’t affect the appearance of the final layout.

Berzerk-ArmDuplication

The Maze Generator-  Based on the diagram below, can you give some further details on how the Maze Generator (MG) is used to create a maze like this one in Berzerk?

  • Alan- “I have not gone back to look in the code but here’s what I remember.
  • 1) take the rooms X and Y byte position (0..255) put then together as Y <<8 | X (c style operators << shift and | or) giving YX as 16 bits
  • 2) put YX into random number generator as seed (start of a sequence)
  • 3) Loop across the posts (as shown in diagram)
  • dir = next_random_number & 3; // give value between 0-3
  • Using this map 0=N, 1=S, 2=E, 3=W (directions north east west south to draw the wall)
  • 4) Start at the post and draw a wall going that direction.
  • 5) Repeat until all the post have drawn one wall.
  • That’s it.  So note that post 1 could draw east and post 2 draw west and those two wall cover the same pixels – its one wall. That makes for a more open maze when that happens.”
  • Sean R- Looking at the code around $25EB – $264B, it looks like the map is N=0 S=1 E=2 W=3

BerzerkMazeDesign

The 4 Layer Stack:  Would you explain how the stack of vertical mazes work, in that you can run vertically through 4 layers of mazes to take you back to the first maze style?

  • This Youtube clips shows how the mazes repeat if you go straight up, similar to sequence of images below.
  • Alan McNeil- “I suspect that is an artifact of the crappy random number generator. Remember we didn’t actually have a multiply instruction.  Each row vertically would be a change in the Y position byte which I suspect was the high byte fed to the random gen.  The random gens back then were simple : take last number multiply by A and add B where A and B had no common factor. Normally primes.  These are only semi random because certain sequences will never happen – example 7, 7, 7.”
  • “So probably all bits of Y are pushed out of the random number.  So you could run vertically and repeat every 4 – BUT the 4 rooms would be different each game (and maybe each death).  Personally I think running down in to a room is the hardest path to survive.”

BerzerkMazeStack

The Maze changes!  How does the MG work (based on diagram below) in comparison to the “first game of the day” maze start and second maze?

  • If you survive, the second maze to the right is always the same.  Yet if you die in the first maze, the next maze is different.  How does that room numbering work in this scenario?
  • Alan- “I suspect all other “patterns” like “I think the first room after death is alway more open” are based on the non-randomness of that random number generator.”
  • Fun tip- If you hit start immediately after starting Berzerk you will get the first screen seen below.  If you wait until the attract mode makes the first maze, when you start the game you will see a different starting maze!
  • These 2 images show what happens if you exit the first maze to the right

BerzerkStartMazes

  • the image above shows the next maze (to the right), if you die within the first maze.

Deja Vu- The “Box pattern”  is another facet of the non-randomness of the RNG.

  • Made famous by Joel West stating in Chasing Ghost’s that you can teach a monkey to play a few mazes, but you can’t teach a man to play Berzerk (1:58 of Youtube)
  • This Youtube clip shows the famed box pattern being implemented, where you can navigate rooms in a box pattern repeatedly.
  • Imagine how long it would take the average player, one quarter at a time, to start figuring out loopholes in the RNG that create repeated scenarios like this?!  A small fortune of quarters spent in a 1980’s arcade! Plus being able to have the cognitive awareness to identify patterns in randomization of a computer processor would surely indicate a very high level of intelligence.  Humans win again!

BerzerkBox

CLICK for a detailed map of the Berzerk mazes generated by the Maze Generator

Further detailed Technical reading for the programmers in the audience that wish to explore the Code aspect of the maze generator HERE

Back to the Main Berzerk Page HERE

 

 


Copyright © 2012. All Rights Reserved.