Comparision of Pathfinding 1k Units Planetary Annihilation vs Forged Alliance

This is from the latest versions available on Steam. 11/3/2014
See the video yourself. I realize that both games do suffer from problems with path-finding. However when dealing with 1 thousand units it is clear that PA is much more responsive and works better. In Forged Alliance, I really couldn't believe how long it took to actually have the units start moving. It was quite strange.
What are your thoughts?

Tested on i5 4590 Processor
16GB RAM
Win 7 64 bit
AMD 270x Video Card

I think what PA does is treat groups of units as one 'flock' instead of thousands of individual units. This allows much cheaper pathfinding. The drawback ofcourse is that some of the units in your flock will hit walls and obstacles and get stuck, or not really be very smart about it individually.

Someone more technical feel free to correct me if i am wrong

First of all: nice comparison!

The thing that bothers me in PA (and previously in SC2), is that when looking at a group of units 'flowing' around a corner or obstacle, many units just 'float' very unrealistically. It gives me a cheap feeling of floating 'images of tanks' instead of actual tanks. Maybe I just have to get used to this..

Wrong on multiple levels actually.

Flocking is used, but not for goal finding but for maintaining the formation. This is independent of the actual path vector field which dictates the the direction when moving towards a certain goal. Units can flock into formation even if not sharing the same goal as long as their movement vectors are not entirely incompatible.

The problem starts when these both systems collide, mostly when the flocking algorithm takes precedence over the pathing component so units will retain formation for too long even though the path field would have long dictated them to avoid the obstacle.

Another problem in PA: Formations are to DENSE by default. So if the formation is stressed by an inhomogeneous path field (which inevitably happens when there are any obstacles), the little cushion we have is used up rather soon so units start to collide - resulting in the collision physic system to take control of the units. And now you got units which no longer follow their predefined movement patterns but become mere toys to the physic.

Floating around corners sounds bad in theory but when it comes to playing a game I much prefer that my units reach their destination. For me a bit of suspension of realistic unit physics is fine here.

for starters this video is non-conclusive.

I can definitely personally say that pathfinding is 'better' in PA.

however : I for one would not have had the same result with this test and an even more different result with different maps.

Why?

one:
in FA how 'well' units pathfind is in direct correlation with your CPU clock. yes I'm serious. not even kidding. the more your cpu can dish out the less time units are stuck in the pathing queue (and this time can very rapidly near zero for the last unit in the queue as CPU speed increases).

two:
this video does not show each game's respective issues with pathing. Rather how good each one is at moving a large group of units. for example : PA pathfinding sucks when it comes to "pushing through an obstacle"... units act blind, it looks like they can't "see" obstacles, they don't anticipate, they butt up straight against them and hope to sort of slide to one side or another. often they end up staying in a sort of tangent where they can't make up their mind. (and generally this concerns a whole swarm of units at a time)

FA pathfinding sucks when it comes to having a lot of units. all units on the map (visible to you or not) are placed in the pathing queue ("pathing queue" with quotation marks, this queue also includes projectile simulation). your damn engineer that you want to move RIGHT NOW!111! to avoid a bomber's shell has a high probability to tell you to f**k off and wait, if there are thousands upon thousands of units on the map. Upside is units seem to "see", they anticipate obstacles but this upside is rigged, this "anticipation" is very often overdone: straight line broken in a more or less relative middle by a 120° angle to navigate a great big straight line down an obstacle-less route...... "complete opposite of what you would have done" and "honey pass me the damn wheel you're going the wrong way" scenarios. E.G. careful when sending an engineer down a path that is parallel to a field of tech one power gens. he might for some reason find it *teeth cringes*......"shorter" to dip into the gap of the first two, decide it wasn't such a good idea. try to turn around, bump three times, make it out finally, proceed on the original straight line, dip into the gap between the second and third pgen because, hey! evidently no lessons were learnt! and so on and so forth.....

three:
the map choices.
lava is PA's best path-finding strength don't ask me why. try to pull the same **** on metal or earth or desert.

isis is not FA's best path-finding strength map, don't ask me why. bigger maps seem to do it a bigger favour and setons seems to be it's favourite in that respect.

all in all I'd have to say, try both, make up your own mind.

me?

pff! heck if I know. I'm fed up with PA's and FA's pathfinding alike! (PA at least managed to have flowfield without the crazy SupCom 2 movement warps, but please please please no more slippy units, they have treads! make 'em feel like tanks!)

PA's pathfinding is pretty good actually. It could definitely be better, things can always improve, but I can't even imagine how technically difficult it would be to code this. Well done Uber, the latest pathing is a huge improvement over what it used to be.

PA manages to pathfind pretty damned well given it's functioning on a curved surface. The mathematics behind it can be tedious/mind-breaking in complexity, and then programming that must be a whole new battle of minds in itself

A fair comparison would be seeing PA pathfinding on a flat surface. Guaranteed improvements right there

I don't know that much about FA's pathfinding, but in PA groups of units are in some ways treated both as individuals and as groups. @Elitron has talked in the past about the flow fields we use, which one gets generated for each group of similarly classed units per order. Selecting 1000 units and giving all of them a move order usually results in a single flow field as an optimization. The easiest way to think about flow fields as a map of arrows pointing towards the optimal direction to travel to get to your destination, in our case only taking into account the terrain and static units (like buildings).

However each unit drives that flow field on their own and with their own steering, both in following the flow field and in avoiding other units. They make choices about how much they should follow the flow field, how much they should be steering to avoid other units, and if they should try to stay in formation with other units with the same order around it. All of these can be giving conflicting directions and it's been a lot of tweaking to get units to where they are now.

In that video you can see some situations where units are moving in a grid, then at the last minute will turn to avoid hitting a wall they're obviously driving towards where a single unit would likely turn sooner, and this can cause bunching up in weird places. This is them preferring their formation for longer than they should.
47 seconds in

Once they're not moving in formation the same thing can occur because of the unit collision avoidance steering will cause units to not follow the flow field if there's another unit in the way along with some units trying to push their way through causing units to get pushed into alcoves.
2:40 minutes in

If unit collision avoidance is too high and unit pushing is to low you can get problems with units just spinning in circles because they're trying to keep a distance between them and another unit which may not be possible.

If flow field adherence is too high you can get problems with units just walking straight into another unit or group of units blindly and getting stuck.

If formation adherence is too low units will never move in formation and will always bunch up making them easier targets. (Being able to explicitly tell units to follow the formation or not was always intended, but never made it in.)

Current pathfinding is pretty awesome. With a few more tweaks I have faith that you guys will make it Uber awesome! Keep up the good work.

And how about at least making the cohesion part of the flocking optional, please? Don't mind about the collision avoidance, that one is fine and makes perfect sense to me.

But why on earth are units trying to stay TOGETHER when they should have clearly split? It almost looks like ... you have not used the same weights for collision avoidance and cohesion, did you? Because that would explain how you got these perfect rectangular formations. And why these formations are so difficult to break.

PS: And I assume you have never tried to make the target distance for collision avoidance dependent on current movement speed? Open field = high speed = huge gaps, bottleneck = low speed = low gaps. Using the same forces in relation to distance as with top speed, but only applying it if distance is below a speed dependent threshold.

Has just to evolve a little in naval sector...
...but in general I can simply underline it!

Secret volcano lair?

good point.

I don't actually know how the collision avoidance is handled. I know collision avoidance using a look ahead based on speed (and turn rate) were being looked at but I don't know if the one that exists in the engine right now is any more advanced than a fixed distance look up and radius. There's a lot of papers on the topic as it's a harder problem than it seems; two units walking towards each other can easily pick the same direction to turn, resulting in them still on a collision course for the next tick, turning again, etc. eventually causing them to just walk side by side and never reach their destination.

Some of the original flow field crowd movement papers were actually written to solve this, but updating a flow field for hundreds of units that includes all of those units isn't viable for game level real time (only academic "real time" which is a very different time scale).

so wait units path per tick? every single tick?

Yes, even though it's actually quite cheap. They perform a lookup in the vector field at their current position, sample for possibly colliding entities and adjust their target movement vector and speed to the result of the computation.

Problem is mostly that they are unaware of bottlenecks and backlogs. That's like running into the end of a traffic jam and not adjusting your driving style. E.g. trying to maintain you default distance at any cost, even if this means to actually waste flow capacity on bottlenecks. To continue with this analogy: Units are rather crashing into obstacles aside the road when slowing down than to make use of the safety margin.

The problem @bgolus described isn't that difficult either. There are quite a lot of cheap algorithms to solve that problem, and all the require is to exchange the normalized movement vectors as they were read from the flow field by each individual unit if a collision ins imminent. Calculate the cross product, check in which quadrants the units are in relation to each other, and you know who has to slow down in order to create a gap.

PS: And please stop calling it "flow fields". Yes, there are many papers on this topic. And some of them used the wrong names too. And some actually used flow fields, but PA doesn't, that's for sure. The pathing system of PA does not measure the flow, and it's not using it either to modify the cost when searching a path. The vector field PA is using only expresses shortest path to the goal, but not any flow. If it did, you wouldn't have the problem of two squads trying to move through the same bottleneck at the same time and stopping each other dead.

wtf. I can totally see things being much better if they pathed over longer distances. and time.

is that the whole concept of flowfield? just pathing every second annnnnnnd VOILA no more climping or bumping?

Our system is not quite just shortest path; the vector fields take into account cost in various forms, just not the cost of other units in motion. The computational cost of taking into account every unit is just too great. So in that regard you are correct that they are not "flow fields", especially in the fluid dynamics definition, but they are vector fields that define movement flow so "flow fields" is still an accurate layman description.

Supreme Commander 2 talked about continuum crowds as being the basis for their pathfinding, and even did a promo video talking about it, which is much more like real flow fields. (Humorously the press release refers to it as "crown continuum".)


And here's the original paper's video:

At one point he refers to being able to compute the simulation at "5 frames per second!" This is that academic "real time" vs video game "real time" I elluded to in my earlier post.

But really SupCom2 just does the same thing PA does, which was more accurately described by another person as "Goal-Based Vector Field Pathfinding", along with collision avoidance steering and unit pushing.

Here's a simpler implementation:

I'm getting the feel that the most efficient pathfinding may not be the most fun. E.G. not the most adapted for video games.

but heck I've always been alone in thinking FA's pathfinding had a better overall global feel than PA's