Alma, Skull, and Leeper: Complex AI from Simple Instructions

Enemy AI is hard. I had us start with Medusa and Don Medusa because their movement is so straightforward. I can honestly say without hyperbole that I believe every other enemy's AI is more complicated.

I mean, look at those gyrations

Alma's movement might be the most complex-looking. An Alma can chase you across the puzzle, hunting you relentlessly and weaving its way through tunnels with scary proficiency.

For goodness sakes, Lolo, run!

I remember Halo: Combat Evolved when it first came out, with its mind-blowing squad-based enemy behavior. I remember hearing that a single Combine Soldier in Half Life 2 is powered by thousands of lines of code. Game programmers have been rightfully bragging about smart and complex AI systems as long as video games have existed. But Lolo was on the Famicom! How did HAL code that behavior on a Famicom?

Well, at first they didn't.

Alma on Eggerland for the FDS was a bit of a dumb-dumb. Yeah, just… painfully stupid.

Frankly, Alma’s behavior here is inscrutable to me. In this example, Alma is trying to move “towards” Lolo, but not always. Alma seems to change to the leftward direction when in the same column as Lolo, but then Alma is willing to move “away” from Lolo to follow the left wall a bit. If anyone has a more thorough understanding of this behavior, please dear glob put it in the comments, I’d love to satisfy my curiosity on this behavior. That said, for Eggerworld, I’m really only interested in Alma’s more potent intelligence from future games.

So let’s look into the future for a more favorable Alma AI, specifically Eggerland: Meikyuu no Fukkatsu and onward. There were some important advancements in the 80s in the field of general computer AI, and I presume those helped HAL improve their own AI offering. Again Boids comes to mind; Craig Reynolds’ Boids paper was published in 1987. Like Boids, Alma’s improved logic seems to follow a simple set of instructions that very effectively emulates pathfinding.

Look at Alma being all smart and following walls and stuff

Obviously we’ll need to dissect this behavior if we are going to implement it ourselves. I’ve put Alma through a gamut of tests in all the games I could get hold of. Thankfully, both Eggerland: Departure to Creation and Revival! Eggerland (aka Eggerland for Windows 95) have editors, so I could conduct controlled experiments to get us this information:

1. In an open field, Alma runs in the same direction as long as running in that direction moves Alma closer to the player.

2. In an open field, if Alma’s forward movement would take it further away from the player, then Alma will rotate 90 degrees left or right such that Alma’s next forward movement brings it closer to the player. Alma will not turn unless it has to.

These are two simple rules to describe Alma’s charging behavior, with emphasis on simple. But what if there’s something in the way when Alma tries to move forward? Well, based on my observation, when the two simple steps above fail, then Alma shifts to a totally different set of simple steps-- a different “state” of mind.

Oh, state of mind, you say? Do I detect a hint of State Design Pattern in that sentence?

Yes.

I recommend we implement Alma’s rules of behavior as states in a state machine. Let’s label the first state as the “chase” state. When Alma hits an obstacle that prevents them from following the chase state rules, then Alma enters the “patrol” state. Patrol is defined with the following rules:

1. When entering the patrol state, remember the direction of Alma’s charge right before patrolling; if patrolling causes Alma to face that direction again, then switch from patrolling back to charging.

2. When entering the patrol state, turn to face Lolo and start following the wall that obstructed the charge. Keep following that wall, turning 90 degrees to stay on it as needed. If a 90 degree turn is not possible, then perform a 180 degree turn. If no movement is possible, then stay still and do not turn.

Here’s what it looks like in Eggerland: Departure to Creation.

Huh, what did you say? Corner cases? Well... Shut up.

Sadly, this “patrol” logic is a case where the verbal description of our job is easy, but the logic itself is… well, I’ve whipped up a proof of concept for you to inspect, but it’s messy. Maybe there’s a way to simplify it, but check out what I have for patrolling so far:

Point loc = alma.region.getCentermostPoint(); // Determine which way the Alma can move if (alma.canMoveInDirection(alma.preferredTurn.getNextDirection(alma.direction), gameRoom, MoveType.ENEMY_MOVE)) {    alma.previousDirection = alma.direction;    alma.direction = alma.preferredTurn.getNextDirection(alma.direction); } else if (alma.canMoveInDirection(alma.direction, gameRoom, MoveType.ENEMY_MOVE)) {    // do nothing, alma's direction is already correct } else if (alma.canMoveInDirection(alma.preferredTurn.getPreviousDirection(alma.direction), gameRoom, MoveType.ENEMY_MOVE)) {    alma.previousDirection = alma.direction;    alma.direction = alma.preferredTurn.getPreviousDirection(alma.direction); } else if (alma.canMoveInDirection(alma.direction.getOppositeDirection(), gameRoom, MoveType.ENEMY_MOVE)) {    alma.direction = alma.direction.getOppositeDirection(); } else {    // No movement is possible, so face a player if possible    // First, get the closest lolo that's on the same horizontal plane as Alma    Optional<Lolo> closestLolo = gameRoom.lolos.stream().filter(lolo -> lolo.region.getCentermostPoint().y == loc.y).min(Comparator.comparingInt(lolo -> Math.abs(lolo.region.getCentermostPoint().x - loc.x)));    if (closestLolo.isPresent()) {        // Alma will turn to face Lolo to the left or right even when it's stuck standing still        Point loloCenterPoint = closestLolo.get().region.getCentermostPoint();        alma.direction = loc.isOtherPointInDirection(loloCenterPoint.x, loloCenterPoint.y, Direction.LEFT) ? Direction.LEFT : Direction.RIGHT;    }    return false; } // Move in the decided-upon direction alma.region.shift(alma.direction, 1); alma.moveCooldown = Alma.MAX_MOVE_COOLDOWN; // A relatively unique circumstance where the state change is only performed AFTER the update. This is so // that an Alma only enters the Charge state if its move is successful if (alma.direction == alma.chargeDirection) {    alma.state = AlmaStateCharge.enterState(); }

Not my cleanest code, but it seems to get the job done

You may notice that I rely on a member variable called “preferredTurn” here. The “Turn” class is one abstraction I’m satisfied with and it cleans up some stuff that would have been even uglier without it. Like the “Direction” enum, “Turn” is an enum that represents either clockwise or counter-clockwise, and it helps Alma remember which wall it should be hugging. We can also ask the Turn class for the Direction Alma would face if it decided to turn that way, which means the code doesn’t have to be aware of the difference between up, down, left, or right, it can operate more generally in terms of just a Direction and a Turn.

public enum Turn {    CLOCKWISE(1),    COUNTER(-1);    private final int indexShift;    Turn(int indexShift) {        this.indexShift = indexShift;    }    public Direction getNextDirection(Direction currentDirection) {        return Direction.values()[(currentDirection.index + 4 + indexShift)%4];    }    public Direction getPreviousDirection(Direction previousDirection) {        return Direction.values()[(previousDirection.index + 4 - indexShift)%4];    }    public Turn getOppositeTurn() {        return Turn.values()[(this.ordinal() + 1)%2];    } }

Much more proud of this because it’s short, sweet, and easy to use

So let’s assume we have the Patrol state working. These two states are all that it takes to get an enemy chasing Lolo across the stage. It’s super effective in practice, and actually quite terrifying to try to escape in-game. There are just two states and their logic was defined above. We also know when those states transition into each other. Alma simply needs to maintain a state machine and tell the state machine to update(), and with that, Alma will chase Lolo. Better still, it’s not just Alma that uses this logic, the chase and patrol states are shared by Leeper and Skull as well. We’ve completed three entities for the price of one! This is most obvious when we compare their movements to each other in Departure to Creation:

I do love a good [3 for 1 specil]!

I’m bending the truth a little bit, because we do have a bit more work to do for each of these entities. They’re not repeat enemies, after all. First, and easiest, Skull only begins moving once the player collects the last heart frame, so Skull has an extra “waiting” state where it does nothing until it notices the last heart frame is gone. Once the last heart frame is collected, Skull enters the charge state and never re-enters the waiting state. I’m not going to go into great detail about the waiting state.

Leeper has its own unique behavior; instead of killing Lolo on touch, Leeper will permanently fall asleep the moment it neighbors Lolo’s position. Leeper’s “sleeping” state means it should do nothing and also should never transition to another state ever again, so, piece of cake!

Alma has a rolling behavior whenever Lolo is on the same horizontal plane. The moment Lolo occupies the same horizontal plane, if there is space for Alma to move towards Lolo, then Alma will curl into a ball and roll in Lolo’s direction endlessly until they hit an obstacle. Once the roll starts, Alma will continue to roll even if Lolo moves out of the way.

Alma’s not so scary once you realize your secret matador powers were inside you all along

This can be a third state for Alma. It’s not sleeping or waiting, but it’s still simple compared to the Charge state and the Patrol state. After Alma is done rolling, they should transition back into the Charge state.

There may be some corner cases we need to work out like which way these enemies should turn when either turn is equally valid, but I’ll do that homework on my own so you don’t have to. For now, I think we should just celebrate that we’re more than halfway through implementing the enemies in this game, and we’re arguably through the most complex of them now that Alma, Skull, and Leeper are solved. I’m excited!