5 ms·

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

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.
- aappleby 3y ago
  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.
  - bonton89 3y ago
    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.
- aappleby 3y ago
  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 3y ago
  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.
  - eru 3y ago
    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.
- araes 3y ago
  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.
  - alexey-salmin 3y ago
    > 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
  - sojuz151 3y ago
    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
  - deleted 3y ago
    [deleted]
  - otikik 3y ago
    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?
    - helloplanets 3y ago
      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 https://learn.unity.com/tutorial/moving-as-one
- SirMaster 3y ago
  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.
  - hypercube33 3y ago
    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.
    - kroltan 3y ago
      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.
  - Log_out_ 3y ago
    It would be also mercilessly exploited if the patching would reveal defense buildings blocking a way..
  - KptMarchewa 3y ago
    Some of the units in Brood War are legendary due to their bad pathfinding like Dragoon.
- eru 3y ago
  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 https://developers.google.com/optimization has a decent collection of tools.
  - hwillis 3y ago
    > 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!
aappleby 3y ago
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.
- two_in_one 3y ago
  nearest object can be dynamic thing
  - eru 3y ago
    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.
- ReactiveJelly 3y ago
  Oh like in path tracing.
doophus 3y ago
> 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 3y ago
  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.
  - KptMarchewa 3y ago
    Oh that would be unpleasant if you wanted deterministic behaviour - for example multiplayer RTS.
moffkalast 3y ago
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.
- oasisaimlessly 3y ago
  I would put money on a lot of these tricks first being used in games and then being 'rediscovered' by the robotics field.
  - moffkalast 3y ago
    Almost on a daily basis I would imagine, yep.
- Log_out_ 3y ago
  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
- deadbabe 3y ago
  They’re tricks because ideally computational power should be so plentiful that optimizations would be totally unnecessary.
  - ivancho 3y ago
    Jevons paradox will kick in, we'll start computing more things instead
- deleted 3y ago
  [deleted]
Udo 3y ago
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.
- the_gipsy 3y ago
  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.
YesBox 3y ago
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/ https://store.steampowered.com/app/2287430/Metropolis_1998/
- mysterydip 3y ago
  Just wanted to say, love the art style and the mechanics. Will be following!
- gkedzierski 3y ago
  Have you considered making video dev logs? That’s very well thought out, and I love the art style!
mrmuagi 3y ago
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.

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.
aappleby 3y ago
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.
- bonton89 3y ago
  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.
aappleby 3y ago
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 3y ago
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.
- eru 3y ago
  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.
araes 3y ago
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.
- alexey-salmin 3y ago
  > 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
- sojuz151 3y ago
  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
- deleted 3y ago
  [deleted]
- otikik 3y ago
  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?
  - helloplanets 3y ago
    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 https://learn.unity.com/tutorial/moving-as-one
SirMaster 3y ago
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.
- hypercube33 3y ago
  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.
  - kroltan 3y ago
    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.
- Log_out_ 3y ago
  It would be also mercilessly exploited if the patching would reveal defense buildings blocking a way..
- KptMarchewa 3y ago
  Some of the units in Brood War are legendary due to their bad pathfinding like Dragoon.
eru 3y ago
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 https://developers.google.com/optimization has a decent collection of tools.
- hwillis 3y ago
  > 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!

aappleby 3y ago

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.

two_in_one 3y ago
nearest object can be dynamic thing
- eru 3y ago
  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.
ReactiveJelly 3y ago
Oh like in path tracing.

doophus 3y ago

> 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 3y ago
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.
- KptMarchewa 3y ago
  Oh that would be unpleasant if you wanted deterministic behaviour - for example multiplayer RTS.

moffkalast 3y ago

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.

oasisaimlessly 3y ago
I would put money on a lot of these tricks first being used in games and then being 'rediscovered' by the robotics field.
- moffkalast 3y ago
  Almost on a daily basis I would imagine, yep.
Log_out_ 3y ago
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
deadbabe 3y ago
They’re tricks because ideally computational power should be so plentiful that optimizations would be totally unnecessary.
- ivancho 3y ago
  Jevons paradox will kick in, we'll start computing more things instead
deleted 3y ago
[deleted]

Udo 3y ago

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.

the_gipsy 3y ago
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.

YesBox 3y ago

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/ https://store.steampowered.com/app/2287430/Metropolis_1998/

mysterydip 3y ago
Just wanted to say, love the art style and the mechanics. Will be following!
gkedzierski 3y ago
Have you considered making video dev logs? That’s very well thought out, and I love the art style!

mrmuagi 3y ago

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.