Spatial Hash Theory
In real-time multiplayer systems, efficiently determining which players should receive updates from which entities is a fundamental challenge. Entangle's Area of Interest (AOI) Spatial Hash solves this by partitioning the game world into a grid-based spatial hash structure, giving O(1) lookups and efficient update distribution.
This page covers the theory, data structures, and design trade-offs behind the AOISpatialHash class. The implementation lives at EntangleServer/Modules/Lobby/AreaOfInterest/AOISpatialHash.cs, with supporting types in AOIGroup.cs and AOIRealiableGroup.cs.
The Core Problem
In a multiplayer environment with hundreds or thousands of entities, there are two ways to distribute updates:
- Naive approach - broadcast every update to all players. Bandwidth grows as O(n^2), which is unscalable for large player counts.
- Spatial approach - only send updates to nearby players. Bandwidth grows as O(n), which scales linearly.
By dividing the world into spatial regions, the system can:
- Quickly determine which region an entity belongs to.
- Identify which players are in relevant regions.
- Distribute updates only to those players.
Core Data Structure: 2D Spatial Hash Grid
The heart of the AOI system is a 2D array that represents a spatial hash grid:
private AOIGroup[,] AOICells;
This array divides the game world into a grid of cells, where each cell (AOIGroup) manages a subset of players and their network updates.
World Space (e.g., 1000x1000 units)
┌─────────────────────────────────────┐
│ │
│ ┌─────┬─────┬─────┬─────┬─────┐ │
│ │ 0,0 │ 1,0 │ 2,0 │ 3,0 │ 4,0 │ │
│ ├─────┼─────┼─────┼─────┼─────┤ │
│ │ 0,1 │ 1,1 │ 2,1 │ 3,1 │ 4,1 │ │
│ ├─────┼─────┼─────┼─────┼─────┤ │
│ │ 0,2 │ 1,2 │ 2,2 │ 3,2 │ 4,2 │ │
│ ├─────┼─────┼─────┼─────┼─────┤ │
│ │ 0,3 │ 1,3 │ 2,3 │ 3,3 │ 4,3 │ │
│ └─────┴─────┴─────┴─────┴─────┘ │
│ │
└─────────────────────────────────────┘
Each cell = AOIGroup instance
Grid dimensions = (width / cellSize) x (height / cellSize)
Cell size is the spatial dimension of each cell:
- Smaller cells give more granular partitioning (more cells, more precision).
- Larger cells give coarser partitioning (fewer cells, less precision).
Grid dimensions are calculated from world size and cell size:
- Grid width = ceil(World Width / Cell Size)
- Grid height = ceil(World Height / Cell Size)
Using a 2D array gives direct [x, z] access, O(1) lookup time, and excellent spatial locality (cache-friendly access patterns).
Supporting data structures
Several complementary structures manage the spatial hash alongside the grid:
// Active cells that currently have participants
private readonly List<AOIGroup> ActiveCells = new List<AOIGroup>();
// Custom groups created by players (e.g., team channels, private groups)
private readonly List<AOIGroup> ActiveGroups = new List<AOIGroup>();
// All players in the room
private readonly List<FNEPlayer> fNEPlayers = new List<FNEPlayer>();
// Global group for when AOI is inactive (low player count)
private readonly AOIGroup AOIGlobal = new AOIGroup();
// Reliable data delivery group (always active)
private readonly AOIRealiableGroup AOIGroupReliable = new AOIRealiableGroup();
Position to Grid Index Mapping
Converting a world position to a grid index uses a simple hash function, with clamping so the result always lands on a valid cell:
private (int, int) GetIndex(TransformLite position)
{
int x = Math.Clamp((int)((position.Position.X - originX) / cellSize), 0, gridWidth - 1);
int z = Math.Clamp((int)((position.Position.Z - originZ) / cellSize), 0, gridHeight - 1);
return (x, z);
}
Example:
Player at world position (150, 0, 250)
Cell size: 100 units
Grid origin: (-500, -500)
Calculation:
x = (150 - (-500)) / 100 = 6.5 -> clamped to 6
z = (250 - (-500)) / 100 = 7.5 -> clamped to 7
Result: Cell [6, 7]
The clamp keeps indices within [0, gridWidth - 1] and [0, gridHeight - 1], so positions at or beyond the world boundary still map to a valid cell instead of throwing or producing a negative index.
Player Assignment and Cell Management
When a player joins or moves, their position is hashed to a grid index and they are added to that cell's participant list. Multiple players can occupy the same cell:
┌─────┬─────┬─────┐
│ │ │ │
├─────┼─────┼─────┤
│ P1 │ P2 │ │ <- Players P1 and P2 in cell [1,1]
├─────┼─────┼─────┤
│ │ P3 │ P4 │ <- Players P3 and P4 in different cells
└─────┴─────┴─────┘
All players in a cell receive updates from entities in that cell and its neighbors.
Lazy cell creation
Cells are created on demand when the first player enters them, rather than allocating the full grid up front:
var cell = AOICells[x, z];
if (cell == null)
{
var aOIGroup = new AOIGroup();
aOIGroup.Subscribe = SubscribeToSpatialGrid;
aOIGroup.UnSubscribe = UnSubscribeToSpatialGrid;
AOICells[x, z] = aOIGroup;
aOIGroup.SetIndexes(x, z);
}
Benefits:
- Memory efficient - only active cells consume resources.
- No initialization overhead for unused areas.
- Automatic cleanup when cells become empty.
Update Distribution Strategy
When an entity updates, the system distributes the update to:
- Own cell - all players in the entity's cell.
- Neighboring cells - players in adjacent cells, for smooth boundaries.
- LOD cells - players in more distant cells, at reduced frequency.
Moore neighborhood (immediate neighbors)
The 8-cell Moore neighborhood ensures players near cell boundaries still receive relevant updates:
┌─────┬─────┬─────┬─────┐
│ N │ N │ N │ │ <- Neighbors (depth 1)
├─────┼─────┼─────┼─────┤
│ N │ E │ N │ │ <- Entity (E) in center
├─────┼─────┼─────┼─────┤
│ N │ N │ N │ │ <- 8 neighbors receive updates
└─────┴─────┴─────┴─────┘
Neighbor directions:
NW N NE
W E E
SW S SE
Total: 9 cells (1 own + 8 neighbors)
This matters because two players can be physically close but sit in different cells:
┌─────────┬─────────┐
│ │ │
│ Cell A │ Cell B │
│ P1 │ P2 │ <- P1 and P2 are close but in different cells
│ │ │
└─────────┴─────────┘
Without neighbor updates: P1 won't see P2's updates, and vice versa.
With neighbor updates: both receive each other's updates, giving a smooth experience across cell boundaries.
Level of Detail (LOD)
For performance, cells beyond the immediate neighborhood receive updates at reduced frequency:
// Immediate neighbors (always updated)
EnqueueEntityDataInNeighbouringCells(cell.Index_X, cell.Index_Z, operationData);
// Depth 2 neighbors (every 2 ticks)
if (LodLevel > 0 && counterLod % 2 == 0)
EnqueueEntityDataInNeighbouringCellsByDepth(x, z, 2, operationData);
// Depth 3 neighbors (every 4 ticks)
if (LodLevel > 1 && counterLod % 4 == 0)
EnqueueEntityDataInNeighbouringCellsByDepth(x, z, 3, operationData);
LOD Distribution (depth 2):
┌─────┬─────┬─────┬─────┬─────┐
│ LOD │ │ │ │ LOD │ <- Depth 2 corners
├─────┼─────┼─────┼─────┼─────┤
│ │ N │ N │ N │ │ <- Depth 1 neighbors
├─────┼─────┼─────┼─────┼─────┤
│ │ N │ E │ N │ │ <- Entity (E)
├─────┼─────┼─────┼─────┼─────┤
│ │ N │ N │ N │ │
├─────┼─────┼─────┼─────┼─────┤
│ LOD │ │ │ │ LOD │
└─────┴─────┴─────┴─────┴─────┘
Update frequencies:
- Depth 1 (immediate neighbors): every tick
- Depth 2: every 2 ticks
- Depth 3: every 4 ticks
LOD reduces network traffic for distant entities, provides smoother performance scaling, and is configurable via LodLevel.
Data flow
Entity Update Arrives
│
▼
┌───────────────────────┐
│ OnEntityDataArrived() │
└───────────────────────┘
│
├─→ Is Presenter? ──Yes──→ Broadcast to ALL active cells
│
└─→ No ──→ Get Cell Index from Position
│
▼
┌──────────────┐
│ GetIndex() │
└──────────────┘
│
▼
┌──────────────┐
│ Find/Create │
│ AOIGroup │
└──────────────┘
│
▼
┌──────────────────────┐
│ EnqueueDataInRelevant│
│ Lod() │
└──────────────────────┘
│
┌──────────┴──────────┐
│ │
▼ ▼
┌──────────────┐ ┌──────────────────┐
│ Own Cell │ │ 8 Neighbors │
│ Enqueue │ │ + LOD Cells │
└──────────────┘ └──────────────────┘
│ │
└──────────┬──────────┘
│
▼
┌──────────────────┐
│ AOIGroup.Tick() │
│ Batch & Send │
└──────────────────┘
Dual-Mode Architecture
The system adapts based on player count, switching between two modes.
Mode 1: Global broadcast mode
Active while player count is at or below the activation threshold (default: 10).
┌─────────────────────────────────────┐
│ Global Broadcast Mode │
│ │
│ ┌─────────────────────────────┐ │
│ │ Global Group │ │
│ │ ┌─────┬─────┬─────┬─────┐ │ │
│ │ │ P1 │ P2 │ P3 │ P4 │...│ │ │
│ │ └─────┴─────┴─────┴─────┘ │ │
│ └─────────────────────────────┘ │
│ │
│ All players receive all updates │
└─────────────────────────────────────┘
Characteristics:
- Single group contains all players.
- All updates broadcast to everyone.
- No spatial partitioning overhead - optimal for small groups.
Mode 2: Spatial hash mode
Active once player count exceeds the activation threshold.
┌─────────────────────────────────────┐
│ Spatial Hash Mode │
│ │
│ ┌─────┬─────┬─────┬─────┐ │
│ │ P1 │ P2 │ │ │ │
│ ├─────┼─────┼─────┼─────┤ │
│ │ │ P3 │ P4 │ │ │
│ ├─────┼─────┼─────┼─────┤ │
│ │ P5 │ │ P6 │ P7 │ │
│ └─────┴─────┴─────┴─────┘ │
│ │
│ Players distributed across cells │
│ Updates only sent to relevant │
│ spatial regions │
└─────────────────────────────────────┘
Characteristics:
- Players partitioned by location.
- Updates distributed spatially.
- Scales linearly with player count.
Mode transition
When player count crosses the threshold, the system switches modes: increasing above threshold clears the global group and assigns players to cells; decreasing below threshold clears the cells and adds everyone back to the global group.
Advanced Features
Custom groups
Players can form groups independent of spatial location (team channels, private groups, and similar use cases):
Spatial Grid Custom Groups
┌─────┬─────┬─────┐ ┌──────────────┐
│ P1 │ P2 │ │ │ Team Alpha │
├─────┼─────┼─────┤ │ P1, P3, P5 │
│ P3 │ P4 │ │ └──────────────┘
├─────┼─────┼─────┤ ┌──────────────┐
│ P5 │ │ P6 │ │ Team Beta │
└─────┴─────┴─────┘ │ P2, P4 │
└──────────────┘
Typical use cases: team-based gameplay, private channels, role-based groups, special event groups.
Presenter broadcasting
Entities marked as presenters (speakers, streamers, event hosts) broadcast to every active cell instead of just their own neighborhood:
if (entity.IsPresenter)
{
// Broadcast to ALL active cells
for (int i = ActiveCells.Count - 1; i >= 0; i--)
{
EnqueueDataInRelevantLod(ActiveCells[i], operationData);
}
}
This is useful for keynote speakers, event hosts, important announcements, and other global-visibility requirements.
Reliable data channel
AOIGroupReliable is a separate channel that is always active and contains all players, used for critical state changes, important events, and system messages that must reach everyone regardless of spatial partitioning.
Performance Analysis
Time complexity
| Operation | Complexity | Notes |
|---|---|---|
| Position to index | O(1) | Simple arithmetic hash |
| Cell lookup | O(1) | Direct 2D array access |
| Add player | O(1) | Array access + list append |
| Remove player | O(1) | Array access + list remove |
| Update distribution | O(1) to O(k) | k = number of neighbor cells (typically 8-24) |
| Cell creation | O(1) | Instantiate and assign |
Space complexity
| Component | Complexity | Notes |
|---|---|---|
| Grid storage | O(W x H) | W = grid width, H = grid height, but cells are created lazily |
| Active cells | O(A) | A = active cells, typically much less than W x H |
| Players | O(P) | P = number of players |
| Total | O(W x H + P) | Dominated by grid size or player count |
Memory efficiency
Lazy cell creation means only populated cells consume memory - a sparse grid representation with automatic cleanup as cells empty out. Memory scales with active areas, not total world size.
World: 1000x1000 units
Cell Size: 100 units
Grid: 10x10 = 100 potential cells
Scenario 1: All cells active
Memory: 100 cells x cell overhead
Scenario 2: Only 5 cells active (typical)
Memory: 5 cells x cell overhead
Savings: 95% memory reduction
Design Decisions and Trade-offs
Why a 2D array over alternatives?
| Aspect | 2D Array | Hash Table | Quadtree | Octree |
|---|---|---|---|---|
| Lookup speed | O(1) | O(1) avg | O(log n) | O(log n) |
| Memory overhead | Fixed | Variable | Variable | Variable |
| Spatial locality | Excellent | Poor | Good | Good |
| Neighbor access | O(1) | O(k) | O(log n) | O(log n) |
| Implementation | Simple | Medium | Complex | Complex |
| Predictability | High | Medium | Low | Low |
Rationale:
- Predictable performance - O(1) lookups are critical for real-time systems, with no worst-case degradation and consistent frame times.
- Spatial locality - neighboring cells are adjacent in memory, giving cache-friendly access patterns.
- Simplicity - fewer edge cases, easier to understand, maintain, and debug.
- Fixed memory footprint - predictable memory usage, which matters for server capacity planning.
- Efficient neighbor access - direct array indexing for neighbors, with no traversal needed for update distribution.
When to use alternatives
- Hash table - when world size is extremely large and sparsity is very high.
- Quadtree / octree - when variable cell sizes are needed, or the entity distribution is highly non-uniform.
Code Example: Complete Flow
Initialization
// Initialize a 1000x1000 world with 100-unit cells
aoiSpatialHash.Init(
cellSize: 100f,
width: 1000,
height: 1000,
activationCount: 10,
lodLevel: 2,
roomName: "MainRoom",
roomId: "room_123",
presenterInGroupCast: true
);
// Creates a 10x10 grid (1000/100 = 10)
// Grid: AOICells[10, 10]
Player movement
// Player moves from (150, 0, 250) to (350, 0, 450)
// Old cell: [6, 7]
// New cell: [8, 9]
aoiSpatialHash.OnPlayerTeleport(player);
// Internally:
// 1. Calculate new cell index: GetIndex(newPosition) -> (8, 9)
// 2. Remove from old cell: AOICells[6, 7].RemoveParticipant(player)
// 3. Add to new cell: AOICells[8, 9].AddParticipant(player)
Entity update
// Entity at position (250, 0, 350) sends update
// Cell index: [7, 8]
aoiSpatialHash.OnEntityDataArrived(entity, updateData);
// Distribution:
// 1. Enqueue in own cell: AOICells[7, 8]
// 2. Enqueue in 8 neighbors: [6,7], [6,8], [6,9], [7,7], [7,9], [8,7], [8,8], [8,9]
// 3. Optionally enqueue in LOD cells (depth 2, 3)
// 4. Each cell batches and sends to its participants
Scalability Characteristics
Naive broadcast bandwidth grows as O(P^2) where P is the number of players. Spatial hash bandwidth grows as O(P x U), where U is the average number of updates per player - effectively constant, based on cell size. The result is linear scaling instead of quadratic, with constant performance per player as player count grows into the thousands.
Real-world applications
- MMO games - large persistent worlds with thousands of concurrent players.
- Virtual events - conferences, concerts, exhibitions; spatial audio distribution and attendee interaction management.
- Social platforms - virtual spaces and metaverses, proximity-based interactions, dynamic group formation.
- Real-time collaboration - shared workspaces, multi-user editors, collaborative design tools.
- Simulation systems - multi-agent simulations, IoT network management, distributed sensor networks.
Typical configuration
- Cell size: 50-200 units (game-dependent).
- Activation threshold: 10-20 players.
- LOD levels: 2-3 levels.
- Update frequency: 10-60 Hz.