Implementing Rocky: Who Wins When Push Comes To Shove?

Many gamers probably never have to think about the order in which entities perform their frame updates. If developers make their games immersive enough, then gamers never have to. But someone has to think about that nitty gritty stuff, and today it’s going to be me and you.

Rocky is an enemy introduced in Eggerland 2 on the MSX who slowly wanders the puzzle. When Lolo is nearby, Rocky will pause to become an obnoxious obstacle. An obnoxtacle. Have you ever tried to pass someone in a hallway, so you move to the side but they move the same way? Then you both bob back and forth trying to get around each other. Well that’s Rocky all the time, and he just loves doing it on purpose. Worse still, when Lolo enters the exact same column as Rocky, Rocky will abandon all reason and endlessly charge at Lolo, pushing Lolo if he can and standing there menacingly even when he can’t push. Rocky never directly harms Lolo, but he’s so good at being in the way that a court of law would probably qualify it as emotional harm.

"I charge you with like a billion counts of Unlawful Detainment" -The Court of Law, probably

Hidden in this behavior, there are two coding mysteries to solve, the first being how he moves and the second being how he pushes. Let’s get the movement out of the way first.

Rocky may seem to simply mill around, but barring his uncontrollable urge to bum rush Lolo, he’s actually following a very predictable and rigid path. Rocky will always move forward if he can, but if he hits a wall, then he will turn right. If he can’t go forward or right, then he’ll turn left. If forward, right, and left are all out of the question, he will turn back the way he came. Naturally, if no direction is available, then he jogs in place.

Gotta get that 10,000 steps

This movement is trivial to code up, it’s a perfectly rigid rules-based movement pattern. Here’s how it currently looks in code:

    // If Lolo is not in Rocky's threat area then attempt to find a direction to move in
    if (rocky.canMoveInDirection(rocky.direction, gameRoom, MoveType.ENEMY_MOVE)) {
        // Do nothing, because Rocky is already facing the correct direction
    } else if (rocky.canMoveInDirection(rocky.direction.getClockwiseDirection(), gameRoom, MoveType.ENEMY_MOVE)) {
        // Change Rocky's facing to move to the right
        rocky.direction = rocky.direction.getClockwiseDirection();
    } else if (rocky.canMoveInDirection(rocky.direction.getCounterClockwiseDirection(), gameRoom, MoveType.ENEMY_MOVE)){
        // Change Rocky's facing to move to the left
        rocky.direction = rocky.direction.getCounterClockwiseDirection();
    } else if (rocky.canMoveInDirection(rocky.direction.getOppositeDirection(), gameRoom, MoveType.ENEMY_MOVE)) {
        // Turn Rocky back around to move backwards
        rocky.direction = rocky.direction.getOppositeDirection();
    } else {
        // If there is no good direction, then just return false and do not move at all
        return false;
    }

    // Move in the new direction
    rocky.region.shift(rocky.direction, 1);
    rocky.threatRegion.shift(rocky.direction, 1);
    rocky.moveCooldown = rocky.maxMoveCooldown;

    // Movement succeeded, so return true
    return true;

Now let’s throw Lolo into the mix; Rocky has a “threat region” just like Gol. In Rocky’s case, he goes all deer-in-headlights, standing there obnoxtacly. This deer-in-headlights threat region is defined by a cross-ish shape surrounding Rocky, one space above and below him, and three spaces left and right of him. You can see this visualized in the graphic below, where all of the squares highlighted yellow around Rocky represent his threat region. If Lolo overlaps even a single yellow square of this region, Rocky will freeze in place.

Yes, even the space inside Rocky counts. Yes, it does happen. No, don't ask how.

We have seen how the Rectangle/Region code works many times now, we came up with that stuff all the way back at the beginning, so I'll skip over that and move right into Rocky’s charging mechanic. As stated before, if Lolo is in Rocky’s exact vertical, then Rocky abandons all previous logic and charges in that direction at double his normal speed. Rocky will even ignore his threat region logic while Lolo is in his column. Once a charge is triggered, Rocky won’t stop until he hits an obstacle. Like the entity state diagram a few posts back, I recorded all this behavior on paper a long time ago:

This handwriting wasn't originally meant for other humans, so... yeah, sorry about that

Movement is nearly complete at that, all except how Rocky pushes Lolo. This is the second overarching problem we needed to solve in the code, and it’s a doozie. I say that a lot, but Lolo seems to be a doozie-y game. And this might be one of the dooziest problems yet.

Take this example: Rocky is charging downward at Lolo. Just as Rocky is about to push Lolo, Lolo decides to push an emerald frame to the left, leaving Rocky's column. Lolo should succeed because he can push emerald frames and move into their space, out of Rocky's way. But what if the emerald frame is blocked by another Rocky? And what if that other Rocky moves out of the way at the same moment Lolo is pushing the emerald frame? Lolo usually succeeds because of his higher priority, but in this case his success is dependent on another Rocky. Lolo attempts, fails, and is pushed downward. But has Lolo already pushed the emerald frame? If the order of updates isn't exactly right, it sounds like Lolo could push the emerald frame and Rocky pushes Lolo. Hmm...

This is another case where the expected behavior is easy to describe but the code is insidious to implement. It’s time I introduce you to the three biggest consequences I had to wrestle with when entities started pushing each other:

1. Pushing entities must be able to move other entities during the pushing entity’s update

2. Entities need access to a dynamic priority system for various actions that temporarily need higher priority than other actions

3. Entities must be able to retry movement options that might have failed before lower-priority entities got the chance to move

That first thing already happened when we implemented Pushey for Snakey and Emerald Frames. Consequently, the second item became complicated since a pusher entity can push a pusher entity, like Rocky pushing Lolo who’s pushing an emerald frame. To address the second item, entities now have priority pools to call update() sooner or later if they need to, it’s essentially a fixed collection of HashSets. Not the most dynamic solution but more than enough for now.

The third item has to do with making sure enemies behave consistently regardless of the order they appear in the game's internal data structure. Entities packed right next to each other might behave differently simply because of the order their load order, which is debatably not ideal. One entity could be blocked in by a second entity during its update, but then the second enemy moves away during its own update, making it look like the first entity other was just being lazy. You can see the effect of this issue in the NES/Famicom games, especially with this chain of Don Medusas I made in Departure to Creation, slowed down so it's easier to see:

It's like an accordion that wants to kill you. Well, I mean more than usual for accordions.

HAL didn't feel the need to address this problem because the effect can seem small in most cases. Also the code solution is performance-intensive, so developers on the NES probably had to pick their battles wisely. Entities in Eggerworld have modern hardware to work with, so they can retry movement in the event that they fail to move the way they wanted. We accomplished this by allowing the Entity update() method to return a boolean, true if the entity's update succeeded and false if it failed.

Every entity that fails its update is placed in a retry pool. Once every entity has tried its update, the code retries every entity in the retry pool in case some obstacle got out of the way during all the updating. Newly successful updates are removed from the retry pool and repeat failures remain in the pool. If even one retry succeeds, then the code retries every remaining entity in the pool once again just in case. These retries keep going until either the pool is empty or every single entity in the pool fails its update. The time complexity of the update code increases from O(n) to O(n*log(n)), for those who care about that nerdy stuff. But don't worry, most real-world puzzles don't have accordions made of don medusas, so you can expect game performance to remain reasonable.

With those things, Rocky is ready to push Lolo around and be the obnoxtacle he was born to be. So far, our testers have been rather emphatic about their opinions on Rocky, using loving pet names for him like “jerk”, “loser”, “blockhead”, and… lots of colorful metaphors. As the Blue Team Gladiator always says to me, “Congratulations… hope it was worth it.”