RVONavmesh equivalent for GridGraph (updated : code inside)

I plan to use a GridGraph and Local Avoidance for my project.
What about the future support of a RVONavmesh equivalent for grid graphs ? any roadmap ?

If this feature is not officially planned soon, are there already some unofficial implementations ? even if not fully functional.

I would be happy to read some advice on this subject. I am currently looking in-deep RVONavmesh and RVOObstacle and plan to compute the Nodes of a GridGraph to generate RVOObstacle based on unwalkable Nodes.

Side note : can RVOObstacle be concave or must they be convex ?

1 Like

After some testing, I know that RVOObstacle can be concave.
If I understand well, in fact, for the avoidance computations, they are internally managed like a set of individual lines with a direction. Concave or convex have no importance.

What I plan to implement is something like in this sketch :
sketch
The blue lines are the walkable grid, the red dots are unwalkable nodes and the green lines are the RVOObstacle.

To produce automatically these RVOObstacle I need to analyze the GridGraph with a sort of edge detection algorithm.

Am I wrong ? Has somebody already worked on this subject ?

For isolated nodes, and for circular obstacle in general, is there a circular RVOObstacle or maybe a static RVO agent with a radius ?

I’ve made some progress, here are some WIP screenshots :

Here are some sketches of the algorithm I have currently implemented :

I take each node of the GridGraph one by one, and I test its walkability against 3 of its neighbors. I compute 2 cases (red dots are unwalkable nodes, green are walkable).

Then, I apply the same pattern 3 more times but with 90 degrees rotation.

Finally, I’ve tested 8 possibilities per node.

This solution produce 2590 RVOObstacle for a slightly modified Example2_Terrain scene (341 for the navmesh based Example11_RVO scene).

My actual RVOGridGraph.AddGraphObstacles() method is only 100 lines long. I don’t know if merging lines of RVOObstacle is worth the effort. This node based approach let me think it could be compatible with partial Graph update…

Below is my actual source code (RVOGridGraph.cs) if somebody want to try it (need A* Pro). If you own A* PRO, feel free to use and enhance it :wink:

It can be used the same way as RVONavmesh (see Example11_RVO) but for a GridGraph. I have personally tested it on the terrain demo (Example2_Terrain) with success and without a big drop of the FPS.

@ Aron Granberg : if posting here some code derived from the A* Pro is a problem, just tell me and I’ll remove it.

`
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using Pathfinding;
using Pathfinding.RVO;

/** Adds a GridGraph as RVO obstacles.

  • Add this to a scene in which has a GridGrah based graph, when scanning (or loading from cache) the graph

  • it will be added as RVO obstacles to the RVOSimulator (which must exist in the scene).

  • \astarpro
    /
    [AddComponentMenu(“Local Avoidance/RVOGridGraph”)]
    public class RVOGridGraph : GraphModifier
    {
    /
    * Height of the walls added for each obstacle edge.

    • If a graph contains overlapping you should set this low enough so
    • that edges on different levels do not interfere, but high enough so that
    • agents cannot move over them by mistake.
      */
      public float wallHeight = 5;

    /** Obstacles currently added to the simulator */
    private List obstacles = new List();

    /** Last simulator used */
    private Simulator lastSim = null;

    public override void OnPostCacheLoad()
    {
    OnLatePostScan();
    }

    public override void OnLatePostScan()
    {
    if (!Application.isPlaying)
    return;

     RemoveObstacles();
    
     NavGraph[] graphs = AstarPath.active.graphs;
    
     RVOSimulator rvosim = FindObjectOfType(typeof(RVOSimulator)) as RVOSimulator;
     if (rvosim == null)
         throw new System.NullReferenceException("No RVOSimulator could be found in the scene. Please add one to any GameObject");
    
     Pathfinding.RVO.Simulator sim = rvosim.GetSimulator();
    
     for (int i = 0; i < graphs.Length; i++)
     {
         AddGraphObstacles(sim, graphs[i]);
     }
    
     sim.UpdateObstacles();
    

    }

    /** Removes obstacles which were added with AddGraphObstacles */
    public void RemoveObstacles()
    {
    if (lastSim == null)
    return;

     Pathfinding.RVO.Simulator sim = lastSim;
     lastSim = null;
    
     for (int i = 0; i < obstacles.Count; i++)
         sim.RemoveObstacle(obstacles[i]);
    
     obstacles.Clear();
    

    }

    /** Adds RVO obstacles for a Grid Graph */
    public void AddGraphObstacles(Pathfinding.RVO.Simulator sim, NavGraph graph)
    {
    if (obstacles.Count > 0 && lastSim != null && lastSim != sim)
    {
    Debug.LogError(“Simulator has changed but some old obstacles are still added for the previous simulator. Deleting previous obstacles.”);
    RemoveObstacles();
    }

     //Remember which simulator these obstacles were added to
     lastSim = sim;
    
     GridGraph gg = graph as GridGraph;
    
     if (gg == null)
     {
         return;
     }
    
     Node[] nodes = graph.nodes;
    
     for (int w = 0; w < gg.width; w++)
     {
         for (int d = 0; d < gg.depth; d++)
         {
             int iA = d * gg.width + w;
             if (nodes[iA].walkable == false)
             {
                 /*
                  * Quarters order ("A" is the tested node) :
                  *  3 | 4
                  *  --A--B
                  *  2 | 1
                  *    C  D
                  */
    
                 // Quarter 1
                 if ((w < (gg.width - 1)) && (d > 0))
                 {
                     ComputeQuarter(sim, gg, w, d, 1, 0, 0, -1, 1, -1);
                 }
    
                 // Quarter 2
                 if ((w > 0) && (d > 0))
                 {
                     ComputeQuarter(sim, gg, w, d, 0, -1, -1, 0, -1, -1);
                 }
    
                 // Quarter 3
                 if ((w > 0) && (d < (gg.depth - 1)))
                 {
                     ComputeQuarter(sim, gg, w, d, -1, 0, 0, 1, -1, 1);
                 }
    
                 // Quarter 4
                 if ((w < (gg.width - 1)) && (d < (gg.depth - 1)))
                 {
                     ComputeQuarter(sim, gg, w, d, 0, 1, 1, 0, 1, 1);
                 }
             }
         }
     }
     Debug.Log(string.Format("RVOGridGraph.AddGraphObstacles() : {0}  obstacles", obstacles.Count));
    

    }

    /** Compute a quarter of 4 nodes (A, B, C, D) where A is unwalkable and add AB or AD ObstacleVertex if needed */
    private void ComputeQuarter(Pathfinding.RVO.Simulator sim, GridGraph gg, int w, int d, int wB, int dB, int wC, int dC, int wD, int dD)
    {
    Node[] nodes = gg.nodes;

     int iA = (d + 0) * gg.width + w + 0;
     int iB = (d + dB) * gg.width + w + wB;
     int iC = (d + dC) * gg.width + w + wC;
     int iD = (d + dD) * gg.width + w + wD;
    
     bool nodeB = nodes[iB].walkable;
     bool nodeC = nodes[iC].walkable;
     bool nodeD = nodes[iD].walkable;
    
     if ((nodeB == false) && (nodeC == true) && (nodeD == true))
     {
         obstacles.Add(sim.AddObstacle((Vector3)nodes[iA].position, (Vector3)nodes[iB].position, wallHeight));
     }
    
     if ((nodeB == false) && (nodeC == true) && (nodeD == false))
     {
         obstacles.Add(sim.AddObstacle((Vector3)nodes[iA].position, (Vector3)nodes[iD].position, wallHeight));
     }
    

    }

    /** Draws Gizmos */
    public void OnDrawGizmos()
    {
    OnDrawGizmos(false);
    }

    /** Draws Gizmos */
    public void OnDrawGizmosSelected()
    {
    OnDrawGizmos(true);
    }

    /** Draws Gizmos */
    public void OnDrawGizmos(bool selected)
    {
    Gizmos.color = new Color(0.615f, 1, 0.06f, selected ? 1.0f : 0.7f);

     foreach (ObstacleVertex ov in obstacles)
     {
         if (ov.next == null)
             throw new System.InvalidOperationException("RVOGridGraph.OnDrawGizmos() : obstacles[...].next == null");
    
         Vector3 a = ov.position;
         Vector3 b = ov.next.position;
    
         Gizmos.DrawLine(a, b);
    
         if (selected)
         {
             // Draw the little arrow to show the direction of the obstacle
             Vector3 avg = (a + b) * 0.5f;
             Vector3 tang = (b - a).normalized;
             if (tang != Vector3.zero)
             {
                 Vector3 normal = Vector3.Cross(Vector3.up, tang);
    
                 Gizmos.DrawLine(avg, avg + normal);
                 Gizmos.DrawLine(avg + normal, avg + normal * 0.5f + tang * 0.5f);
                 Gizmos.DrawLine(avg + normal, avg + normal * 0.5f - tang * 0.5f);
             }
         }
     }
    

    }
    }
    `