[HN Gopher] A* tricks for videogame path finding
___________________________________________________________________
A* tricks for videogame path finding
Author : azhenley
Score : 161 points
Date : 2024-01-01 17:52 UTC (5 hours ago)
(HTM) web link (timmastny.com)
(TXT) w3m dump (timmastny.com)
| markisus wrote:
| 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 wrote:
| 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 wrote:
| I haven't seen RL with decision trees! it sounds really
| interesting. Any classic results worth looking into?
| markisus wrote:
| 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.
| malux85 wrote:
| 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 wrote:
| Any time A* comes up, someone plugs this great resource:
| https://www.redblobgames.com/pathfinding/a-star/introduction...
| urbandw311er wrote:
| The next big advance after A* is something called [contraction
| hierarchies](https://en.m.wikipedia.org/wiki/Contraction_hierar
| chies)
|
| 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.
| 1letterunixname wrote:
| See also _Time-Dependent Contraction Hierarchies_ (2008)
| [pdf] https://algo2.iti.kit.edu/documents/routeplanning/tch_a
| lenex...
|
| Oh the fun of cobbling heuristic algorithms to work in the
| real-world where precise algorithms are big-O too slow.
| bee_rider wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| You have invented the pink ghost from Pac-Man.
| bee_rider wrote:
| The pac-man ghost AIs are definitely worth a search, fun
| stuff from such a simple program.
| gary_0 wrote:
| > 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.
| sitzkrieg wrote:
| 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
| slowhadoken wrote:
| 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 wrote:
| > 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 .
| hwillis wrote:
| > 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.
| aappleby wrote:
| 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.
| aappleby wrote:
| 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.
| superjan wrote:
| 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.
| forrestthewoods wrote:
| 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.
| araes wrote:
| 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.
| aappleby wrote:
| 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.
| doophus wrote:
| > 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.
| aappleby wrote:
| 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.
| moffkalast wrote:
| 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.
| deadbabe wrote:
| They're tricks because ideally computational power should be
| so plentiful that optimizations would be totally unnecessary.
| antman wrote:
| Check out dstar, take a look the graph at 3:36
|
| https://m.youtube.com/watch?v=skK-3UfcXW0
| mopierotti wrote:
| 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.
| GuB-42 wrote:
| 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.
| mopierotti wrote:
| 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.
| superjan wrote:
| 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 wrote:
| 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.
| whateveracct wrote:
| 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...
| whateveracct wrote:
| Apparently that's deprecated in favor of monad-dijkstra!
| https://hackage.haskell.org/package/monad-dijkstra
| o11c wrote:
| 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 wrote:
| 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?
| mm_aa wrote:
| Micromouse competition is exactly about this. There are plenty
| of algorithms published. Some version of flood fill is the most
| popular I think.
___________________________________________________________________
(page generated 2024-01-01 23:00 UTC)