Monday, August 23, 2010

Path Following Performance pt. 2

Got the performance to quite constant sub 1 ms with adaptive sampling even in heavily crowded situations. The RVO samples (red) still dominate the performance. I think I'll stop here for a moment, remove a couple of quadratic loops, start figuring out how to package it better and open the flood gates for a couple of trillion bug reports.

That yellow spike is new path requests for all agents in a single frame. I'm quite happy about the Detour performance here. It stays about the same on larger meshes too. I'm particularly happy that I could keep the raycast there to optimize paths a little each update.


  1. its amazing to see an already awesome product becoming so much better (in little time).

    Continue the good work!! Many people including myself will and are finding this useful!

    ps: do you really think you can get it to 0.5 ms like you said in the previous post?

  2. Thanks! I don't know if 0.5ms is possible without getting creative. Currently I'm steering and adjusting the velocity at 20Hz, if I drop that to half, it should still be fine and I might get to 0.5ms. But I think I'll profile the sampling a bit more first.

  3. Have you ever implemented this system in something like Unity3D (Game engine) ? I am wondering how that would go?

  4. I recognize a pathfinding issue with the latest revision when moving the crowd:
    Level "nav_test.obj" has a pillar along the staircase. In some cases moving the crowd upwards/downwards the stairs one of the touching navmesh polygons is not highlighted yellow and eventually will be ignored by all agents although the way over this polygon becomes a benefical option as soon as the crowd squeezes beside the pillar. The agents then even turn back to go aroung the pillar on the other side...


  5. Kranky, that is interesting problem and more so since every single game solves it differently. I'm currently trying to figure out the best way to split the API so that it is useful for people who wish to multi-thread it as well as to those who just want to get some agents moving around.

    Mirko, the crowd simulation will be littered with that kind of things. You can always deduct a better way to handle certain case than computer :) The multi-agent code is getting closer and closer to the muddy waters called "AI behavior".

    The yellow polygons is just the closed list of the last pathfind, so it is hard to inspect anything concrete based on that. I will implement agent highlighting and tie some debug drawing to that so that it is easier to inspect the movement of the individuals.

    The agents try to optimize the path a bit as they go. Currently they only adjust the path based on visibility (that raycast in the code). It means that if they all choose to travel through the tiniest choke point in the level, they are likely to do that just queue there even if there is large open area next to it.

    My goal is to build simulation for 25 agents in an action game like scenario. It means that I simulate individual NPCs, but they can gracefully deal with small number of others moving in the same space. I'm not aiming to solve crowd simulation, although I hope to design the code so that it is possible add later on.

    I'm super nervous to release the path following code, because I know that if people start adopting it they will have a lot to complain about :)