OK, I’m being overly dramatic. But things where looking a little tight for a while.

 

World Map

This all started with a somewhat dramatic change to the game’s map structure. You see, the world in Slave Craft’s is made up of Locations. Each location has properties, and can contain contents. For instance, one location might be a bedroom, and contain a bed and a character. Characters can travel from one location to another using a travel action, or change the contents of a location using other kinds of actions.

Locations also have connections to other locations. These connections determine if or how a character can travel from one to another. The structural change I made to the map has to do with these connections.

The old map structure was arranged like a tree:

With this structure, traveling involves going either up or down to a higher or lower level location. This means that finding a path from two, not directly connected, locations is simple. All a character needs to do, to reach a destination, is travel upwards until they reach a common parent, then travel downwards until they reach their destination. The computation time for this is trivial.

Now that tree structure sucks. For a lot of reasons. And I’m not going to justify how or why I thought it was a good idea. But at some point, I decided that it needed to change.

So I changed it into a graph:

This structure looks more natural, and functions much better. It works similar to to the old system; traveling moves a character from one location to another through a connection.

 

The Problem

Artificial Intelligence. Slave Craft controls slaves using a fairly basic AI system. It simply evaluates all the actions that a character can perform, and picks one with a high rating (with some variation). So, what’s the problem? Well, often actions involve a target. For instance, a ‘sleep’ action might require a target to sleep on, like a bed. For the AI to consider the ‘sleep’ action, it needs to know about all the beds in the game. It needs to evaluate each bed to determine which one would be the best to sleep on. This evaluation involves several factors, like whether the bed is owned by someone else, as well as the distance to the bed. Is it better to travel for 8 hours just to reach your bed, or is it better to just find somewhere nearby? This evaluation involves something called pathfinding, which is usually computationally expensive. With the old map, finding a path from one location to another is fairly quick. With the layout t is not. Even worse, it involves pathfinding hundreds, or even thousands of times whenever the AI does it’s thing. So to support the new map structure, I had to solve this serious performance issue.

 

Pathfinding

This is where things start to get a little technical. Does anyone know what the “A* Search Algorithm” is? Anyone?
* crickets *

It’s basically the standard way of pathfinding in computer science, and an extension of Dijkstra’s algorithm. Most systems that have pathfinding use some variation of Dijkstra’s / A* to compute a path, so It was likely that I would need a custom variation of this algorithm for Slave Craft.

In order to develop a pathfinding system, I had to create a test. Not sure of how big the game’s map was going to be, I had to make sure that my test represented a reasonable “worst case scenario”. I settled on the following two basic properties:

1. The map will have at most 2,500 locations (but probably less than 500).
2. The map would be sparse (a technical distinction).
3. The pathfinder may need to find up to 10,000 distances each run.

My test was simple:

1. Create a randomly generated map, with anywhere from 500 to 2,500 locations with random connections.
2. Calculate around 10,000 distances using whatever algorithm I came up with, and time it.

 

Solution 1

The first solution I tried was to simply implement the shortest path algorithm, and see if it would work. Why fix a problem you don’t have? So I did. And it didn’t.

Technically it did work because it computed the correct paths. However, one run of the test took around 250 seconds. That’s over 4 minutes for one run of the AI!

Unacceptable. If the new map was going to be this slow, then it was never going to happen.

 

Solution 2

I realized that a lot of the time, the algorithm was re-calculating paths it had already tried. I mean think about it: 10,000 shortest paths, when there are only 2,500 possible destinations. So I looked at doing what any reasonable programmer might do; cache the results.

I developed a system for storing “signposts” at each location. These signposts would work much like signposts do in reality. For any destination, it would store both the direction to travel, and the total distance. When computing a path, I would store signposts at each location along the path. If a location already had a signpost for a given destination, I would simply use the signpost value instead of running any pathfinding.

This sped my test up. It was now taking 2.5 second. Better, but still very problematic. I couldn’t have the game freezing for several seconds every time a slave’s AI needed to run.

 

Solution 3

I realized the fundamental flaw my approach. What I was doing, was computing shortest paths one at a time. What I should have been doing was computing all paths at the same time. The reasoning behind this is simple. Consider the image of the graph map example I posted above. If a character is currently at location 10 (bottom right corner), then any path they take, to any other part of the map will involve traveling through Location 6 and Location 3. This needs to be computed every time the pathfinder runs.

But what if I do something a little different. What if I run the algorithm once, with no destination as the target? The algorithm then visits every single location, and finds the shortest path to all locations on the map. Then, I just need to store all those signposts. That way, only the first run needs to use pathfinding. Every run after is a lookup.

Making this change brought the test time down to 250 milliseconds. Much better. But it also introduced a problem. As I kept running tests, the game would generate more and more signposts. Eventually, every location would have a signpost to every other location. This started to consume a lot of memory, and slow down the system. Think about it; each location would need a signpost for every other location. This means the map would need to store a total of [2,500 x 2,500] = [6,250,000] over six million signposts! Not only that, but if the map changed at any point, every signpost would need to be re-calculated.

 

Current Solution

Because of the memory issues, and the fact that the map can change, I realized that the problem was with caching the results. My brilliant plan of using signposts was problematic, and I decided to get rid of them. I thought about how each time the AI ran, it would do so from the same starting point; from whatever location the character was in at the moment. The only information I needed was the distance to all other destinations on the map. I didn’t even need the paths! That would only be needed once the AI had actually chosen an action, and started traveling. Thinking about this, I realized how foolish I was; the pathfinding algorithm already computes and stores all the distances! There was no need to convert or cache the data. It was already sitting right there in the algorithm. All I needed to do was export it. What I had basically discovered (apparently in my infinite wisdom) was a commonly used variation of Dijkstra’s algorithm. So, the current solution is to do this:

1. Run pathfinding with no destination.
2. Steal the contents of the algorithm (specifically the ‘total cost’, and ‘came from’ structures) and put those in a sort of “Path Map” structure.
3. Store the “Path Map” for use while the AI computes its options. Distance lookups check the ‘total cost’ structure.
4. When the AI is done, throw away the “Path Map”.

Doing things this way, and with a few other optimizations, I’ve managed to drop the testing time to 5 milliseconds, with insignificant memory overhead. This was finally an acceptable result. Even if 20 slaves all need to process their AI at the same time, the pathfinding cost would only cause a delay of 100 milliseconds. Even better, at 500 locations, the test finishes in about 1 millisecond.

 

Conclusion

This got me thinking; what can I use all this extra processing time for? Now I’m not confirming anything here, but I’ve started looking into having all NPCs controlled by the AI system. This could produce a very dynamic and interesting game. I haven’t worked out all the details, but I’m definitely moving in that direction.