# Is moving entities between sectors of a grid spatial partitioning inefficient?

I'm using a grid system for spacial partitioning. If I have moving entities, will I have to reassign every entity to its correct section every frame?

Surely this is inefficient. Have I got the wrong idea?

First of all, unless you have an exorbitant number of entities, assigning them to a sector on every logic frame is most likely performance-wise negligible.

That said, it sounds like you are in over your head. Either your game doesn't actually need spatial partitioning, or what you are trying to create is too advanced for your level.

The point of spatial partitioning is usually that you can avoid double-looping over all your entities to do collision detection. But that double-loop usually isn't a big issue if you have less than around 1000 entities.

If you plan on having that many entities, then ask yourself: Do the big number improve the gameplay? And do I have the resources to do all the work this requires?

The point of all this is that you should focus your effort, don't solve problems that don't exist, and try to achieve the desired gameplay by as simple means as possible. Stacking on more complexity is easy, retaining a good game while doing so is difficult.

You don't have to check every entity, every frame. You only have to check entities when you move them. Further, since you're using a grid system, you can just check to see if they've crossed a boundary.

For example, if they're currently in grid 5,5 and you have a grid line every 10 units, you only have to do a modulus on their current x and y coordinates to know if they belong in a new grid. This is a pretty fast test.

This does not necessarily have to be as computationally expensive as you imagine. First of all, as you hinted at, you don't have to check every entity; just the ones that are moving. As such it might be wiser to have individual entities update their grid cell in their update method.

As for checking coordinates, there are a few optimizations you could make. For example, say your grid is made up of cells that are 64x64. To figure the coordinates of which cell an entity is in, all you have to do is x>>6 and y>>6 (try it). This is faster than, say, a grid with cells that are 100x100, where to find out the cell coordinates you would need to do x/100 and y/100 and floor the result (or cast into int if it's not already). Thus it's more efficient on a larger scale to pick cell sizes that are powers of 2 for example.

Although I doubt that this will be a bottleneck (remember premature optimization is the root of all evil), you could also update zones less frequently than on every game tick and maybe even make the rate depend on the maximum/expected speed of any given entity.

The frame you're in is irrelevant. You don't do this every frame. When the entity moves just check if it's in a new section and update it as needed.