“When game developers look at AI research, they find little work on the problems that interest them, such as nontrivial pathfinding, simple resource management and strategic decision-making, bot control, behavior-scripting languages, and variable levels of skill and personality — all using minimal processing and memory resources. Game developers are looking for example “gems”: AI code that they can use or adapt to their specific problems. Unfortunately, most AI research systems are big hunks of code that require a significant investment of time to understand and use effectively.”
- John Laird, “Bridging the Gap Between Developers & Researchers”
Pathfinding is a least-weighted path graph problem. There, I said it.
My plan for this blog was to keep it at a fairly high level of abstraction and not to use terms that would scare away computer game designers who, for the most part, feel about math the way vampires feel about garlic (or silver or crosses depending on which particular form of vampire fiction you’re reading this week). But, yeah, pathfinding (which is an important part of RPGs, wargames and even sports games) can be reduced to well researched and well understood mathematical problem.
Computer game designers (or programmers) usually work in a grid; that is to say their world (or battlefield, or playing field) can be represented by a two-dimensional matrix. Though we often think of a graph as a tree-like object, a two-dimensional matrix in which every cell is connected to its neighbors (e.g. a battlefield, RPG world, football field, etc.), can also be represented as a graph.
So, as a computer game programmer, why do we care that RPG worlds can be represented as a graph? Well, it turns out that there is an algorithm that can be mathematically proven to return the shortest path between two points in a graph. Now, if you’re not a computer game programmer you’re probably saying, “well, if they’ve got this whole shortest path thing worked out, why is that half the time in a game when I tell my player to go from Point A to Point B it gets stuck behind a wall or a rock or something trapped like a doofus?” And the answer to that is: because the programmer didn’t use a guaranteed least weighted path algorithm.
The reason that we refer to this type of an algorithm as a “least weighted path” algorithm is because we can give a ‘weight’ representing the ‘cost’ of moving from one cell (or square) to the next cell (or square). For example, we might say that moving ‘north’ through ‘clear’ terrain costs 1, and moving northeast through a swamp costs 3 and moving east through a forest costs 2, etc. So we’re not really talking about a ‘fastest’ path or a ‘shortest’ path, but, technically, the path with the lowest ‘movement costs’ or weight. Does that make sense? If it doesn’t, drop me an email and I’ll explain it, hopefully more clearly, in another post.
And now let’s look at the reasons why the programmer didn’t use a guaranteed least weighted path algorithm:
- Speed. The oldest guaranteed least weighted path algorithm is commonly known as Dijkstra’s algorithm. It was first discovered by Edsger Dijkstra in 1959 and there is a very good explanation of how it works (complete with animation) here. Dijkstra’s algorithm is taught in every undergrad AI class. It’s not very complicated and it’s easy to implement (in fact, it’s usually an assignment by the middle of the semester). So if the “fastest path from Point A to Point B in a computer game” problem has been solved why doesn’t everybody use Dijkstra’s algorithm? Good question. The reason that computer game programmers don’t use Dijkstra’s algorithm is that it is an “exhaustive search” (which means that it has to look at every possible path) and then determines the fastest route. In other words, it’s sloooooow. Really, really slow.
- Time. I’m not talking game development time – though often the problem is simply that the game publisher is forcing the game ‘out the door’ before it’s really completed – I mean ‘clock cycles’ or there isn’t enough time for the computer to both render all these polygons that represent explosions and mountains and whatever and for the computer to do AI calculations. AI is constantly getting short shrift when the CPU budget is being determined.
- Ignorance. There’s another solution to the “least weighted path problem” known as A*; pronounced ‘A star’ (I once had the temerity to ask Nils Nilsson, one of the authors of A* what the ‘A’ stood for and he replied, “algorithm;” and now we all know). Thankfully, Amit Patel has done a great job of explaining A* (with lots of graphics) here, so I don’t have to. Again, I’m not going to get into the math behind A* but I am going to leave you with this mind-blowing statement, “the guaranteed worst-case runtime of A* is the best-case runtime of Dijkstra’s algorithm.” What did he just say? That Dijkstra’s algorithm will never return a least weighted path in less time than A*. So, you should be asking, “well, why doesn’t everybody use A* instead of Dijkstra’s algorithm?” The answer, as crazy as this sounds is, A* is rarely, if ever, taught in academia. What?!?!? Yeah, there is a weird prejudice against it because Dijkstra solved the problem way back in ’59, it is a mathematically proven solution, so why bother with anything else?
You see in Academia, especially in computer science which is usually a department inside the division of mathematical science, RAM and runtime are often thought of as ‘infinite’ commodities. I suspect that this way of thinking about problems stems, in part, from Turing’s theoretical machine which had infinite RAM (an infinite strip of paper) and an infinite amount of time to solve a problem. Unfortunately, those of us that live and work in the ‘Real World’ have neither infinite RAM or time. We need algorithms that return solutions fast.
Lastly I would like to mention Dimdal’s work on optimizing A* in “Real World Terrain” situations. I wrote a paper about it which is available here. I use a modified version of Dimdal’s modification of Nilsson’s A* for my own pathfinding routines in TIGER. The result is an extremely fast least weighted path algorithm that takes a fraction of the time to calculate as Dijkstra’s algorithm or A*.
And now you know the difference between academia and the real world and why your character in an RPG gets stuck behind a bunch of rocks acting like a doofus.
