RVO Controller Removal with Double Buffering

Hi!

Need some help… Working on a VR title where frame-rate is really important. I purchased this asset and its fantastic. We only have one issue with RVO.

We need to use Double buffering and multi-threading as its running on PS4 and needs to have minimal impact (without it, it consumes 10ms on a busy level). However when we register or de-register and agent BlockUntilSimulationStepIsDone() is performed, causing the main game thread to stop for a while. This is a problem for us… I understand why its performed, however we use pooling. So is it not possible to move the agent off the game map, wait for when it can be removed safely, then remove it at the right time so as to not upset the simulation (without hanging the main thread). Is this possible? Any ideas how we would do it? I am not good with threading, and don’t want to screw this up :slight_smile:

Infact, maybe we can just replace BlockUntilSimulationStepIsDone() with some kind of Ienumerator that does not block (yield loop until threads are done), then allows the agent to be removed when the threads are done? Any ideas?

Many thanks

Mark

Hi

Yes what could be done is to change the block call to just add it to a list and then at the next simulation step you would go through the list and actually remove those agents from the simulation… Actually I should probably make that change in the official version. Alternatively you can as you say just move the agent to somewhere far away (don’t put them all at the same spot though because then that place will become crowded and cost a lot of CPU time).

I can add them to a list, good idea. Where would I put the code to iterate through the list to Add or Remove agents?

Right before it starts the next simulation tick. In the Update method.

Got it. Going to play with it this evening, will let you know.

Out of curiosity… If an RVO agent has not been added yet (as its waiting in the list) what happens when an Aipath agent calls it for a movement delta? Will it just return a blank delta, or cause issues with movement?

Thanks for responding so fast!

Mark

I think it should return a zero movement delta.

Hmm, not having much luck I am afraid. Starting with the task of just removing Agents and Obstacles (will try adding later).

In RemoveAgent() I added:

   AgentsToRemove.Add(agentReal);

And removed the block and the line to set the simulator to null.

Then in Update I have:

            if (Multithreading) {
				// Make sure the threads have completed their tasks
				// Otherwise block until they have
				if (doubleBuffering) {
					for (int i = 0; i < workers.Length; i++) workers[i].WaitOne();
					for (int i = 0; i < agents.Count; i++) agents[i].PostCalculation();
				}

                //Now update the lists
                for (int i = 0; i < AgentsToRemove.Count; i++)
                {
                    AgentsToRemove[i].simulator = null;
                }

                AgentsToRemove.Clear();

But it seems to cause issues…

System.NullReferenceException: Object reference not set to an instance of an object
at Pathfinding.RVO.Sampled.Agent.CalculateNeighbours () [0x0002e] in D:\Projects\Korix\Assets\AstarPathfindingProject\Core\RVO\RVOAgent.cs:249
at Pathfinding.RVO.Simulator+Worker.Run () [0x00034] in D:\Projects\Korix\Assets\AstarPathfindingProject\Core\RVO\RVOCoreSimulator.cs:796
UnityEngine.Debug:LogError(Object)
Pathfinding.RVO.Worker:Run() (at Assets/AstarPathfindingProject/Core/RVO/RVOCoreSimulator.cs:810)

Am I doing it in the right place?

Sorry, Missed the list removal. I am an idiot. Seems to work :slight_smile:

1 Like

HI! So its ALMOST working… Can you help?

On occasion, it crashes (Triggered by the RVO update the workers get into an infinate loop of some kind and hang the app). This is what I have done:

  1. Adding an agent like so:

public IAgent AddAgent (IAgent agent) {
if (AgentsToRemove.Contains(agentReal))
{
AgentsToRemove.Remove(agentReal);
}
AgentsToAdd.Add(agentReal);
return agent;

  1. Removing an agent like so:

public void RemoveAgent (IAgent agent) {
if (AgentsToAdd.Contains(agentReal))
{
AgentsToAdd.Remove(agentReal);
}
AgentsToRemove.Add(agentReal);
}

  1. I do the same with adding or removing Obsticles.

  2. Then in the update, in the Multithreading Double Buffering section:

    if (Multithreading) {
                 // Make sure the threads have completed their tasks
                 // Otherwise block until they have
         
     			if (doubleBuffering) {
     				for (int i = 0; i < workers.Length; i++) workers[i].WaitOne();
                     for (int i = 0; i < agents.Count; i++) agents[i].PostCalculation();
     			}
    
                 //Now update the lists
    
                 for (int i = 0; i < AgentsToAdd.Count; i++)
                 {
                     agents.Add(AgentsToAdd[i]);
                     AgentsToAdd[i].simulator = this;
                 }
    
                 AgentsToAdd.Clear();
    
                 for (int i = 0; i < AgentsToRemove.Count; i++)
                 {
                     AgentsToRemove[i].simulator = null;
                     agents.Remove(AgentsToRemove[i]);
                 }
    
                 AgentsToRemove.Clear();
    
                 for (int i = 0; i < ObsticlesToAdd.Count; i++)
                 {
                     obstacles.Add(ObsticlesToAdd[i]);
    
                 }
    
                 ObsticlesToAdd.Clear();
    
                 for (int i = 0; i < ObsticlesToRemove.Count; i++)
                 {
                     obstacles.Remove(ObsticlesToRemove[i]);
    
                 }
    
                 ObsticlesToRemove.Clear();
    
                 for (int i = 0; i < ObsticlesToUpdateV.Count; i++)
                 {
    
                     int count = 0;
                     bool identity = ObsticlesToUpdateM[i] == Matrix4x4.identity;
                     var c = ObsticlesToUpdateV[i];
                     do
                     {
                         if (count >= ObsticlesToUpdateV3[i].Length)
                         {
                             Debug.DrawLine(c.prev.position, c.position, Color.red);
                             throw new System.ArgumentException("Obstacle has more vertices than supplied for updating (" + ObsticlesToUpdateV3[i].Length + " supplied)");
                         }
    
                         // Premature optimization ftw!
                         c.position = identity ? ObsticlesToUpdateV3[i][count] : ObsticlesToUpdateM[i].MultiplyPoint3x4(ObsticlesToUpdateV3[i][count]);
                         c = c.next;
                         count++;
                     } while (c != ObsticlesToUpdateV[i] && c != null);
    
                     c = ObsticlesToUpdateV[i];
                     do
                     {
                         if (c.next == null)
                         {
                             c.dir = Vector2.zero;
                         }
                         else {
                             Vector3 dir = c.next.position - c.position;
                             c.dir = new Vector2(dir.x, dir.z).normalized;
                         }
    
                         c = c.next;
                     } while (c != ObsticlesToUpdateV[i] && c != null);
    
                     ScheduleCleanObstacles();
                 }
    
                 ScheduleCleanObstacles();
    
                 ObsticlesToUpdateM.Clear();
                 ObsticlesToUpdateV.Clear();
                 ObsticlesToUpdateV3.Clear();
                 UpdateObstacles();
                 PreCalculation();
         CleanAndUpdateObstaclesIfNecessary();
         BuildQuadtree();
    
                 for (int i = 0; i < workers.Length; i++) {
     				workers[i].start = i*agents.Count / workers.Length;
     				workers[i].end = (i+1)*agents.Count / workers.Length;
     			}
    
                 // BufferSwitch
                 for (int i = 0; i < workers.Length; i++) workers[i].Execute(1);
     			for (int i = 0; i < workers.Length; i++) workers[i].WaitOne();
    
    
                 // Calculate New Velocity
                 for (int i = 0; i < workers.Length; i++) workers[i].Execute(0);
    
     			// Make sure the threads have completed their tasks
     			// Otherwise block until they have
     			if (!doubleBuffering) {
     				for (int i = 0; i < workers.Length; i++) workers[i].WaitOne();
     				for (int i = 0; i < agents.Count; i++) agents[i].PostCalculation();
     			}
          
     		} 
    

I just saw it crash when an enemy died and was being removed from the simulator. Any ideas? This is the only bug now preventing me from release :frowning: I don’t get any errors out of it when this happens.

FYI I can probably add and remove a few hundred agents before it crashes. Its totally random, can happen at the start, middle or end of a level at any time. Its just pure luck, but 1 in 200/300 it locks up and a worker / the workers go into an infinite loop.

Many thanks for your help.

Hi

Hm… I’m not sure what would be the cause of that.
Is it possible for you to attach a debugger and pause it when the infinite loop happens and then figure out where in the code it is being blocked?

I will see what I can do. I will try to hook one up tonight.

If it helps, I know that one time it did give a null ref error on the line:

simulator.Quadtree.Query(position, neighbourDist, this);

in CalculateNeighbours ()

However it only did that once, all other times no errors are spat out.

Firstly, Even though I have selected to have 2 worker threads, it looks like I have 6. 4 give a “No compatible code running” message. Is that normal? I see 2 running and can debug them (I have it paused now).

They appear to be looping round the following loop in RVOQuadtree @ line 142

while (a != null) {
				float v = agent.InsertAgentNeighbour(a, radius*radius);
				if (v < radius*radius) {
					radius = Mathf.Sqrt(v);
				}

				//Debug.DrawLine (a.position, new Vector3(p.x,0,p.y),Color.black);
				/*float dist = (new Vector2(a.position.x, a.position.y) - p).sqrMagnitude;
				 * if ( dist < radius*radius && a != agent ) {
				 *
				 * }*/
				a = a.next;
			}

A.next is an agent at the X coordinates of 4.5112. Then next time round a.next is an agent at X coordinates of 5.297, then next time round its 4.5112 again, then 5.297. Looks like this while loop is flipping backwards and forwards between two agents indefinitely. Want me to check anything while I have it paused? Maybe (its a big ask), could we possibly jump on skype for 10 mins while I have it debugging?

Thanks!

Hi

Hm… If you see six of them maybe you have encountered a bug I fixed recently. Sometimes RVO worker threads would not be terminated when the simulator was destroyed. I’m not sure what the “No compatible code running” message means though.

Yeah sure, we could do that. PM me with your skype info.

Not a single crash all day… Looks like its sorted! If anyone comes across this thread… There was a very special situation with special timing that led to an agent being added to the simulation multiple times. Simply check its not already added before adding and its fine.

Now its smooth like butter with 200 units running around on a standard PS4 with great framerates.

1 Like

Awesome! I’m glad it works now :slight_smile: