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.

  • \$\begingroup\$ Are you restricted to just one physical server? \$\endgroup\$ Commented Mar 18, 2012 at 0:19
  • \$\begingroup\$ Ultimately, no. But for the sake of both simpleness and achievability, for now, i can't complicate the project even more :) \$\endgroup\$
    – Grimshaw
    Commented Mar 18, 2012 at 2:42
  • \$\begingroup\$ Start simple. Something like WoW that does operate on multiple physical boxes per "server" just divides up their world into a grid and all updating is based on who's in the same boxes as you. Very simple, easy to tweak, works well and you can use it with just your one box to control processing. \$\endgroup\$ Commented Mar 18, 2012 at 2:47
  • \$\begingroup\$ I fully agree with your point of view, and maybe i missed something in my question. What if there is one player on the very right of the box' cell, and another in the very left of the right neighbour cell ? They should see each other! The world looks continues for a game like WoW.. This is what I don't understand, how to make a continuous world grid, while keeping it efficient? Certainly there are situations when players from two "servers" should see each other :) \$\endgroup\$
    – Grimshaw
    Commented Mar 18, 2012 at 3:11
  • 1
    \$\begingroup\$ And yeah, if you are going to have both a lot of stuff all over and a lot of players all over you really do have to plan for everything to be active everywhere and all the time, no magical way around that. This is why single boxes of an MMO server group only service 200-500 players maximum AND why MMO AI for NPCs is pathetically stupid (aka cheap to compute). \$\endgroup\$ Commented Mar 19, 2012 at 0:31

1 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.

  • \$\begingroup\$ Combining space partioning of a region with priority updates should be exactly what I need, optimal for little amounts of players, and still optimized when a lot of areas are loaded. Thanks. \$\endgroup\$
    – Grimshaw
    Commented Mar 19, 2012 at 0:21
  • \$\begingroup\$ @DevilWithin It should help, and it requires no changes on the client side. I also added a few more details to the answer. \$\endgroup\$
    – Coyote
    Commented Mar 19, 2012 at 0:28
  • \$\begingroup\$ The simplified AI is a wonderful idea. While the NPC are far from players, they don't need to be doing anything besides moving in most cases. That means I can just do an approximation of what they are up to, every 1 minute or something, just to make them roam around the world.. imagining them as zombies, they would do so! \$\endgroup\$
    – Grimshaw
    Commented Mar 19, 2012 at 0:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .