Comparision of Pathfinding 1k Units Planetary Annihilation vs Forged Alliance

I hate to correct you @bgolus, but you are actually very wrong about this. It saddens me to see a developer know so little of how his own game works...

We, the players who accompany the games development, all know the unit path-finding in PA is calculated by WITCHCRAFT.

One of the biggest problems with FA's pathplanning is that it looked like standard A*. Now while thats not terribly much of a problem, they were calculating paths for every unit regardless of how similar their destinations and positions were. You can see this because if you give a large group a move order, the game will trickle the orders through the group so that the cpu is not destroyed for that single frame. It spreads it over many 'ticks', which can be a little irritating at times.

Unfortunately this technology never made it into the final game, did it?

It still doesn't seem that expensive at first, all it requires is to project the flow every few ticks and then recalculate the vector field. There's no need to update the projection in real time, even though it was done it the example, lanes will still form and rebalance either way. And while the construction of the vector field itself isn't trivial to parallelize, parallelization on a per-field base actually is.

There's also only a single flow field required per player, as it only needs to include predictions by objects controlled by or immutable to that player. Overhead in memory consumption is limited, and the computational overhead can be reduced to an best effort approach - if there are not enough resources to update the pathing vector field in realtime - no problem, just continue to use the old one as long as you like.

And have a look at it from a different perspective: Collision physics aren't exactly cheap either, and collisions are occurring on a regular base even during trivial maneuvers.

I know https://forums.uberent.com/threads/...lation-vs-forged-alliance.65751/#post-1029805

What you see there is the power of Flow Fields. Basically it allows you to do very little pathfinding calculation for tons of units. It is uniquely powerfull for large scale RTS like PA.
It is not that good if you a lot of independant untis going for a different goal each. But ever since Dune (C&C forerunner) implemented multi-select and group buttons, large groups going to the same target are the thing in RTS.

Back when they made SupCom 1 they did not have flowfields. They had not been developed back then. So intstead they delayed actualyl executing the move until all units had "thier" path found. unfortunately paths got invalidated as other units mooved in the way.
Also it lacked a proper client-server architecture and multithreaded sim (while PA lacks the later too, it has been part of the plan).

Flowfields were only inveted/got useable with SupCom 2. Wich despite his other shortcommings, did have similar pathfinding to PA (even on a smaller scale):

And path finding in PA was developed by same guy who made them form SupCom2.

And just as in SupCom 2: Flowfields didn't make it in the actual game. Seriously, the stuff shown in that trailer? It doesn't work ingame, neither in SupCom 2 nor PA. They kept the shared vector fields for navigation since it still saves a lot of resources, but they stripped out the dynamic part which balances the flow and avoids head on collisions.

because performance? or why else? the promo video for supcom2 looks quite awesome, but well... a promo video.

I never got any problems with path-finding its obvius iff you play on a crap pc(cpu/gpu) will notice.
And you dont want compare a hard multitasking game like FA to Little PA ?
Its like compare Crysis 1 to Farcry 1
But thats a silly comparation from a game that have + 7 years old and still bether then your PA.
Wy dont you try compare the real game ,the game play?
Or are you afraid?
Iff not show me how on gameplay and game options around all game, PA is bether then FA.

Just a note we play with 12 players any kind map,gameplay fluid has long you have a decent cpu /gpu /net.

It's a task CPUs are not really fit for. A lot of memory to update in each iteration. But on the positive side: No causal dependencies, so it's quite easy to do on the GPU. ATI did it back in, well I don't remember the year, but it was one of their showcases when they started promoting GPGPU, long before Cuda, OpenCL and DirectCompute were fleshed out. If I'm not completely mistaken, then they even managed to do it in realtime, even though I'm absolutely clueless how on earth they managed to build the per goal vector field on the GPU - because the flow field is the easy part over there. However they did the entire per-unit stuff of the pathfinding purely on the GPU which allowed to scale the demo to several thousand units moving collision free in realtime.

The pathing shown in that SupCom2 video was done without implementing the full crowd into the field. It's all with collision avoidance steering, unit pushing, and a lot of spacing in the formation.

And it's absolutely possible to do tens of thousands of units moving with the full flow field implementation updating at 60fps or greater. Modern CPUs are fast, and GPUs are faster.

But those kinds of academic demos or test cases where this is possible has a lot of limitations imposed. Yes we can do 100k units, as long as they're all smaller than the flow field grid size, all the same size, all movement is on a 2d grid, etc. That's not PA, most of those are not true for most games. It's also artificial situations where you can use nearly 100% of the CPU / GPGPU time devoted to processing the flow fields.

The reality is never that pretty. There's other things happening in the game, many of them very expensive and take a lot of time, so really pathing only gets a tiny fraction of the sim time for most updates.

And you're thinking of the Froblins demo:
http://developer.amd.com/resources/...os/ati-radeon-hd-4800-series-real-time-demos/

That's actually a new piece of information, so far the word was always that the full tech didn't made it into the game. And I always assumed that that demo used some of the unused tech since the behavior still differed a lot from the ingame behavior, but that might have been due to the extra spacing.

But then again, if PA is actually using the same algorithms as SupCom 2, why is it failing so badly then?
Could it have something to do with the map design? Most SupCom2 maps had some type of long, wide lanes and few wide cross sections, so there was always enough space to navigate proberly. While in PA you tend to have a lot of wide open spaces and if areas are divided, then it's usually by a bunch of bottlenecks, actual bottlenecks that is where the pathing breaks since unit are forced to collide with the obstacles. You didn't have any of such issues in SupCom 2 maps, unless of course inside your own base.
Then there is also the scale thing, units in PA are huge compared to default spacing in formations. May have helper the artists with their toy style, but surely didn't help the cause.

Ah, and yes, that Froblins demo was just what I was looking for. Interesting, they were using the full Continuum Crowds. And they managed to solve the potential function on the GPU rather efficient for a multiple goal scenario. Ok, latter one is not applicable to your cause, since your sparse structure is actually better suited for a classic priority queue bases algorithm, and I see why you can't do the full Continuum Crowd algorithm either, that thing really is nasty in the default version where it requires you to solve the vector field again every single step since units would otherwise collide with the discomfort zones they projected themselves. And they only used tiny grids, so they had to compute no more than 65k fields per frame in their biggest example while a rough estimation just for movement on the surface on a radius 800 planet with a 4 meter voxel grid already yields at least ten times that number.
Sorry, should have read the paper a lot earlier.

I would not say PA's pathfinding is failing badly. Units get from A to B, usually in a pretty efficient way.

Unless there is a crack in the way, or other brushes with concave bits. Seen AI commanders get stuck on those a lot.

PA is "worse" than SupCom2 because @Elitron had to rewrite all of it from scratch; SupCom2 took 3 years and started with an existing engine with all movement on a 2d plane. We didn't and the engine and the pathing system was developed in tandem. We actually threw out the entire vector field pathing system about 6 months ago after over a year working on the initial version and @Elitron started again. It started as 2d patch vector fields warped and wrapped across arbitrary geometry, which is what we showed off originally in the live streams. Since then it's been rewritten as a voxel vector field because some of the issues with the 2d patches simply couldn't be solved efficiently (edge aliasing, edges not lining up with adjacent patches, vector direction alignment across patches, etc.).

So now it's basically fresh code with not a lot of time to find bugs in and the steering system and formation system didn't get the same amount of love as it did in SupCom2. We'll continue to work on it and improve it, but I don't have any ETAs for when.


There's also some early movement behavioral stuff that needs some love. When a unit is given orders it starts to move almost immediately ... but it doesn't always know which way to go. Right now it just starts moving in the direction of the goal, even if there's a crack or a mountain in the way. On large planets if the goal is far enough away it might take a couple of updates on the sim before the flow field is finished generating (it starts at the goal and expands outward in the direction of the units that need it), so for quite a while (maybe half a second) it might seem like it's moving in the wrong direction before the voxel flow field reaches it and tells it to not drive into that giant canyon.

A common user behavior we don't handle well is clicking multiple times. Each time you give a unit an order it has to recalculate that flow field, and like I said it might take a while. If you have a unit selected (like a commander) and click multiple times over and over it might never finish building out the flow field all the way to the commander so it'll just keep walking straight at the goal, and thus straight at a wall. There's stuff in there to try to handle that, but it's not perfect.

Could that be what's happening with the AI? It gives a new order every few seconds (dat high APM...) and resets all the units back to dead-reckoning? I've mostly been watching AI games lately, so that's where I've been seeing the problems.

For AI it's a different issue.

For anyone interested in flow fields here is cool article and demo in JavaScript (inspired by PA):
http://coldconstructs.com/2013/10/flow-field-pathfinding-with-flocking/

PS: Live demo doesn't actually work, but code available on github.
...
Oops! Working link for demo:
http://coldconstructs.com/labs/flowfield/

Actually something I think you should consider- the way the pathing works with multiple clicks- i.e. 'dumb' is actually an advantage to my mind...

If I am microing a unit intensely at that level, I want that unit to do *exactly what it's told* and nothing else. If there are units gunning for my commander I need to make him hug a wall. If the automated pathfinding corrects my orders and makes him go the other direction I would not be impressed as it could cost me the game.

TL-DR this may actually be beneficial and wanted behavior. Personally I think the full on path generation is more useful for long orders- for micro type work most players want the unit to do what it's been told. The automated formations prove problematic when micro managing air units for example.