Rust game dev: dynamically splitting servers?

Say we are building a game server, where for x,y,z coordinates we have:

0 <= x <= 10_000
0 <= z <= 10_000
y is up direction

one way to statically split over 100 servers is to have a server for each (i, j) where

i * 1000 <= x <= (i+1) * 1000
j * 1000 <= z <= (j + 1) * 1000

Now, this is not very useful if something interesting happens at x=5500, z = 5500, and all the users jump to the same server. To do this we want to do something where instead of statically splitting the game server, we dynamically split the server based on where the players are.

Question:

Is this a solved problem for game server design? What are the most common hacks/techniques for this ? Is there any rust crates for doing this?

[1] It is important do not "shard" (i.e. have multiple worlds that do NOT interact). I want there to be one world where any pair of connected users can interact.

Adaptive space partitioning is a pretty well-studied problem. It's usually presented in the context of rendering, but the same principles apply to you problem. You could, for example, maintain a k-d tree for the whole world and associate each of your servers with a leaf node.

I have only dabbled in this space, so there is likely a better-suited datastructure for your needs; hopefully this gives you a place to start your own research.

2 Likes

To the best of my knowledge, all what k-d tree says is: every time when we split the world, split it via the hyperplane x = constant or y = constant or z = constant.

Octree steps can be viewed as the special case of splitting along x, y, z.

Grids can be viewed as the special case of splitting along x0 x1 ... xn followed by y0 y1 ... yn.

Although I agree that the end solution will probably look like a kd-tree (i.e. splits along axis = constant), I think a lot more is needed than merely "use kd trees".

I'm not sure I see the connection to rendering (which I'm interpreting as 'ray tracing w/ kd trees' since in that case, the scene is static/read-only). I do see similarities to 'distributed physics' -- but afaik, it a bunch of heuristics there.