How deterministic is this implementation?

[alexpyattaev]

A very reasonable use for this would be in an RTS game. Have you done any tests to validate deterministic operation of this algorithm? In the perfect world, running this on a fixed timestep should result in identical results on any two machines, questions are:

• was this considered during design?
• was this tested in any way?

If the answer is no to any/both of these, I'll be happy to test & report.
Thank you!

[BlondeBurrito]

I was inspired by RTS games and this is largely based on the pathfinding used in Supreme Commander 2, I really suggest checking out this I've cited in the README.

So the main goal was to produce a pathing calculation that's "good enough" for dealing with a large number of actors. From my reading around Flow/vector fields there are ways to optimise the algorithm to produce the true and perfect set of paths every time however there's naturally a performance cost when trying to do that. The chief recommendation I read suggested that with a large number of actors a slightly less optimal path shouldn't be that obvious to the human eye when you have a group of actors flocking to a destination together.

So during design I didn't focus on a deterministic calculation, simply getting a good looking result, having a quick think about it now I don't think there should be anything to suggest that it's not deterministic though*. The example visualise_flow_field_tiles calculates the fields from going point A to B and I believe it'll always produce the same fields across devices but I haven't explicitly tested it that way.

Given that the calculations are against 2d arrays (that can't be mutated while the calculation is running, only on a separate frame/ordered bevy SystemSet) and the components of those calculations always run in the same order then the same result should be produced every time.

If you'd like feel free to determine if it's truly deterministic and/or potentially add a specific example or test to validate it, it'd be much appreciated

* I believe there's an edge case bug that may invalidate this in large simulations but as you can probably tell from the issues I've created there's a lot of other stuff I'd like to refactor/tinker with before nailing down edge cases (and I've been super busy with life tbh, when work calms down I'd like to get back into this properly)

[BlondeBurrito]

Just in case you've decided to look into some kind of determinism test you may want to hold off for a little bit.

Having some people check this out in the last few days has spurred me into tackling some big bits of the backlog, I'm currently refactoring parts of the integration and flow calculations to achieve:

• refactor: consider moving LOS calc into integration layer #34
• feat: propagate LOS calculation into neighbouring sectors #36

Which will reduce the number of computations needed to generate the fields, some interfaces to the public internals (ways to access bits of the field calcs, maybe I'll find a way to not have some of them pub as they probably shouldn't be accessible) will change as a result but it should make it perform better and make the LOS code more readable.

I'm not sure if the user interface to access generated fields will change, in the 2d_continuous example some behaviour has creeped in a few commits back that's making actor A share actor B's flow field when requiring to pass through the same sector, even though it's a slightly worse path, which I'd like to fix and add some tests for.

Hoping to get it refactored and merged over the next few days.

Thanks for checking this out, it's a huge and complicated piece of work and people showing interest has given me the energy to dive back in!

[alexpyattaev]

Thanks for the information, I've been a bit swamped with some work related stuff recently. I've been involved a bit with the Spring engine (springrts.com), specifically the Zero-K game based on it. The deterministic pathing is a key component of their network architecture (as you do not need to sync positions of the units over the network, instead you can rely on the pathing being deterministic, so given identical inputs simulations do provide identical pathing => identical unit positions. Granted, this is largely irrelevant for single player games, but for competitive multiplayer keeping network traffic low is quite important. I typically do not have much time to dedicate to open source, but I'll keep you updated once I have some scaffolding for the realistic over-the-network test.

[BlondeBurrito]

No worries, that's pretty cool, I've been a follower of Beyond All Reason which I believe is also built using Spring.

Very good point on cutting down network traffic. I've actually been playing with bevy_repilcon in a server-client experiment of flowfields. Deterministic pathing would certainly be a big boon to this library and make network considerations a lot easier for people wanting to do multiplayer RTS with this. Once I've done those issues above I'll do a bit of reading about deterministic design and best practices for vetting and testing it and see what could be done as well

[alexpyattaev]

BAR is basically same as ZK under the hood. I'd be happy to help with determinism. I feel like first step would be getting rid of floats in the code in favor of softposit crate. There is only like 40 of them in the whole thing, mostly related to input and output scaling and such. External API would break though...

[BlondeBurrito]

Oh wow, I've never heard of Posits before but according to some university studies they seem really quite powerful and apparently bitwise identical across systems. I'm not too fussed about breaking API changes given that this library is still effectively an alpha. The main thing is to make the API easy to use from Bevy, admittedly the current format tends to require users to read and process the whole README, so the aspiration is to refine the interface so that users only need a high-level understanding of FlowFields, how to initialise the fields and consume the results. If those things are achievable with an interface that makes use of Posits (probably) then it'll be worthwhile exploring the benefits gained and what it may look like.

I've completed a chunk of the Integration calc rewrite and then the actual FlowField calc should be straightforward to refactor for release 0.11. That should put things in a good place to consider Posits (or other ideas) for a refactor on top 👍

[alexpyattaev]

I'll poke around with posits then once I can clear my schedule a bit=) If you have some kind of chat/IM accounts that you use, I think it would might be nice if you email me how to contact you easier as to not pollute the issue tracker.