Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Discussion Deterministic pathfinding in native

Discussion in 'Scripting' started by Fatferret, Feb 8, 2023.

  1. Fatferret

    Fatferret

    Joined:
    Apr 20, 2013
    Posts:
    18
    Hi,

    I would like to have performant deterministic pathfinding in Unity, there is some talk about it on the internet but it seems no one has actually taken the plunge to implement it it seems ( please do correct me )

    I am wondering what would be a sensible course if I were to implement it myself

    Seeing as I could take the navmesh generated by Unity and modify it to a deterministic format, I would only need to worry about the Detour part and make that deterministic using either in C# or C++, I would not need to do anything with Recast

    I am wondering if there would be an actual need to do it in C++ since IL2CPP also creates C++ code, probably with a lot more overhead than plain C++ but it might still be performant, or perhaps unsafe sections
     
  2. Kurt-Dekker

    Kurt-Dekker

    Joined:
    Mar 16, 2013
    Posts:
    38,514
    There's two potential problems here.

    Determinism is one potential problem.

    Performance of pathfinding is another potential problem.

    Have you determined that you actually have either one of these as an ACTUAL problem?

    In other words can you tolerate a non-deterministic pathfinding solution?

    Or can you simply do your pathfinding a little less aggressively, eg, don't update paths as often?

    But it is easy enough to create Astar routines in C# and a C++ , feed each one with the same graph and start /end points and see if there is ANY benefit??

    And as far as determinism, usually the pathfinding is NOT the thing that varies. It will be the framerate and the time spent by an AI traversing a path on different platforms, indeed even on the same platform over different runs.

    Don't solve problems you don't have.
     
  3. Fatferret

    Fatferret

    Joined:
    Apr 20, 2013
    Posts:
    18
    I want to have a solution that can be used in a lockstep RTS game, so non-deterministic won't work as it would require syncing hundreds of agents over the network in the worst case scenario


    Determinism is something that does vary between different machines as pathing on a navmesh uses floating point artihmetic
     
  4. Kurt-Dekker

    Kurt-Dekker

    Joined:
    Mar 16, 2013
    Posts:
    38,514
    I would start by making a navigation mesh (graph) with integer (fixed point if necessary) representations for costs / lengths.

    Get that up and going and tested and stress test it with all the frame rates you could reasonably expect.

    Until I had that working 100% solidly (stress-proven with a small handful of agents) with aggressively-degenerate framerates (such as periodically going from 10fps to 100fps, or even freezing updates for one or two full seconds), I would not muddy the waters by reaching for C++ integrations.

    Once you have a small cohort working, scale it up to a pilot example of your ultimate game, ad then optimize if you must. Remember that making something faster is not the only way to optimize. Simply doing it less often is an even better way of optimizing.

    Determinism is HARD. It's like a chain of custody for a cryptographic key: any interruption anywhere along the way means you can no longer trust the values involved.
     
  5. Fatferret

    Fatferret

    Joined:
    Apr 20, 2013
    Posts:
    18
    Yes after reading some more it looks like it was an uphill battle for the games that use it, SpringRTS as well

    Taking it step by step as you mention makes sense

    I need to evaluate what I am trying to achieve here exactly maybe I can scale things down and use a traditional networking model instead