For example I have 6000 entities on a 2D map and I want to get about 180 which are on my player's screen. When my player is moving new entities may appear on the map, at the same time some entities or enemies die so they disappear. I used to clear the entire spatial hash and insert everything again a few times a second. But I am thinking maybe it is better to only update those entities that change on the map, the number of changes may be huge though, but still, compared to the number of entities on the map it is still small. I am just not sure if this is worthy or not.

It sounds like you're mixing up the concept of a spatial partitioning method - which is just an efficient data structure for storing and finding things with positions - with the concept of interest management - which is a system for knowing which entities are of interest to which players/clients/whatever.

The server should have precisely 1 spatial hash / quadtree / whatever, containing all the relevant entity positions. You can use that to quickly determine which entities are of interest. But that data structure should not be attempting to represent any individual player's area of interest, nor changing based on what a player can see.

Most spatial partitioning methods will let you remove an entity and re-add it very efficiently. A simple hash or a grid falls into this category. Some spatial partitioning methods are not quite as effective with that, e.g. kd-trees, and some are in the middle, e.g. octrees. This is the simplest approach, to simply adjust the position in the structure where needed, so start with that, and see if it's performant enough.

If it's not, you might find that you get better results by recreating the whole structure, but that seems unlikely except in some extreme cases.

13 minutes ago, Kylotan said:

It sounds like you're mixing up the concept of a spatial partitioning method - which is just an efficient data structure for storing and finding things with positions - with the concept of interest management - which is a system for knowing which entities are of interest to which players/clients/whatever.

The server should have precisely 1 spatial hash / quadtree / whatever, containing all the relevant entity positions. You can use that to quickly determine which entities are of interest. But that data structure should not be attempting to represent any individual player's area of interest, nor changing based on what a player can see.

Most spatial partitioning methods will let you remove an entity and re-add it very efficiently. A simple hash or a grid falls into this category. Some spatial partitioning methods are not quite as effective with that, e.g. kd-trees, and some are in the middle, e.g. octrees. This is the simplest approach, to simply adjust the position in the structure where needed, so start with that, and see if it's performant enough.

If it's not, you might find that you get better results by recreating the whole structure, but that seems unlikely except in some extreme cases.

 

Yes I have 1 spatial hash. But what I am doing is for every player I clear the hash and insert everything again and use the player's position to determine the interested entities. I am just being lazy not to look into the performance details when I first implemented it. I find the spatial partitioning method is easy to find interested entities of a player. I used to use a radius-based system to get interested entities but that's more like brutal-force so I removed that. But I guess what you mean is to only insert/delete those players/entities that change their status. How should I use spatial partition correctly? How often should I check the environmental updates in interested region for each player? a few times a second or less, or more?

You don't need to perform any changes to the data structure "for every player". You should be able to query the hash based on any arbitrary position you give it. These structures are literally just a way to efficiently implement the following query:

List<Entity> FindEntitiesNear(Position x, float max_distance)

The data structure needs updating as objects move; whether you do that via deleting and re-adding, or via some internal method that can make the adjustment, is an implementation detail.

How often you check for updating a client/player's area of interest is a completely separate issue and has nothing to do with the spatial partitioning. That's a choice you make based on your game's needs. Start with once per second perhaps, and adjust if you need to.

@Kylotan Thanks but I am already doing what you said. Maybe I didn't explain it properly. I did only query based on a player's position. I do not perform the insert/clear operation on every player. I am just worrying about inserting all the entities too many times during game play. For example when my player is moving I find player A is also moving around me, 250ms later when I do a second spatial partitioning by inserting all the entities again into the hash, A is still moving around me. So I am inserting it two times. after 1 second maybe A is still moving in the same region and I am inserting it and removing it 4 times already. The same applies to the foods for example, which are static unless they are removed from the map. When my player is moving sometimes half of the foods on the screen never change, but during this time I have to insert them many times for spatial partitioning.

"250ms later when I do a second spatial partitioning by inserting all the entities again into the hash" - don't do that. There is no reason to keep recreating the whole structure.

"I am inserting it and removing it 4 times already" - why are you worried about moving a single object a few times in a second, when your computer is capable of calculating and showing showing you something like 100 million new pixels every second?

@Kylotan I 

35 minutes ago, Kylotan said:

"250ms later when I do a second spatial partitioning by inserting all the entities again into the hash" - don't do that. There is no reason to keep recreating the whole structure.

"I am inserting it and removing it 4 times already" - why are you worried about moving a single object a few times in a second, when your computer is capable of calculating and showing showing you something like 100 million new pixels every second?

I worry that because I am not inserting only one object. I am inserting and clearing 8000 objects 4 times per second. Maybe that's not a lot for a game but I have no idea because I am building a game for the first time. Now I guess your suggestion is like what I said in my first post, just update/add/remove the entities that actually change, instead of recreating everything again, is that correct?

Yes. There's no reason to clear the whole data structure. If I was writing bank software I wouldn't build a whole new database every time someone made a transaction.

I see the things that worry you.    

I believe you profiled it .... if not, you should do it before trying to optimize.

If it is really a bottleneck of your game  :-

1. Hash is too slow ?

• use sparse set
• Every entity may have its own unique ID :   https://programmingpraxis.com/2012/03/09/sparse-sets/
• Your game engine may need overhaul

2.  Inserting / deleting causes too much ?

• try to optimize the data structure instead of trying to reduce inserting/deleting

3. Query every frame is too expensive ?

• AABB should be fast enough for the task if you deploy Octree appropriately.
• http://www.bulletphysics.org/mediawiki-1.5.8/index.php/BtDbvt_dynamic_aabb_tree
• https://en.wikipedia.org/wiki/Octree

For me, cache miss always causes more CPU times than "often" hash-query.