Efficient solution for multiplayer space partioning?

Question

This question is a little tricky, but I will try to make it clear.

Lets say I am building an online game (not MMO-scale), but that supports as many players as possible, in a authoritative server approach. I want really big worlds with lots of AI simulated enemies.

I am aware of a few strategies to save server CPU by subdividing the space and not processing what doesn't need processing. I have already split the world by regions, that will require loading times and small transitions, which I think is important to maintain the quality of gameplay when playing locally (alone or even with a couple of friends). I don't expect the players to be in more than one or two regions.

The problem is that a region can become pretty big, and have a lot of NPCs simulating at once. How do I handle this without affecting the players' experience? Approaches like one server per region and alike are not in the table.

I am mainly looking for data structures to hold hordes of enemies, and even peaceful NPCs. To finalize the question, please note that vehicles exist, therefore its considerably fast to travel within a region, influencing the "when" to cull areas.

Answer 1

From what I understand you will have some sort of physics running on your server.

If that's the case there are also other techniques available for AI/physics other than space partitioning. From most to less obvious:

• priority: NPCs with no direct interaction with players can receive less CPU time by lowering their refresh rate. You can use priority queues and run queues with the higher priority from first to last, while other queues will run only 1/2, 1/4 or 1/8 of the queue each cycle. this way you ensure each object runs at some point but you reduce the number of times it consumes CPU.
• physics can also be lowered (only the collision boxes and spheres can be used while roaming and away from sight).
• simplifying AI/simulation by allocating very basic behaviors to NPCs and environment while players are far away. Usually it will be roaming or scanning for enemies instead of hunting, gathering, farming...
• some physics and AI can also be delegated to the clients. If you really lack CPU on the servers you can tag object as being partially resolved and the clients will adjust the physics and position of those objects locally (to avoid floating NPCs). The clients can be given some responsibility in running AI (during combat against a player the targeted player's device can be directly running the attacking NPCs)
• for players, physics can also be lowered on the server and clients will receive more responsibility in collision resolution. Ex: you hit an object with your vehicle, the server will only solve the collision on the collision boxes and tag the objects as potentially in collision. The client will send the resolution to the server with a timestamp which will accept it if the objects are tagged and the solution seems right.

Once you have implemented these mechanisms you can decide how much and how often you need them. The great thing about this is that later you can add a few servers which will be able to take over some of the tasks instead of the client apps.

Of course the approximated collision detection will create some aberrations, but you will be able to solve them by adding more precision from time to time.

Also concerning physics you should have a look at libs which support some sort of GPGPU system like OpenCL or CUDA if you have access to a server which supports either.