Looking for more info on seekers avoiding seekers in GridGraph, no RVO

Hello, this question was previously addressed here, but without much detail.

I’m in the early stages of development but my game involves having maybe a dozen seekers walking around a somewhat small area doing tasks, and they keep running into each other and getting stuck.

In the previous thread, Aron made two suggestions.

1:

… use a graph update to mark the node under the players with their own unique tag (e.g tag 1 for player 1, tag 2 for player 2 etc., I’m assuming here that you have less than 31 players) and then set each Seeker’s allowed tags to be only the default tag and their own tag.

2:

You can alternatively allow all tags, but have a really high penalty for moving into other players. This might be preferable because usually the other player has moved when the player gets to the position the other player had when the path was calculated.

The second solution seems preferable, and I thought I might implement it like this:

// _guo and _bounds are properties in this class, which is attached to the same gameObject as the seeker
void FixedUpdate () {
  if (isMoving && !_bounds.Contains(transform.position)) {
    // reset penalty on previous GUO
    if (_guo != null) {
      _guo.addPenalty = -10000;
      AstarPath.active.UpdateGraphs(_guo);
      _guo = null;
    }
    // set penalty on new GUO
    _bounds = GetComponent<Collider>().bounds;
    _guo = new GraphUpdateObject(_bounds);
    _guo.addPenalty = 10000;
    _guo.updatePhysics = false;
    AstarPath.active.UpdateGraphs(_guo);
  }
}

But it doesn’t work. I set A* Inspector -> Settings -> Debug Mode to “Penalty” and adjusted the gradient max value to be 10000, and all the nodes in the path still stay green. Any ideas? Thanks very much for your help!

EDIT: I updated some of the above a few times after spending more time working on this. Getting closer but still stuck!

Bumping this in the hope someone can help? Btw I’m using the pro version.

Hi

There is no out of the box solution for this yet, however there are some improvements on the tooling to get there.
Take a look at this tutorial: https://arongranberg.com/astar/docs/turnbased.php
It presents some tools to make it possible to reserve nodes using a simple API and create path requests that respects different rules for which other agents should be avoided.
This is mostly useful for static agents or turn based games however you should be able to use the ITraversalProvider interface to get a more stable and faster penalty based system for agents compared to using GraphUpdateObjects.
Full cooperative pathfinding is something I have experimented with (see https://arongranberg.com/2015/06/cooperative-pathfinding-experiments/) but this is not something that has been included in the package yet.

Also, as a general note. When you are constructing the bounding boxes, make sure that those bounding boxes actually contain some nodes (including on the Y axis) as otherwise they will not be updated.

Hey, so after taking a closer look at your turn based tutorial, I experimented a bit with using BlockManager and SingleNodeBlocker to try to understand better.

  • I added a BlockManager component to an empty GameObject
  • I added a SingleNodeBlocker component to each of my units, and set the BlockManager to the BlockManager object I created. In addition to the SingleNodeBlocker, the units also have the Seeker and AIPath components. They also have my custom Unit component attached, referenced in my posts above, which now looks like this:
public class Unit : MonoBehaviour {
  
  public bool isMoving = false;
  private Bounds _bounds;
  private SingleNodeBlocker _blocker;

  void Start () {
    _blocker = GetComponent<SingleNodeBlocker>();
  }

  void FixedUpdate () {
    if (isMoving && !_bounds.Contains(transform.position)) {
      _blocker.Unblock();
      _blocker.BlockAtCurrentPosition();
      _bounds = GetComponent<Collider>().bounds;
    }
}
  • In AIPath.cs, I added some parts of BlockerPathTest.cs from your example:
public class AIPath : AIBase {
  // ......
  public BlockManager blockManager;
  public List<SingleNodeBlocker> obstacles;
  BlockManager.TraversalProvider traversalProvider;
  // .....
  protected virtual void Start () {
    startHasRun = true;
    traversalProvider = new BlockManager.TraversalProvider(blockManager, BlockManager.BlockMode.OnlySelector, obstacles);
    Init();
  }
  // .....
  public virtual void SearchPath () {
    if (target == null) throw new System.InvalidOperationException("Target is null");
    lastRepath = Time.time;
    Vector3 targetPosition = target.position;
    canSearchAgain = false;

    // ADDED FROM BlockerPathTest.cs
    ABPath p = ABPath.Construct(GetFeetPosition(), targetPosition, null);
    // Make the path use a specific traversal provider
    p.traversalProvider = traversalProvider;
    // Calculate the path synchronously
    seeker.StartPath(p, OnPathComplete);
  }
}
// .....
  • I’m testing with five units, for each unit added the other four to the obstacles list.

Update: This seems to work OK, but I’m not sure if I’m doing it correctly and could use some feedback about this implementation and how it could be improved. Can you tell me what I’m getting right and wrong, and how using ITraversalProvider will help? Specifics and/or code examples would be very much appreciated! Thank you!

Could really use a little more help here, thanks again! I’ve update my last comment with some improvements, but still need some advice and feedback.

Hi

Sorry for the late answer.
The reason it is late is because I’ve been trying to get my cooperative pathfinding code to work again and improve it.
What you are attempting here is essentially cooperative pathfinding, but planning as if all other agents are stationary, which they in pretty much all cases are not. It may work decent if the agents are not very close together, but there will be many cases which it will not be able to handle well at all.
I will be trying to get it to work reasonably well and get back to your.

1 Like

Thanks so much, Aron! Much appreciated. Let me know how it goes, or if there’s anything I can do to help.