Get the top HN stories in your inbox every day.
warent
Udo
Maybe someone can clear something up for my understanding here.
Having implemented A*-style algorithms occasionally, I was under the impression that by "navmesh" people mean a planar vector structure that can then be navigated using, for example, A*. As opposed to a grid data structure consisting of cells that can then be navigated using a pathfinding algorithm. I always saw A* as a strategy to find a path in any graph, and I saw navmesh as an example of such a graph.
Now it seems people are defining navmeshes as both a data structure AND pathfinding strategy, and by the same token are likewise seeing A* as both. This seems really confusing to me.
Have I been using the lingo wrong all this time?
warent
No I think you're right and that I was mistaken. The only navmesh implementations I've seen do not use Astar, with Astar only being used in grid structures. But now I see that was a coincidence.
Agentlien
I've worked on several AA and AAA games which use nav meshes and they've all used A* for search.
This is also how many game engines, including Unity, implement their NavMesh queries.
dheera
Astar can also be used for non-grid structures. It can actually be used for any graph traversal, including e.g. Google Maps Navigation type use cases, and is arguably even more suited to those problems than grid movement, since the lowest-cost path through a grid is often a very unnatural way to move through an open space, especially if you're using Manhattan distances.
hesdeadjim
A* is as valid on a navmesh as it is in a grid-based layout. A* just needs "points" (or each edge of a navmesh polygon) and the edges that connect them, how those points and edges are represented or exist in the world is entirely an implementation detail.
TillE
It's funny cause A* (a slight modification of Dijkstra's algorithm) is explicitly an algorithm that operates on graphs. Applying it to a "navmesh" is actually conceptually simpler than thinking of a grid-based game world as a big uniform graph.
Agentlien
In all games I've worked on nav meshes have been used. They are definitely the goto solution for NPC movement.
However, I did work on a number of popular open world racing games where a lot of NPCs were travelling across the map, often where no player was nearby. For these, as well as for visualization of travel routes on the map, we used a graph of the road network and A* with some simple modifications such as adding edges from the start and end point to the nearest points on the road network.
marijnz
Note that a navmesh can be used exactly with A* (and also for a post-search path shortening pass, with for example http://digestingduck.blogspot.com/2010/03/simple-stupid-funn...)
Mageek
You still run A*, it’s just on the nav mesh rather than on a grid.
softfalcon
Interesting, this was at the bottom of the slides:
> It’s not yet clear to what degree new algorithms like Anya and Polyanya can help improve the state-of-the-art in these areas.
Considering how Poly-Anya was sometimes slower than Anya (the non-nav-mesh version of path finding), it seems like the jury is still out as to whether this technique + nav-mesh is useful?
I could be completely wrong, I'm just looking at the results from the papers/slides you posted. It seems that A* still has relevance because it and modifications to it are still the fastest path-finding algorithms?
1248
But if you want to navigate in a 3d space (flying/space games) navmeshes are useless and you have to roll your own spline(ish) 3d space navigation/obstacle avoidance system. (It's kinda weird that an engine as popular and massive as UE5 only has nav meshes.)
softfalcon
Yeah, both UE5 and Unity3D seem to rely heavily on nav meshes for their built in path-finding. In my experience, both are sub-optimal for many, many use cases but are convenient in that they apply to a bunch of "on the ground" topology that can be somewhat easily generated using a quick ortho camera project/ray-cast operation.
Maybe they use it cause it's quick and easy, not because it's the most optimal?
BlueTemplar
IIRC UE also still only has the (built-in) option for a static, same vector at every space&time point (gravitational) force field ?
Of course this does cover most of the cases, probably even for "space" games (which are often more akin to WW1/WW2 naval simulators).
agumonkey
Very nice paper, thanks.
haunter
If anyone curious about some historic examples here is the pathfinding code from the C&C/Red Alert games
>The path algorithm works by following a LOS path to the target. If it collides with an impassable spot, it uses an Edge following routine to get around it. The edge follower moves along the edge in a clockwise or counter clockwise fashion until finding the destination spot. The destination is determined by Find_Path. It is the first passable that can be reached (so it will handle the doughnut case, where there is a passable in the center of an unreachable area).
https://github.com/electronicarts/CnC_Remastered_Collection/...
https://github.com/electronicarts/CnC_Remastered_Collection/...
(on a side note the comments are incredibly detailed, considering this is from 1993-95)
hinkley
I was only able to win Warcraft 3 by learning to cheese the heavy enemies like demons by forcing them to pathfind along walls festooned with archers. It was funny but it wasn’t really fun.
It was experiences like that which made be briefly consider a career trying to make better game AI.
kevincox
I guess the problem here is that if you have a few rocks in your path it will go around each rock to the opposite side for each rock. Rather than going to the side of the first rock, walking past all of the rocks, then coming back to the opposite side.
otikik
> The paths are simplified to produce fewer nodes with gentler turns between them, which is helpful when units drive along them
It looks like a much more useful optimization would be to produce a simplified map that splits the "real" map into "connected regions" via chokepoints. Pathing on that simplified map should be orders of magnitude simpler than on the "real" one. That's the "high-level plan": go to region A, then to region B, then target is on region C.
Once you have a high-level plan, each unit only need to do the expensive pathing until their next chokepoint (or to the target, if they are on the same region).
This is especially relevant on dynamic maps that are continuously changing (e.g. enemy units blocking paths, or building structures, or fog-of-war that keeps being updated, or closing and opening doors). Re-calculating the high-level path every time for every unit, and throwing it away when there's a change, is too expensive. Much more economical to recalculate the high-level map once for everyone, and then do high-level plans + pathing to the next choke.
Rimworld has a video where they explained their Region system, which implements this: https://www.youtube.com/watch?v=RMBQn_sg7DA
hinkley
Halo 2 devs also bragged publicly about how some of the AI is compiled into the map. The map understands things like “cover” and the enemies will seek out that information when reacting to the player, rather than evaluating the environment for themselves.
The map in Rimworld is destructible though, so that sort of technique doesn’t quite work.
ilyt
> The map in Rimworld is destructible though, so that sort of technique doesn’t quite work.
It could just be updated. Terrain/building destruction events don't happen all that often in Rimworld, maps also aren't too big
meheleventyone
Rimworld also has to update the pathing and information for all the buildings and usable by NPCs 'stuff' so is likely doing a lot of this already.
hinkley
Running calculations are one thing, but for Halo 2 it was done at build time.
bee_rider
I really liked it the Halo2 AI, it was sort of the high water mark in FPS AI as far as I saw. I probably just haven’t played whatever games are advancing it; I heard the FEAR series had especially good AI but I only played it a little bit.
One thing I really liked was how chatty the enemies were. I think they claimed the Grunts would “act smarter” when Elites were around to command them. No idea if that was just marketing fluff though. Hard to notice either way, because there’s the confounding factor that the Elites are just stronger enemies so those fights would naturally be harder.
I’ve always thought it would be cool if the developers would take a “no cheating” approach — model what every unit has observed and require them to make a noise in order to share that information. It would add another dimension of difficulty — “highly trained” units could be modeled as able to communicate more information with less noise (and then add some units that just use hand signals or if it is sci-fi, psychics that can give orders silently).
mlsu
I never played FEAR, but ended up reading basically this whole page when it was posted here a while ago:
https://alumni.media.mit.edu/~jorkin/goap.html
Really interesting stuff.
It appears chronologically dated at this point, but I'm not sure that anyone's made substantial improvements, given the lack of investment into single player games.
BlueTemplar
Yet another example (with nice animations, and discussion about how to deal with non-contiguously pathable regions) :
Factorio Friday Facts #317 - New pathfinding algorithm :
otikik
That was really interesting, thank you.
Using the low level map for the heuristic on the high level one is neat. Making the high level algo resumable is also very neat. I still think they should be pathing “only to the next region” on the high level map.
EamonnMR
This is what they did for the StarCraft pathfinding, but I can't back that up with the links I wanted to send. Also, StarCraft definitely uses the static map for long paths, units will get stuck if you block choke points with mobile units.
Agentlien
I've implemented similar systems for commercial games I worked on and it works really well in a lot of fairly tricky situations.
gabereiser
This is gold. The part about spreading the movement as to not create bottlenecks is something every RTS player has experienced to the point where some RTS' from big name developers ("Chilly") just make it so units can pass through each other.
chii
One of the reason starcraft has such a high skill ceiling is that you do need to individually control the pathing of the units so as not to bottleneck.
ajkjk
All I want is for there to be a Starcraft 3 that doesn't have most of the micro in it, so that games can hinge more on tactics and strategy than rapid clicking. It's such a pain ... I feel like microing was fun in the 2000s but now it's just annoying.
Baeocystin
I loved the original Brood War. But The Fun™ for me was always in the macro side of things. I wanted to give units large-scale orders, and have them figure it out.
The rest of the RTS world relentlessly pursued micro, of course. And the MOBAs that came of that are fine for what they are, but what they aren't is something I personally want to play.
It always surprised me that parts of the tech research tree in any RTS didn't seem to include smarter unit behavior as part of the stack. Paying in-game resources to off-load cognitive load is an interesting loop!
Partial credit is due to Majesty, which is the only indirect-control RTS I've come across. Old game, but still fun for what it was. I liked the idea.
_carbyau_
I've never even looked at Starcraft 2 with it's "micro" reputation. I favour Supreme Commander. To be fair it is: Supreme Commander + Forged Alliance + FAF online community.
Persistent between games: Configurable building templates - one building command queues whatever you set in whatever arrangement, rotatable on placement.
Factory infinite repeating queues with waypointing including automated airlift ferrying for ground units if required.
Adjustable waypoints. Move, insert, remove waypoints without having to redo the whole set from scratch.
Plus I like the storage aspect of resource management and the titanic units. Not so sure I care much for nukes though...
xen0
In war, everything is simple but the simplest things are hard.
I feel that Brood War embodies this part of Clausewitz quite well.
whateveracct
There will always be marginal advantages to be had in micro-managing units I think.
hypertele-Xii
And the skill in question ain't strategy.
raincole
RTS games (at least most of them) are always like that tho. The ability to micro-manage your units is the most foundamental skill for a competitive player.
I believe that's one of the reason LoL and Dota became more popular than any RTS.
axus
Logistical tactics? The Russian military was really hurt by the lack of this skill in the first week of the Ukraine invasion, lots of pathing problems.
CyanBird
How you administer your own actions/APM bandwidth as a player is itself a resource over which the player needs to strategize accordingly
CabSauce
The starcraft parlance is Micro vs Macro.
alternatetwo
Age of Empires 2 also does this for units in a "unit group".
jcarrano
I wonder why the Eikonal equation (and variations) and level-set methods are so rarely discussed. They yield any-angle paths and can also take into account the kinematics of the vehicle (e.g. minimum turn radius). I used it to solve a pathfinding problem in robotics and it could perform parking maneuvers all by its own.
The resulting algorithm bears similarities to Dijkstra's or A* (i.e. it is a sort of value iteration, see the "fast marching method") but yields a scalar field, whose gradient will give the direction of the optimal path at any point.
BlueTemplar
I guess because while minimum turn radius is unavoidable in real life, most games prefer to minimize it and its consequences as much as possible, due to the explosion in complexity they create ?
graffix
In game AI, these are discussed often under various guises like "influence maps" and "Dijkstra maps".
YesBox
Path finding is a tricky problem. I developed my own algorithm[0] for a city builder game (Metropolis 1998) I'm working on. I needed an efficient solution to finding _all_ shortest paths between two points, and after a few weeks of trudging through the mud, I ended up with a good one.
The algorithm can handle 100,000+ units path finding to their own unique destinations at 60 FPS. [edit: on a single CPU core]. The graph is processed once, and stores all possible paths (using near minimum storage)
Additionally, I can have additional preference weights in the graph so units can use paths that match their preferences.
Note: The video[0] no longer represents the look of my game, as I've moved on to isometric[1].
vhartman
The path simplification technique in the post is called "shortcutting" in robotics. Here [1] is some approachable explanation, the original paper [2] is relatively digestible read as well, and has some other techniques in there (amongs thm, partial shortcutting, which I found extremely helpful in robotics path planning).
Regarding general multi agent path finding: There is a lot of literature around with respect to time optimal planning in MAPF both in robotics, and in adjacent fields.
[1] http://www.osrobotics.org/osr/planning/post_processing.html
[2] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...
candiddevmike
This article is over committing the number of web workers and cores. You should not do n cores = n web workers, it should be at best n-2 web workers (or 1). The reason being this is a consumer device and the cores are absolutely not dedicated to just your app.
dspillett
That and unless you are purely number-crunching, or the work done by the workers is bursty rather than relatively constant, you browser will want some CPU resource the main thread (and display updates) to be responsive.
BlueTemplar
The article does consider issues like these towards the end.
Kiro
What problem does it create to use all cores?
LawTalkingGuy
It's for non-server machines which will be running other things like the user's browser. You won't get the same performance on the shared cores so sometimes it's better to just run on the free ones, and without checking/adjusting it's just easier to use n-2 cores.
In a production environment you do want to eliminate the other processes.
Kiro
Thanks. What does n-2 cores mean?
ElectricalUnion
You want to use better localized memory structures in faster cache, and you want to allow the use of the higher frequency/IPC cores instead of being thermally/memory bandwidth limited by all the cores being loaded at lower frequency all the time.
MintPaw
I feel like making this multithreaded is a bit overkill. Or at least it should have presented a situation with many more units.
I made an RTS in C++ a while ago and was able to build paths for many units per frame on a fairly large map. And even if I couldn't, there's many optimizations I would have considered before threading, like only building a partial path based on portals. Or building a "bad" path and simplifying it on future frames.
Here's a great A* references with a bunch of helpful tricks: http://theory.stanford.edu/~amitp/GameProgramming/
AshleysBrain
(Author here) I can imagine multithreading in C++ is a last resort. But with web workers it's guaranteed safe and relatively easy to do with message passing. So why not? Even using one thread lifts the performance overhead of pathfinding off the main game thread, which helps scale it up to 1000s of units, which I'm hoping to do!
garaetjjte
Having excess processing power available is not an excuse for writing inefficient software.
MintPaw
> So why not
Because multithreading introduces a lot of complexity, making it inflexible and hard to scale. Of course you would never do it if the code was fast enough to not have to.
I never had to consider it, I could generate about 16 complete flow fields per frame on a 512x512 map with no quadtree optimization.
It sounds like a nice way to learn webworkers, but I think you're always better off hitting the perf bottleneck first, rather than trying to design around it early.
ilyt
I'd imagine that's not the only thing that will be multithreaded.
qikInNdOutReply
Why not mention flow fields? They make for important movement improvements.
AshleysBrain
I've not heard of flow fields before! Do you know a good reference to read up on them?
stefan_
The basic sin here is doing pathfinding around a million square cells just because that happens to be the base of your rendering. You merge it all into convex polygons and suddenly the pathfinding is a pen&paper homework problem because theres about 5 of those left.
substation13
Most classic RTS games have you place buildings on a grid. The buildings block movement so are important for pathing.
You could merge large squares of open space as an optimization though.
FooBarBizBazz
And if you pathfind on the visibility graph of those polygons' vertices, your path is even optimal in Euclidean space. Granted, that's a slightly larger graph, but still much smaller than all the grid cells.
And actually, depending on the connectivity of the fine square grid, pathfinding on it is pretty suboptimal too, because you're only finding paths that are shortest in Manhattan- or 8-connected distance (barring some fast-marching/Eikonal thing). If your units are really restricted to those motions then that's correct, but if they can move continuously then you're losing a lot of diagonals. So that's another argument for polygons.
undefined
MayeulC
Hmm, I keep thinking this would be better handled with 3D position vectors (on a sparse 3D grid; 3D because it's 2D game coordinates + time): not every unit is at the same place at the same time. You could even apply the same "spread" strategy in time, to avoid units following too closely.
Of course, that's more complicated, but you get collision avoidance as well. Probably better coordination than real-world vehicles. One may get weird results though, such as two units using a completely different path because that saves them two seconds, which may not be a good strategy in an RTS.
ilyt
You generally want your units as close together as possible during movement, as so when enemy attacks during it the most amount of your own units is within range to shoot it
Arrath
It would be interesting to see a formation setting that dictated a desired interval between units as a protection against splash damage collateral affecting too many units at once.
ilyt
I guess it all depends what kind of game you're making. The whole point of aoe damage is to hit multiple targets, having game to give option to just say "lol, no, you can't hit many units coz they are spread out automatically" makes the interaction shallower.
Which might be entirely fine if you want to make strategy focused on macro, not micro.
Some games have formations that are compact or spread that player can choose, some, like TW:Warhammer, have some units that are spread and some that are compact (in a game where you control only whole squads) and all of that have different drawbacks, compact ones are good for defending chokepoints, spread ones are harder to aoe etc.
undefined
tjchear
A bit late to this thread but it'd be remiss of me if I didn't share this slide on left 4 dead's AI and navigation algorithm:
The AI Systems of Left 4 Dead - Akamaihd.net https://steamcdn-a.akamaihd.net/apps/valve/2009/ai_systems_o...
Get the top HN stories in your inbox every day.
I just got into the weeds of this for a hobby game I'm working on.
What I've learned is that A* is largely deprecated these days. Modern games mostly use "navigation meshes" for "any angle" pathfinding to address what is otherwise an np complete problem. The idea is that you generate a set of vertices across your terrain and compute the path from there.
One of the current leading experts in this is Daniel Harabor. His papers are brilliant
http://harabor.net/data/presentations/gdc2019.pdf
https://harabor.net/daniel/index.php/pathfinding/