A* is cool but pixel base solutions are naive. Also Dijkstra with a heuristic is just the beginning to a A.I. rabbit hole.
A* tricks for videogame path finding
11–20 of 108 posts
Re: A* tricks for videogame path finding
#12It 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 haven't seen RL with decision trees! it sounds really interesting. Any classic results worth looking into?
Re: A* tricks for videogame path finding
#13Any 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.
Re: A* tricks for videogame path finding
#14A* 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.
Re: A* tricks for videogame path finding
#15Some 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 .
Re: A* tricks for videogame path finding
#16It 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.
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
Re: A* tricks for videogame path finding
#17The “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.
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.
> 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.
Re: A* tricks for videogame path finding
#18Check out dstar, take a look the graph at 3:36
Re: A* tricks for videogame path finding
#19I'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.
Re: A* tricks for videogame path finding
#20Some 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 path…
> 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.