There is a room of a given size, divided into square sectors. Sector size is a power of two. The bodies are presented in the form of circles. Bodies can be as small, in which case you can take them as a point, and large enough. In the second case, the body can simultaneously be in several sectors. The main problem is that the bodies are moving. Correspondingly, the list of occupied sectors changes over time.
Is there a more efficient way to update the list of occupied sectors than to search all sectors again each time? In principle, the code in computational terms is not too complicated - we build an AABB rectangle corresponding to a circle, then we find sectors belonging to it, not forgetting to check for intersection with the circle. What is good one-time when adding, not the fact that such with frequent updates. It seems to me that there must be something more efficient.
Below is an example of a search (used when adding an object to a container)
void Gridmap::add(Cell* cell) { geometry::Vec2D delta(cell->radius, cell->radius); geometry::AABB aabb(cell->position - delta, cell->position + delta); aabb = clip(aabb); uint32_t rowStart = static_cast<uint32_t>(aabb.ay) >> m_power; uint32_t rowEnd = static_cast<uint32_t>(aabb.by) >> m_power; uint32_t colStart = static_cast<uint32_t>(aabb.ax) >> m_power; uint32_t colEnd = static_cast<uint32_t>(aabb.bx) >> m_power; uint32_t sectorSize = 1 << m_power; int32_t y = rowStart * sectorSize; for (auto row = rowStart; row <= rowEnd; ++row) { int32_t x = colStart * sectorSize; for (auto col = colStart; col <= colEnd; ++col) { geometry::AABB box(x, y, x + sectorSize, y + sectorSize); x += sectorSize; if (geometry::intersects(box, cell)) { Sector* sector = &m_sectors.at(row * m_colCount + col); sector->cells.insert(cell); cell->sectors.insert(sector); } } y += sectorSize; } } 