A* tricks for videogame path finding
timmastny.com
timmastny.com
1. Hierarchical graphs: city-level, inter-room in building, intra-room. Allows for navigation from any point in any room in any building in any city to any other point in a fraction of a millisecond.
2. Store metadata about the current a* search in the graph nodes themselves so you don't have to maintain in a separate associative array.
3. Don't follow the resulting paths directly, use them as input to a steering behavior that tries to cut corners to the next path node when possible. Also, if you are pathing to go to another character, make the target character drop "breadcrumbs" that get added to the path when their new position would not be straight-line navigable from the last node of the path .
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 a hard thing... and then I watched a video or read something that pointed out that if you don't want units walking through each other then every single moving thing is constantly re-pathing around every other unit. New respect for command and conquer.
I initially used hand placed objects for the path nodes but I was experimenting with having the game rain down falling objects and keeping track of where they hit the ground to create a set of path nodes automatically. At first I was just going to look for negative space with a cog verb and set the nodes just above, but this doesn't catch walkable surfaces that are 3D objects instead of level surfaces. I then had to rain a node down from the stop point to get walkable areas beneath them.
There were still entity specific concerns that were not fully worked out. Entities had different sizes so could fit in different spaces. I had accounted for crouching and set the nodes to be more expensive when that was required as the entity moved slower. I had max jump distance somehow factored in and just had enemies detect a pit dynamically and jump when needed, although this made it easy for me as a player to block their landing site and force them into a pit.
Doors were interesting too, I never really solved that. My idea was to have a second metadata factor beyond node distance that would make paths through doors very expensive when they were closed so the entities would find away around if possible but hang out at the door if they weren't. You'd still need the door to manually communicate with the nodes since some doors are lockable but many just open automatically so are not an obstacle. That required a bunch of manual work for the level designer which I didn't like.
It was a very fun set of problems to work through since the base problem is simple (in that it is solved) but there were lots of interesting edge cases that weren't. And trying to make it work in a dynamic changing environment really changes the whole problem.
When you start getting into 10,000 unit formations that need to pivot or strafe, while moving around or through other unit groups and obstacles, A* starts being rather challenging.
Trying to get 100,000 horses to ford a river reasonably when there's only a relatively small zone of safety can be tough to program.
Also, mipmaps towards the hierarchical comment of aappleby and hwillis.
Short video on a basic sort of crowd simulation would work in Unity: https://learn.unity.com/tutorial/moving-as-one
I imagine this is also very tough in real life
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.
If the pathing of SC had been "great", the game mightn't have taken off the way it did competitively.
There were more important factors, like having the limit to 12 units in a group - any more would make Zerg much more powerful - now Zerglings are easy to use en masse. Terran bio would benefit from it as well.
In the case of SC1, the dragoon in particular was really bad because its speed would change significantly depending on which part of the animation it was in. That’s what made wheeled vehicles and tanks were less wonky. Their speed was constant as they moved.
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.
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 randomly generated level, but not every frame or so.)
https://developers.google.com/optimization has a decent collection of tools.
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!
If you are inside the bubble, you can disable collision with the fixed objects, and only check for the moveables.
In old-school terms that's background vs sprites.
This might be suitable in some circumstances, but it mixes your hot & cold data, prevents concurrent searches from being performed. Personally I'd steer away from this without an extremely good reason.
My personal recommendation is flow field and ROAM. Works excellent for the spring engine
1. The streets have their own graph, as does each individual building. There's an address book; each building stores the driveway tile connecting to the street graph here.
2. Pathing inside homes uses A*. In order to make this extra fast, I bake the 8-directional egress weights for each tile in the building/yard.
2b. This gets condensed down into a 16-bit bitmask (2 bit chunks, 8 directions) and then stored in a hash table
2c. Each bit-chunk has four possible states:
FULL_BLOCK (e.g. a wall)
HARD_BLOCK (e.g. a large object that prevents walking through the tile from any direction)
SOFT_BLOCK (e.g. a smaller object that prevents passage on one edge)
NO_BLOCK (e.g. an unoccupied tile, or a tile with a tiny object)
This way a unit pathing inside a building does not need to check for obstacles on every tile. This also allows units to pass through tiles with objects provided the object is not huge and is rotated in such a way that the exit and entrance edge is not blocked. Lastly, an agent can still walk through a wall if the player e.g. forgot to place a door, to prevent the simulation from breaking down.
3. I use a waypoint system (stored in a queue) for agents so they can traverse through the different graph hierarchies with ease. This is also used to e.g. tell the unit to walk to their car first if they are driving.
4. Pathing on the street uses a different method (though still utilizes a baked graph) that makes it extra zippy.
[0] https://store.steampowered.com/app/2287430/Metropolis_1998/
- MPAA (multipath adaptive A*) is great if you need to re-search the same area multiple times as obstacles are introduced. It allows you to feed in the results of previous searches in order to speed up pathfinding.
- JPS (jump point search) looks very appealing in theory because it allows you to significantly reduce the number of "nodes" considered, but I found that the increased overhead in identifying jump points meant it didn't provide a speedup. There might be a way to marry the ideas of MPAA and JPS, but it is very easy to conceptually shoot yourself in the foot with minor conceptual details when getting creative with the algorithms. (As a contrived example, using a ">" when you needed a ">=" might mean you are no longer guaranteed to output the real shortest path in certain situations)
- Instead of using a proper heap for storing open nodes, consider using a bucketed priority queue if your max priority value is a relatively low integer. This means there's an underlying array indexed by priority, which makes push'ing and pop'ing quite fast.
[0] Quoridor takes place on a 9x9 grid, and repeated pathfinding is essential in order to determine how close a player is to their goal, and more broadly whether the goal is even reachable. (In order to even determine the valid moves from a given position, all moves must be checked to see if they make a goal unreachable). I plan to release this within the next few months, including at least 3 decision making "engines": mtdf (a min-max variant), MCTS (parallel with some tricks), and a hybrid involving catboost.
The nice thing about that is that you can use it as a lookup table for your heuristic function instead of the usual straight line. This table can be initialized at the start of each turn, for example using the Floyd-Warshall algorithm with the already placed walls. I managed to significantly speed up my A* on a similar problem using this technique, plus, it is really simple, it was straight A* though, no MPAA or JPS.
With MPAA you preserve all previous shortest paths that have been found (in the form of an Array where array(nodeIndex) points to the nodeIndex of the next node on the path). When attempting to optimistically follow one of these paths, if the algorithm hits a new wall, it will null out the path it took up until the wall. However a future search (or iteration in the same search) may still reuse the part of the shortest path that still exists after the wall.
That said, you're right that it's a tiny grid, and cache behavior can dominate any abstract theoretical properties in surprising ways.
3240 if you're nasty.
Many years ago I added a visualisation to the JPS implementation of PathFinding.js to visualise this recursive search to find jump nodes - here's an online demo: https://qiao.github.io/PathFinding.js/visual/
Thankfully we’re quite forgiving about this stuff, humans seem to model everything as intelligent, haha.
Basically we would need to have the enemy update their path only after a small delay (instead of every frame), so "momentum" would carry them on their existing path so the player could fake them out.
Of course, it is easy to come up with fun ideas for enemy AI, I think if you went after all of them you’d never have time to write the nice blog post.
It's wasteful to recompute paths every frame, since people don't entirely rethink their gross movements every 16ms. Way back when I coded some monster pathfinding, I also randomized the re-pathing interval to avoid intermittent lag (multithreading wasn't really a thing back then), which also made the monsters behave more realistically.
0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
1 - https://web.archive.org/web/20230804100329/https://alumni.me...
See also (not mine): https://github.com/agoose77/goap-resources
The server was really chugging and so I ran a trace on it. I found the zombies were stuck in a loop trying to find their way into a village that we had completely secured with a large fence. Being a naive implementation (at the time) it meant they never gave up.
I recall there being a bug report with a good amount of detail about how they were going about fixing it.
Beautiful.
(Of course, one could argue that it's incredibly realistic behavior for a cat to very insistently demand to get past a closed door. It would be even more realistic if, once the door is finally opened, the cat would immediately change its mind and lose all interest in getting through!)
I was trying to use a modified Dijkstra / A* algorithm for this year’s Advent of Code Day 17 problem:
https://adventofcode.com/2023/day/17
I never got the right answer though because there was some issue with the way I was tracking visited nodes. I was trying to use north, south, west, east rather than row and column direction values like other solutions I read, but I’m stubborn and it seems to me I should be able to get it work storing cell (as a (row, column) tuple)), direction, and distance travelled (1-3).
If you did this day, how did you do it?
More or less a straight depth first search with a priority queue from there.
Otherwise it was just making sure I got the rules right, like all AoC problems, and testing different cases to make sure my solution did the right thing.
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 apparent.
Oh the fun of cobbling heuristic algorithms to work in the real-world where precise algorithms are big-O too slow.
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...
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 :)
If you take some time to snapshot the map state (ideally a nearly static grid like this) and throw it into another thread, you can free up your core game loop to work on other things. Once the path is done, deliver it to what asked for it asynchronously for use on the next update.
Alternately, limit the number of nodes explored per tick at a time. The path will eventually be found without hurting your frame rate as much.
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.
Are there better ways?
Why, and what do you mean, and what are the alternatives? Pixels are just the search space and may have nothing to do with the sophistication level of the search algorithm, no? In the case of simple 2d games that can run on retro hardware, searching over pixels may be the best thing to do with limited memory and limited cycles, it’s why they often do collision detection on pixels as well.
Tie handling is really important! A* is often described as minimizing f(n), where f(n) = g(n) + h(n), g(n) = path distance so far, h(n) = distance to goal heuristic. But for any valid shortest path the remaining work for the algorithm to do is determined by the size of g(n). So when selecting the next node to explore you must minimize first by f(n), and then maximize g(n) as a tiebreaker. Same is achieved by breaking ties with LIFO.
A random forest is also a universal function approximator so anything a neural net can do, so can a random forest (in theory). In practice, neural nets are easier for modern hardware to optimize while I think trees incur computational overhead due to branchiness.
Or finds a bug in the environment and learns to teleport, those are fun too
* If you assign terrain costs to tiles rather than borders (= paths) between tiles, that creates a user-visible asymmetry! ... unless the cost is always max() of the two tile costs or something.
* The direction in which you run the algorithm matters, especially if you're doing one-to-many or partial paths. That said, it is possible to do any-to-goal directly, by adding an extra field to your datum.
* A* fails pretty badly on C-shaped obstacles
* You need to have an admissible heuristic. This means no negative (usually stricter, in fact: not less than 1) weights (usually reasonable, but can cause complications if you want to funnel traffic onto "highways" even if that's slightly longer), and makes teleporters complicated:
\* if a teleporter connects to all other teleporters, the new heuristic is `min(old heuristic, heuristic to the nearest teleporter, heuristic from the teleporter to the goal)
\* if sets of teleporters are unrelated, you probably want to preprocess paths between every pair of teleporters. Doing this without unnecessary work is left as an exercise for the reader.
* Optimization gets harder if your map has multiple movement types (e.g. walk, swim, fly) and individual entities can exercise more than one of those.
* When pathfinding across multiple maps (hierarchial pathfinding is important), the shortest connectivity is not necessarily the shortest path. Sometimes cutting through a building is faster than going around it. If your transitions are not point-like, even recording shortest paths between all such transitions isn't enough. (imagine citygate| .house. |citygate, where the house transitions are small enough to not be part of the shortest paths from the extremity of one gate to the other, but are optimal if you start at the center of the gate)
\* speaking of non-point-like transitions, *please* preserve relative position at least somewhat. Instead of "entering this transition line teleports you to this point on the other map", use "entering this transition line teleports you to the equivalent (with scaling if needed) position along this other transition line". It's not hard when I say it like that, right? (even if you want one-way transitions, you should model them as a transition that is currently disabled, so your target is homogeneous)
What is the method for doing this?