Pathfinding is and has always been incredibly interesting to me. From the first time I saw a unit move around an obstacle back in the late ’90s playing Starcraft, I have been awed by the ability of a computer to something more than walk a straight line to its target. Many times before had I exploited that weakness of computer-controlled enemies to my advantage, hiding from enemies behind a short wall to take a rest or lob ranged attacks while they sat there running into the wall in a hopeless attempt to get me. At the time I was amazed, I was just getting started with programming, and while I could grasp at least at the conceptual level how most of the game worked, I was positively mystified by this feat.
Obviously I have come a long way since those days, and while I wouldn’t have considered myself an expert, I felt like I could hash out at least a workable version of this concept when the need arose for a prototype I worked on recently. This was actually somewhat true in that I was able to write out some code that produced a workable path, but oh man was it slow. Not like, sit there and wait for it to finish slow, I was still measuring times in milliseconds, but running in real time was not an option. Thankfully, this wonderful internet age we live in meant that the answer of how to speed this up was out there just waiting for me to find it.
Initial searches led to the obvious choices. A* on a grid was the first algorithm I found, and while not an eye-opening revelation, they were certainly doing things in a smarter way than I was. I took to task and quickly implemented the algorithm on my little world, and while this was decidedly faster, the paths it came up with were less than desirable. Choppy, robotic movement was something I had encountered in other games, and now I fully understood why.
Source: http://commons.wikimedia.org/wiki/A*_Algorithm
This worked, and honestly for as unimportant as the paths were to the project I should have just stopped here and moved on, but that’s not how I roll. I wanted something that seemed a bit more natural, a path that I would actually walk in that situation. I wanted something more like this.
A more natural path
I did a bit of research on various methods of smoothing A* paths, and found a great article about optimizing the heuristic used to generate better paths. (http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html)
This helped, and the paths looked better, but I had two real issues with this. The first was that some of the paths still looked wrong; my entities were not tied to the grid, so it made no sense for them to walk along it’s lines. The second was that while my terrain was tied to a grid, I wasn’t exactly happy with that either, I wanted to be able to drop obstructions of arbitrary shapes and sizes at arbitrary locations. In search of a better algorithm, I came upon a nice little gem of an algorithm called Theta*.
The gist of this algorithm is that it keeps track of significant turns and casts lines between turning point nodes and the new nodes it searches. It basically then comes up with a straight of lines as possible by keeping only the nodes at the turn points. This was a bit more of an eye-opening moment to me. The answer seemed so simple and obvious I was almost annoyed with myself for not coming up with it on my own. With pride sufficiently swallowed, I set out to put it into practice.
Real people tend to walk straight to the nearest opening.
This was almost exactly what I was looking for. No more movement awkwardly restricted to only 90 or 45 degrees. This looked like what a real person might have done, given the circumstances. Theta* was a great success, but there was still a little bit of work to be done. By toying with how the entities moved, giving them a sort of inertia and not letting them snap on turns, I managed to get exactly what I was looking for.
Real people tend to round corners.
The last real issue here was that I was still tied to a grid. I will spare you the gritty details for maybe another time, but in the theta* implementation they mentioned using visibility graphs. After a bit of research on building one, I wrote up a quick algorithm to generate the graph allowing me to place my existing tiles anywhere on the map, which led to this.
Because sometimes curves just look better.
I still can’t get over how nice that all looks. I’ve seen some impressive pathfinding in 3D games, but not usually in the realm of 2D gaming. I’m excited for the natural look this will give movement in my projects, and while I realize this will likely be a feature nobody really cares all that much about, I just really couldn’t help myself.
