Fix the cell span query in a spatial hash

Review the AI's codeEasy10 min

Your task

Your collision broadphase is a spatial hash: the world is a grid of square cells, and each query visits the cells an axis-aligned box overlaps. The first version stopped one cell short, so objects on a cell boundary tunnelled through each other. The fix lists every cell the box touches, the last row and column included.

An assistant wrote spatial_cells_for_box(min_x, min_y, max_x, max_y, cell_size). It is in the editor. It has a bug. Find it and fix it.

Input and output:

  • min_x, min_y, max_x, max_y: the box's corners. They may be negative, and may arrive swapped.
  • cell_size: the width of a grid cell.
  • Return the cells as [cx, cy] pairs.

Rules the tests check:

  • If cell_size is 0 or less, return [].
  • If max_x is less than min_x, swap them. Do the same for y.
  • A coordinate v falls in cell floor(v / cell_size). Floor rounds down, so -0.5 with a cell size of 1 is in cell -1.
  • Return every cell from the min corner's cell to the max corner's cell, both ends included, on each axis.
  • Order the cells by cx ascending, then by cy ascending within each cx.

Examples

spatial_cells_for_box(min_x: float, min_y: float, max_x: float, max_y: float, cell_size: float) -> list[list[int]]
Example 1
Inputspatial_cells_for_box(0.5, 0.5, 1.5, 1.5, 1)
Output[[0, 0], [0, 1], [1, 0], [1, 1]]
Example 2
Inputspatial_cells_for_box(0.1, 0.1, 0.9, 0.9, 1)
Output[[0, 0]]
Example 3
Inputspatial_cells_for_box(1, 1, 2, 2, 1)
Output[[1, 1], [1, 2], [2, 1], [2, 2]]