A* tricks for videogame path finding(timmastny.com)
timmastny.com
A* tricks for videogame path finding
https://timmastny.com/blog/a-star-tricks-for-videogame-path-finding/
107 comments
Im working on a city builder[0] where you can see inside homes. Expanding on point 1...
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/
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/
Have you considered making video dev logs? That’s very well thought out, and I love the art style!
Just wanted to say, love the art style and the mechanics. Will be following!
Oh, and compute the distance from each path node to the nearest obstacle and store that in the path node. As long as your character is inside one of these "bubbles", you can skip collision detection against the world entirely.
Oh like in path tracing.
nearest object can be dynamic thing
Yes, though many systems make a distinction between fixed objects (like level geometry) and moveable stuff.
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.
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.
> 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 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.
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.
Handmade, but trivial to build - I made a tool so the guys in the world editor could just click anywhere to drop a path node and the tool would automatically link path nodes and prune redundant edges from the graph. Took a few minutes to do a whole city. Building graphs were mostly autogenerated from the navigation mesh and labeled "door" objects, with optional manually placed nodes when the room geometry was weird.
I once hacked in an A* implementation into Jedi Knight: Dark Force II. The in built AI in the game was very primitive (as most AI was at the time) but cog language provided me a way to work around it.
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.
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.
This is one of the main issues in attempting to build a game like the Total War series.
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.
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.
TBH running a full A* for each soldier is not only waistfull but also not realistic. Most people are just moving with the group and might not even know where the entire formation is going
Isn’t the standard solution there to pick one of the horses to do the full path while telling the others “try to move along this path, if not possible then as close as possible, otherwise in the average direction of this group of horses” or something similar?
Yeah, I'd imagine you'd always split this into two separate problems of pathfinding and crowd simulation. Making thousands of separate calls to a pathfinding algorithm that returns the same path (or very close to it) would be mayhem for a game like Total War. Would be super interesting to read through some of the original source for that from Total War.
Short video on a basic sort of crowd simulation would work in Unity: https://learn.unity.com/tutorial/moving-as-one
Short video on a basic sort of crowd simulation would work in Unity: https://learn.unity.com/tutorial/moving-as-one
> 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.
I imagine this is also very tough in real life
I imagine this is also very tough in real life
[deleted]
Search for "flowfield pathfinding". Individual units don't follow a per-unit line. They follow a high-level flow and use local steering to avoid nearby units.
Also every single thing shouldn't be pathing around everything else, they should use something like a flocking behavior to organize themselves. Pathing is only for long distance navigation in complex environments.
I have seen an article posted here that did A* on a low resolution versions of the game map, and use the output of that as the heuristic for the full res version. In that design, the low res version was auto generated.
That's nifty, because A* itself is already a two-step process that uses a heuristic. You can blow it up to multiple steps fairly easily.
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.
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.
Well pathing in sc2 improved significantly, although some problems remain (ultralisks dieing before reaching their target).
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.
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.
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 fix that type of problem.
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.
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.
Some of the units in Brood War are legendary due to their bad pathfinding like Dragoon.
Which is incidentally what made SC the high skill ceiling it has.
If the pathing of SC had been "great", the game mightn't have taken off the way it did competitively.
If the pathing of SC had been "great", the game mightn't have taken off the way it did competitively.
Eh, there's more to it, the pathing has been one of maybe dozen components that came together like that.
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.
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.
It would be also mercilessly exploited if the patching would reveal defense buildings blocking a way..
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 randomly generated level, but not every frame or so.)
https://developers.google.com/optimization has a decent collection of tools.
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.
> 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!
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!
> 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.
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.
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.
Correct, but it was still way faster that way. Pathfinding was already asynchronous (queries happened on another thread so they didn't block any game update loops) and queries were infrequent enough that doing one at a time was fine.
Oh that would be unpleasant if you wanted deterministic behaviour - for example multiplayer RTS.
You know as someone who deals with path planning in robotics where there's a stack of academic papers on each of these concepts, seeing it labelled "tricks" is really funny.
I would put money on a lot of these tricks first being used in games and then being 'rediscovered' by the robotics field.
Almost on a daily basis I would imagine, yep.
We auto devalue everything a human can do as easy. Navigation is a given soon after walking. It's so easy a animal or child can do it intuitively. Until they can't and there are traffic jams.
My personal recommendation is flow field and ROAM. Works excellent for the spring engine
My personal recommendation is flow field and ROAM. Works excellent for the spring engine
[deleted]
Expanding on the "breadcrumbs": pheromone trails or "trampled grass" are awesome, not only because they are a great data source for steering heuristics, but they also lead to organic-seeming navigation behavior that is pleasant to look at.
Usually if something wants to go where something else is, it either want to go in its footsteps or flank it at a point where it predicted to be when both meet.
3. Also allows for "characters" one driving extremely risqué, or completely over the top, other steering safe and boring. Univwrsal Optimal behavior is boring..
Songs of Syx is a very performant game that uses 1. I believe, not 100% sure though. It's like Dwarf Fortress but with 100 of times more amount of map actors.
takes notes Fascinating. Any other sage advice on navigation and game-ai?
I've spent a lot of time thinking about fast pathfinding in order to speed up my Scala Quoridor AI*[0], and here are some tips/tricks I've learned:
- 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.
- 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.
9x9 is a really small grid. 81 tiles. Storing all the distances from every tile to every other tile would take 6561 bytes. Fits in a typical L1 cache.
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.
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.
Interesting idea, thanks! I will probably try this. I had stopped tweaking things too much after implementing MPAA, because most of the searches end up "short circuit"-ing relatively quickly.
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.
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.
> would take 6561 bytes
3240 if you're nasty.
3240 if you're nasty.
JPS is fun; though I struggled to interpret the suggested performance gains by the authors indeed due to the calculation of the jump nodes.
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/
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/
+1 for the bucket queue. I learned about that trick a few weeks ago and in my use cases it cut the time to run A* by around 60-70%.
When there is more than one enemy, it can become worthwhile to simply use dijkstra from the player’s point of view, and then each monster can look up the optimal route to the player. It makes the computation cost more predictable when the monster count is variable.
The “depth too small” problem shown in the last animation produces an interesting behavior appearance; it looks like the monster is “waiting to see” which way you’ll go. I think you can even “fake it out” by starting to go in one direction, then switching, right?
Thankfully we’re quite forgiving about this stuff, humans seem to model everything as intelligent, haha.
Thankfully we’re quite forgiving about this stuff, humans seem to model everything as intelligent, haha.
Author here: That's a cool idea, I hadn't thought of that! It doesn't quite work in the current implementation, but would with some small tweaks.
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.
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.
It could also be interesting to target a tile some number of nodes in front of the player, so the monster will go to “cut the player off” sometimes. Maybe it could result in some interesting behavior if combined with your momentum idea. The goal of enemy AI is to be trick-able in a fun manner, right?
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.
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.
You have invented the pink ghost from Pac-Man.
The pac-man ghost AIs are definitely worth a search, fun stuff from such a simple program.
> instead of every frame
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.
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.
i did exactly this implemented w a turn delay + "scent trail following" added on too, it works out nicely and at times looks like the ai is pausing to recollect itself before beelining towards the player lol
An interesting application of A* in a game context was a programmer who was faced with making the Computer opponents of a game in the early 2000s and what he came up with was an abstraction of the options the AI had in the game and used A* to find the closest distance in the graph. I thought it was pretty cool because it wasn't using A* in the traditional way of pathfinding the world but instead pathfinding in a representation of choices the computer could make where the shortest path represented a possible best strategy.
One of the more common approaches to AI in games is called GOAP [0][1] (Goal Oriented Action Planning), and it essentially "selects" which action set using the same concept -- graph searching (typically using A*) the available options.
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
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
I think the ability to use similar ‘planning’ algorithms for walking through a room, choosing an option for attack/defend/use item, which enemy to target, may account for some of the attribution of intelligence to game AI. Humans seem to think they and other humans put as much thought and think in similar patterns about wildly dissimilar activities like planning a route or weighting risk/reward or planning an event 6 months out. So the ability to encode a wide variety of ‘search space’ into an appropriate graph for use with a common algorithm lends a perceived verisimilitude to the AI’s thoughtfulness and near-personhood when immersed in play.
This is basically how you win every CodinGame Spring/Fall Challenge, though you check many paths in parallel (beam search) instead of a single at a time (A*).
I remember learning A* at uni while at the same time experiencing it's quirks on our shared minecraft server.
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.
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.
A similar long-time bug in Dwarf Fortress: if you have a door or hatch marked as impassable by animals, but a stray tame critter (usually a cat) wants to get through, it will never give up trying to find a path to the other side. This can have a very noticeable effect on your fps, especially if there are several animals all trying to get past the impassable portal.
(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!)
(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!)
Been looking around for the past 10 minutes trying to find information on the mob-following implementation in Minecraft - can't find a thing. I assume it's just vanilla A* with some parameters?
> Since working the (apparently A) pathfinding algorithm...*
Beautiful.
Beautiful.
Aappleby's deep dive into A* pathfinding is like opening a treasure chest of game dev secrets, from using hierarchical graphs for smooth sailing across different game scales to dropping 'breadcrumbs' for dynamic path adjustments. YesBox builds on that, painting a picture of their city builder's intricate street and building pathing system, showing us how every bit (or 16-bit bitmask) counts in game design. And gkedzierski? They're soaking up these nuggets of wisdom and already dreaming up video dev logs to spread the word. It's like a masterclass in making virtual worlds come alive!
You may be interested in a paper we have written for multi agent systems using A* in unfamiliar terrain: https://www.researchgate.net/publication/333917261_Implement...
This article + this HN thread have some nice tricks. I haven't needed A* for much (yet), but I do know there's a nice Haskell library for it https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...
Apparently that's deprecated in favor of monad-dijkstra! https://hackage.haskell.org/package/monad-dijkstra
[deleted]
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.
Off topic, but tangentially related:
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?
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?
My search nodes were tuples of position, direction, and steps taken in the same direction.
More or less a straight depth first search with a priority queue from there.
More or less a straight depth first search with a priority queue from there.
How were you storing direction? Was it a symbol for one of NORTH, EAST, SOUTH, WEST, or a symbol for one of FORWARD, LEFT, RIGHT, or a pair of values for row direction and column direction (i.e. +1, 0 or -1, 0 or 0, +1, or 0, -1)?
A tuple vector with row and column offset, your third option here, which happen to have symbol names of N, S, E, and W.
Thanks for replying. Maybe I just have a dumb bug in my logic and should take another crack at it.
I know I had issues keeping track of how many steps I’d taken, but making sure I was generating a good set of neighbours helped with that.
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.
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.
Any 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 apparent.
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.
See also Time-Dependent Contraction Hierarchies (2008) [pdf] https://algo2.iti.kit.edu/documents/routeplanning/tch_alenex...
Oh the fun of cobbling heuristic algorithms to work in the real-world where precise algorithms are big-O too slow.
Oh the fun of cobbling heuristic algorithms to work in the real-world where precise algorithms are big-O too slow.
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 <20 lines of code) for good speedup (3-5X on my game map tests [1]).
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'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...
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 :)
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 :)
One "simple" trick here also is to consider putting at least some of your pathfinder calculations outside of the core game thread.
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.
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.
Can 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?
Micromouse competition is exactly about this. There are plenty of algorithms published. Some version of flood fill is the most popular I think.
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.
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.
Check out dstar, take a look the graph at 3:36
https://m.youtube.com/watch?v=skK-3UfcXW0
https://m.youtube.com/watch?v=skK-3UfcXW0
One neat pathfinding trick that I use for an in game GPS is to allow the user to specify multiple destinations and find the closest one. Rather than just running it multiple times, I temporarily add a synthetic node to each of the destinations and path to the synthetic node and then look at the previous node to figure out which one to go to.
Are there better ways?
Are there better ways?
A* is cool but pixel base solutions are naive. Also Dijkstra with a heuristic is just the beginning to a A.I. rabbit hole.
> pixel base solutions are naive.
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.
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.
If every tile in the game ("tile" being some discrete unit of walkable/not walkable) is 8px by 8px, then you're doing 64x the work you need to. The tile data will also be stored somewhere anyways to handle player collisions etc. (except in cases where memory is _extremely_ limited, but those are rare - in that case pixel data is used, as you suggested)
True, but if players and AI and game elements can move in units of pixels, and exist in multiple tiles at once, the it may be difficult to work in units of tiles. Not clear the parent was distinguishing between pixels and tiles too, or if the ‘naive’ comment was aimed at any kind of gridding, or something else.
Voronoi graphs are a fast option to get you in the approximate area, then a fine grid can do the last-mile part if need be. It does require preprocessing the map first though.
Naive implementations of A* can break down in some common scenarios, with highly connected graphs where many solutions exist. Imagine a long barrier with the start and goal placed on either side at the exact midpoint.
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.
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.
It would be interesting to see these classical methods compared to a simple RL method that optimizes a tiny neural net or decision tree which is given access to the map, player, and monster positions. I think it would cost a tiny bit more compute but have fewer annoying edge cases.
I suspect that it would have a similar number of edge cases, but they would be harder to interpret and reproduce. That's just been my experience with moving from unlearned algorithms to deep learning in general.
Usually what happens in cases like this is that the RL network ends up learning a slightly crappier version of A*
Or finds a bug in the environment and learns to teleport, those are fun too
Or finds a bug in the environment and learns to teleport, those are fun too
I haven't seen RL with decision trees! it sounds really interesting. Any classic results worth looking into?
This is a relatively recent paper you might find interesting. https://arxiv.org/abs/2204.03771
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.
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.
Some other tricks:
* 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:
* 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)
* 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)
Try observing how you pathfind IRL. It has nothing to do with A*, whose only pro is easy computability. It shouldn't be the default unless you need high performance pathfinding.
> 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?
What is the method for doing this?
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 .