# 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 :

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

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
/
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;

{
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++)
{
}

sim.UpdateObstacles();
``````

}

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);
}
}
}
}
``````

}

/** 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))
{
}

if ((nodeB == false) && (nodeC == true) && (nodeD == false))
{
}
``````

}

/** 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);
}
}
}
``````

}
}
`