[deleted]
A* tricks for videogame path finding
21–30 of 108 posts
Re: A* tricks for videogame path finding
#22Some 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…
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.
Re: A* tricks for videogame path finding
#23Some 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…
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.
Re: A* tricks for videogame path finding
#24Some 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…
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.
Re: A* tricks for videogame path finding
#25Some 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…
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.
Re: A* tricks for videogame path finding
#26Some 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…
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.
Re: A* tricks for videogame path finding
#27When 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.
Re: A* tricks for videogame path finding
#28It 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?
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.
Re: A* tricks for videogame path finding
#29Some 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…
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.
Re: A* tricks for videogame path finding
#30I 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.