Use spatial hash by default when checking GridPoint for entities #253

New issue

Closed

opened 2026-03-03 20:02:33 +00:00 by john · 1 comment

john commented

2026-03-03 20:02:33 +00:00

Owner

❯ best, most correct, or performant way to check for another entity at (x, y) on a grid? 

∴ Thinking…

  The user is asking about the best way to check for an entity at a specific (x, y) position on a grid in McRogueFace. Let me look at the available APIs.

  From my memory, I know that GridPoint has an entities property. Let me check the current API to give the most accurate answer.

● The most direct way is via the GridPoint API:

  cell = grid.at(x, y)
  entities_here = cell.entities  # list of entities at this cell

  This returns the entities whose grid_pos matches (x, y). Let me verify the current implementation to confirm performance characteristics.

● Search(pattern: "entities")
  ⎿  Found 42 lines (ctrl+o to expand)

● Search(pattern: "GridPoint.*entities\|get_entities\|entities_at")
  ⎿  Found 0 lines

● Read(src/UIGridPoint.cpp)
  ⎿  Read 50 lines

● Search(pattern: "spatial_hash")
  ⎿  Found 1 file (ctrl+o to expand)

● Search(pattern: "spatial_hash|SpatialHash")
  ⎿  Found 2 lines (ctrl+o to expand)

● Read(src/UIGrid.cpp)
  ⎿  Read 50 lines

● Search(pattern: "class SpatialHash")
  ⎿  Found 31 lines (ctrl+o to expand)

● Here's the summary of your three options, from best to worst:

  1. grid.entities_in_radius() — Best for exact cell lookup (O(k))

  entities = grid.entities_in_radius((x, y), 0.5)

  This uses the spatial hash (bucket size 32), so it only checks entities in the relevant bucket — not the entire entity list. Complexity is O(k) where k is the number of
  nearby entities. For an exact-cell check, a radius of 0.5 will match entities at integer position (x, y) without bleeding into adjacent cells.

  2. grid.at(x, y).entities — Simplest, but O(n)

  cell = grid.at(x, y)
  entities_here = cell.entities

  Readable and obvious, but the implementation (UIGridPoint.cpp:109) does a linear scan of the entire grid.entities list, comparing every entity's position against
  (target_x, target_y). Fine for small entity counts, but scales poorly.

  3. Manual iteration — Most flexible, same O(n)

  at_pos = [e for e in grid.entities if int(e.pos[0]) == x and int(e.pos[1]) == y]

  Same linear scan but in Python, so strictly slower than option 2 (which at least does the loop in C++).

  ---
  Recommendation: Use grid.entities_in_radius((x, y), 0.5) for performance-sensitive code (pathfinding, collision checks). Use grid.at(x, y).entities when readability
  matters more than speed and entity counts are small.

✻ Sautéed for 35s

❯ any reason why the implementation of GridPoint.entities shouldn't use the spatial hash internally? 

● No, there's no good reason. It should. Let me check if there's any subtle difference that might matter.

● Read(src/SpatialHash.h)
  ⎿  Read 72 lines

● Read(src/SpatialHash.cpp)
  ⎿  Read 126 lines

● No reason at all. The spatial hash is already maintained by the grid — GridPoint.entities just ignores it and does a brute-force linear scan instead. It's purely a
  historical artifact (#114 predates #115).

  The only minor consideration is that queryRadius does a circular distance check, but for an exact cell match you'd want equality. A small dedicated method like
  queryCell(int x, int y) on SpatialHash would be ideal — just a single bucket lookup plus position match, no radius math. But even using the existing queryRadius(x + 0.5f,
  y + 0.5f, 0.5f) would be a big improvement over the O(n) scan.

``` ❯ best, most correct, or performant way to check for another entity at (x, y) on a grid? ∴ Thinking… The user is asking about the best way to check for an entity at a specific (x, y) position on a grid in McRogueFace. Let me look at the available APIs. From my memory, I know that GridPoint has an entities property. Let me check the current API to give the most accurate answer. ● The most direct way is via the GridPoint API: cell = grid.at(x, y) entities_here = cell.entities # list of entities at this cell This returns the entities whose grid_pos matches (x, y). Let me verify the current implementation to confirm performance characteristics. ● Search(pattern: "entities") ⎿ Found 42 lines (ctrl+o to expand) ● Search(pattern: "GridPoint.*entities\|get_entities\|entities_at") ⎿ Found 0 lines ● Read(src/UIGridPoint.cpp) ⎿ Read 50 lines ● Search(pattern: "spatial_hash") ⎿ Found 1 file (ctrl+o to expand) ● Search(pattern: "spatial_hash|SpatialHash") ⎿ Found 2 lines (ctrl+o to expand) ● Read(src/UIGrid.cpp) ⎿ Read 50 lines ● Search(pattern: "class SpatialHash") ⎿ Found 31 lines (ctrl+o to expand) ● Here's the summary of your three options, from best to worst: 1. grid.entities_in_radius() — Best for exact cell lookup (O(k)) entities = grid.entities_in_radius((x, y), 0.5) This uses the spatial hash (bucket size 32), so it only checks entities in the relevant bucket — not the entire entity list. Complexity is O(k) where k is the number of nearby entities. For an exact-cell check, a radius of 0.5 will match entities at integer position (x, y) without bleeding into adjacent cells. 2. grid.at(x, y).entities — Simplest, but O(n) cell = grid.at(x, y) entities_here = cell.entities Readable and obvious, but the implementation (UIGridPoint.cpp:109) does a linear scan of the entire grid.entities list, comparing every entity's position against (target_x, target_y). Fine for small entity counts, but scales poorly. 3. Manual iteration — Most flexible, same O(n) at_pos = [e for e in grid.entities if int(e.pos[0]) == x and int(e.pos[1]) == y] Same linear scan but in Python, so strictly slower than option 2 (which at least does the loop in C++). --- Recommendation: Use grid.entities_in_radius((x, y), 0.5) for performance-sensitive code (pathfinding, collision checks). Use grid.at(x, y).entities when readability matters more than speed and entity counts are small. ✻ Sautéed for 35s ❯ any reason why the implementation of GridPoint.entities shouldn't use the spatial hash internally? ● No, there's no good reason. It should. Let me check if there's any subtle difference that might matter. ● Read(src/SpatialHash.h) ⎿ Read 72 lines ● Read(src/SpatialHash.cpp) ⎿ Read 126 lines ● No reason at all. The spatial hash is already maintained by the grid — GridPoint.entities just ignores it and does a brute-force linear scan instead. It's purely a historical artifact (#114 predates #115). The only minor consideration is that queryRadius does a circular distance check, but for an exact cell match you'd want equality. A small dedicated method like queryCell(int x, int y) on SpatialHash would be ideal — just a single bucket lookup plus position match, no radius math. But even using the existing queryRadius(x + 0.5f, y + 0.5f, 0.5f) would be a big improvement over the O(n) scan. ```

john added the

Bugfix

priority:tier1-active

labels

2026-03-03 20:02:33 +00:00

john commented

2026-03-15 20:18:00 +00:00

Author

Owner

Roadmap context

Part of the Grid & Entity Overhaul Roadmap (docs/GRID_ENTITY_OVERHAUL_ROADMAP.md), Phase 1 (Foundation). This is a prerequisite for the behavior system — grid.step() and pathfinding collision both rely on efficient spatial queries at cell granularity.

Suggested approach: add SpatialHash::queryCell(int x, int y) — single bucket lookup + exact cell_pos match, no radius math. Then use it in GridPoint.entities getter.

## Roadmap context Part of the Grid & Entity Overhaul Roadmap (`docs/GRID_ENTITY_OVERHAUL_ROADMAP.md`), **Phase 1** (Foundation). This is a prerequisite for the behavior system — `grid.step()` and pathfinding collision both rely on efficient spatial queries at cell granularity. Suggested approach: add `SpatialHash::queryCell(int x, int y)` — single bucket lookup + exact `cell_pos` match, no radius math. Then use it in `GridPoint.entities` getter.

john referenced this issue from a commit

2026-03-16 11:21:02 +00:00

Phase 1: Safety & performance foundation for Grid/Entity overhaul

john closed this issue

2026-03-16 11:21:02 +00:00

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

john/McRogueFace#253

No description provided.

Rows
Columns