Fix compute_fov() O(n²) performance bug - return None instead of cell list #146

New issue

Closed

opened 2025-11-29 02:10:16 +00:00 by john · 0 comments

john commented

2025-11-29 02:10:16 +00:00

Owner

Problem

Grid.compute_fov() has O(grid_size) performance instead of O(radius²) due to building a Python list of all visible cells by iterating through the entire grid.

Benchmark on 1000×1000 grid:

Current compute_fov(): 15.76ms (iterates 1M cells)
Actual FOV computation + querying 961 cells: 0.21ms

This is a 75x performance penalty from unnecessary list building.

Current Implementation (UIGrid.cpp:1192-1218)

// After computing FOV, iterates ENTIRE grid:
for (int gy = 0; gy < self->data->grid_y; gy++) {
    for (int gx = 0; gx < self->data->grid_x; gx++) {
        if (self->data->isInFOV(gx, gy)) {
            // Build Python tuple for each visible cell...
        }
    }
}

Solution

Change compute_fov() to return None. Users query visibility with is_in_fov(x, y).

# Before (slow)
visible_cells = grid.compute_fov(entity.x, entity.y, radius=15)
for cell in visible_cells:
    ...

# After (fast)  
grid.compute_fov(entity.x, entity.y, radius=15)  # Returns None
if grid.is_in_fov(x, y):  # Query as needed
    ...

Implementation

Remove the list-building loop from py_compute_fov()
Return Py_None instead of result_list
Update any tests/demos that depend on the return value

Notes

The actual TCOD FOV algorithm is O(radius²) and perfectly fast
Rendering doesn't need a list - it checks is_in_fov() per-cell as it draws
See #113 for discussion of better patterns for bulk FOV data access

## Problem `Grid.compute_fov()` has O(grid_size) performance instead of O(radius²) due to building a Python list of all visible cells by iterating through the entire grid. **Benchmark on 1000×1000 grid:** - Current `compute_fov()`: **15.76ms** (iterates 1M cells) - Actual FOV computation + querying 961 cells: **0.21ms** This is a **75x performance penalty** from unnecessary list building. ## Current Implementation (UIGrid.cpp:1192-1218) ```cpp // After computing FOV, iterates ENTIRE grid: for (int gy = 0; gy < self->data->grid_y; gy++) { for (int gx = 0; gx < self->data->grid_x; gx++) { if (self->data->isInFOV(gx, gy)) { // Build Python tuple for each visible cell... } } } ``` ## Solution Change `compute_fov()` to return `None`. Users query visibility with `is_in_fov(x, y)`. ```python # Before (slow) visible_cells = grid.compute_fov(entity.x, entity.y, radius=15) for cell in visible_cells: ... # After (fast) grid.compute_fov(entity.x, entity.y, radius=15) # Returns None if grid.is_in_fov(x, y): # Query as needed ... ``` ## Implementation 1. Remove the list-building loop from `py_compute_fov()` 2. Return `Py_None` instead of `result_list` 3. Update any tests/demos that depend on the return value ## Notes - The actual TCOD FOV algorithm is O(radius²) and perfectly fast - Rendering doesn't need a list - it checks `is_in_fov()` per-cell as it draws - See #113 for discussion of better patterns for bulk FOV data access