Championship Lode Runner: Guard psychology and analysis of the C code

I expended a great deal of time working on a reckoning routine that would not be trapped by such lakes and yet would retain desirable economies of motion. After much wasted effort I discovered a better solution: delete U-shaped lakes from the map. - Chris Crawford

 

Anyone who's played Lode Runner for an appreciable amount of time comes to understand that the pathfinding AI can be a bit whack. It's clearly not a greedy algorithm, but it's also one that must take some shortcuts in order to fit in the Apple II+'s 48KB of memory, and it doesn't take much for the guards to get confused and march in erratic directions that get them nowhere. For the most part you don't really need to exploit or understand this - when the guards are acting dumb, getting stuck on ladders, and walking around in circles when there's a perfectly clear and direct path to getting the runner, you just shrug and grab those crates unmolested. Otherwise, you just find ways around them and dig traps for them to stumble into when they're in your way.

This is very different in Championship Lode Runner, a set of 50 user-made, Broderbund-curated levels whose creators, much like the authors of modern Kaizo-style ROM hacks, understood the engine better than its programmer had, and with this knowledge made bastard hard levels.

So, at the suggestion of Renga in Blue author and occasional commenter Jason Dyer, I thought I'd take a post to analyze the Lode Runner AI and better understand just what's going on inside those Bungelings' subpixel-sized brains. Coder Simon Hung remade Lode Runner, porting from C code that had been officially published in a Taiwanese reference book, and his conversion was invaluable in understanding this.

Goal 1: Get the runner

The first rule, after a few trivial rules that more concern physics than AI (e.g. falling, climbing out of pits, not passing through other guards, slowing down proportionally to the number of guards), is pretty simple to understand:

If I am on the same vertical level as the runner, and there is a clear path to the runner, then move toward the runner.

Pits dug by the runner are ignored, and subsequently fallen into.

 

Natural pits, however, are regarded as obstacles.

 

Walls, curiously, are also ignored. I'll assume I can just walk through them. I can't, but if the runner is on my level, I'll try anyway.

Climb the ladder? Are you nuts? That would move me off the runner's level!

Goal 2: Approach the runner's level

Here's where things get more complicated. If I can't just beeline for the runner, either because I'm not on the same vertical level, or because something seems to be in my way, then my second and final priority is to get to an advantageous level.

To do this, I will first look down, then up, then left, and then right. Each direction is assigned a score based on how advantageous it appears, and the lowest scoring direction wins. I will pick a direction that allows me to ascend or descend, but these are the outcomes from most to least favored:

• Get on the runner's level. In the event that there's more than one way to do this, the shortest path from me to the level (not necessarily to the runner himself!) wins.
• Get above the runner. If there's more than one way, then the closer I wind up to the runner's vertical level, the better.
• Get below the runner. The closer to the runner's vertical level, the better.

 

When multiple moves score the same, the first one examined wins.

Let's look at an actual level to illustrate:

 

Three guards are present here, one on the upper-left, one toward the right, on the monkey bars, and another between them, by the ladder.

 

Step 1: Look down

Only the guard on the monkey bars has the option of moving down, so this step is meaningful only to him.

Guard logic: From above this ladder, I have a clear shot all the way to the bottom.

 

Let's look at all of the places in this column where I might disembark left or right:

I will not consider disembarking left or right from a ladder into a freefall unless I am at the top or bottom of it. The runner might consider it, but I won't.

What luck, the bottom of this drop, where I can move left or right, puts me exactly on the runner's level! This column is 0 tiles away from my current position, so I give this direction an unbeatable score of 0.

Notation: "↓ =0" : "If I go down I will be level with the runner with a score of 0."

Step 2: Look up

This time, only the middle guard has the option of climbing upward, so we'll see about him:

Guard logic: I can climb this ladder to the top, and there are three places I might disembark from:

I'll already be above the runner at the first stop, so I must stop there and climb no higher. I'll be nine levels above the runner, so I give this path a score of nine.

Notation: "↑ >9" : "If I go up I will be above the runner with a score of 9."

Step 3: Look left

All of the guards can move left, so let's start with the leftmost one.

Left guard logic:

There's a ladder to my left.

 There are two possible disembarkation points on this ladder:

Both of these put me above the runner, but the bottom one is closer - six tiles above him, so I give this path a score of six.

 

Middle guard logic:

There's a ladder to my left, with two possible disembarkation points.

The closest of the two puts me 11 tiles above the runner. This is not better than going up, so I disregard this path.

Right guard logic:

Let's see how far I can climb this bar to the left.

Note that, although I will not disembark into freefall from a ladder that I've climbed, this doesn't apply to ladders that I merely maneuver onto laterally.

That's a lot of options! Two ladders, each with multiple disembarkation points, plus I could just drop down from the bars where ever I feel like it!

Climbing to the first ladder to my left and taking it down gets me the closest to the runner, but this doesn't beat the option of dropping down and landing exactly on his level. So I disregard this path.

 

Step 3: Look right

All of the guards can move right. Let's start with the leftmost one again.

Left guard logic:

To my right, I can climb a ladder or keep going and drop off.

Either way, I'll land six tiles above the runner which does not beat the option of going left. So I disregard this path.

Middle guard logic:

There's a ladder to my right, which I could climb up or down.

 

Down all the way still puts me above the runner, but closer than my previous score (3 vs. 9), so this becomes my new path.

Right guard logic:

To my right I can either climb up a ladder or down a ladder.

Neither option is as good as my initial path of just dropping down to the bottom, so I disregard this path.

The final decisions:

Left guard goes left, so he can climb down the ladder and get you. Middle guard goes right, so he can climb down the ladder and get you. Right guard drops down so he can get you.

Seems elegant, right? Well,

 

When things get weird

Let's look at some examples of ways this two-step logic can go very wrong, which Lode Runner: Championship Edition demands you understand well enough to invoke on purpose:

Example 1: Fleeing the target

 

I'm on the ladder in the lower-right corner. So why are the guards running away? Why not just go right, climb down a tile, and kill me?

Simple - the AI doesn't realize it can reach this spot! As far as pathfinding goes, it is only considering places it can disembark from ladders and/or drop from.

 

The runner's spot was never considered a reachable endpoint. The spot below him to the left is, and the path there does cross the runner, so why not go there?

Because getting above the runner is better than getting below him. Doesn't matter how much farther away you wind up. Better to be three floors above the runner than one floor below him.

And so, the guards all go to the left, where they can climb ladders to a spot three floors above the runner. But what happens when they reach the ladders?

Example 2: Ladder physics suck

Ladder trouble - it's not just for Gordon Freeman

 

So the guard decided it's going to go for the ladder and take it up to a higher vantage point, right? But then when it gets to the ladder, it just sort of gets stuck there.

The reason is simple. When the guard is at the base of the ladder, it wants to climb up to the nearest disembarkation point. But the guards recalculate their paths with every step they take, and once the guard has climbed and is no longer considered to be at the base, the base becomes a valid disembarkation point, so he climbs down, entering an infinite loop! The guards on the left ladder are attempting the same, but have created a log jam.

If you climb your ladder up or down, you will become level with a valid disembarkation point and the guards will unstuck themselves.

Example 3: A reverse false wall

Two weird things are happening here.

First, as soon as you climb the first ladder, the guards chasing you turn around and climb the other ladder. They do this because both ladders will get them to your level, but the ladder on the right is closer (to them).

Second, once the guards reach the second ladder, they just won't go over the top of the ladder, as long as you don't. What gives? Shouldn't they want to reach the top, so they can reach the bars just above you, climb over, and drop down?

They would, except for one thing. Ladders against walls are confusing to guards, because their logic for determining valid disembarkation points determines walls in relation to where their feet will be, but not where their bodies will be! Every tile on the ladder is treated as a valid disembarkation point for pathfinding purposes - as long as you don't rise above the ladder, they'll try to beeline for you to the left, thinking they can step on the tile at their feet, but they can't because there's a tile in their way. They get stuck there.

Remove the wall, and they act a bit more sensibly.

Emphasis on a bit.

Example 4: Left-to-right reading order

 

Before I climbed that ladder, the guard was chasing me to the right. After I started climbing it, he turned around and started running for the ladder to the left. We already examined why he wouldn't necessarily chase me up the ladder, but why turn around and go for the one that's farther away?

It's because neither ladder reaches me (as far as the AI is concerned), but both go to the same level above me. Left gets evaluated before right, so left wins.

This is far from a comprehensive guide on the guard AI, and does not cover the many corner cases both implicit and explicitly defined in the game logic, nor any of the peculiarities of the game physics that sometimes dictates their behavior, but I think this more or less explains how the Lode Runner guards think, and illustrates what's going on in most of their screw-up situations. For now, I'm going back to Championship Lode Runner's punishing levels.

Game 355: Championship Lode Runner

Hello. Have we met?

Just what I needed - another 50 levels of Lode Runner - the quintessentially classic puzzle platformer that I praised for its solid mechanics and inventive challenges but also criticized for being far too long. Essentially a retail level compilation disk, compiled from the best user-made submissions to Broderbund, Championship Lode Runner offers no new enemies, nor obstacles, traps, or treasures, and even removes the original game's level editor. What you get instead is difficulty - this one wastes no time with simple levels, presuming that only Lode Runner experts will bother.

In this first level, the guards are easily trapped in the space below, letting you grab the treasures suspended in the air from the rope above uninhibited, but then retrieving the two crates at the bottom is a problem. You can either blast one of the walls adjacent to the ladder and make a mad dash for them and return, which requires frame-perfect movement and timing and absolutely can't tolerate any guard interference, or you can manipulate them into falling down the middle and getting the crates for you, which requires precise manipulation of the AI which I still don't understand well enough to perform reliably.

Instead of a level, select you have the option to save and load games in progress, but even loading your game is punitive! Loading a file permanently removes one of your lives, and does this every time you load it. It didn't take long at all to realize I'd never beat Championship Lode Runner fairly, but the game even blocks emulator save states by booting you back to the main menu when it detects discrepancies between your disk and memory.

Well, crap. At least it can't detect WOZ backups! I think.

 

Forget my 30 minute rule - I'm saving and making a backup of the disk image every time I beat a level, to get around the penalty for loading. Especially when the levels are like this.

Cute design, but there's nowhere to dig and nowhere to run!

What becomes clear from even just the first two levels is that this level pack demands AI manipulation to get anywhere. It demands understanding things such as that standing on one part of the ladder will make the guards climb the monkey bars over to the right and drop down on you, but moving just one pixel down will make them swing to the left instead and isolate themselves from the pack, giving you some breathing room, letting you figure out a way to get all of them bunched up in a corner where they'll stay out of your way, and when you poke your head out will chase you single-file instead of surrounding you from all sides. I don't think you are expected to actually learn the AI routine in such granular detail that you can deduce the proper methods, but rather that through trial and error will uncover the specific tricks in each stage and learn where to go and when so that the guards get herded where you need them.

Now this leads me with another tricky problem - assuming I can power through and beat the game, how do I go about blogging it? Certainly not by describing every single level and its solutions in exhaustive detail - that wouldn't be fun for anyone. For the original game I gave updates roughly twice a week and showed off about 30 out of the 150 levels, giving some of them nothing more than a captioned screenshot and some others detailed accounts of their novel challenges and solutions. Even that approach felt like a chore, and stats tell me that most of my readership only bothered to read the first post and none of the subsequent updates. And progress through this game is likely to be much slower, at least in terms of how many levels I can beat per day.

As of right now, I'm on level 7, and I've been playing for roughly three hours, most of my progress made today. Some levels have definitely been more difficult than others, but five out of the six I've beaten required strange AI manipulation techniques as I've described. I'm open to suggestions on how frequently to update on my progress and/or in how much detail - updates on my progress in the original Lode Runner looked like this, for comparison. Part of me wants to just give my next and final update when I've beaten the damned thing, but that could easily take a week or two.