Decoding the Berzerk AI

The artificial intelligence of the robots is really the heart and soul of Berzerk.  Without it, you're just walking around shooting at things, and a great many of the arcade games released in the late '70s and early '80s let you do that.  In what follows, I'm going to take an inductive approach to dissecting the AI.  If anyone knows of a full disassembly of the arcade source code and can confirm or deny what I detail below, please let me know.

Firing

One thing that seems clear from my experiments with Berzerk is that the AI does not have a sophisticated firing algorithm.  Any time the middle of your body lines up with one of the robots' eight firing lines, they will fire at you.  This is true no matter how far away they are or what's in front of them.

Clips of gameplay from the 1980 arcade game, Berzerk.  Here the player tries to get the robots to shoot at him.

The frequency and speed of the robots' shots increase with level, and at the lower levels they fire infrequently enough that you can sometimes cross their firing line without getting shot at.  Note that it's not enough for your legs or head to be vulnerable -- they will try to line themselves up to hit the center of your body before firing.

Movement

The real nuance of the robot AI is in their movements.  Ultimately, it comes down to two things: tracking the player and avoiding walls.  The reason nuance is required, however, is that these two things are very frequently at odds.  Most robots will have at least one wall between themselves and the player to start the level, so they can't just run straight at the player.

Let's start with the first part of the AI: tracking the player.  Let's suppose the robots are able to track the player's position at all times, and that they always try to move towards them.  How would they move?

A clip of gameplay from the 1980 arcade game, Berzerk.  Here the robot tracks the position of the player and moves in response to the player's movements.

In the example above, the arrows show the eight possible directions that the robot can move at any time.  If the robot wants to move closer to the player, it will need to move in one of the three directions indicated in green, and this does, in fact, seem to always be the case.  But how does it decide which direction to go?  For example, why does it start by moving downwards instead of on the diagonal?  That's where the walls come into it.

The grid layout of the 1980 arcade game, Berzerk.  Mazes are randomly generated using a 3 x 5 template.

The Berzerk mazes are laid out within a 3 x 5 grid, with cells about 65 pixels tall and 50 pixels wide.  Robots never seem to walk directly into walls (except at the ends, but more on that later), so there must be an aspect of the AI preventing them from these collisions.   If the player is stationary, the robots' movements only appear to change when they cross to a new cell, suggesting that they're keying in on the walls in their current cell.  If robots want to maximize their motion towards the player without hitting walls, the following simple rules could be applied:

[Updated 03/26/20, new parts in bold]

1)  Don't move in any direction that brings the robot closer than a given distance to a wall in any of his currently occupied cells.
2)  If there are no walls in any of the robot's currently occupied cells that hinder motion to the player, move towards the player.  Unless the player is straight along the horizontal or vertical, this will be diagonal motion.
3)  If diagonal motion would cause the robot to get too close to a wall in any of his currently occupied cells, then move along the other component of the vector towards the player (that is, along the wall).
4)  If both components of the vector to the player are obstructed by walls, stop the robot.

Now let's revisit the case we looked at before:

A clip of gameplay from the 1980 arcade game, Berzerk.  The grid cells are overlaid to demonstrate the movements of the robots as they go from cell-to-cell.

1)  The robot starts in A4, moving down along the vertical because the horizontal is impeded by a wall in his cell.
2)  When the robot is completely past that wall and inside B4, it starts moving diagonally down towards the player because B4 doesn't have walls in either direction.
3)  The player moves above the robot before he leaves B4, so it starts moving diagonally upward (again, no walls in either direction).
4)  B3 has a wall at the top, so the robot can only go left towards the player.
5)  B2 has a wall on the left, so the robot must go up to approach the player.
6)  Finally, the robot enters A2, which is on the top edge, so the robot can only go left.

[Passage below was removed on 03/26/20]

Note that the robot won't add components to its motion until it's entirely in the new cell (e.g., A4  B4), but it will remove them just as it starts entering a cell with a wall in that direction (e.g., B4  B3).

Special Cases

The rules described seem to account for the motion of the robots in the vast majority of situations, but there are some special cases worth noting.

Close Approach

Clip of gameplay from the 1980 arcade game, Berzerk.  When the robot is in the same cell as the player, it goes straight for him.


If the player and the robot are in the same cell, the robot will move towards the player no matter what walls are in that cell.  You can sometimes make use of this fact to line them up or bring them into your firing line, but it's obviously a risky maneuver.

Screen Edge

From the standpoint of the robots' movements, all screen edges are walls, even if they have openings in them.  Since these openings are only meant for the player to go through, it makes sense that the robots would not walk towards them.

Wall Ends


In my Berzerk strategy guide, I mentioned that the robot AI can be made to smash into the ends of walls, and now you can see why.  Because the wall the robot is smashing into is not one of the boundaries of the cell it's occupying, it's not aware of it.

On rare occasions, you'll see robots walk into the walls of the cell they entered.


Here, I think what's happening is that the robot stopped its vertical motion as soon as it entered the cell with the wall at the bottom, but it was already walking toward the end of the wall at that point.

[03/26/20 - The robot has not moved close enough to left wall to be stopped by it, but stopped moving downwards the moment his sprite began crossing into the left cell, which has a bottom wall.]

Comments

  1. I think the movement rules work like this:
    1: Robot picks a direction that it wants to move. (set X=[-1,0,1], set Y=[-1,0,1])
    2: If the X-axis direction would move too close to the vertical wall of the currently occupied cell, don't. (set X=0)
    3: If the Y-axis direction would move too close to the horizontal wall of the currently occupied cell, don't. (set Y=0)
    4: Robot moves if it can. (set robotX += X, set robotY +=Y)

    In your last gif, the robot wants to move southwest. Rule 2 only considers the west edge, and since it never gets close enough to trigger the rule, it keeps moving west. Rule 3 gets triggered as soon as it enters the cell containing a wall on its south edge, and the Y-movement then becomes 0.

    ReplyDelete
    Replies
    1. I initially was going to pose the rules in terms of distances to walls, but found it problematic because "too close" didn't seem to be the same in every case. But I see what you're saying about that last example: the way I have it posed right now, the robot should stop when part of it enters the new cell. I'll revisit my distance measurements.

      Delete
    2. So I think both of our sets of rules explain the vast majority of what's going on here, but what I'm still puzzling over is the transition of the robots from one cell to another. In my GIF with the cells labelled, notice how the robot at the top behaves in A2. There's no wall on the bottom, but it doesn't seem to recognize this until it's well inside the cell. Fine, but then as it's moving diagonally downward, it seems to recognize the lefthand wall of B2 just as it's entering it. This was what led me to include the following passage to the article (which should probably have been added as a rule):

      "Note that the robot won't add components to its motion until it's entirely in the new cell, but it will remove them just as it starts entering a cell with a wall in that direction"

      But this is refuted by the last case, where the robot fails to remove its forward motion just as it's entering the new cell. Your rules can explain this, but we still need a condition to explain why sometimes the robot responds to a change in the walls just when it's entering a new cell and sometimes it responds just when it's leaving.

      My current thought is that the robot is considered to be in *both* cells when it's on the boundary and that it will react to a wall within a specified distance in either cell. And the distance criterion has to be different for the horizontal than for the vertical, but that's probably okay given the dimensions of the grid.

      Delete
    3. It makes sense that a robot may be aware of walls in adjacent cells when close enough to the border. I don't believe robots will ever walk into convex corners. E.g. the robot in B4 will not walk into the top-left corner despite B4 not containing any walls on the top or left edges. Therefore, it must be aware of either B3's top edge or A4's left edge as it gets close.

      Robots also don't get paralyzed with indecision when approaching a corner in this manner. I think the best explanation for this is that a robot only checks one adjacent cell per AI loop. In the B4 example, the robot is only aware of B3's top wall, and therefore it halts upward movement, but continues walking left, unaware of A4's left wall.

      You can get away with a lot of shenanigans by using MAME's cheats to turn off robot firing and evil Otto. Just be careful about invincibility, because that will turn off general collision detection and break the AI.

      Delete
    4. Thanks for the MAME cheat suggestion, I just tried that myself.

      In the B4 example, it looks to me that it's just not close enough to A4 to be considered overlapping and so it wouldn't pay attention to its walls. It begins disregarding A4's left wall in its original descent at about the same vertical position.

      Delete
    5. Hi, while googling for "berzerk disassembly" to check if search engines were listing it, I found this blog.

      Berzerk's disassembly is here: seanriddle.com/berzerk.asm
      Frenzy (the sequel to berzerk) disassembly is here: https://github.com/ScottTunstall/FrenzyZ80Conv

      Delete
    6. Thanks for leaving the link. Deciphering AI algorithms from assembly code is not something I’m eager to tackle right now, but it’s good to have it here for reference.

      Delete

Post a Comment

Popular Posts