Border between two spaces

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
mcmonkey
Posts: 92
Joined: Fri Apr 17, 2015 11:42 pm

Border between two spaces

Post by mcmonkey » Sat Sep 03, 2016 2:06 am

HHaHAHahahAHAhaHAHaHAhA I'm insane and so is this post, so bear with me a little...

I have a problem.

I have a /really big/ area to cover.
Way bigger than a Vector3 of floats can cover, unfortunately.

So I came up with a plan: Make a big grid of spaces that generate and destruct as you enter or leave them.
Reasonable, right?

There's one problem though:
What happens as you move from one space to the next?
Of course you just shift the coordinates a fair bit and move the entity over.

But what about when an entity slightly protrudes into the next space, but does not fully enter it?
How do we make things still hit it physically reasonably?

My plan currently is something along the lines of:
Generate duplicate entities in all spaces touched that aren't the main space,
and for any force applied to any duplicate, apply it back to the real entity, and keep the duplicate matched to the real one.

What do you think of this plan? It probably will create a delayed reaction or something, I'm really not sure.

Just hoping for feedback on how to best accomplish it within BEPU.

Norbo
Site Admin
Posts: 4772
Joined: Tue Jul 04, 2006 4:45 am

Re: Border between two spaces

Post by Norbo » Sat Sep 03, 2016 9:02 pm

There's a few different options here, depending on what your needs are.

Do you need to simulate things that aren't near the player?
1) If not, you can get away with incrementally loading and removing elements from the simulation, and periodically recentering things so that the covered area is always well within the decent precision range of a 32 bit float. For reference, for a simulation using the demos scale, 32 bit floats will do okay from around -10000 to 10000 along each axis. In this model, there is no worry about entities on a border, because there is no second space.

2) If far simulation is required, but the simulation can fit on a single computer in terms of memory and CPU use, one of the more common approaches to large worlds is to just make the engine use doubles instead of floats. In v1.4.X, this is a little tedious since you have to do a bunch of find-replaces, but it doesn't hurt performance that much. There's no SIMD being used, so it's just some occasional extra memory/cache pressure.

(A more targeted approach could swap out only the position's numerical representation. This would be a little bit difficult in the context of v1.4.X, because the transitions from local/relative/world are not perfectly contained. For example, contact point positions can be read out in world space which means they'd need their representation updated, and so on. In v2, one of the things I'm looking at is isolating the position more, so that it might be as simple as a compiler switch to change between, say, 32 bit floats and 32 bit fixed point. The broadphase's use of singles would become a problem at extreme scales too, though. Changing it over to 64 bit representations would hurt SIMD throughput, but I am still considering it as an option.)

3) If far simulation is required, and the simulation can't fit on a single computer, then you start needing multiple spaces. At this point, we're basically talking about distributed computing, so a lot of the same concepts apply. One option to deal with space borders would be to give both spaces a proxy of the simulated object. One of the two spaces would be heuristically determined to be the 'authority' over the object. The results of the simulation would be replicated over to the 'slave' simulation. In a networked setup, this would be a periodic thing, so the 'slave' simulation would still be simulating it normally in between updates. It's a lot like a client-server setup.

The trick comes in when dynamic objects start interacting. When object A is owned by server X and object B is owned by server Y and they start bouncing around on each other, the servers will be sending each other 'corrections' about the simulation state but it might not converge to a coherent result. The servers just fight each other. That tends to look crappy.

To resolve that problem, the authority heuristics need to get a little more clever. If two objects are directly interacting, try to move their authority over to a single server, so there is no possible disagreement. That way, even a pile of objects will stay as stable as if it were on a single server.

Depending on the game's design, it's possible for things to get even more complicated. Consider what happens if a bunch of players in an MMO got together and tried to DOS the server by dumping stuff in one of these border regions, so they're loading down 2 or possibly more servers at once. Ideally, the 'border' would adapt, so that only one server would be handling the DOS-pile. Maybe you'd have a high powered $200,000 super-node with 192 cores that you dedicate to the task...

Technically, it's possible to do some of this without any concept of a in-world geographic region handled by a given server. You're primarily interested in distributing these 'simulation islands' as units of work. There's some nontrivial complexity involved in making sure objects transition between simulation islands properly, but it can be done. There are some proofs of concept floating around out there- I think one of the newer distributed-physics-as-a-service things do something similar, but I forget the name.

And on a truly enormous simulation, maybe one where you have a slightly looser physics budget than 5ms/frame, you might bite the bullet on the cross-server messaging overhead and do the equivalent of fine grained multithreading on a per-system level, except across multiple nodes...

The rabbit hole goes deep. If you don't really, really need a certain property of one of these complicated things, it's best to just do the simpler thing.

mcmonkey
Posts: 92
Joined: Fri Apr 17, 2015 11:42 pm

Re: Border between two spaces

Post by mcmonkey » Sun Sep 04, 2016 6:53 am

Let me explain my situation a bit better.

The world is NOT going to be a million by a gerjillion wide actively loaded and calculating. I don't intend to run off a supercomputer here.

The world is going to be some smattering of activity at -10000 units, and perhaps some at 234567 units and so on.

As it's a multiplayer game, there's a potential for EG two players to be tens of thousands of units apart and still expecting reasonable physics simulation.

On a larger setup with many players or non-player area loaders of whatever form, there could be EG a straight line loaded from -100000 to 100000 units (Though probably rather thin).

We need to be performance conscious, as the computers running servers won't be amazingly superpowerful.

A double would get some increase in potential distance, but only so much and at a potentially visible performance cost - any little bit of performance cost is a problem. (So much optimization still to-do >.> -- hoping for BEPU 2.0 to be possible to transition to some year..., also hoping for any reasonably doable perf improvement backporting :P )
A "decimal" would remove all distance problems, but waste performance.


As far as I can see, the /only/ good way to do this is to simulate multiple spaces each with their own centering. It fits unrelated systems well too. I'm open to suggestions here but I feel somewhat confident it's a reasonable solution.

The question is how to handle the edges really... when two spaces touch, how do the entities avoid problems?

I think just transmitting forces from a physics entity clone in the touched region back to the original entity in the first region is a solid start to solving that problem. I imagine it would cause some oddities, particularly at moderately high movement speeds where something may attempt to ram its way through a wall in just as a bad a manner as disabled CCD would at /very/ high speeds.

Norbo
Site Admin
Posts: 4772
Joined: Tue Jul 04, 2006 4:45 am

Re: Border between two spaces

Post by Norbo » Sun Sep 04, 2016 7:14 pm

As far as I can see, the /only/ good way to do this is to simulate multiple spaces each with their own centering. It fits unrelated systems well too. I'm open to suggestions here but I feel somewhat confident it's a reasonable solution.

The question is how to handle the edges really... when two spaces touch, how do the entities avoid problems?

I think just transmitting forces from a physics entity clone in the touched region back to the original entity in the first region is a solid start to solving that problem. I imagine it would cause some oddities, particularly at moderately high movement speeds where something may attempt to ram its way through a wall in just as a bad a manner as disabled CCD would at /very/ high speeds.
It can be a reasonable solution, and it has been done before successfully, but this is still basically #3 from my previous post, just running on one machine. It has most of the same complexity, just with lower latency on messaging. Updating the 'slave' proxy works pretty much exactly the same as in a networked game. Most commonly, just snap its position, orientation, and velocities directly to the new values. Just remember that it is very easy to make simulation quality terrible in the border region if the authority and updates are not managed very carefully.
A double would get some increase in potential distance, but only so much and at a potentially visible performance cost - any little bit of performance cost is a problem.
For reference, a single can simulate up to around 16,000 meters in a given direction with millimeter spatial resolution or better. A double can simulate up to around 8,800,000,000,000 meters in a given direction with millimeter spatial resolution or better. That is about 11 times the average distance between the Sun and Jupiter. So probably enough for most purposes :)

The cost of managing duplicated proxies at the border and all the authority issues around that will almost certainly be more expensive than using doubles across the board. Keep in mind that most modern desktop x86-64 CPUs will execute a single and double op at the ~same rate. On some platforms with some compilers, doubles will actually be faster. There is no SIMD being used in v1.4.X, so the actual raw compute throughput is basically unchanged.

The only significant change is the memory size, and v1.4.X is a loooong way from being so optimized that the cache impact of doubles versus singles matters. In most of the cases where there is potential for an 'extra' cache miss, the design already virtually guarantees a cache miss, regardless of the data type size. In v2 there will be a much larger difference between the two, but hopefully I can address range issues more directly in v2 anyway.

As always, do some performance tests to confirm. Just make sure the compilation target is 64 bit, not 32 bit.

mcmonkey
Posts: 92
Joined: Fri Apr 17, 2015 11:42 pm

Re: Border between two spaces

Post by mcmonkey » Fri Sep 09, 2016 10:13 pm

Welllllllllp
I did research based on your suggestion.

Turns out modern processors are just as fast if not faster calculating doubles than floats, excluding tiny amounts of memory usage.

I did a test run of BEPU s/float/double, and after fixing your terrifying entity state manager write buffer thingy (Explicit layout where a Vector3 and a Quaternion share data space - I have no idea what that's even intended for, but I fixed the layout locations for doubles)

I guess I have to scrap my awesome-tastic fun idea to overcomplicate things, and behave reasonably now :(

So now in my code I use doubles for phyics calcs, I'll experiment with whether I can match this on the GPU but probably I'll just want to shift everything relative to the player view before rendering it.

Also, seriously.

Code: Select all

        [StructLayout(LayoutKind.Explicit)]
        internal struct EntityStateChange
        {
            [FieldOffset(0)]
            internal Quaternion orientationQuaternion;
            [FieldOffset(0)]
            internal Vector3 vector;
            [FieldOffset(16)] // changed to 32
            internal TargetField targetField;
            [FieldOffset(24)] // changed to 40
            internal Entity target;
How did this end up being the best solution

Norbo
Site Admin
Posts: 4772
Joined: Tue Jul 04, 2006 4:45 am

Re: Border between two spaces

Post by Norbo » Sat Sep 10, 2016 2:13 am

I guess I have to scrap my awesome-tastic fun idea to overcomplicate things, and behave reasonably now
Alas :)
How did this end up being the best solution
The overlapped fields marginally reduce the required memory with no real overhead. Consider an alternative where the struct held the position, orientation, linear velocity, and angular velocity all at once. Assuming contiguous positions and single precision, that would be 52 bytes instead of 16 for the property data portion.

You could make the argument that an entity's properties tend to get changed together so it makes sense to have a single entry per entity rather than a sequence of changes. That would also be a reasonable design.

(At this point, I think the actual "best solution" is to delete everything related to buffered/interpolated states in the engine!)

Post Reply