Possibility to implement deterministic path finding? about sharpnav HOT 3 OPEN

Unfortunately this is not nearly as simple as your example makes it out to be. Making that change would modify method declarations, structs, etc. You could overload all the math operators and casts but you'll still probably have to hunt down some strange bugs.

There are also a few other issues, the biggest one being of scale. How many bits are you dedicating to the decimal? If another user is working on a much smaller scale, will they run out of precision?

If I were to choose a 26.6 format (6 bits of decimal) and a user was working in a world where 1 unit == 1 km, then they would be limited to a resolution of 16m (about one point per 3.5 car lengths). On the other hand, if I were to choose a 16.16 format (16 bits of decimal), and a user was working in a world where 1 unit == 1cm (Unreal Engine 4 uses this scale) then the maximum navigable world size is ~655m^2, which can be severely limiting to open-world type games.

I personally have no interest in implementing this, but if it works well and you have a pull request I'll consider merging it in, cleaning it up, and maintaining it.

Instead of doing this the brute-force way, have you considered other ways of avoiding floating-point determinism issues across systems/platforms?

• Only have the server do pathfinding, send the found path (in the form of NavPoint[]) over the network?
  • Non-determinism in floating point numbers only happens when you're doing math with them. Serializing and deserializing floating point numbers between systems should work perfectly as long as they're being serialized as binary data (ToString() and float.Parse() will drift a tiny bit)
• Do it on both the client and server anyways, let a server-authoritative entity/agent position correct the path as it goes along.
  • Only a tiny fraction (< 1%) of your queries will end up looking different between two systems because of floating point determinism. Most games will send the positions of all characters over the network and the clients will usually snap to or interpolate towards the correct position because they all use floating point math. If you do this as well, you could just have it recalculate the path if this correction causes your agent to move across a Poly edge.

Also your physics engine will cause far more issues with floating point determinism than AI/navigation will, seeing as every frame depends on the previous one, creating errors that get exponentially worse every frame if not reset. Have you found a physics engine that works with fixed-point numbers in C#?

from sharpnav.

We may start with a 23.20 format which stored as long so that we can use these fixed-point numbers in some other game logic. But I suppose a int version is enough for spatial values. Also people can adjust bits of decimal according to their world size, it is only fixed during runtime.

We've considered several server-authoritative designs, the major problem is that we're building a mobile game and we want to provide a good offline experience (connections are only required when battle starts and finishes).

Also it's a RTS-style game, most physics calculation are collision detection. This simplify things a lot. So we may write our own collision detection lib with fixed-point numbers.

Thanks for the reply. I'll give it a try. If it works, I'll open a pull request :-)

from sharpnav.

Adjusting the bit size will (at least at first glance/consideration) probably kill performance in SharpNav. There's a ton of floating point math everywhere, adding a jump + load + shift + original operation + jump-return to every operation which is currently inlined and calculated on dedicated hardware is not likely to be on the same order of magnitude in terms of performance. If you fix the size, you don't need to load which will make all the functions more likely to be inlined, removing the jumps.

I would appreciate some benchmarks if you do get it working.

The way I'd recommend this be designed would depend on whether or not you want to also have the navmesh be stored as fixed-point verts. Assuming you don't care about the map format, you could just add some overloads to NavMeshQuery with fixed point numbers. Not sure how to handle the map change, as changing the format will have an impact on serialization (see SharpNav.IO.Json). Let me know if that's your plan.

I also have a few fixed-point number implementations from SharpFont, a FreeType2 wrapper... Here's the 26.6 example: https://github.com/Robmaister/SharpFont/blob/master/Source/SharpFont/Fixed26Dot6.cs

Can't wait to see what you come up with either way 😄

from sharpnav.