Berzerk Arcade Video Game Maze Generation
|
| Berzerk Arcade Video Game - In Game Screen |
Berzerk is an arcade video game designed by Alan McNeil and released in 1980. Its a 1 or 2 player survival game where the only objective is to shoot as many robots as possible and last as long as you can scoring as much as possible. Originally designed as a black and white game, a video colour overlay chip was added late in the game design to provide simple colour but being a colour overlay chip, this leads to some colour clash when different coloured objects are close together.
For anyone who has ever played the 1980 Berzerk Arcade Videogame, you will know that it has a number of amusing querks including how the enemy robots accidentally shoot each other and often bump into maze walls and destroy themselves.
An important part of the game is the maze area in each room that you enter. On initial gameplay, the mazes appear to be "Perfect" as in all areas of the room can be accessed through the maze, however if you explore the game enough, you will find rooms that have "penned in" areas in the centre of the screen that you cannot access.
Berzerk advertising material claimed that the game had (depending on the source you read) either "64000 different random mazes" or "over 64000 different random mazes".
For anyone who has ever played the 1980 Berzerk Arcade Videogame, you will know that it has a number of amusing querks including how the enemy robots accidentally shoot each other and often bump into maze walls and destroy themselves.
An important part of the game is the maze area in each room that you enter. On initial gameplay, the mazes appear to be "Perfect" as in all areas of the room can be accessed through the maze, however if you explore the game enough, you will find rooms that have "penned in" areas in the centre of the screen that you cannot access.
Berzerk advertising material claimed that the game had (depending on the source you read) either "64000 different random mazes" or "over 64000 different random mazes".
|
| Berzerk Arcade Video Game - Flyer |
I gathered a lot of information on Berzerk a while back when I was working on a Berzerk remake. I did a lot of playing the game and scribbling notes and also a lot of reading.
I was specifically interested in how the mazes were generated. Initially I though that maybe Kruskal's Maze Algorithm had been used. This uses random generation to create a "perfect" maze as in a maze where all locations on the screen can be visited.
I came to the conclusion that Kruskal's couldn't have been used for two reasons:
1. Kruskal's Maze Algorithm takes some working out in memory before the maze can be displayed, and as RAM in arcade machines was on the very low side, I doubted that additional RAM would be included to generate a maze.
2. The Mazes that Berzerk generated weren't always perfect. There would be some rooms with "Penned Off" areas in the centre of the screen.
After some head scratching and with no solution in sight, I contacted Alan McNeil (Berzerk Creator) himself via email to discuss the maze generation and he obliged me with a good thorough explanation.
And so, this is how the mazes are generated in Berzerk.
I was specifically interested in how the mazes were generated. Initially I though that maybe Kruskal's Maze Algorithm had been used. This uses random generation to create a "perfect" maze as in a maze where all locations on the screen can be visited.
I came to the conclusion that Kruskal's couldn't have been used for two reasons:
1. Kruskal's Maze Algorithm takes some working out in memory before the maze can be displayed, and as RAM in arcade machines was on the very low side, I doubted that additional RAM would be included to generate a maze.
2. The Mazes that Berzerk generated weren't always perfect. There would be some rooms with "Penned Off" areas in the centre of the screen.
After some head scratching and with no solution in sight, I contacted Alan McNeil (Berzerk Creator) himself via email to discuss the maze generation and he obliged me with a good thorough explanation.
And so, this is how the mazes are generated in Berzerk.
For the initial screen setup, the outer walls are drawn with openings at the top, bottom, left and right to enter/exit the room.
After this, the internal wall configuration needs to be generated.
After this, the internal wall configuration needs to be generated.
The game has 8 theoretical posts or pillars, 2 rows of 4 posts. Attached to each of these posts is a wall which can either be placed pointing up, right, down or left from the post.
The direction of the wall is decided using a pseudo-random generator based on a number sequence similar to a fibonacci sequence but using the room number as one seed number and a fixed value as the other. In this way, while the wall generation looks random, if you leave a room and then revisit it, the walls should come up the same as the first visit.
The direction of the wall is decided using a pseudo-random generator based on a number sequence similar to a fibonacci sequence but using the room number as one seed number and a fixed value as the other. In this way, while the wall generation looks random, if you leave a room and then revisit it, the walls should come up the same as the first visit.
A wall in one of four directions is generated for each "Post" and this forms the maze in the room. Often one wall is drawn straight over the other so that it looks like there are less than 8 walls e.g. if the wall on post 1 is pointing straight down, and the wall on post 5 is pointing straight up then they are drawn on top of each other and look like just one wall. This means that in extreme cases, the room could only apear to have 4 walls as each of the 4 walls is overwritten by the other 4 walls.
This led to some confusion when I was working on my remake. I would visit room after room writing down how many walls were in each room and coming up with a range of walls that should be randomly generated. As explained above, this was not what was happening at all.
This led to some confusion when I was working on my remake. I would visit room after room writing down how many walls were in each room and coming up with a range of walls that should be randomly generated. As explained above, this was not what was happening at all.
The wall post positioning is somewhat odd as well. If post 2 has a wall pointing straight up, the top of the wall makes the top door / opening smaller as posts 2 is aligned to be within the door opening.
This is also true for post 6 having a wall pointing straight down.
This is also true for post 6 having a wall pointing straight down.
And so to wrap this post up and return to the statement made at the beginning about either "64000 different random mazes" or "over 64000 different random mazes"...
The game has eight wall posts with a wall attached to each in one of four directions. This makes 4 x 4 x 4 x 4 x 4 x 4 x 4 x 4 = 65,532 possible inner wall combinations and hence the statements "64000 different random mazes" or "over 64000 different random mazes".
The game has eight wall posts with a wall attached to each in one of four directions. This makes 4 x 4 x 4 x 4 x 4 x 4 x 4 x 4 = 65,532 possible inner wall combinations and hence the statements "64000 different random mazes" or "over 64000 different random mazes".
Comments
Post a Comment