Gamasutra: Ashley Kreuer’s Blog – Implementing SEO in Video Games

So we all know Google and other search engines use a variety of optimization techniques. How does that apply to video games? Well the classic example is the shortest path problem. You want your AI whether it be enemies or NPC’s to take the shortest path to the player or some other goal. The way to accomplish that dynamically is to use a search algorithm.

The first thing you need to know when implementing this sort of algorithm is how to set up the problem. There are essentially 3 variations you need to worry about single-source shortest path problem, single-destination shortest path problem, and all-pairs shortest path problem. The first one is essentially you have a starting location and you are trying to find a route to every other place on the map. The second is basically the opposite of the first. You are trying to find the shortest path from all possible starting locations to a single end point. The last one is both combined. You are trying to find the shortest rout between all possible starting and ending locations.

Now you have a variety of options for algorithms Dijkstra’s, Bellman-Ford, A*, as well as a few others that I’m not going to get into. The first two are excellent algorithms but the benefit of using the A* Search Algorithm in video games is that it adjusts for a heuristic(basically a rule or sort of hunch of which direction to go). Now this is where you can really let your creativity shine when it comes to AI characters. You can make some of them move more optimally. You can make them become stunned or disoriented and move less optimally. You can even add in another goal or end condition. Now traditionally the heuristics are used to speed up the algorithm. You can use it for that perhaps routing over terrain that lets the AI move faster and is more likely to connect two points for example roads. The thing to remember though when you are implementing them is that it is up to you how you want use and/or modify the search algorithms. This can be a bit of a scary thing if it isn’t something you’ve done before. Personally it is something I love. I really enjoy writing custom algorithms for problems. I once got very frustrated at a hashing library in the middle of the night and wrote my own single direction hashing algorithm but that is a story for another time.

Suppose you are wanting to use A* and you want to use the heuristic to actually optimize it. There are so many different heuristics you could use customized to your unique implementation. For example maybe because of the way your maps are designed there is a set max minimum distance between every two points say 9 squares, everything is normally within 9 squares of everything else. Well now you can use the heuristic to favor that search range. Maybe you know the direction the goal is in so you make your heuristic to favor paths that go in that direction. Now the problem with this is that if there is a problem with your heuristic it can throw off the entire algorithm.

Heuristics are not the only way to optimize search algorithms. You can also use a technique called pruning. Which like pruning a plant or tree refers to cutting away branches or options that you already know won’t lead to your desired outcome. One example of it is Alpha-beta pruning which is an algorithm that seeks to limit the number of nodes searched by the Mini-Maxi algorithm. It is used for games against an opponent.

Just because an algorithm was designed for a specific purpose doesn’t mean you can’t modify it to suit your specific needs. No one is judging you on how correct your implementation of a specific algorithm is. When considering how you can optimize your search algorithms you have a lot of options from setting up the problem in different formats, using different algorithms, heuristics, and pruning. Search Engines don’t release their algorithms but that doesn’t mean you can’t use some of the same techniques they do to improve your game.