How could I implement origin re-base on my large world server?

Question

I wish to make a game set in space where the world is empty space, mostly empty but continuous (i.e. no sectors with jump gates separating them) and extends to long distances like a few hundred or a thousand kilometres, where players move around at realistic speeds of spacecrafts. I'm thinking of something like "Star Citizen".

One approach I thought of was scaling down everything and moving slowly to effectively make an illusion of large world but this approach tends to suffer with problems in precision of calculations, specifically floating point calculations. Then I found out about the concept of origin re-basing.

I'm having trouble understanding how I could implement that on the server: clients can have objects relative to their origin but the server needs to have the entire world in the same co-ordinate system since there is only one world on the server in which everything interacts.

How could I manage both client and server coordinates systems on the server for my very large space environment in a realistic way in the perspective of the player?

Answer 1

One approach I thought of was scaling down everything and moving slowly to effectively make an illusion of large world.

As mentioned above, reducing scale doesn't actually increase the usable play space, because the precision limits of a floating point number scale with the magnitude of that number. (So, reducing the size of your ships by a factor of 1024 reduces the error in their positions by only that same factor of 1024, meaning that relative to the game content the errors are still the same size)

So, how would we implement a local origin system for a large continuous world?

1. Divide the world into zones.

   • You can do this based on a regular grid, where each zone is identified by an integer grid coordinate tuple. You can find the offset between two nodes implicitly, by taking the difference in their coordinate values multiplied by the grid spacing.

     (eg. the 1024 km cube of space in the "middle" of your world is zone(0, 0, 0), beside it there's another 1024 km cube called zone(1, 0, 0)...)

   • Or you can do this based on local landmarks, where each zone is a node in a graph. Nodes can either have explicit positions in some global coordinate system (either using higher precision or rounding to representable coordinates), or you can store just the offset between two neighbouring nodes in the edges of the graph.

     (eg. you might have a zone for each space station, planet, or interesting space feature/anomaly - locations where you expect gameplay interactions will usually gather. You might need to scatter empty zones in between to maintain even coverage. Instead of a grid, your zone boundaries form a collection of Voronoi cells)

2. Treat all "Positions" in your game as tuples, combining:

   • a zone ID, and...
   • a local offset relative to that zone's centre.

   As a dynamic object travels outside its current zone, it can update its position to one relative to the new zone it enters, like so:

   localOffset += newZone.GetOffsetFromZone(currentZone); currentZone = newZone;

   By keeping your zone spacing small, you can ensure you retain the desired level of precision throughout these operations. You can consult the table in this answer to find at what magnitude of number you hit a particular error threshold that's significant for your game, and then back up an order of magnitude or two for safety.

3. For a client, convert all visible entities to your local zone. (Simplest Case)

   That keeps one coordinate system for simplicity, while still guaranteeing the desired precision for everything near the player - whether they're natively in the player's own zone or one immediately adjacent. Objects in more distant zones will have less accuracy on the client machine, but their sheer distance should make this unnoticeable.

   When the client needs to convert their position to a new zone, they apply the new offset to everything at once, so from the player's eye view nothing happened at all - they're just sailing continuously through space.

   If you have a mechanic that involves fine-precision sniping across multi-zone distances then you may need to take a somewhat more robust approach...

4. For the server, sort dynamic entities into "islands" (General Case)

   This is a common step in many physics engines to limit the complexity of collision checking & constraint solving. You perform a crude range or bounds check to determine which objects are close enough together to potentially influence each other, grouping them into clusters you can solve in isolation.

   Once you have your islands, you can update them accordingly:

   • If an island is contained entirely within a single zone, all of its interactions can be resolved in that zone's local coordinate system.

   • If an island spans multiple zones, then they need to agree on a lingua franca first. Convert their positions into a common zone (either pick the one closest to the center of the island, or invent a one-off zone for the purpose), then resolve the interactions in this space.

   This should handle cases where your world is sparse, so you never have a single object or chain of mutually-interacting objects spanning a more than a small cluster of adjacent zones. This is pretty typical for space. Megastructures like the Ringworld would of course require somewhat exotic treatment. ;)

   Each island can potentially be farmed-out as a separate work unit for scaling across multiple threads / multiple servers. The island sorting itself can be handled incrementally, as very few objects will need to change islands in any given tick (especially if your island assignment is conservative or includes some hysteresis, so an object skimming the interaction range of another doesn't get added & removed repeatedly)