White Shining Rock Logo
White Shining Rock Logo

Tech Stuff #3: Pathfinding

April 29, 2013 | Dukus | 32 Comments

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....

Leave a Reply

32 comments on “Tech Stuff #3: Pathfinding”

  1. 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.

  2. 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?

  3. 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!

  4. 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.

  5. 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?

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

  7. 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.

  8. 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.

  9. @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 🙂

  10. 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

  11. 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.

  12. 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.

  13. 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.

  14. 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?

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

  16. 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. 😀

  17. 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.

More Posts

UI Redo: Part 3

October 25, 2021

UI Redo: Part 2

October 19, 2021

UI Redo: Part 1.

October 5, 2021
1 2 3 46
Back to devlog
Back to devlog
© Copyright 2021 Shining Rock Software
Website Design & Branding by Carrboro Creative
menu-circlecross-circle linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram