I am implementing space partitioning on the server for my top-down MMO game. In my demo I modified my algorithm from a space-hashing algorithm used to work fine on client side so it works like dynamic clustering. But the sprites/players are constantly moving so I will have to check every player for collision detection. Therefore the final array contains every sprites for collision check. This makes my space partitioning algorithm look redundant. And it is incredibly slow.

Here is how I do this:

• I pick a moving sprite from the sprite array
• do a spatial hashing for it and get some nearby sprites
• based on the above method, I loop through the entire sprite array and pick one by one to get some nearby sprites
• I put all the results into a big array and it will store all the sprite for collision detection.

Imagine I have 400 moving sprites on a 640 x 480 map. The real map may be 8 - 9 times larger though. But is there a better way to implement space-partitioning on the server without slowing the game too much?

400 is a trivial number of entities. A very simple spatial hash - e.g. a coarse grid - should reduce the number of collision checks down to an even more trivial number. Instead of looping through the whole list, your spatial data structure should contain references to the nearby objects. Whenever an object moves, recalculate which area it's in, which is a cheap operation, and let the spatial structure know.

400 is a trivial number of entities. A very simple spatial hash - e.g. a coarse grid - should reduce the number of collision checks down to an even more trivial number. Instead of looping through the whole list, your spatial data structure should contain references to the nearby objects. Whenever an object moves, recalculate which area it's in, which is a cheap operation, and let the spatial structure know.

But all the entities are moving at all time, to any location without any obstacles unless colliding with other entities. I need to let every entity know its nearby objects, shouldn't I loop through the whole list and then broadcast the objects to the entity I am checking?

It isn't clear what you're asking. But no, the whole point of a spatial data structure is to avoid having to iterate through the whole set of objects.

Simple example:

• divide the world up into large tiles (e.g. a couple of screens wide)
• whenever an entity moves, work out which tile it's in
• store a link to that entity in the tile (and remove it from the previous tile if necessary)
• when checking collisions, you only have to look at entities in the same tile, or adjacent tiles

It isn't clear what you're asking. But no, the whole point of a spatial data structure is to avoid having to iterate through the whole set of objects.

Simple example:

• divide the world up into large tiles (e.g. a couple of screens wide)
• whenever an entity moves, work out which tile it's in
• store a link to that entity in the tile (and remove it from the previous tile if necessary)
• when checking collisions, you only have to look at entities in the same tile, or adjacent tiles

Thanks for a swift reply. My problem is like this:

First of all, every entity is moving all the time. Second, I am doing the collision detection on the server. I know how to do it on client for just one player. It works perfectly fine. But because the server is authoritative, it needs to know the state of each entity, whether it is colliding with other entity or no collision. I need to get the collision state of every entity on the map, so that I can send the information to them to guarantee every one of them knows if it is colliding with someone or someone near it collides with other entities. If I only check entity A001's collision on one side of the map, entity A199 which is on the other side of the map will have no idea whether it is colliding with someone or not.

The fact that every entity is moving is not interesting, nor the fact that you do collision detection on the server (since I was assuming all this was server side anyway).

Here's the base state: the server knows every entity in the game. The server has a spatial data structure so that, for any given entity, it knows that only a small subset are nearby and can quickly access that subset via that data structure. Whether those entities are moving all the time or not is irrelevant since keeping such a structure up to date is simple and cheap.

If clients need to perform collision checks as well, that's fine: your server can quickly tell who is nearby, due to the spatial data structure, and can send each client that short list of entities. It wouldn't normally need to do this all that often (maybe once or twice a second) and most MMOs do minimal client-side collision checks anyway.

If this doesn't solve your problem then you need to explain more clearly what your actual problem is.

The fact that every entity is moving is not interesting, nor the fact that you do collision detection on the server (since I was assuming all this was server side anyway).

Here's the base state: the server knows every entity in the game. The server has a spatial data structure so that, for any given entity, it knows that only a small subset are nearby and can quickly access that subset via that data structure. Whether those entities are moving all the time or not is irrelevant since keeping such a structure up to date is simple and cheap.

If clients need to perform collision checks as well, that's fine: your server can quickly tell who is nearby, due to the spatial data structure, and can send each client that short list of entities. It wouldn't normally need to do this all that often (maybe once or twice a second) and most MMOs do minimal client-side collision checks anyway.

If this doesn't solve your problem then you need to explain more clearly what your actual problem is.

Thank you I think I get what you mean. See if I can restate your solution. The server has a hash or whatever spatial data structure for performing partitioning at every physics update. When an entity gets an update passively or the server is about to send an update state to a specific entity, the server performs a spatial partition collision detection on that entity and gets a bucket of nearby objects. Then the server send this information to the entity that is waiting for the information update. I will skip client collision detection here. I think I just overdid the spatial partition and tried to prepare the information for all the entities in one go.

If what I just said is correct. How often do you suggest I perform the collision detection on the server side? Is it on each physics update or each network update?

"When an entity gets an update passively or the server is about to send an update state to a specific entity, the server performs a spatial partition collision detection on that entity" - No, this is a 2-step process:

• Update the data structure to accommodate the moved entity
• Use the data structure to detect or resolve any collisions

You can do them both in one call, but it's important to realise that the 2 steps are conceptually separate. A spatial data structure - whether a grid, a quadtree, or whatever - doesn't intrinsically know or care about collisions. But since it makes it easy to find which entities are near others, it makes collision detection quicker.

How and when to update entities is generally separate from this process, and depends largely on your game design. You don't want to send data about every other nearby entity every time a entity moves, because most of that data is going to get duplicated.

A top-down game can usually send movement updates for entities a handful of times per second. If all entities are generally moving then I'd recommend starting with a simple a system like this:

for each player_entity:
    if time_since_last_position_update > 0.2:  # update 5x a second; adjust to taste
        all_nearby_entities = spatial_data_structure.get_entities_near(player_entity.position)
        movement_message = MakeMovementMessage([position, velocity for entity in all_nearby_entities])
        player_entity.send_message(movement_message)
        reset last_position_update time

There are obvious inefficiencies in there, but you may find it's not a problem for you. MMOs often have a system where each entity remembers which entities are nearby, and when it last received a position update from them, which means the server can send them individually when necessary, and send them less often when they're offscreen (for example). Do a search for "interest management" or "area of interest management".

"When an entity gets an update passively or the server is about to send an update state to a specific entity, the server performs a spatial partition collision detection on that entity" - No, this is a 2-step process:

• Update the data structure to accommodate the moved entity
• Use the data structure to detect or resolve any collisions

You can do them both in one call, but it's important to realise that the 2 steps are conceptually separate. A spatial data structure - whether a grid, a quadtree, or whatever - doesn't intrinsically know or care about collisions. But since it makes it easy to find which entities are near others, it makes collision detection quicker.

How and when to update entities is generally separate from this process, and depends largely on your game design. You don't want to send data about every other nearby entity every time a entity moves, because most of that data is going to get duplicated.

A top-down game can usually send movement updates for entities a handful of times per second. If all entities are generally moving then I'd recommend starting with a simple a system like this:

for each player_entity:
    if time_since_last_position_update > 0.2:  # update 5x a second; adjust to taste
        all_nearby_entities = spatial_data_structure.get_entities_near(player_entity.position)
        movement_message = MakeMovementMessage([position, velocity for entity in all_nearby_entities])
        player_entity.send_message(movement_message)
        reset last_position_update time

There are obvious inefficiencies in there, but you may find it's not a problem for you. MMOs often have a system where each entity remembers which entities are nearby, and when it last received a position update from them, which means the server can send them individually when necessary, and send them less often when they're offscreen (for example). Do a search for "interest management" or "area of interest management".

This is exactly what I mean: Loop through each entity, and perform spatial partitioning just before sending out the spatial partitioning information (in this case all nearby entities' messages) to current connected entity. Then the server broadcast network state to that entity. Then the server goes on to do the same thing for another entity in the entity list until it sends out update messages for every entity. The above is all done in one update step in my case, maybe every other update step. Say there are 500 entities and a spatial partitioning returns a 10 entities bucket. I still need to do 5000 checks in one step. To reduce resource consumption on the server I think I might send out the spatial information less often.

Is Interest management on the client side or on the server side? I have heard of it but I don't know how it works together with spatial partitioning.

"The above is all done in one frame" - you would set the update timers so that you are not updating all entities at the same time. And given that you only do the broadcast 5x a second (in my example above), that's certainly not every frame. Given 500 entities, 10 entity bucket, and running at 20 frames per second (for example), that's 1250 checks per frame, and that is not expensive. Most of them will be single if-checks. If you're not running the server on a Commodore 64 you don't have much to worry about.

And you don't "send out the spatial partitioning information". The client doesn't (in most games) know or care about that. It just needs to know where everybody is.

Interest management is server side. You don't normally need to do anything like this on the client side.