8 ms·

A* tricks for videogame path finding

478 points by azhenley 3y ago

panosfilianos 3y ago
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_Implementation_of_a_Single_and_Multi_Agent_system_for_Goal-Box_Problem https://www.researchgate.net/publication/333917261_Implement...
hoseja 3y ago
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.
NBJack 3y ago
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.
Kerima 3y ago
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!
Danywebb 3y ago
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.
- SeraGrey 3y ago
  [dead]
matheusmoreira 3y ago
> 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?
markisus 3y ago
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.
- Calavar 3y ago
  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.
- qumpis 3y ago
  I haven't seen RL with decision trees! it sounds really interesting. Any classic results worth looking into?
  - markisus 3y ago
    This is a relatively recent paper you might find interesting. https://arxiv.org/abs/2204.03771 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.
- malux85 3y ago
  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
mysterydip 3y ago
Any time A* comes up, someone plugs this great resource: https://www.redblobgames.com/pathfinding/a-star/introduction.html https://www.redblobgames.com/pathfinding/a-star/introduction...
- urbandw311er 3y ago
  The next big advance after A* is something called [contraction hierarchies](https://en.m.wikipedia.org/wiki/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.
  - amitp 3y ago
    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://arxiv.org/pdf/1504.05140.pdf * https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.pdf https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.p... [1] https://www.redblobgames.com/pathfinding/heuristics/differential.html https://www.redblobgames.com/pathfinding/heuristics/differen...
    - payasr 3y ago
      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 https://arxiv.org/pdf/1504.05140.pdf, and http://www.sommer.jp/spq-survey.pdf 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/EfficientRoutePlanningSS2012 https://ad-wiki.informatik.uni-freiburg.de/teaching/Efficien...) and her talk at ICAPS (https://www.youtube.com/watch?v=B3wKfJAVRkg https://www.youtube.com/watch?v=B3wKfJAVRkg), both excellent :)
bee_rider 3y ago
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.
- tmastny 3y ago
  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.
  - bee_rider 3y ago
    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.
    - OscarCunningham 3y ago
      You have invented the pink ghost from Pac-Man.
      - bee_rider 3y ago
        The pac-man ghost AIs are definitely worth a search, fun stuff from such a simple program.
  - gary_0 3y ago
    > 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.
slowhadoken 3y ago
A* is cool but pixel base solutions are naive. Also Dijkstra with a heuristic is just the beginning to a A.I. rabbit hole.
- dahart 3y ago
  > 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.
  - Arch485 3y ago
    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)
    - dahart 3y ago
      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.
  - moffkalast 3y ago
    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.
aappleby 3y ago
Some tricks I used for A* in a production MMO: 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 .
- Zondartul 3y ago
  takes notes Fascinating. Any other sage advice on navigation and game-ai?
- Log_out_ 3y ago
  3. Also allows for "characters" one driving extremely risqué, or completely over the top, other steering safe and boring. Univwrsal Optimal behavior is boring..
- hwillis 3y ago
  > 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.
  - forrestthewoods 3y ago
    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.
antman 3y ago
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
mopierotti 3y ago
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.
- gerjo 3y ago
  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/ https://qiao.github.io/PathFinding.js/visual/
- GuB-42 3y ago
  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.
deleted 3y ago
[deleted]
superjan 3y ago
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.
gwillz 3y ago
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.
- justinl33 3y ago
  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?
  - gwillz 3y ago
    Found it! https://bugs.mojang.com/browse/MC-17630?focusedCommentId=92590&page=com.atlassian.jira.plugin.system.issuetabpanels%3Acomment-tabpanel#comment-92590 https://bugs.mojang.com/browse/MC-17630?focusedCommentId=925...
    - justinl33 3y ago
      > Since working the (apparently A) pathfinding algorithm...* Beautiful.
- Sharlin 3y ago
  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!)
whateveracct 3y ago
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#readme https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...
- whateveracct 3y ago
  Apparently that's deprecated in favor of monad-dijkstra! https://hackage.haskell.org/package/monad-dijkstra https://hackage.haskell.org/package/monad-dijkstra
o11c 3y ago
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: \* 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. * If you have a convex walkable area, you know that the shortest path between any two points within it is a straight line, and this can significantly shorten A*. Note that a given tile will almost always be part of more than one such useful area (you certainly don't want to consider all valid areas), and this should not be limited to rectangular areas (in particular, don't let diagonal corridors be a worst case). It's okay to exclude "pocket" tiles near the wall; they'll still exist as individual tiles for pathfinding purposes if you really need to go there. * 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) * Even if you do run a full A*, you don't have to store every node, only nodes where you turn (this usually beats storing immediate direction for every node, except for extreme mazes of twisty little passages). Rounded convex obstacles (thus concave open spaces) are your enemy unless you also add wall-sliding logic here.
deadbabe 3y ago
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?
- Sohcahtoa82 3y ago
  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.
- mm_aa 3y ago
  Micromouse competition is exactly about this. There are plenty of algorithms published. Some version of flood fill is the most popular I think.
djmips 3y ago
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.
- programjames 3y ago
  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*).
- adanto6840 3y ago
  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-a-r-with-goal-oriented-action-planning https://www.gamedeveloper.com/design/building-the-ai-of-f-e-... 1 - https://web.archive.org/web/20230804100329/https://alumni.media.mit.edu/~jorkin/goap.html https://web.archive.org/web/20230804100329/https://alumni.me... See also (not mine): https://github.com/agoose77/goap-resources https://github.com/agoose77/goap-resources
- throwaway17_17 3y ago
  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.
initplus 3y ago
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.
criddell 3y ago
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 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?
- Cogito 3y ago
  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.
  - criddell 3y ago
    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)?
    - Cogito 3y ago
      A tuple vector with row and column offset, your third option here, which happen to have symbol names of N, S, E, and W.
      - criddell 3y ago
        Thanks for replying. Maybe I just have a dumb bug in my logic and should take another crack at it.
        Cogito 3y ago
        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.
spullara 3y ago
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?

478 points by azhenley 3y ago

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_Implementation_of_a_Single_and_Multi_Agent_system_for_Goal-Box_Problem https://www.researchgate.net/publication/333917261_Implement...

hoseja 3y ago

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.

NBJack 3y ago

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.

Kerima 3y ago

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!

Danywebb 3y ago

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.

SeraGrey 3y ago
[dead]

matheusmoreira 3y ago

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

markisus 3y ago

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.

Calavar 3y ago
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.
qumpis 3y ago
I haven't seen RL with decision trees! it sounds really interesting. Any classic results worth looking into?
- markisus 3y ago
  This is a relatively recent paper you might find interesting. https://arxiv.org/abs/2204.03771 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.
malux85 3y ago
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

mysterydip 3y ago

Any time A* comes up, someone plugs this great resource: https://www.redblobgames.com/pathfinding/a-star/introduction.html https://www.redblobgames.com/pathfinding/a-star/introduction...

urbandw311er 3y ago
The next big advance after A* is something called [contraction hierarchies](https://en.m.wikipedia.org/wiki/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.
- amitp 3y ago
  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://arxiv.org/pdf/1504.05140.pdf * https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.pdf https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.p... [1] https://www.redblobgames.com/pathfinding/heuristics/differential.html https://www.redblobgames.com/pathfinding/heuristics/differen...
  - payasr 3y ago
    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 https://arxiv.org/pdf/1504.05140.pdf, and http://www.sommer.jp/spq-survey.pdf 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/EfficientRoutePlanningSS2012 https://ad-wiki.informatik.uni-freiburg.de/teaching/Efficien...) and her talk at ICAPS (https://www.youtube.com/watch?v=B3wKfJAVRkg https://www.youtube.com/watch?v=B3wKfJAVRkg), both excellent :)

bee_rider 3y ago

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.

tmastny 3y ago
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.
- bee_rider 3y ago
  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.
  - OscarCunningham 3y ago
    You have invented the pink ghost from Pac-Man.
    - bee_rider 3y ago
      The pac-man ghost AIs are definitely worth a search, fun stuff from such a simple program.
- gary_0 3y ago
  > 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.

slowhadoken 3y ago

A* is cool but pixel base solutions are naive. Also Dijkstra with a heuristic is just the beginning to a A.I. rabbit hole.

dahart 3y ago
> 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.
- Arch485 3y ago
  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)
  - dahart 3y ago
    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.
- moffkalast 3y ago
  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.

aappleby 3y ago

Some tricks I used for A* in a production MMO: 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 .

Zondartul 3y ago
takes notes Fascinating. Any other sage advice on navigation and game-ai?
Log_out_ 3y ago
3. Also allows for "characters" one driving extremely risqué, or completely over the top, other steering safe and boring. Univwrsal Optimal behavior is boring..
hwillis 3y ago
> 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.
- forrestthewoods 3y ago
  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.

antman 3y ago

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

mopierotti 3y ago

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.

gerjo 3y ago
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/ https://qiao.github.io/PathFinding.js/visual/
GuB-42 3y ago
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.

deleted 3y ago

[deleted]

superjan 3y ago

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.

gwillz 3y ago

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.

justinl33 3y ago
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?
- gwillz 3y ago
  Found it! https://bugs.mojang.com/browse/MC-17630?focusedCommentId=92590&page=com.atlassian.jira.plugin.system.issuetabpanels%3Acomment-tabpanel#comment-92590 https://bugs.mojang.com/browse/MC-17630?focusedCommentId=925...
  - justinl33 3y ago
    > Since working the (apparently A) pathfinding algorithm...* Beautiful.
Sharlin 3y ago
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!)

whateveracct 3y ago

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#readme https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...

whateveracct 3y ago
Apparently that's deprecated in favor of monad-dijkstra! https://hackage.haskell.org/package/monad-dijkstra https://hackage.haskell.org/package/monad-dijkstra

o11c 3y ago

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: \* 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. * If you have a convex walkable area, you know that the shortest path between any two points within it is a straight line, and this can significantly shorten A*. Note that a given tile will almost always be part of more than one such useful area (you certainly don't want to consider all valid areas), and this should not be limited to rectangular areas (in particular, don't let diagonal corridors be a worst case). It's okay to exclude "pocket" tiles near the wall; they'll still exist as individual tiles for pathfinding purposes if you really need to go there. * 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) * Even if you do run a full A*, you don't have to store every node, only nodes where you turn (this usually beats storing immediate direction for every node, except for extreme mazes of twisty little passages). Rounded convex obstacles (thus concave open spaces) are your enemy unless you also add wall-sliding logic here.

deadbabe 3y ago

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?

Sohcahtoa82 3y ago
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.
mm_aa 3y ago
Micromouse competition is exactly about this. There are plenty of algorithms published. Some version of flood fill is the most popular I think.

djmips 3y ago

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.

programjames 3y ago
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*).
adanto6840 3y ago
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-a-r-with-goal-oriented-action-planning https://www.gamedeveloper.com/design/building-the-ai-of-f-e-... 1 - https://web.archive.org/web/20230804100329/https://alumni.media.mit.edu/~jorkin/goap.html https://web.archive.org/web/20230804100329/https://alumni.me... See also (not mine): https://github.com/agoose77/goap-resources https://github.com/agoose77/goap-resources
throwaway17_17 3y ago
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.

initplus 3y ago

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.

criddell 3y ago

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

Cogito 3y ago
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.
- criddell 3y ago
  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)?
  - Cogito 3y ago
    A tuple vector with row and column offset, your third option here, which happen to have symbol names of N, S, E, and W.
    - criddell 3y ago
      Thanks for replying. Maybe I just have a dumb bug in my logic and should take another crack at it.
      - Cogito 3y ago
        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.

spullara 3y ago

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?