Tech Stuff #3: Pathfinding

Pathfinding seems simple. Find the shortest, or a least a good path from point A to point B. As humans we do this all the time. We do it unthinking while driving in the car, walking through a city, or looking at a map of roads. Making it work in a game is not so easy.

Pathfinding is the one system in the game that I am constantly fixing and making better. I’ll think I’ve gotten it right, and two months later the game grinds to single digit frame rates because the pathfinder is working overtime, or an AI will stand dumbly in the forest and freeze to death.

The core of the pathfinding system is A*. It’s fairly easy to implement and works well. When a path exists from point A to point B, A* finds it fast. When the path doesn’t exist A* searches a huge section of the map, only to fail. Because my maps are large, even an optimized implementation can’t run fast enough to handle the failing case, especially when hundreds of AI’s need to move from place to place.

Let take an example scene. This area has a bunch of buildings, roads, trees, bridges, and water. The AI’s need to navigate the area to get from their home to the market and to their jobs.

Pathing Scene

Besides finding a valid path around buildings, A* allows you assign weights to movement in different areas. This makes some areas easier to pass than others. When searching for a path, it makes the people prefer roads, but if cutting across a large farm is faster than following a road around it, the people will do it. It also makes people avoid tight clusters of trees or rocks, but if that’s the only way to go, they’ll go through them.

I can dynamically set these weights in game. For wild animals like deer, the weights are very high for roads and buildings, so they’ll generally stick to the wilderness, avoid settlements, and have no problem crossing a river.

The path weights look like this.
Pathing Weights

In this image, the roads have the lowest weight (orange), open areas are next (green), then farming/stockpile areas (yellow), then trees, rocks, and other obstacles (grey). Water (blue) and buildings (black) are not passable.

I worked hard to optimize this whole system. From my initial implementation to what I have now was probably a 20x speedup. A* needs a whole lot of record keeping. It needs to keep a bunch of sets and priority queues of information. Since the map is constant size, much of this data can be preallocated. However there is a dynamic priority queue that uses a custom AVLTree with a constant time memory allocator for high performance. After all the optimization it’s still too slow to handle the failure case quickly.

After researching a bunch of other pathfinding optimizations, I came to the realization that I was trying to optimize the wrong thing. Most of the time the game engine wants to know if an AI can get from point A to point B. I was using A* to make this determination, and throwing the path information away. The only time A* is important is when an AI actually starts walking, otherwise I just need to know that a path does or doesn’t exist.

I went with the simplest thing possible: a large table that can be used to lookup the A to B accessibility. For this I turned back to my software graphics rendering roots, and implemented a fast flood fill. The code flood fills all regions that are connected with an identifier. When the fill is complete, any unvisited areas are then flood filled with a different identifier. This continues until the entire map is filled.
Pathing Accessibility

The colors in the image above represent the different identifiers. Before pathing from point A to point B, the game simply looks in the accessibility map at points A and B. If they have the same identifier an AI can make the trip. If not, they’ll move onto doing something else. This is very fast and takes so much less time than running A*.

When a building, bridge, or something else is placed that could change the accessibility information, the flood fill is simply performed again. This is fast and doesn’t show up on any profiling I’ve done.

There are other things to consider while pathfinding. For example, an AI could already be walking from A to B when the route is cut off, so AI’s constantly have to check the accessibility map, and either re-path or cancel the current task.

All that pathing and flood fill code I just described is only about 350 lines of C++. Strange that a small amount of code has caused me so many performance issues and headaches….

32 Comments

    Alluvian Est-Endrati
    April 29, 2013 10:20 am

    Interesting. The pathing was looking very good in the recent videos, thanks for giving us a behind the scenes look at how this process has been coming along.

    Sheldon
    April 29, 2013 10:23 am

    Awesome! Looks like things are coming along. Keep it up!

    Mathew
    April 29, 2013 10:32 am

    Wow, great work.
    You’re definitely very multi-talented

    Alex
    April 29, 2013 10:34 am

    Hi! I would consider make the AI not constantly check anything. If the AI wants to go from A and B, run A* to find a path and start going, if while the AI is going to B the path is blocked or has changed, the AI should not be omnipresent and know it all, so let it reach the blockade and find another path! That’s more realistic, at least would be nice if you tried that out and let us know how it went. Does it feel more natural?

    Jerry
    April 29, 2013 10:46 am

    Always enjoy seeing another update and looking forward to buying this when it’s ready.

    Tjeerd
    April 29, 2013 10:46 am

    Very interesting and thanks for the update!

    Håvard
    April 29, 2013 10:54 am

    I can’t wait to play this game, but please, take all the time that you need.

    Beuner
    April 29, 2013 11:14 am

    Ah it was great to read this. Brings back memories from when I was messing with C++ myself. Keep it going, I’m looking forward for more tech stuff!

    Dan
    April 29, 2013 11:31 am

    You have a great gift for taking complex ideas and explaining them in a very clear, straightforward manner.

    If you had any interest in such a thing after you finish this project, I suspect a book or series of articles detailing how you made the game would be hugely well received.

    I’ve been toying with the idea of trying to make a game for years, but my field isn’t game design, and I’m constantly put off by the ominous mountain of complexities that I have no way to anticipate given my lack of experience.
    I’ve poked around with pathfinding before now, but this is a classic example of something I would never have thought of, and such an elegant solution, clearly explained!

    I would love a game design resource written as well as your blog posts.

    Burning_trees
    April 29, 2013 11:34 am

    Very cool. Just wondering though, can AI swim through rivers or streams to get to where they are going? Or do they need a bridge? Swimming could be a last resort eh?

    Kat
    April 29, 2013 11:41 am

    IIIII am looking forward to hear more!

    BILL
    April 29, 2013 11:52 am

    yeah looking forward to hear more and may be you will have a change of mind to make this game online playable.

    David
    April 29, 2013 2:11 pm

    I’m excited to play this with my wife. I think she’ll like this kind of game. It’d be fun to make a town together.

    pkrcel
    April 29, 2013 4:05 pm

    Great, simply great post dude.

    As many have said you’re very talented and on multiple assets as well.

    Also, I second the idea of writing down your experiences and maybe then open parts of the code (pseudo-one) in the articles/book/whatever….you’re very clear in getting the point in a few well formed sentences.

    Wouter Lievens
    April 29, 2013 5:39 pm

    Do you use a classic flood fill algorithm? In most applications, Connected-Component Labeling (CCL) can be equivalent and more efficient, so you could check it out.

    http://en.wikipedia.org/wiki/Connected-component_labeling

    Efe M
    April 29, 2013 6:54 pm

    I love reading your blogs. Keep’em coming please.

    Dan
    April 29, 2013 7:44 pm

    @Burning_trees – hehe, I thought that, might be interesting to give water a super-high path cost, but have it as an option. If you spot villagers swimming to cut trees, you know something’s up with your supply lines :-)

    Ricky H
    April 30, 2013 4:31 am

    Love it, clever solution.

    Maklak
    April 30, 2013 5:29 am

    I’ve seen a comparison somewhere and AVL trees are much slower than Red-Black trees or skip lists, so you might consider those instead. Or just use a heap – those are great for priority queues.

    Overall what you did (A* + connectivity map) is a pretty standard solution for pathfinding on a grid.

    You also might want to look up some bay12 threads on pathfinding. Mostly there’s just chatter, but there are links to some code and articles on things like path caching, hierarchical pathfinding, multithreading and other improvements to A*.
    http://www.bay12forums.com/smf/index.php?topic=76278.msg1932980#msg1932980
    http://www.bay12forums.com/smf/index.php?topic=118276.msg3733415#msg3733415
    http://www.bay12forums.com/smf/index.php?topic=112209.msg3404213#msg3404213
    http://www.bay12forums.com/smf/index.php?topic=29515.msg386613#msg386613
    http://www.bay12forums.com/smf/index.php?topic=43265.0

    Erlo
    April 30, 2013 2:56 pm

    Neato … I love seeing the mind at work!

    Joseph
    April 30, 2013 4:24 pm

    Well, this just proves the old adage: The best solution is the simplest solution.

    Hayden
    April 30, 2013 8:17 pm

    I like how you solved this problem, though I don’t see how to do the flood fill but I have only started Computer Graphics this semester.

    Looking at the connected component labeling could be helpful as you could use it to create realism. As in when A joins B you could make the joining (change from B -> A) propagate slowly over the region to suggest that people learn about it over time. Thus the further away it is from the settlement the longer it will take for them to know about it.

    Just an idea.

    craftworkgames
    April 30, 2013 10:05 pm

    Very clever! I’ll have to remember this if I ever run into the same problem.

    Christen
    May 1, 2013 1:54 pm

    Nice work! Thanks for sharing this info. I am really excited about playing your creation.

    General Funky Feel
    May 1, 2013 6:50 pm

    Very clever. I know very little about coding, but your description of the problem and it’s solution sounds smart.

    It’s also nice that efficient and optimized performance seems like a high priority for you.

    Can’t wait to hear more.

    Indie Game Blogs
    May 2, 2013 5:51 am

    Hi there, just dropping in to let you know that you have been featured on Indie Game Blogs: http://indiegameblogs.com/shining-rock-software/

    Amit Patel
    May 2, 2013 2:17 pm

    Great! Always go back to the problem you actually want to solve :-)

    In maps where not everything is connected, Connected Components are usually calculated before A* so that you can decide whether A* should run at all. You’d only want to run A* if the start and goal are in the same region.

    MrE
    May 3, 2013 2:54 pm

    I really like the technical posts!

    How will transport times impact your village?

    I.e. what could the difference be between clever road and bridge placement and not so clever placement?

    Geandily
    May 4, 2013 2:14 pm

    I’d like to hear MrE’s question answered too :)

    Preston
    May 4, 2013 8:25 pm

    If there is ever a beta, will you let me have a beta code, or perhaps a trial game?

    Nesetalis
    May 5, 2013 6:38 am

    ohhh I love this stuff!
    I recall a month or so ago, shortly after that abomination of Sim City was released… I was discussing pathfinding with a friend, and we were looking at your game. And I was pointing out how yours seemed to be quite a bit more competent. He seemed skeptical from the video we were watching, so I’ll have to link this to him. 😀

    dvb-t
    May 6, 2013 4:13 pm

    Hey there, You’ve done an incredible job. I’ll definitely digg it and personally recommend to my friends. I’m sure they’ll be benefited from this web site.