Spatial Partition

Intent: Efficiently locate objects by storing them in a data structure organized by their positions.

Acron Mapping

Need

Acron approach

Collision / overlap queries

CollisionTraverser + CollisionHandlerQueue — use this first

Ray / line-of-sight queries

CollisionRay / CollisionSegment through CollisionTraverser

Custom spatial queries (range, k-nearest)

Manual grid / quadtree in Python over NodePath positions

Broad-phase filtering

Acron’s collision bitmasks (setFromCollideMask, setIntoCollideMask)

Use Acron’s collision system for collision queries before building a custom partition. Build a custom partition only for non-collision use cases: audio attenuation, enemy aggro range, minimap population, etc.

How to Implement — Acron collision (preferred)

  1. Add a CollisionSphere (or CollisionBox) to each entity: attach to a CollisionNode, reparent to the entity root.

  2. Create a global CollisionTraverser: base.cTrav = CollisionTraverser().

  3. Use a CollisionHandlerQueue and call base.cTrav.traverse(render) to get all overlapping pairs.

  4. Use bitmasks to narrow which objects collide with which categories.

How to Implement — custom uniform grid

  1. Choose a cell size appropriate to your max entity interaction radius.

  2. Maintain a dict[tuple[int, int], list] mapping (cell_x, cell_z) to entity lists.

  3. Update the grid in a low-sort task each frame: clear and re-insert all moving entities.

  4. Query: compute the cell(s) overlapping the query circle, union their lists, filter by exact distance.

Code Sketch (Python) — uniform grid

class SpatialGrid:
    def __init__(self, cell_size: float = 10.0):
        self._cell = cell_size
        self._grid = {}

    def _key(self, x, z) -> tuple:
        return (int(x // self._cell), int(z // self._cell))

    def insert(self, entity, x: float, z: float):
        k = self._key(x, z)
        self._grid.setdefault(k, []).append(entity)

    def clear(self):
        self._grid.clear()

    def query_radius(self, cx: float, cz: float, radius: float) -> list:
        results = []
        r_cells = int(radius // self._cell) + 1
        cx_cell, cz_cell = int(cx // self._cell), int(cz // self._cell)
        for dx in range(-r_cells, r_cells + 1):
            for dz in range(-r_cells, r_cells + 1):
                for entity in self._grid.get((cx_cell + dx, cz_cell + dz), []):
                    ex, _, ez = entity.node.getPos(render)
                    if (ex - cx) ** 2 + (ez - cz) ** 2 <= radius ** 2:
                        results.append(entity)
        return results


# Usage in entity manager update task
grid = SpatialGrid(cell_size=15.0)

def update_grid(task):
    grid.clear()
    for e in entities:
        px, _, pz = e.node.getPos(render)
        grid.insert(e, px, pz)
    # Query: enemies within 20 units of player
    nearby = grid.query_radius(*player_pos_xz, radius=20.0)
    return task.cont

Pitfalls

  • Cell size too small: tiny cells mean many cells to check per query and a large _grid dict. Set cell_size ≥ max interaction radius.

  • Forget to clear and rebuild: the grid must be rebuilt every frame for moving entities, or insertions accumulate stale entries. Clear in the same task that rebuilds.

  • Don’t replace CollisionTraverser for collision: Acron’s collision system is already optimised and handles bitmask filtering. Only implement a custom grid for non-collision spatial queries.