Maintaining the same object id:s after deserialization

[opera-aberglund]

Hi! I'm opening this as a discussion since I'm not sure if this is solvable with the current version of PlayRho or not.

The problem is, after serialization and deserialization of the world, I want to make sure all objects that are recreated reclaim the same id:s as the previous objects.

This is no issue if objects are only created, since they can simply be recreated in the same order, from beginning to end, and the new objects will get the same id. Where it gets complicated for me is if objects are destroyed, because then they will be marked as "free" and subsequent newly created objects will reclaim their id:s.

I found I could work around this by recreating all the objects first in the same order as they existed in the buffer. Then, looping through the list again and calling Destroy on the ones that were destroyed so that they are marked as free.

The only issue I have now is that I want subsequent created bodies in the new world to get the same ids as if I had created them in the old world I serialized from. Looking at the code for the ObjectPool, it appears that new object will reclaim the id of the last destroyed object:

size_type Allocate(const value_type& copy)
    {
        if (!m_free.empty()) {
            const auto index = m_free.back();
            m_data[index] = copy;
            m_free.pop_back();
            return index;
        }
        const auto index = m_data.size();
        m_data.push_back(copy);
        return index;
    }

based on that it calls m_free.back(). This means I would have to destroy the objects in the deserialized world in exactly the same order as they were destroyed in the world I serialized from.

One way to maintain the determinism could be to make the m_free list a sorted list, so that perhaps always the smallest free id is picked for the new object. Or expose the m_free list so this information can be passed through serialization, so that free objects can then be destroyed in the same order.

Is this something you have thought about already when doing your tests? @louis-langholtz

[louis-langholtz]

that new object will reclaim the id of the last destroyed object

Yep. It seemed algorithmically like that'd be faster than alternatives I'd thought of.

This means I would have to destroy the objects in the deserialized world in exactly the same order as they were destroyed in the world I serialized from.

Yep. I believe this would provide a way to get back to the same object IDs after deserialization.

...could be to make the m_free list a sorted list, so that perhaps always the smallest free id is picked for the new object.

With the potential for a significant number of contacts being created and destroyed per step, I suspect this could noticeably slow down the world step function. And only help for cases where deserialization with the same resulting object IDs was more important than speed, and only serve to provide another way to get back to the same object IDs.

I wonder how hard it would be to write the code for recreating the same IDs as suggested.

[opera-aberglund]

I wonder how hard it would be to write the code for recreating the same IDs as suggested.

Not too difficult I suppose if I keept track of it in my game and passed it along, but I'm trying to make this a general library for serialization, so the information has to be in the physics world already.

[louis-langholtz]

Sorry. I meant that I wonder how hard it would be to use the technique I mentioned above to write a function for this library that users could use in this case to recreate the IDs exactly. I'll look into this a bit and get back with you on that.

[opera-aberglund]

I see! That's probably a good feature, allowing users more control over IDs.

[louis-langholtz]

That's probably a good feature, allowing users more control over IDs.

Not if that's at the expense of world steps of course. So that's the challenge: providing a way to reproduce the same ID allocations without slowing the world steps. For clarity, that's why ObjectPool allocates IDs the way it does and not using the lowest ID free but just the last ID freed.

Thinking out loud...

I've been considering getting rid of the GetBodies, GetJoints, GetContacts, etc. interfaces (#568) in favor of making everything in linear order of elements. That gets rid of buffers that I'm not sold on being necessary and converts memory access order to the more favorable linear order. The free order buffer meanwhile of ObjectPool can't go away, so maybe I export that instead.

[opera-aberglund]

I agree with that, performance for normal world steps has to come first. As long as perfect deserialization is possible, the deserialization process doesn't necessarily need good performance for most use cases. I'm using it solely once-per-time for players late-joining a multiplayer lobby where they need a snapshot of the world state.