Dungeon Dregs

Prisoner AI

One thing was clear: no traditional simple rules for walking and turning would make the prisoners head for the exit in any realistic manner. They would need help somehow. I got the idea from a Digital Image Processing course I took a few years ago.

Take a digital, binary image of a simple object. An elementary operation in Image Processing is determining the generalized radius. To begin with, all boundary points are located and marked with a value corresponding to a distance of 1 pixel from the edge. Next, all pixels neighboring those marked ones are marked too, with a value one step higher, and so on. Eventually each pixel has a value corresponding to its distance from the edge. The maximum value inside the object is its radius.

An interesting side effect is that, given these values, there is now an incredibly simple strategy for finding the shortest route from any pixel to the edge. Just look at the surrounding pixels up, down, left and right and go to the one that has a value one step lower than the current pixel. Repeat until you have reached your destination.

I knew I could easily convert this to the game dungeon by counting the rooms and passages as the "object" and starting the count at the exit point. A few tricks would ensure the implementation became simple. Thus, I auto-generated an array identical in size to the dungeon map and filled it with two values: -1 for walls or solid objects and 500 everywhere else. Then I located the exit/exits and gave it/them the value 0. Finally, I set the distance-finding algorithm in motion, starting from the 0. Negative values (i.e. -1) would count as being outside the free path.

The first room and its initial "distance map" are shown below.

 -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1 
 -1 500 500  -1 500 500 500 500  -1  10   9   8   9  -1 
 -1 500 500  -1 500 500 500 500  -1   9   8   7  -1  -1 
 -1 500 500  -1  -1  -1  -1  -1  -1  10  -1   6   5  -1 
 -1  -1  -1  -1  14  13  14  13  12  11  -1   5   4  -1 
 -1  16  15  14  13  12  -1  -1  -1  -1  -1   4   3  -1 
 -1  -1  -1  -1  -1  11  -1 500 500  -1  -1  -1   2  -1 
 -1 500 500 500  -1  10  -1  -1  -1  -1   3   2   1   0 
 -1 500 500 500  -1   9   8   7   6   5   4  -1   2  -1 
 -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1

Apparently, the closed prison cells have not been touched by the algorithm at all. They still contain 500. But this is perfectly OK.

Whenever the player smashes something -- a door or another breakable object -- I set the corresponding distance map value to its lowest positive neighboring value plus one, and start the distance-finding algorithm anew from there. All positive distance values that are higher than that of the current square, plus one, are replaced and in turn put in a queue for later examination. An added quality of the algorithm is that whenever it finds a block that has an unchained prisoner standing on it, it replaces that part of the map with an ordinary piece of ground and activates a prisoner, as a mobile character, on the same spot.

In order to ensure that the game runs smoothly, I only let the applet compute one distance level per animation frame, but it will still only take a couple of seconds until the entire room (where necessary) is affected. The changes spread very much like rings on water. Sometimes it's possible to notice a split-second delay between the moments prisoners at different distances from the door start cheering.

Below is a scene from later in the game with its corresponding distance map.

 -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1 
 -1 500 500  -1  15  14  13  12  11  10   9   8   9  -1 
 -1 500 500  -1  16  15  14  13  -1   9   8   7  -1  -1 
 -1 500 500  -1  -1  -1  -1  -1  -1  10  -1   6   5  -1 
 -1  -1  -1  -1  14  13  14  13  12  11  -1   5   4  -1 
 -1  16  15  14  13  12  -1  -1  -1  -1  -1   4   3  -1 
 -1  -1  -1  -1  -1  11  -1 500 500  -1  -1  -1   2  -1 
 -1  14  13  12  -1  10  -1  -1  -1  -1   3   2   1   0 
 -1  13  12  11  10   9   8   7   6   5   4  -1   2  -1 
 -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1

For practical purposes, I treat each room separately. It would take too much unnecessary work to update the entire dungeon whenever the player breaks a crate or something else. The "AI" still works perfectly within each room, though. Whenever a prisoner reaches the value 0, I just let it keep going. That will send it into the next room, where it can continue its path with the same exit-finding strategy as before. (This may in fact be more realistic than if the prisoners immediately knew the shortest path through the entire dungeon.)