A* Pathfinding Project

Avoidance, but not local


#1

Hi all,
Hi Aron,

I’m trying to make my characters avoid each other and the local avoidance does not suit me, I talk about 10 characters aiming to different points around a moving target.

I’d better see them disabling the nodes they are on while moving, like that the calculated paths take in account these obstacles from the start.

But if I do that the paths go crazy because the start nodes are disabled.

I am pretty sure I don’t see the thing like I should, is there a way to solve that?

Maybe I could add some penalty to the nodes the characters are standing on but how can I restore them once they are empty?

Cheers


#2

Hi

To solve this well you have to use something called Cooperative Pathfinding.
I have done some experiments with this some time ago (see https://arongranberg.com/2015/06/cooperative-pathfinding-experiments/) but so far nothing is included in the package.

There are some examples of much simpler approaches intended for turn based games shown on this page: https://arongranberg.com/astar/docs/turnbased.html. They might work for you.

There’s also an old beta of the cooperative pathfinding available here https://www.arongranberg.com/astar/download if you click on ‘Show Older Versions’ and choose the one labeled ‘cooperative’.


#3

Thank you Aron,

Right now I am in holidays but I will be able to try it next week.

You take care


#4

Hi @aron_granberg ,

So I was able to play with it the last days and it does not suit me.

I need kind of an aura where other characters can’t go but still allows me to calaculate a path.

I tried with tags but when one of my character moves it replaces others characters node tags.

What I would love would be a function calculating the path with a start point, an end point and a list of nodes to avoid.

Do you have that in stock?


#5

Hey,

The way I have this implemented is using the ITraversalProvider

Just like the example for the turnbased path checking I have an array of blocked nodes.

The Agent group manager ranks the agents based on distance to the player, and allows the closest one to calculate it’s path first. ( I used BlockUntilCalculated to make sure others don’t calculate their path yet before this one finishes ). Once it’s path has been calculated I add a the current position and a few nodes infront to the blocked list. Then proceed to the next agent.

The ITraversable will block the path finding for other agents on those nodes.

You might still have to alter the GetNearest function to find a new target destination in case an agent is trying to use a blocked node as a destination.
For this you’ll have to work with the NNConstraint You’ll have to make some tweaks to feed the data from the ITraversableProvider into the NNConstraint but it gives great results in tight situations.

Below you can find a screenshot of my implementation. The thin vertical line is the result destination, even though both were fed the position of the capsule.

You can also expand your avoidance nodes based on the size of the agents for example:

This solution is definitely not the best one, you loose a lot of the multi threading performance etc. But you could manually offset path calculations per agent etc. This solution definitely worked for us.

If you have further questions feel free to reach out.
-Wolf


#6

Here is a picture of the actual system in working.
You can see that the furthest agent deviates it’s path to avoid the other agent.

If you want to take this system even further you could look into influence maps:

But that can fundamentally change movement behaviour of agents. I hope to be able to fully implement this myself.


#7

Hey Wolf,

Thank you so much for taking the time to make such a complete answer :star_struck: :star_struck: :star_struck:

I tried the ItraversalProvider and did not succed, and did not see how I could reach what I want exactly.

But thanks to your explanation I have a new plan in head using it that might work.

So thank you, really, I hope I will be able to give you back the help you just sent me.

You take care


#8

Glad it was somewhat of help,

If you want I can share some code snippets of how it works on my end.
Though it has been a while since I’ve implemented this, so I’d have to look into the details and make sure I don’t leave out any important steps :slight_smile:

Good luck!