Search Unity

Looking for Pathfinding with special requirement

Discussion in 'General Discussion' started by Ricks, Nov 20, 2011.

  1. Ricks

    Ricks

    Joined:
    Jun 17, 2010
    Posts:
    647
    Hello all,
    I wanted to ask if a pathfinding solution for Unity exists (commercial or non-commercial) which is able to do the following (see picture attached):

    The red blobs are the enemies and the green blob is the player. Now what I experienced mostly is that the pathfinding will result in (A). The expected solution however is (B).

    In (A) only the first 1-3 enemies in the first row will get close enough to the target, while the remaining ones try to find their path through the ones standing in front of them - which will result in jittering if they aren't stopped. This is possible, however I am not satisfied with the overall behavior. I thought that the remaining enemies try to surround the enemy as long as there is enough room around target - which definitely is.
     

    Attached Files:

  2. larvantholos

    larvantholos

    Joined:
    Oct 29, 2009
    Posts:
    668
    Check out the pathfinding videos from 3.5 might do what you need, its just not out yet ;)
     
  3. recon

    recon

    Joined:
    Nov 28, 2009
    Posts:
    119
    I think this is more of a "flocking" kind of problem then a pathfinding kind of problem. See this
     
  4. Ricks

    Ricks

    Joined:
    Jun 17, 2010
    Posts:
    647
    I used Aron Granbergs (only version 2.9 though). I didn't try out his latest version although (if I recall correctly) Aron mentioned something like an option to "update grid /calculate new path in runtime, despite dynamic objects".
    I didn't try out "SimplePath" yet, but I'm afraid it'll result in the same. That said all these solutions are great, maybe it's just I expect too much intelligence from the pathfinding and I need to make a custom workaround to achieve this behavior. I don't know... that's why I'm asking.
     
  5. niosop2

    niosop2

    Joined:
    Jul 23, 2009
    Posts:
    1,059
    There are actually 2 problems. First, you are having every enemy trying to get to the same spot. Instead you should have them trying to get to spots surrounding the target. Some sort of system that generates points around the target and allows an enemy to reserve a spot for them would probably be required. Second is how the enemies actually get to those spots. For this, some sort of steering system would be required so they don't just try and push their way through.
     
  6. Ricks

    Ricks

    Joined:
    Jun 17, 2010
    Posts:
    647
    Yeah, hmmm the thing with the spots around the target got quite complicated (I actually tried that some weeks ago, but the assignment of enemies->spots got messed up after a while. Guess I'll need to give it a second try. Also probably checking if the enemy slowed down (=stuck) and then calculate a new path including the necessity to evade dynamic objects. Sounds... costly in performance. I wonder how old Games like Age of Empires II achieved such magnificent and performant steering/AI behavior with hundreds or thousands of units.
     
  7. recon

    recon

    Joined:
    Nov 28, 2009
    Posts:
    119
    Well, this is a pretty good explanation from the man who actually coded the AI in aoe2 it so that should help you out a bit :)

    Im even more amazed by the steering / flocking in starcraft 2 though.
     
  8. gustavolsson

    gustavolsson

    Joined:
    Jan 14, 2011
    Posts:
    315
    Check out collaborative diffusion. It is an extremely cool and simple (pathfinding) algorithm for situations where several actors need to cooperate in order to reach a common goal.

    Oddly enough, the algorithm seems to be relatively unknown, even though it was used in the Sims series if I remember correctly :)
     
    Last edited: Nov 21, 2011
  9. TehWut

    TehWut

    Joined:
    Jun 18, 2011
    Posts:
    1,577
    Aron is working on a local avoidance system that does exactly this
    http://www.arongranberg.com/

    It tries to move to a point, while avoiding fellow objects that are also moving, without pushing or much issue. It's actually looking really good, I would check out the link. this "local avoidance" is supposed to be included sometime in the package.
     
  10. Ricks

    Ricks

    Joined:
    Jun 17, 2010
    Posts:
    647
    Thanks a lot, very interesting read from Gamasutra! Though it's more likely I'll go with Aron's solution (for it's proven to work on terrain, different layers, within buildings etc.) once the local avoidance is implemented. Looks really awesome and might do just what I need.
     
  11. Ricks

    Ricks

    Joined:
    Jun 17, 2010
    Posts:
    647
    If anyone's interested, I eventually got it to work with Aron's package by using pure pathfinding and no steering behavior at all. It needed some tweaks in AIFollow.cs and in DynamicObstacleScript, also I did a full rescan of the pathgrid each 0.3 sec. The result is by no means perfect and the performance suffers a lot... but still nice to see that the characters do not pile up anymore. Though definitely not possible to use in any RTS games or wide open areas :)

    Leftclick = set target object

    http://dl.dropbox.com/u/53390051/WebPlayer/WebPlayer.html
     
  12. AnomalusUndrdog

    AnomalusUndrdog

    Joined:
    Jul 3, 2009
    Posts:
    1,494
    I think what you meant is flanking, is it?
     
  13. AnomalusUndrdog

    AnomalusUndrdog

    Joined:
    Jul 3, 2009
    Posts:
    1,494
    I tried implementing the concept described in that collaborative diffusion page, and here's how it turned out:

    http://dl.dropbox.com/u/25260770/PathfindingTest/WebPlayer.html

    Its the same controls with what marctro did. Left-click to set the destination.

    I'm pretty sure some of my code is a bit naive. Its only in certain situations that the agents will exhibit flanking behaviour. Some agents end up stuck, and I don't like the bee-like zig-zag movement they make.

    Also I think it would be better to couple this with typical A*, such that, the path created by the A*, the area of the influence map that that path takes up, will be set to zero influence. Its as if the agent will be saying "to my allies, this is the path I'll take, don't cross it, its mine only".
     
  14. mgear

    mgear

    Joined:
    Aug 3, 2010
    Posts:
    5,853
  15. hippocoder

    hippocoder

    Digital Ape Moderator

    Joined:
    Apr 11, 2010
    Posts:
    26,177
    The unity 3.5 system should do this by default, providing there is a navmeshagent on the player, they'll figure it out that to be closer, they need to surround you. However, if they don't, just specify positions in a circle around the player. Typical A* is more than capable of this with decent grid granularity.
     
unityunity