john/McRogueFace
1
0
Fork 0
Code Issues 27 Pull requests Projects Releases Wiki Activity

SpatialHash Implementation #115

New issue
Closed
opened 2025-07-12 19:03:00 +00:00 by john · 2 comments
john commented 2025-07-12 19:03:00 +00:00
Owner
Copy link

Implement spatial hashing for efficient queries on 10,000+ entities.

Definition of Done:

  • O(1) average case entity lookup by position
  • Handles entity movement efficiently
  • Scales to 10,000+ entities on 1000x1000 grids
  • Benchmark showing performance improvement

Wiki References:

Implement spatial hashing for efficient queries on 10,000+ entities. **Definition of Done:** - O(1) average case entity lookup by position - Handles entity movement efficiently - Scales to 10,000+ entities on 1000x1000 grids - Benchmark showing performance improvement **Wiki References:** - [Performance and Profiling](https://gamedev.ffwf.net/gitea/john/McRogueFace/wiki/Performance-and-Profiling) - [Performance Optimization Workflow](https://gamedev.ffwf.net/gitea/john/McRogueFace/wiki/Performance-Optimization-Workflow) - [Entity Management](https://gamedev.ffwf.net/gitea/john/McRogueFace/wiki/Entity-Management)
john commented 2025-12-28 04:25:04 +00:00
Author
Owner
Copy link

Benchmark Results (commit fcc0376)

Added tests/benchmarks/entity_scale_benchmark.py to establish baseline metrics.

Current Performance (2,000 entities on 100×100 grid)

Operation Time Scaling
Range Query 0.05ms O(n) - checks all 2,000 entities
N×N Visibility 128ms O(n²) - 0.064ms × 2,000 queries

Cost Per Entity Checked

0.052ms / 2000 entities = 26ns per entity

Extrapolation to 10,000 Entities

  • Single query: 10,000 × 26ns = 0.26ms
  • N×N (all-to-all): 10,000 × 0.26ms = 2,600ms (2.6 seconds)

Projected Gains with SpatialHash

Scenario Current With SpatialHash Speedup
Single query (10k entities) 0.26ms (checks 10k) ~0.005ms (checks ~20) 50×
N×N visibility (10k entities) 2,600ms ~50ms 50×

Mechanism: With bucket size 32 and query radius 15, we check ~16 buckets × ~5 entities = ~80 entities instead of 10,000.

Frame Budget Impact

For 100 AI entities doing visibility queries per frame:

  • Current: 26ms (exceeds 16.67ms budget)
  • With SpatialHash: 0.5ms (3% of budget)

This is the higher-priority optimization for enabling complex AI at scale.

## Benchmark Results (commit fcc0376) Added `tests/benchmarks/entity_scale_benchmark.py` to establish baseline metrics. ### Current Performance (2,000 entities on 100×100 grid) | Operation | Time | Scaling | |-----------|------|---------| | Range Query | 0.05ms | O(n) - checks all 2,000 entities | | N×N Visibility | 128ms | O(n²) - 0.064ms × 2,000 queries | ### Cost Per Entity Checked ``` 0.052ms / 2000 entities = 26ns per entity ``` ### Extrapolation to 10,000 Entities - **Single query**: 10,000 × 26ns = **0.26ms** - **N×N (all-to-all)**: 10,000 × 0.26ms = **2,600ms (2.6 seconds)** ### Projected Gains with SpatialHash | Scenario | Current | With SpatialHash | Speedup | |----------|---------|------------------|---------| | Single query (10k entities) | 0.26ms (checks 10k) | ~0.005ms (checks ~20) | **50×** | | N×N visibility (10k entities) | 2,600ms | ~50ms | **50×** | **Mechanism**: With bucket size 32 and query radius 15, we check ~16 buckets × ~5 entities = ~80 entities instead of 10,000. ### Frame Budget Impact For 100 AI entities doing visibility queries per frame: - **Current**: 26ms (exceeds 16.67ms budget) - **With SpatialHash**: 0.5ms (3% of budget) This is the higher-priority optimization for enabling complex AI at scale.
john closed this issue 2025-12-28 05:44:17 +00:00
john commented 2025-12-28 05:44:30 +00:00
Author
Owner
Copy link

SpatialHash Implementation Complete

Implemented in commit 7d57ce2.

New API

# Query entities within radius using spatial hash
nearby = grid.entities_in_radius(x, y, radius)

Benchmark Results

Entities Query O(n) Query SpatialHash Speedup
100 0.025ms 0.003ms 8.7×
500 0.035ms 0.005ms 7.0×
1,000 0.040ms 0.004ms 9.0×
2,000 0.044ms 0.003ms 16.2×

N×N Visibility (full grid)

Entities O(n) approach SpatialHash Speedup
100 1ms 0ms 20×
500 7ms 0ms 39×
1,000 33ms 1ms 36×
2,000 74ms 1ms 105×

Implementation Details

  • Bucket size: 32 cells (configurable)
  • Uses weak_ptr to avoid keeping deleted entities
  • Automatic hash updates on entity position changes
  • O(1) insert/update, O(k) query where k = nearby entities
## SpatialHash Implementation Complete Implemented in commit 7d57ce2. ### New API ```python # Query entities within radius using spatial hash nearby = grid.entities_in_radius(x, y, radius) ``` ### Benchmark Results | Entities | Query O(n) | Query SpatialHash | Speedup | |----------|------------|-------------------|---------| | 100 | 0.025ms | 0.003ms | 8.7× | | 500 | 0.035ms | 0.005ms | 7.0× | | 1,000 | 0.040ms | 0.004ms | 9.0× | | 2,000 | 0.044ms | 0.003ms | **16.2×** | ### N×N Visibility (full grid) | Entities | O(n) approach | SpatialHash | Speedup | |----------|---------------|-------------|---------| | 100 | 1ms | 0ms | 20× | | 500 | 7ms | 0ms | 39× | | 1,000 | 33ms | 1ms | 36× | | 2,000 | 74ms | 1ms | **105×** | ### Implementation Details - Bucket size: 32 cells (configurable) - Uses weak_ptr to avoid keeping deleted entities - Automatic hash updates on entity position changes - O(1) insert/update, O(k) query where k = nearby entities
Sign in to join this conversation.
No Branch/Tag specified
Branches Tags
master
rogueliketutorial25
alpha_presentable
alpha_streamline_2
alpha_streamline_1
interpreter_mode
grid_entity_integration
reprs_and_member_names
break_up_ui_h
standardize_font_handling
standardize_vector_handling
standardize_color_handling
standardize_texture_handling
raii_pyobjects
rebase-for-7DRL_Feb-2024
engjam_uicollection
engjam_ui_overhaul
No results found.
Labels
Clear labels   
Alpha Release Requirement

This issue is a blocker to 0.1 Alpha release of McRogueFace.

  
Bugfix

   
Demo Target

Functionality to demonstrate; Depends on new features, but this issue isn't for writing them.

  
Documentation

   
Major Feature

Significant time and effort required.

  
Minor Feature

Some effort required to create or overhaul functionality.

  
priority:tier1-active

Current development focus - critical path to v1.0

  
priority:tier2-foundation

Important foundation work - not blocking v1.0

  
priority:tier3-future

Future features - deferred until after v1.0

  
priority:tier4-deferred

   
Refactoring & Cleanup

no new functionality, just improving the codebase.

  
system:animation

Animation and property interpolation

  
system:documentation

Documentation infrastructure

  
system:grid

Grid system and spatial containers

  
system:input

Input handling and events

  
system:performance

Performance optimization and profiling

  
system:python-binding

Python/C++ binding layer

  
system:rendering

Rendering pipeline and visuals

  
system:ui-hierarchy

UI component hierarchy and composition

  
Tiny Feature

quick and easy - a few lines or with little interconnection around the codebase

  
workflow:blocked

Blocked by other work - waiting on dependencies

  
workflow:needs-benchmark

Needs performance testing and benchmarks

  
workflow:needs-documentation

Needs documentation before or after implementation

No labels
Alpha Release Requirement
Bugfix
Demo Target
Documentation
Major Feature
Minor Feature
priority:tier1-active
priority:tier2-foundation
priority:tier3-future
priority:tier4-deferred
Refactoring & Cleanup
system:animation
system:documentation
system:grid
system:input
system:performance
system:python-binding
system:rendering
system:ui-hierarchy
Tiny Feature
workflow:blocked
workflow:needs-benchmark
workflow:needs-documentation
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
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#115
No description provided.