Comparision of Pathfinding 1k Units Planetary Annihilation vs Forged Alliance

Discussion in 'Planetary Annihilation General Discussion' started by warrenkc, November 3, 2014.

  1. warrenkc

    warrenkc Active Member

    Messages:
    542
    Likes Received:
    191
    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
  2. elodea

    elodea Post Master General

    Messages:
    1,696
    Likes Received:
    3,050
    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
    warrenkc likes this.
  3. datura2012

    datura2012 Member

    Messages:
    19
    Likes Received:
    48
    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..
    warrenkc likes this.
  4. exterminans

    exterminans Post Master General

    Messages:
    1,881
    Likes Received:
    986
    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.
    warrenkc likes this.
  5. GoogleFrog

    GoogleFrog Active Member

    Messages:
    676
    Likes Received:
    235
    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.
    stuart98, Quitch, pieman2906 and 5 others like this.
  6. tatsujb

    tatsujb Post Master General

    Messages:
    12,878
    Likes Received:
    5,374
    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!)
    Last edited: November 3, 2014
  7. Planktum

    Planktum Post Master General

    Messages:
    1,060
    Likes Received:
    510
    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.
    felipec likes this.
  8. davostheblack

    davostheblack Well-Known Member

    Messages:
    364
    Likes Received:
    313
    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
  9. bgolus

    bgolus Uber Alumni

    Messages:
    1,481
    Likes Received:
    2,298
    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.)
  10. Planktum

    Planktum Post Master General

    Messages:
    1,060
    Likes Received:
    510
    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.
  11. exterminans

    exterminans Post Master General

    Messages:
    1,881
    Likes Received:
    986
    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.
    Last edited: November 3, 2014
    tatsujb likes this.
  12. radongog

    radongog Well-Known Member

    Messages:
    638
    Likes Received:
    295
    Has just to evolve a little in naval sector...
    ...but in general I can simply underline it!
  13. wondible

    wondible Post Master General

    Messages:
    3,279
    Likes Received:
    2,084
    Secret volcano lair?

    Screen Shot 2014-11-03 at 13.38.59 .png
  14. tatsujb

    tatsujb Post Master General

    Messages:
    12,878
    Likes Received:
    5,374
    good point.
  15. bgolus

    bgolus Uber Alumni

    Messages:
    1,481
    Likes Received:
    2,298
    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).
    squishypon3 and wondible like this.
  16. tatsujb

    tatsujb Post Master General

    Messages:
    12,878
    Likes Received:
    5,374
    so wait units path per tick? every single tick?
  17. exterminans

    exterminans Post Master General

    Messages:
    1,881
    Likes Received:
    986
    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.
  18. tatsujb

    tatsujb Post Master General

    Messages:
    12,878
    Likes Received:
    5,374
    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?
  19. bgolus

    bgolus Uber Alumni

    Messages:
    1,481
    Likes Received:
    2,298
    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:
    warrenkc, wondible, Remy561 and 4 others like this.
  20. tatsujb

    tatsujb Post Master General

    Messages:
    12,878
    Likes Received:
    5,374
    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 :(

Share This Page