Walking around realistically feature - Software Inc.

In this article, I will go through some improvements and optimizations I made for the pathfinding algorithm I use in Software Inc. You should note that most of these things has obvious superior solutions, so this article should not serve as a “how to”, but more as inspiration. I don’t know exactly who this article is aimed at, maybe aspiring programmers, maybe newbies looking for some tips, maybe just
someone with an interest in what kind of problems you deal with when you make games.

Last night I spontaneously decided to improve my pathfinding algorithm, even though I have way more important things on my todo list for Software Inc. In any case, it won’t hurt to fix up some periphery stuff.

I’ll begin with how the previous algorithm works. I don’t know how the previous algorithm works, because I downloaded off the internet… It’s a grid based jump-point search algorithm, which is an improvement to the A* algorithm. If I remember my terminology correct, it is a greedy algorithm, which means it makes a greedy/naïve choice, to avoid considering all possible solutions to a problem. It does this by going directly for the goal when trying to find a path, where A* would consider all possibilities, and then pick the seemingly best one.

I replaced it with the un-optimized A* algorithm, which means it’s slower, but I understand it better and I will have a better chance to optimize it later. This sounds stupid, and it is, but the reason was that the algorithm had a problem, and for the life of me, I didn’t know how to get the algorithm to do the
correct thing. The problem is illustrated below. The ability to move diagonally.

I want people to move diagonally, but I don’t want them to move inside walls or slither in between small cracks. For some reason I couldn’t get it to work the way I wanted with the fast algorithm I had downloaded. My solution was to rewrite the algorithm using the standard A* template.

For every point in the grid, to determine where we can move from that point, I choose every point above, below, and to the right and left, where nothing is blocking, and also diagonally, but only if there is nothing next to or above/below the diagonal point with respect to the current point. So, if we wanted to move to the north east, both the north and east point should be free. The result is illustrated below.

Okay, so far so good. Now the problem is how jagged the route is; only robots move like that. To solve this I use spline interpolation, I think it’s called. I participated in a course once, in which we were taught how to implement Bezier curves, which is what you’d get if you draw a line over four points, and then draw a curve that fits inside that line “cage”. I did what you should do when you’re not immediately sure how to do something and you don’t want to spend your day researching it, pick from the freely available solutions. Don’t reinvent the wheel, if not for educational purposes. I ended up going with something called cardinal splines, which uses a “tension” variable to decide how curvy a path should be. It basically split the path up in to more points, by placing new points in between the current points in such a way, that it looks smooth. It was still not good though, as illustrated below. It looks worse than before.

The solution here was simple enough. Every time I make a turn, I take the points at either side of the corner, find a point right between them, and move the corner point closer to that point. This makes all turns a little rounder and tighter, the spline interpolation now works much better.

And I’m done! Was what I thought, but my game now took on average 3 seconds to find a path and that is, of course, completely unacceptable. Now, it is very important to note, for the aspiring programmer, the best optimizations I could’ve done here would have been high level, like using jump point search or something similar. But, I actually got the average time down to about 3 milliseconds by using sub-par low level solutions, like switching out data structures and making some assumptions about the system I am looking for a path in, e.g. it’s a grid…

I started out putting in small performance probes, to find out where the code was slow. I note the time, do something, and output the how much time has passed.

The A* algorithm finds the best candidate point when looking for a path, by choosing the point which has the lowest guesstimate of how far it is from the goal. The guesstimate is based on how far we have traveled so far and approximately, how far away the goal is… Far. Finding the best candidate, i.e. the point with the lowest distance, took more than half of the 3 seconds. I was basically going through ALL points previously visited, looking up their individual distance, and taking the smallest one. To solve this problem you can create a data structure, which sorts values as you put them in. So now, when I put a point in my “To Visit” list, I note their distance and put them in the correct order right away, so when I have to find the best candidate, it will be on top of the pile. Think of taking random cards from a deck and putting them in an ordered deck by placing them between cards that are higher and cards that are lower, instead of looking through all of them each time.

The best way to do this is probably a balanced binary tree, which is out of scope of this article. I chose the not-so-best way to do it, for reasons of laziness (this is where you should find a free solution online). My solution was a linked list; you hold on to one point, and that point holds on to the next. When I add a new point, I go through each point and when I find a point that has a higher distance, i.e. is a worse candidate point, I place my point in that position. So in the worst case scenario, I will have to go through the entire list when I add a point, and when I want to find the best candidate, I just take the first point, since it is guaranteed to have the lowest score.

That got me halfway to a good solution, the rest of it was just doing what should you never do. I repeat myself, write code that is hard to manage and doesn’t work in the general case, e.g. “What if the system is not a grid, but a bunch of points in 3D space?” I just throw that notion out the window and think, “What works best for me in my current situation?” This meant making everything more static, writing out loops, reusing memory with global variables, hardcoding logic, etc. For example, instead of having a separate function, “Which places can I go to from here?” I just go through the points currently around me one by one directly in the algorithm. Instead of saying “Does this point exist somewhere in this list?” I just look for the number 32768*x + y, because I know my data points are 2D points in a grid, and 32768 * x + y is a way of expressing that with one unique number (all coordinates are between 0 and 256).

That is it. The code is extremely ugly, but it got me from 3 seconds to 3 milliseconds, and that is all the player is going to notice.

I will finish off by stressing that, if you put some thought into it, you could make this beautiful and still have it be optimal. There exists way better choices than the ones I have made and rethinking the design of an algorithm can often get you farther than just fixing low-level stuff in your code.