[HN Gopher] How to smooth and spread A* paths for an RTS
___________________________________________________________________
How to smooth and spread A* paths for an RTS
Author : AshleysBrain
Score : 146 points
Date : 2023-01-31 13:04 UTC (9 hours ago)
(HTM) web link (www.construct.net)
(TXT) w3m dump (www.construct.net)
| candiddevmike wrote:
| 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 wrote:
| 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.
| Kiro wrote:
| What problem does it create to use all cores?
| ElectricalUnion wrote:
| 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.
| LawTalkingGuy wrote:
| 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 wrote:
| Thanks. What does n-2 cores mean?
| Dylan16807 wrote:
| n here is the number of cores
|
| So subtract two. Leave two free.
| vhartman wrote:
| 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...
| Existenceblinks wrote:
| As an old man yells at ML, this is a lot more fun. A*, Minimax,
| Simulated Annealing etc.
| throwaway17_17 wrote:
| Do you know of any examples of games using Simulated Annealing
| for pathfinding? I've had thoughts that it would provide an
| interesting 'big-step' granularity for unit pathing at large-
| ish goal scale, with other algorithms supplementing the more
| granular pathing. I think this may actually be me trying to
| combine object/goal selection by units and pathing into a
| consolidated decision point, though.
| Existenceblinks wrote:
| I personally only remember 8-queen puzzle. I tried google
| recently and it comes up with quite many applications.
| Basically anything that is likely to be solved by allowing
| free moving into wrong spot/position/thing to boost chances
| of being right and then at some point lowering the chance to
| form the solution. Well .. the name is self-described so I
| can't do it better than that.
| otikik wrote:
| > 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
| Agentlien wrote:
| I've implemented similar systems for commercial games I worked
| on and it works really well in a lot of fairly tricky
| situations.
| EamonnMR wrote:
| 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.
| hinkley wrote:
| 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.
| bee_rider wrote:
| 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 wrote:
| 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.
| ilyt wrote:
| > 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 wrote:
| 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.
| [deleted]
| bnastic wrote:
| Truth to be told, A* over navmeshes and path smoothing ('string
| pulling' by eliminating points with LoS) with adding
| occupancy/weight to individual triangles (or polygons? Not sure
| what's used here) is nothing particularly new... going some 25
| years maybe?
|
| I've not been in triple-A games for many years, but I'm not sure
| I'd choose navmeshes today for an RTS style game over a large
| terrain - they tend to be static in nature (without attaching a
| lot of additional data to them, projecting dynamic obstacles onto
| them, re-weighting all the polys all the time, while making sure
| that the resolution is fine enough for this purpose or coming up
| with some vector field on top of the larger ones.... but no one
| needs to save RAM these days, do they... it's not 32MB of
| Playstation 2 anymore)
| [deleted]
| haunter wrote:
| 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)
| kevincox wrote:
| 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.
| hinkley wrote:
| 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.
| jcarrano wrote:
| 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.
| KronisLV wrote:
| Oh hey, I recall using Construct Classic as one of my earlier
| forays into game development back in the day. At the time, visual
| scripting just felt like a great way of getting into things and
| easily playing around.
|
| Construct seems to have come a long way since.
| MayeulC wrote:
| 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 wrote:
| 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 wrote:
| 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.
| tommica wrote:
| Looks really interesting - would love to have a button that would
| enable me to either fork the project in construct3 to poke at it
| or just get to play the "game" and move units around and see it
| in action.
| gabereiser wrote:
| 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.
| alternatetwo wrote:
| Age of Empires 2 also does this for units in a "unit group".
| chii wrote:
| 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 wrote:
| 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.
| whateveracct wrote:
| There will always be marginal advantages to be had in
| micro-managing units I think.
| ketralnis wrote:
| Of course, but the game is more fun for the vast majority
| of players if it's not required for the vast majority of
| the skill population. Pro matches focus heavily on micro-
| heavier caster units and that's fine if it's still fun
| for the players that don't want to focus on that.
| xen0 wrote:
| In war, everything is simple but the simplest things are
| hard.
|
| I feel that Brood War embodies this part of Clausewitz
| quite well.
| hypertele-Xii wrote:
| And the skill in question ain't _strategy._
| CabSauce wrote:
| The starcraft parlance is Micro vs Macro.
| axus wrote:
| 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 wrote:
| How you administer your own actions/APM bandwidth as a
| player is itself a resource over which the player needs to
| strategize accordingly
| raincole wrote:
| 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.
| qikInNdOutReply wrote:
| Not necessary, you can dance all the micro you want, but
| if you play BAR against SA pushing that exponential eco
| curve, you will loose. Human skill and attention are
| linear.
|
| A master of click work, will loose against the onslought
| of material of the Big E, in the long run.
| throwaway17_17 wrote:
| I can get the point of your post in the broadest sense,
| however, it feel a little like trying to read a foreign
| language. So, just because I am trying to kill some time
| before my Motion Hearing starts, can you give me a
| breakdown of what you are actually referencing?
| qikInNdOutReply wrote:
| There are artifical strategy games limitations, by the
| User Interface, by technology and by the players
| themselves. Some games do not adhere to those limtations
| - like Beyond All Reason or Supreme Commander. It allows
| a experienced player, to grow a exponential economy and
| marshal the produced armys without a taxation on the
| limited, linear attention of the player or the Input Rate
| of some players. Meaning, the micro management gained
| tactial advantages, get swept away by a ever larger
| exponentially growing economy.
|
| Its mostly visible in the pros vs joes matches of BAR
| Players, in which well managed exponential eco allows a
| recovery from impossible situations, marshalling
| exponential growth against several weaker, though elo
| strong players at the same time.
|
| https://www.youtube.com/watch?v=QuAPHw3DwMY
|
| Its like watching BIG O N^2 beating Big O lin N to pulp,
| but in a rts. Blink and you miss it though. Its the
| infrastructure bootstrapping itself, in the back of the
| base.
| JRKrause wrote:
| Can't help but point out that, in SC2 specifically, micro
| is not really a fundamental skill at all. Macro-ing
| efficiently will win you the vast majority of fights
| until you reach the 90th percentile of players. It's only
| in these high level games that micro skills become the
| determining factors.
| Dylan16807 wrote:
| Though starcraft macro has a high ratio of fiddly
| clicking to strategy. Less so in SC2 but still
| significant. Good macro involves a lot of clicking
| buttons in many different places as soon as they become
| available, because you can't queue them.
| egypturnash wrote:
| Modeling each unit singly and finding a wholly bottom-up solution
| works, I guess, but I wonder if it's worth coming at it from a
| tactical level. You're the commander pushing entire divisions
| across the battlefield, and the individual units in the division
| would be trained to maneuver _together_. They 're soldiers with a
| commander, not individual ants. Shouldn't the model reflect that?
|
| I wonder if a better solution would be to treat the whole group
| of units as one mega-unit, pathfind for _that_ , then if the path
| for the megaunit is some factor longer than the straight
| collision-ignoring route, split it up into 2-6 squad-units. Or
| split the megaunit up into however many squad-units it takes to
| have a maximum of a dozen units per squad, pathfind for the
| squads with some collision avoidance, then do a more fine-grained
| process of calculating a path for each unit from its current
| position relative to its squad's center to the same position
| relative to the next point on the squad's path.
|
| I never play this sort of game so maybe this is routine now, I
| dunno.
| brainzap wrote:
| Supreme Commander 2 used Flowfield path finding.
| code_witch_sam wrote:
| best i can tell, dragoons in starcraft 1 used A- paths. that
| is, A*, but completely f-ing random
| Miraste wrote:
| And SupCom 2 has way better pathfinding than 1, which I believe
| is A* based and is absolutely, game-losingly terrible.
| MintPaw wrote:
| 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 wrote:
| (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!
| MintPaw wrote:
| > 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 wrote:
| I'd imagine that's not the only thing that will be
| multithreaded.
| qikInNdOutReply wrote:
| Why not mention flow fields? They make for important movement
| improvements.
| AshleysBrain wrote:
| I've not heard of flow fields before! Do you know a good
| reference to read up on them?
| qikInNdOutReply wrote:
| https://www.youtube.com/watch?v=lOYXUktahv8
|
| No reading up, but somewhere there was a blog post by the
| programers and a reference to the paper
| softcactus wrote:
| They are actually pretty simple. Essentially you generate
| the Dijkstra values for an undirected graph (this can be
| a grid, navmesh, etc), then you create directed edges
| pointing from high values to low values. So a grid space
| of value 8 will point to its neighbors with values less
| than 8, etc.
|
| All an agent has to do is query their current spot in the
| graph and it will return a vector that leads them to the
| next lowest cost. This is useful if you have lots of
| agents going to the same location.
|
| https://www.youtube.com/watch?v=BHcQ4JCj27w
|
| The description of this video has a lot of good
| resources. I made it when I was a much much worse
| programmer though so I wouldn't bother actually watching
| the video lol.
| throwaway17_17 wrote:
| Emerson's chapter from 2013's Game AI Pro acts as a
| decent overview from what I have heard.
|
| [1] - http://www.gameaipro.com/GameAIPro/GameAIPro_Chapte
| r23_Crowd...
| stefan_ wrote:
| 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.
| FooBarBizBazz wrote:
| 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.
| substation13 wrote:
| 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.
| qikInNdOutReply wrote:
| https://en.wikipedia.org/wiki/Quadtree actually
| [deleted]
| bee_rider wrote:
| In Age of Empires 2, units that are all selected together make a
| sort of formation, and then move as a unit. This is visually
| pleasing, especially by the standards of a turn-of-the-century
| RTS.
|
| I wonder if they do something along these lines, or if they
| literally just treat the formation as a single unit and path for
| that?
| warent wrote:
| 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/
| Udo wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| 1248 wrote:
| 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 wrote:
| 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?
| hesdeadjim wrote:
| 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.
| marijnz wrote:
| 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...)
| Agentlien wrote:
| 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.
| agumonkey wrote:
| Very nice paper, thanks.
| softfalcon wrote:
| 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?
| Mageek wrote:
| You still run A*, it's just on the nav mesh rather than on a
| grid.
| secondcoming wrote:
| > That did impose some limits on parallelism, but it will
| probably still make full use of CPUs with up to 6-8 cores, which
| seems to cover most devices anyway.
|
| Probably true, but this seems like a massive resource utilisation
| for an RTS game.
___________________________________________________________________
(page generated 2023-01-31 23:01 UTC)