john/McRogueFace

Fork 0

FOV optimization for behavior TARGET triggers #303

New issue

Closed

opened 2026-03-15 00:32:29 +00:00 by john · 1 comment

john commented

2026-03-15 00:32:29 +00:00

Owner

Summary

Optimize FOV computation in the turn system's TARGET trigger check. Without optimization, computing FOV for every entity every turn is prohibitively expensive on large grids. The goal is to eliminate unnecessary FOV computation via tiered pre-filtering.

Target scale

McRogueFace targets 8192×8192 grids. Naive FOV for 100 entities = 100 × 67M cells = catastrophic. Even with TCOD's radius-bounded FOV, we need to avoid calling it when unnecessary.

Optimization tiers

Tier 1 — Label check (O(1))

If entity.target_label is None, skip entirely. Most entities won't have triggers configured. Expected elimination: majority of entities.

Tier 2 — Spatial hash proximity pre-filter (O(bucket_count))

Before computing FOV, query the spatial hash for entities with target_label within sight_radius. Check the bounding square [cell_x ± radius] × [cell_y ± radius].

If no target-labeled entities exist in any overlapping spatial hash buckets, skip FOV entirely.

With 32-cell buckets and radius 10, this checks at most ceil(20/32)² = 1 bucket in the best case. This catches 100% of cases where the target is simply too far away.

Tier 3 — Bounded FOV computation

TCOD's compute_fov() already accepts a radius parameter. For radius=10, FOV touches ~314 cells regardless of grid size. This is O(radius²), not O(grid_size).

Verify that TCOD's implementation actually bounds its work to the radius and doesn't iterate the full map. If it does iterate the full map, consider:

Windowing the TCOD map to a subregion
Implementing a custom radius-bounded FOV
Modifying libtcod-headless fork to add bounded iteration

Tier 4 — Static entity FOV caching

Entities that haven't moved since last FOV computation don't need recomputation. Track a fov_dirty flag per entity, set when:

cell_pos changes
Any cell's transparent property changes within sight_radius

Tier 5 — Subgrid-aware early termination (future)

For very large grids, spatial hash buckets provide natural subgrid boundaries. If an entire subgrid has no transparent-changing cells and no target entities, its FOV contribution is known without computation.

Expected performance

With 100 NPCs on 100×100 grid, 1 player (worst case: all NPCs have target_label = "player"):

Tier	Entities remaining	Work per entity	Total
No optimization	100	~10,000 cells	1,000,000 cell checks
Tier 1 (label check)	50 (assume half have triggers)	—	—
Tier 2 (proximity)	5 (near player)	—	—
Tier 3 (bounded FOV)	5	~314 cells	1,570 cell checks
Total	—	—	~640× reduction

TCOD investigation needed

Before implementation, verify:

Does TCOD_map_compute_fov() with a radius actually bound its iteration? Or does it scan the entire map and filter?
If it scans the full map, is it feasible to modify the libtcod-headless fork to add bounded iteration?
What's the actual performance of FOV on an 8192×8192 map with radius 10?

Dependencies

#301 (grid.step() — this optimization lives inside the turn processing loop)
#296 (entity labels — for target_label queries)
#295 (cell_pos — for spatial hash queries)

Files likely affected

src/UIGrid.h/cpp — FOV computation optimization
src/EntityBehavior.cpp — trigger evaluation in turn processing
Potentially modules/libtcod-headless/ — if TCOD modification needed

## Summary Optimize FOV computation in the turn system's TARGET trigger check. Without optimization, computing FOV for every entity every turn is prohibitively expensive on large grids. The goal is to eliminate unnecessary FOV computation via tiered pre-filtering. ## Target scale McRogueFace targets 8192×8192 grids. Naive FOV for 100 entities = 100 × 67M cells = catastrophic. Even with TCOD's radius-bounded FOV, we need to avoid calling it when unnecessary. ## Optimization tiers ### Tier 1 — Label check (O(1)) If `entity.target_label` is None, skip entirely. Most entities won't have triggers configured. Expected elimination: majority of entities. ### Tier 2 — Spatial hash proximity pre-filter (O(bucket_count)) Before computing FOV, query the spatial hash for entities with `target_label` within `sight_radius`. Check the bounding square `[cell_x ± radius] × [cell_y ± radius]`. If no target-labeled entities exist in any overlapping spatial hash buckets, skip FOV entirely. With 32-cell buckets and radius 10, this checks at most `ceil(20/32)² = 1` bucket in the best case. This catches 100% of cases where the target is simply too far away. ### Tier 3 — Bounded FOV computation TCOD's `compute_fov()` already accepts a radius parameter. For radius=10, FOV touches ~314 cells regardless of grid size. This is O(radius²), not O(grid_size). Verify that TCOD's implementation actually bounds its work to the radius and doesn't iterate the full map. If it does iterate the full map, consider: - Windowing the TCOD map to a subregion - Implementing a custom radius-bounded FOV - Modifying libtcod-headless fork to add bounded iteration ### Tier 4 — Static entity FOV caching Entities that haven't moved since last FOV computation don't need recomputation. Track a `fov_dirty` flag per entity, set when: - `cell_pos` changes - Any cell's `transparent` property changes within sight_radius ### Tier 5 — Subgrid-aware early termination (future) For very large grids, spatial hash buckets provide natural subgrid boundaries. If an entire subgrid has no transparent-changing cells and no target entities, its FOV contribution is known without computation. ## Expected performance With 100 NPCs on 100×100 grid, 1 player (worst case: all NPCs have `target_label = "player"`): | Tier | Entities remaining | Work per entity | Total | |------|--------------------|-----------------|-------| | No optimization | 100 | ~10,000 cells | 1,000,000 cell checks | | Tier 1 (label check) | 50 (assume half have triggers) | — | — | | Tier 2 (proximity) | 5 (near player) | — | — | | Tier 3 (bounded FOV) | 5 | ~314 cells | 1,570 cell checks | | **Total** | — | — | **~640× reduction** | ## TCOD investigation needed Before implementation, verify: 1. Does `TCOD_map_compute_fov()` with a radius actually bound its iteration? Or does it scan the entire map and filter? 2. If it scans the full map, is it feasible to modify the libtcod-headless fork to add bounded iteration? 3. What's the actual performance of FOV on an 8192×8192 map with radius 10? ## Dependencies - #301 (`grid.step()` — this optimization lives inside the turn processing loop) - #296 (entity labels — for target_label queries) - #295 (`cell_pos` — for spatial hash queries) ## Files likely affected - `src/UIGrid.h/cpp` — FOV computation optimization - `src/EntityBehavior.cpp` — trigger evaluation in turn processing - Potentially `modules/libtcod-headless/` — if TCOD modification needed

john added a new dependency

2026-03-15 00:32:56 +00:00

#301 grid.step() — turn manager for entity behaviors

john referenced this issue

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

Deduplicate redundant FOV computation #292

john commented

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

Author

Owner

Roadmap context

Part of the Grid & Entity Overhaul Roadmap (docs/GRID_ENTITY_OVERHAUL_ROADMAP.md), Phase 3d (last in behavior system, after grid.step #301 is working).

Reuses the fov_dirty flag from #292. Requires investigation of TCOD's compute_fov() to confirm it bounds work to O(radius^2), not O(grid_size), on large maps. If TCOD iterates the full map, may require modifying the libtcod-headless fork.

## Roadmap context Part of the Grid & Entity Overhaul Roadmap (`docs/GRID_ENTITY_OVERHAUL_ROADMAP.md`), **Phase 3d** (last in behavior system, after grid.step #301 is working). Reuses the `fov_dirty` flag from #292. Requires investigation of TCOD's `compute_fov()` to confirm it bounds work to O(radius^2), not O(grid_size), on large maps. If TCOD iterates the full map, may require modifying the libtcod-headless fork.

john referenced this issue from a commit

2026-04-02 05:36:03 +00:00

Per-entity FOV cache for TARGET trigger optimization, closes #303

john closed this issue

2026-04-02 05:36:03 +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.

Depends on

#301 grid.step() — turn manager for entity behaviors

john/McRogueFace

Reference

john/McRogueFace#303

No description provided.

Rows
Columns