Optimization When I do a spatial partition, how often should I insert/delete entities?

This topic is 420 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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.

Edited by caymanbruce

Share on other sites

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.

Share on other sites
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?

Edited by caymanbruce

Share on other sites

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.

Share on other sites

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

Edited by caymanbruce

Share on other sites

"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?

Share on other sites
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?

Edited by caymanbruce

Share on other sites

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.

Share on other sites

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 ?

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 ?

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

Edited by hyyou

1. 1
2. 2
3. 3
Rutin
19
4. 4
5. 5
JoeJ
12

• 14
• 22
• 9
• 31
• 17
• Forum Statistics

• Total Topics
632617
• Total Posts
3007470
• Who's Online (See full list)

There are no registered users currently online

×