Looking for Pathfinding with special requirement

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.

 

Check out the pathfinding videos from 3.5 might do what you need, its just not out yet

 

I think this is more of a "flocking" kind of problem then a pathfinding kind of problem. See this

 

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.

 

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.

 

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.

 

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.

 

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

 

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.

 

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.

 

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

 

I think what you meant is flanking, is it?

 

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".

 

I made some test versions from that "collaborative diffusion" also:
http://unitycoder.com/blog/2011/12/29/hill-climbing-ai-unity3d/ (2 webplayer demos)

Its not finished yet, but its quite interesting..
Nice to have the mobs "automagically" using different routes towards the target.

 

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.