The Path to AI

Probably the most important part of Lode Runner is the monks chasing you. Without them, the game would be boring and not very challenging.
This is also the most important part of our version; whether or not the entire project was a waste of time really hinges on me being able to replicate the original's AI. This version not only needs to look and feel the same but actually play the same too.

As said previously, we don't have access to the original source code. Not knowing how the monks were programmed has left me having to repeatedly play the game and make recordings. Over 100 recordings. Whilst this obviously isn't ideal (I'd love the code!), there isn't any other alternative.

Path finding

As you probably already know, path finding and AI go hand in hand.
Even though it's not drawn on the screen, Lode Runner is a grid based game with each item occupying a cell. This has not only made the pathfinding easy to write but has enabled me to do so quickly.

First off, I played the original to determine which tiles (apart from the obvious) do not have an affect on the monks:

  • doors
  • teleports
  • liquid
  • fall through
  • phase

The monks treat these as if they're not even there, however, they will interact with them if their path happens by.

Puzzle 178

I had originally created waypoints for every tile but since the monks can't get to every tile, I now only create them where they can get to.
You'll notice that I've put nodes to the side of turf and ladders - monks can leap sideways off their current tile and fall.

Waypoints added

Now that the waypoints have been created, I iterate over them and decide if they should connect to each other.
The thin yellow lines in the following image are one way connections and the thicker lines means that particular waypoint has both an outgoing & incoming connection.

Waypoints connected to each other

Generating and connecting waypoints has only added an extra ~20-30ms to the load time which I'm quite chuffed with.

Path found!

This will need tweaking as we go because I've currently set the Cost for each connection to 1. I need to play the original more to determine if that'll do but from what I've seen so far, these monks really don't put much thought into how they are going to get you (they ignore teleports that provide the shortest route and instead take the long way).

Next up

I need to start work on the AI. I don't think this will take too long as the monks really don't seem to be doing anything intelligent. That said, I'll take as long as it takes to get it to feel like the original.