Diving into the world of A* pathfinding reveals some serious game dev wizardry. Think about it: creating complex navigation systems that scale from city streets to cozy rooms, all while cleverly using data to guide characters, not just dictate their every move. And then there's the art of optimizing pathing in buildings, turning it into a fine-tuned dance of bits and bytes. It's amazing how these intricate details weave together to bring virtual worlds to life. Makes you think that sharing these behind-the-scenes insights in video logs could inspire a whole new generation of game creators.
A* tricks for videogame path finding
101–108 of 108 posts
Re: A* tricks for videogame path finding
#102Diving into the world of A* pathfinding reveals some serious game dev wizardry. Think about it: creating complex navigation systems that scale from city streets to cozy rooms, all while cleverly using data to guide characters, not just dictate their every move. And then there's the art of optimizing pathing in buildings, turning it into a fine-tuned dance of bits and bytes. It's amazing how these intricate details we…
[dead]
Re: A* tricks for videogame path finding
#103Earlier quoted context omitted.
> Hierarchical graphs: city-level, inter-room in building, intra-room. Handmade? It's always annoying to me when you have a small NP-hard problem (graph partitioning is definitely a recurring one for me) and you want to just throw some box algorithm at it without having to shop around for a library that you have to learn. I remember there was a while in college where I didn't understand why A* in an RTS would be such…
Small NP-hard problems aren't actually that bad. You can usually formulate them as eg a integer programming problem or a SMT problem, and throw an off-the-shelf solver at them. You only need to learn the solver once, and you can re-use it for all kinds of problems. (Assuming that your instances don't have to be solved with low latency. Eg only as part of your level generation process, or at most when loading a random…
> You only need to learn the solver once, and you can re-use it for all kinds of problems. (Assuming that your instances don't have to be solved with low latency.
Mostly I run into this issue trying to script/hack together something quickly in a language I don't use very often. Ie usually missing a clean environment, working builds, nice package control. Like I want to do something in lua for a plugin, or python for some blender thing, etc etc.
It's just one more hassle that makes the whole thing frustratingly not worth it. That toolbox is a neat link though, thanks!
Re: A* tricks for videogame path finding
#104Can someone share tips for A* pathfinding where NPCs have limited knowledge about the map, where they must got from point A to point B without knowing entirely about what’s in between?
I would simply make the path finder assume all unknown areas are traversable. As the areas are discovered, you re-run the path finder. Eventually it will unveil enough of the map to find the path.
Of course, there's a possibility that the uncovered area of the map has a known possible path, but there's an undiscovered shorter path. You could tweak the cost of traveling through unknown areas to nudge the path finder towards or away from trying to travel through unknown areas of the map in case there's a shorter way.
Re: A* tricks for videogame path finding
#105Any time A* comes up, someone plugs this great resource: https://www.redblobgames.com/pathfinding/a-star/introduction...
The next big advance after A* is something called [contraction hierarchies]( https://en.m.wikipedia.org/wiki/Contraction_hierarchies ) I’d love to see a “part 2” of this resource or similar that explains those in this kind of Laymans terms. There were some white papers but then I suspect the big tech companies started to guard this research a little more closely once its potential to give a commercial edge became app…
There are lots of variants of A* that depend on what you can assume about your graph, whether you can preprocess, how often the graph changes, etc. Contraction hierarchies, subgoals, bidirectional A*, hierarchical search, all-pairs compression, moving obstacles, group movement, coordinated movement, landmarks, labeling algorithms, transit nodes, arc flags, cluster distances, vertex separators, reach, highway hiearchies, etc. Differential heuristics are my favorite for "bang for the buck", as they are fairly low effort (maybe There's lots of research papers out there, especially for road maps.
I tried keeping track of them all and gave up :-( But you might find these two papers useful:
* https://arxiv.org/pdf/1504.05140.pdf
* https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.p...
[1] https://www.redblobgames.com/pathfinding/heuristics/differen...
Re: A* tricks for videogame path finding
#106Earlier quoted context omitted.
I don’t know about C&C but in StarCraft units are constantly walking into each other, getting temporarily hung up and stuck a bit. If they were constantly re-pathing around each other though you would certainly also run into issues too. Why shouldn’t the units use the information they have about the current destination and path of the other allied units instead of just constantly seeing them as moving obstacles.
Funny you bring up CNC - OpenRA immediately came to mind for it's horrid pathfinding code that trips itself up when units start crossing bridges and things like that causing units to immediately reroute around the map instead of realizing that the bridge will clear since those units are in motion - red alert 2 at least dealt with this far better but I'm not where near smart enough to figure out how to write code to f…
If the graph is directly modified by dynamic obstacles, store "time to available" in the busy edges. Then the unit walking in can check if by the time it gets there, the edge is still busy.
If obstacles are handled separately, you do the same thing except it ends up being a line intersection between nearby agents' routes. Find route intersections, estimate arrival times, if they conflict based on both units' movement speed, reroute.
Another approach would be to ignore unit as obstacles and rely on movement timeout: If I'm stuck for longer than X time, reroute.
Re: A* tricks for videogame path finding
#107Earlier quoted context omitted.
The next big advance after A* is something called [contraction hierarchies]( https://en.m.wikipedia.org/wiki/Contraction_hierarchies ) I’d love to see a “part 2” of this resource or similar that explains those in this kind of Laymans terms. There were some white papers but then I suspect the big tech companies started to guard this research a little more closely once its potential to give a commercial edge became app…
There are lots of variants of A* that depend on what you can assume about your graph, whether you can preprocess, how often the graph changes, etc. Contraction hierarchies, subgoals, bidirectional A*, hierarchical search, all-pairs compression, moving obstacles, group movement, coordinated movement, landmarks, labeling algorithms, transit nodes, arc flags, cluster distances, vertex separators, reach, highway hiearchi…
Those seem a little outdated, there has been a ton of work since then :)
A bit more updated reference is https://arxiv.org/pdf/1504.05140.pdf, and http://www.sommer.jp/spq-survey.pdf is great!
There are also Prof. Hannah Bast's lectures (https://ad-wiki.informatik.uni-freiburg.de/teaching/Efficien...) and her talk at ICAPS (https://www.youtube.com/watch?v=B3wKfJAVRkg), both excellent :)
Re: A* tricks for videogame path finding
#108> you could pre-compute the maximum depth A* needs to find a path from any position on the map
What is the method for doing this?