Serialize/deserialize world state?

[opera-aberglund]

Hi there!

I'm working on a Rollback Netcode engine and I'm currently looking for a physics engine for a test game that has the capability to completely serialize its state so that it can be stored and restored if needed at any time.

I was previously looking at Box2D but quickly found that making a 100% accurate copy of the World was impossible, so I found this engine instead! It's amazing that the world can be so easily cloned, good work on this! However, for my application to work I need to be able to store the copies as a flat byte array and then be able to parse them back to a World object. This is because the Rollback engine is designed to be generalizable to any game state while also needing to be able to send the entire state over the internet.

My question is therefore: is this something that by chance is already supported by PlayRho, or, if it isn't currently supported, would it be technically feasible to implement it?

Another thing I'm wondering regards the determinism of the engine. I've read the Box2D is deterministic with the exception of floating point errors on different architectures. Is there an option in PlayRho to use fixed-point math only?

Very thankful for any help I can get with this, and happy to explain further what I'm working on.

// Alex

[louis-langholtz]

Hello! Thank you for considering PlayRho for this!

Sounds like you have two questions:

1. Does PlayRho already support serialization and deserialization of state?
2. What's the determinism of PlayRho?

Here's some info on these questions:

Regarding serialization and deserialization:

Assuming you want to be able to copy state across restarting the program or the computer, the short answer is that's not already supported.

Longer...

As you found, PlayRho fully supports value semantics of actions like copying and equality-checking. So if all you want is to be able to rollback at any point in an application's lifetime, that should work just by saving the copies in memory. If you want to make a copy that you can reload after stopping the program however, then that state needs to be stored somehow across that restart. Assuming like a full shutdown, that of course pushes matters to using a persistent storage mechanism and it sounds like that's the realm you're wanting support in. PlayRho doesn't have code already to do this.

Is there a particular format like XML or JSON that you'd prefer to serialize/deserialize from/to? If I put aside other projects, I could whip up code for a standard format probably in like a week. Not sure I can put the other ones aside though. In any case, I'd probably do it as a separate GitHub repo/project that depends on PlayRho and an external open source library that supported that format. It shouldn't need internal access to World state; it should be doable using just publicly accessible member functions and non-member functions.

Regarding determinism of PlayRho:

PlayRho is just as deterministic as Box2D. And, like Box2D, has the exception of floating point math across different hardware.

PlayRho, unlike Box2D, was designed to support using a fixed-point type however for its Real alias. That comes with some requirements though:

1. The underlying type has to qualify as a C++ LiteralType.
2. The underlying type comes with a library supporting all the math functions needed.

I have code for such a fixed-point type and library, but it's not production quality. I'd made it originally just to test out what it'd take to have the Real alias use a custom C++ type that provided fixed-point support. You can find it at realnumb. Some warnings: it's slower in my use than any floating point type I've used, you'd want to minimally use realnumb::fixed64, fixed64 requires using a hardware/compiler combo that supports __int128_t.

Improving realnumb to the point I'd call it "production ready", would probably take me around 3+ weeks, and that wouldn't address its slower speed.

To my knowledge, there's not another implementation of a fixed-point type & library that fully satisfies both of these requirements. If you can find one however, that'd probably be your better option.

[opera-aberglund]

Just FYI, I started working on my own implementation of a serializer for the World state. For now we just have a very minimal sample game so for our purposes I only need to serialize a couple different bodies and shapes, but it will probably have to be extended for most kinds of objects later when we have a more diverse game.

I'm currently using this external library https://github.com/felixguendling/cista for the low-level serialization/deserialization part. If you'd like it I could create I public repo for what I've done so far so you can have an eye on it ;)

[louis-langholtz]

Thank you for the update!

I just took a quick look at Cista. I hadn't looked at it before. It's interesting to me. I like that they have fuzz testing for it. It makes me wonder about use of terms like "simple", which are subjective. But that may be my biggest beef with Cista.

I'd love to have an eye on what you're done so far, yes. On my end, I'm not sure how much time I'll have for helping. I'd love to, but I am still deep in work on my time-machine-helper repo/project (for helping with macOS Time Machine backups).

[louis-langholtz]

Out of curiosity, are you using PlayRho from its master branch or from a release?

[opera-aberglund]

I see! So far I'm liking Cista. It's good for my purposes at least since I only want to serialize to byte arrays, and I must have something really fast as well.

I'm using it from the release branch. I saw somewhere you were working on a 2.0 release? Do you think it makes more sense to use the master branch right away?

I'm also wondering if you have any broad opinions on how the serialization should be done? I'm currently pondering if I should use some kind of visitor pattern for traversing the different shape types for instance, so I don't have to use GetTypeID and TypeCast everything. However, that would require me to add an accept method on all the inherited classes in PlayRho to get it going.

I checked out some of your blogposts and somewhere you mentioned you preferred composition over inheritance and I was wondering why you're not using std::variant for the shapes, but I just looked at the master branch and saw you've added a "Compositor". Does it serve the same purpose and would it simplify implementing a visitor pattern? Thanks! :)

[opera-aberglund]

Another question: would it be fine if I instead create a new branch in this repo and add the serializer there? It would be much easier because I don't have to go through the legal process in my company of open-sourcing code. Then, depending on what you prefer, you could just move it to a separate repo yourself.

[louis-langholtz]

So far I'm liking Cista. It's good for my purposes at least since I only want to serialize to byte arrays, and I must have something really fast as well.

Makes sense to me as well. I had been thinking of serializing to an ASCII format, like JSON as I'd mentioned. But serializing to a binary format like byte arrays seems more sensible for performance.

I saw somewhere you were working on a 2.0 release

Yes. The master branch code is where the active development head is and I intend to make a 2.0 release from it. I think it's ready, or close to it. I'd like to get some more testers of it before making that however.

have any broad opinions on how the serialization should be done?

You may have thought more about this by now than I have.

For a full state transfer, I'd start by looking at the state that the world instance holds. That'd be in the implementation code in WorldImpl in release 1.1, or in AabbTreeWorld in master.

I'm not sure that all the necessary state can be accessed via public member functions and non-member functions. But I'm of the opinion that it should be. Anything missing that way I'd be more inclined to address in the master branch.

Some of the world state is cached state which shouldn't need to be serialized.

I'm of the opinion that the state that's important for serialization would be the same state that'd be important for determining equality and vice versa. I'm also of the opinion that the master branch code for this - see bool operator==(const AabbTreeWorld& lhs, const AabbTreeWorld& rhs) noexcept - is better in this regard.

I was wondering why you're not using std::variant for the shapes

I love std::variant. But I'm of the opinion it's not ideal for representing an open set of types that all share some common traits (think Rust-like traits). std::variant I consider being a closed set in this regard - closed in the sense of being closed at compile-time to only the types listed in the template parameters given to it.

For a Rust-like traits interface, I'm of the opinion that what I call "polymorphic value types", are more ideal. And shapes are accessed via Shape - which is such a type. I like to think of polymorphic value types, as like a std::variant (or std::any too), but that holds a value of any type that satisfies the trait-like requirements of the polymorphic value type.

Incidentally, I have been thinking about the Shape interface. There's something that bothers me about the shape design in PlayRho. It's that PlayRho solved the problem of ghost collisions without needing chain-shapes like Box2D uses. PlayRho has no need for the additional complexity and overhead of child shapes - but is still providing these. Without which, there'd just be the DistanceProxy elements - purely convex shapes. Concavities are implemented using multiple convex shapes but without child-shapes, then DistanceProxy and Shape would be combinable essentially into one type. Anyway, I bring this up as I'd love to get conversation going with you or anyone else about this that might be interested in this.

...you've added a "Compositor". Does it serve the same purpose and would it simplify implementing a visitor pattern?

Hmm... hadn't thought about it this way before. The compositor has been an experiment with compile-time shapes for reducing memory overhead for common shapes. I think it'd make more sense though if PlayRho merged the DistanceProxy with Shape as described above.

would it be fine if I instead create a new branch in this repo and add the serializer there?

I'm not sure. I guess that'd depend mostly on what you mean.

I don't have objection to your doing what's most convenient for you. If you're asking whether there's any technical issue with like contributing back such work if it's done with the same git repo of code (instead of as a separate repo that was dependent on the library component), you may already know the answer to that better than I at this point.

I think ultimately I'd need to see the code for what you mean to speak more articulately to this. That sounds like it might be a bit of a catch-22 or chicken and egg problem though.

[opera-aberglund]

Thanks for the info!

If the master branch is almost ready for another release I think it makes more sense for me to to build it for that straight away.

Regarding the design of the shapes, I don't think I've gotten well versed enough to have an opinion on that yet (Edit: I found a couple things that bothered me and submitted issues for those). This is my first time working with a physics engine so I'm learning about the concepts as I go here. I was a bit confused with how the child shapes work though, but I should check out what's changed in the master branch.

I think ultimately I'd need to see the code for what you mean to speak more articulately to this.

I'm thinking now that perhaps it would be best if I just created a private repo and shared it with you for starters, then we can see if we can do something more with it. So far I've implemented an almost complete serialization for the bodies and the different shapes, and it has worked surprisingly well with my rollback multiplayer game from the tests I've done.

[opera-aberglund]

Also, great tip with the equality operator! I was just thinking about how I could confirm its correctness, and when you say it, it seems pretty obvious.

[opera-aberglund]

The reason why I asked about the visitor pattern is because I ended up with something like this when serializing the shapes:

auto shapeType = GetType(shape);

if (shapeType == GetTypeID<ChainShapeConf>()) {
    auto chainConf = TypeCast<ChainShapeConf>(shape);
    ...
  } else if (shapeType == GetTypeID<DiskShapeConf>()) {
    auto diskConf = TypeCast<DiskShapeConf>(shape);
    ...
  } else if (shapeType == GetTypeID<EdgeShapeConf>()) {
    auto edgeConf = TypeCast<EdgeShapeConf>(shape);
    ...
  } else if (shapeType == GetTypeID<MultiShapeConf>()) {
    auto multiConf = TypeCast<MultiShapeConf>(shape);
    ...
  } else /* if (shapeType == GetTypeID<PolygonShapeConf>()) */ {
    auto polygonConf = TypeCast<PolygonShapeConf>(shape);
    ...
  }

Which is fine since there are only 5 different types, but it would still be really nice to be able to do it somehow without linearly going through and checking each different type. This is what I like most about std::variant because it comes with the std::visit, but I totally understand your liking of the Rust-like traits (or polymorphic values like you call them :) )

[louis-langholtz]

The reason why I asked about the visitor pattern is because I ended up with something like this when serializing the shapes:

auto shapeType = GetType(shape);

if (shapeType == GetTypeID<ChainShapeConf>()) {
    auto chainConf = TypeCast<ChainShapeConf>(shape);
    ...
  } else if (shapeType == GetTypeID<DiskShapeConf>()) {
    auto diskConf = TypeCast<DiskShapeConf>(shape);
    ...
  } else if (shapeType == GetTypeID<EdgeShapeConf>()) {
    auto edgeConf = TypeCast<EdgeShapeConf>(shape);
    ...
  } else if (shapeType == GetTypeID<MultiShapeConf>()) {
    auto multiConf = TypeCast<MultiShapeConf>(shape);
    ...
  } else /* if (shapeType == GetTypeID<PolygonShapeConf>()) */ {
    auto polygonConf = TypeCast<PolygonShapeConf>(shape);
    ...
  }

That's what I've done too. See Testbed/Framework/Main.cpp for example.

[louis-langholtz]

it would still be really nice to be able to do it somehow without linearly going through and checking each different type

I agree. Yes.

I'd prefer to see code like shown at cppreference.com for std::visit:

std::visit(overloaded{
  [](auto arg) { std::cout << arg << ' '; },
  [](double arg) { std::cout << std::fixed << arg << ' '; },
  [](const std::string& arg) { std::cout << std::quoted(arg) << ' '; }
}, v);

With the right template magic, I wonder if something like std::visit would be possible for visiting the different shape or joint types. I have not tried to put the code together for that before however. OTOH, if it could, why isn't something like that for std::any?

I did look into using switch statements. It's currently limited to fundamental integer types however, and case statements also need to have constant-expressions of integer types. So using like reinterpret_cast<std::uintptr_t>(GetTypeID<ChainShapeConf>().GetName()) isn't valid. There seems like a reasonable proposal to the C++ standards committee to update what switch handle, which I'd considered making before but pushing proposals through seems like more work than I have the time for now. I believe there's already been proposals for this and likely in a future standard switch will become more flexible in this respect anyway.

Perhaps the answer at code review for this could provide guidance on how to do this.

As perhaps something of a hack, I suppose a map type could be used. That'd give us more like the syntax we want. It also wouldn't be a linear search. Though performance wise, I'd guess it'd be a loss to using if-else-statements.

[opera-aberglund]

It would be awesome if we can get something like that working!

By the way, I created a fork of PlayRho that has the new serializer inside its sources, I call it "RhoBox". You can check it out here: https://github.com/opera-gaming/PlayRho. What's mainly missing is all the joints, as well as the contacts but I'm waiting for you to update the API so I can deserialize those. For now though, it looks like it's still working deterministically without serializing them.

[louis-langholtz]

It's interesting that you've used a cista::offset::variant for the different shapes, but not for the different joints. I'm curious why for one but not the other.

Note that if a user added a new Shape satisfying type or a new Joint satisfying type, the cista variant would presumably need to be updated just like a std::variant to support that new type. I'm guessing that wouldn't be an issue in your use case but I wanted to mention it just in case. You'd asked before about why I did use a variant for Shape or Joint and that speaks to whether Shape and Joint are open (as they are now) vs. closed.

[opera-aberglund]

It's interesting that you've used a cista::offset::variant for the different shapes, but not for the different joints. I'm curious why for one but not the other.

Actually I did use one for the joints as well, it's just that it currently only contains the rope joint because I haven't completed the others yet.
https://github.com/opera-gaming/PlayRho/blob/49fa5f6f6538bd6965b45aa7d02a405f9d544b9f/Library/include/rhobox/rhobox_joints.hpp#L181

Note that if a user added a new Shape satisfying type or a new Joint satisfying type, the cista variant would presumably need to be updated just like a std::variant to support that new type.

I actually never thought about that. It's only now that I realise why you've designed it to be "open": so that users can add their own types! It's true that a cista::variant will probably work good enough for my use case, but my ambition is still to the create something general that will work for everything. My guess how that would have to work is that users would have to overload their own serialization/deserialization functions for their custom shapes and joints, but I have to give that some more thought.. Thanks for the heads up!

[louis-langholtz]

Oh, and I noticed you used BodyConf::UseType(BodyType) instead of just BodyConf::Use(BodyType). I'm sorry I didn't get rid of that longer named interface first. Hope you won't mind if I removed it shortly.

[opera-aberglund]

Yeah no worries

[louis-langholtz]

As for recreating World after serialize/deserialize, I'm thinking about how to deal with the DynamicTree and how it interacts with the automatic creation and deletion of Contact objects. Like adding a CreateContact runs up against needing to have the indices of the AABBs for which the contact is for in terms of what's body-contacts cache. A bit of a chicken and egg problem then.

Incidentally, have you tried serializing/deserializing without doing so for the Contact objects, but with running a Step with a zero time to have the engine recreate the dynamic tree (of AABBs) and contacts itself? That'd miss any particular settings on the contacts as I've mentioned before but those settings themself could be serialized/deserialized and then applied just using SetContact. I don't believe I have any test code for this pattern of use but theoretically it seems like it might work and reduce the state that has to be transferred. I'm guessing equality would need some related tweaks though. I'm going to switch to this angle cause I'm running up against that chicken and egg problem with a CreateContact interface. To at least see how close that gets us.

[louis-langholtz]

PR #562 has been merged into master now. Hopefully this PR moves things along with getting this working.

[opera-aberglund]

Unfortunately the issue remains for me. It's behaving very differently in each test I do.

It seems though for the first case where the shapes are only overlapping but not touching, the contact is never recreated in the deserialized world. In this case the manifold in the original world is the unset type, and no manifold exist in the deserialized world.

In the case where they are touching, the contact is usually recreated, but the manifold is the unset type and not the circles type as it is in the original world. This is not always the case, sometimes the contact is recreated and then after another step it disappears again. Only one time so far I've managed to both have the contact and manifold recreated correctly when they were touching and I don't know what I did different.

Would a potential solution for this be to just add a CreateContact and SetManifold so I can serialize them like everything else? Or is that just putting a bandaid on the problem?

[opera-aberglund]

If you'd like you can test the serializer yourself as well. I updated the readme here if you scroll to the bottom so you can see how to use it.

[louis-langholtz]

I see here at line 46 that Step(world, Time(0)); is called. Then contacts are copied at line 53.

I don't know that the problem you're seeing is due to the following, but I do believe it will be a problem...

I realize with this effort, that the zero time step won't recreate the original contacts in the same order. So in a world having more than one contact, the CopyContactConfig is likely to apply any contact tweaks to the wrong contacts and checking by contact ID may not match between source and destination.

I'll want to update my implementation of world equality to match-up contacts by their Contactable data so that better reflects that ordering I don't believe should be important. The copying your deserialization code is doing would I think need to do similar in the sense of finding the new contact that matches the contactable info of the source contact and then applying the tweaks from the matching source to the matching destination contact.

[opera-aberglund]

I realize with this effort, that the zero time step won't recreate the original contacts in the same order.

Yes you're right this will probably be an issue as well. But for now the main issue is that not the same amount of contacts are created, so I'll worry more about the ordering later.

[louis-langholtz]

...
I'm working on a Rollback Netcode engine and I'm currently looking for a physics engine for a test game that has the capability to completely serialize its state so that it can be stored and restored if needed at any time.
...

I've created a "Support serialization/deserialization" project for this for me to help track changes for this.

My question is therefore: is this something that by chance is already supported by PlayRho, or, if it isn't currently supported, would it be technically feasible to implement it?
...

Copying worlds is supported and tested, but recreating them from their components per anything like serialization and deserialization is another matter I'm realizing. I don't know of a reason why it would not be technically feasible to get this to work however. Moreover, I'd really like to get this working and unit test proven.

[louis-langholtz]

I just pushed my latest working branch for this. The branch has work in progress; it's not complete. But the changes do seem to move closer to the goal. Made a draft pull request of it of PR #563.

Among other changes, I'm considering supporting an is-destroyed flag on settable world components - i.e. Contact, Body, Shape, Joint - as an alternative to supporting an IsDestroyed(const World&, *ID id) like function interface for each of those. Cons of the latter are having to plumb the info through the world interface which enlarges its already larger than I'd prefer interface and not being as performant as the former. Cons of the former are having to support such a flag and synchronization on all the world component types which would mean also increasing trait requirements on the Shape and Joint types. I can't say I'm particularly fond of either set of cons. Perhaps the I need a third alternative for this like having the existing Get*(const World&, *ID id) interfaces return those as a std::optional. That'd avoid the cons of either of the first two but would have the con of changing user code.

Thinking about the remaining differences, I'm suspecting the copy needs to be built and then have the same non-zero time step run on the destination copy as the source to see more complete equality. I'm working on test code for this. Otherwise, I don't see the tree/AABB movement able to reflect the same state resulting in less contacts in the destination until a non-zero time step is for worlds with non-static bodies that are moving.

[louis-langholtz]

Update: PR #563 is getting closer.

I've had to think more deeply about the meaning of state, like Contact::NeedsUpdating. For example, with the latest changes in this PR, NeedsUpdating should always be false for all contacts after any Step calls on that world. Similarly, TOI should always be unset after any Step calls, with the exception of when sub-stepping is enabled.

Note that objects within a world of Contact, represent overlapping AABBs for pairs of convex shapes that may also be touching/overlapping (but may not be). In this sense, they're not really contacts unless the touching property is true.

Anyways, now I'm seeing that for every touching contact, I can find a contact in the recreated world and can set the manifold impulses to match the source. I still have to update the world equality operators for this however. The upshot though is that while the number of contacts may be different, the number of contacts for actually touching/overlapping bodies are the same and state from the source world can be assigned over into the destination world for these contacts. This is done by matching Contactable data though; not by ContactID from source necessarily being same as in destination world.

[louis-langholtz]

FYI: Merged that PR now with changes in it that got recreation with equality working for me with the pyramid demo while it was still being solved.

[opera-aberglund]

Anyways, now I'm seeing that for every touching contact, I can find a contact in the recreated world and can set the manifold impulses to match the source.

So this means that the non-touching contacts won't be recreated? I guess that makes sense, bit wouldn't it break the determinism if you have events in the pre- and postsolve steps? And does it mean that I should only serialize the contacts for which IsTouching is true?

Besides that, it seems to work very well now. Good work! I'm calling the MakeTouchingMap function you added before I serialize the contacts, and then again on the recreated world when I copy the contact configs to make sure they are matched correctly. I found that I didn't need to send any extra information, because MakeTouchingMap should always map the contacts in the same order right? Because the contactables are used as the keys and they should be the same in the recreated world.

Just fix this one and I think we're good.

[louis-langholtz]

@opera-aberglund How's this coming along for you? As far as I'm aware, this is working fine now. Is that what you're seeing?

[opera-aberglund]

@louis-langholtz Hello again, thanks for asking! Yes, I don't think I've seen any other issues so it seems to be working! We are currently working on developing our multiplayer game with this technology. I'll write you back when it's published :)