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 .
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.
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.
Some of the units in Brood War are legendary due to their bad pathfinding like Dragoon.
Which is incidentally what made SC the high skill ceiling it has.
If the pathing of SC had been "great", the game mightn't have taken off the way it did competitively.
Eh, there's more to it, the pathing has been one of maybe dozen components that came together like that.
There were more important factors, like having the limit to 12 units in a group - any more would make Zerg much more powerful - now Zerglings are easy to use en masse. Terran bio would benefit from it as well.
Well pathing in sc2 improved significantly, although some problems remain (ultralisks dieing before reaching their target).
In the case of SC1, the dragoon in particular was really bad because its speed would change significantly depending on which part of the animation it was in. That’s what made wheeled vehicles and tanks were less wonky. Their speed was constant as they moved.
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.
It would be also mercilessly exploited if the patching would reveal defense buildings blocking a way..
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.
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?
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
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
I imagine this is also very tough in real life
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.
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.
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 has a decent collection of tools.
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!
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.
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.
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.
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.
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.
I would put money on a lot of these tricks first being used in games and then being 'rediscovered' by the robotics field.
Almost on a daily basis I would imagine, yep.
They’re tricks because ideally computational power should be so plentiful that optimizations would be totally unnecessary.
Jevons paradox will kick in, we'll start computing more things instead
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
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.
nearest object can be dynamic thing
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.
Oh like in path tracing.
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.
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.
Oh that would be unpleasant if you wanted deterministic behaviour - for example multiplayer RTS.
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/
Just wanted to say, love the art style and the mechanics. Will be following!
Have you considered making video dev logs? That’s very well thought out, and I love the art style!
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.
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.
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.
takes notes Fascinating. Any other sage advice on navigation and game-ai?
3. Also allows for "characters" one driving extremely risqué, or completely over the top, other steering safe and boring. Univwrsal Optimal behavior is boring..