nx_aoi_grid.nx source
↩ module page · 352 lines · 13809 B
1// nx_aoi_grid.nx -- area-of-interest spatial grid for open-world culling.
2//
3// Per the Agar.io/Slither.io lesson (reverse-engineered protocols at
4// ClitherProject + Diep.io / Krunker community wikis): the single
5// biggest bandwidth saver for open-world multiplayer is to ONLY stream
6// entities within the player's view radius. Naive "broadcast all
7// entities to all players" scales as O(N^2) in players-times-entities;
8// area-of-interest culling brings it to O(N * view_density).
9//
10// This primitive provides:
11// - 2D cell-bucket grid over Q14-fixed-point world coordinates
12// - insert / remove / query_radius operations
13// - returns entity IDs within radius for a (player_x, player_z) query
14//
15// Use case: caller maintains an "entity table" keyed by entity ID; the
16// grid is the spatial index that lets a per-player streamer ask
17// "which entities should this player see?" 60 times per second.
18//
19// Bandwidth math (from genre-bench doc):
20// Naive: 100 entities * 60 Hz * 30 B/entity = 180 KB/s -- 25x over
21// the 7 KB/s dial-up ceiling.
22// With AOI (20 in-view): 20 * 60 * 30 = 36 KB/s. Still over.
23// With AOI + nx_state_delta_codec (4 B/entity typical):
24// 20 * 60 * 4 = 4.8 KB/s. FITS UNDER 7 KB/s.
25//
26// Storage layout (i64 cells in flat block + raw bucket bytes):
27// h[0] = cell_size_q14 (size of one cell side in Q14 metres)
28// h[1] = grid_dim (cells per axis; total cells = grid_dim^2)
29// h[2] = origin_x_q14 (world coord of cell (0,0) lower edge)
30// h[3] = origin_z_q14
31// h[4] = bucket_capacity (max entities per cell)
32// h[5] = bucket_storage (i64 ptr; layout below)
33//
34// Per cell layout (i64 cells):
35// [0] = count of entities in cell
36// [1..1+3*cap] = (id, x_q14, z_q14) triples
37// Cell stride = 1 + 3 * bucket_capacity.
38//
39// Source references (open):
40// - Slither.io protocol: ClitherProject/Slither.io-Protocol (GitHub)
41// - Diep.io / Agar.io community wikis
42// - AoE 2001 GDC "1500 Archers" (informit) -- bandwidth lessons
43// - WoW area-of-interest server design (Blizzard architect blog circa 2007)
44//
45// genealogy_id: agar_io_aoi_2015 + slither_io_protocol + wow_aoi_2007
46// lineage_id: spatial_culling_for_open_world_multiplayer
47
48// nx_safety_envelope:
49// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
50// sil_target: SIL1
51// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
52// verdict: NOT_YET_EVALUATED
53
54import "nx_syscalls.nx"
55import "nx_tier.nx"
56const NX_MAGIC_16384: i64 = 16384
57const NX_MAGIC_9999: i64 = 9999
58const NX_MAGIC_2000: i64 = 2000
59
60const NX_AOI_HDR_CELL_SIZE: nx_int = 0
61const NX_AOI_HDR_GRID_DIM: nx_int = 1
62const NX_AOI_HDR_ORIGIN_X: nx_int = 2
63const NX_AOI_HDR_ORIGIN_Z: nx_int = 3
64const NX_AOI_HDR_BUCKET_CAP: nx_int = 4
65const NX_AOI_HDR_STORAGE: nx_int = 5
66const NX_AOI_HDR_SIZE: nx_int = 6
67
68// ===== Bucket access helpers ========================================
69
70func _aoi_cell_stride(g: *i64) -> nx_int {
71 let cap: nx_int = g[NX_AOI_HDR_BUCKET_CAP]
72 return 1 + 3 * cap
73}
74
75func _aoi_cell_ptr(g: *i64, cx: nx_int, cz: nx_int) -> *i64 {
76 let dim: nx_int = g[NX_AOI_HDR_GRID_DIM]
77 let stride: nx_int = _aoi_cell_stride(g)
78 let cell_index: nx_int = cz * dim + cx
79 let storage: *i64 = (g[NX_AOI_HDR_STORAGE]) as *i64
80 let base: i64 = storage as i64
81 return (base + cell_index * stride * 8) as *i64
82}
83
84// ===== Coordinate transforms ========================================
85
86// Convert world Q14 coord to integer cell coord on this axis. Returns
87// (-1) if out of grid bounds.
88func _aoi_to_cell(g: *i64, world_q14: nx_int, axis: nx_int) -> nx_int {
89 let dim: nx_int = g[NX_AOI_HDR_GRID_DIM]
90 let cell_size: nx_int = g[NX_AOI_HDR_CELL_SIZE]
91 var origin: nx_int = 0
92 if axis == 0 { origin = g[NX_AOI_HDR_ORIGIN_X] }
93 else { origin = g[NX_AOI_HDR_ORIGIN_Z] }
94
95 let rel: nx_int = world_q14 - origin
96 if rel < 0 { return -1 }
97 let c: nx_int = rel / cell_size
98 if c >= dim { return -1 }
99 return c
100}
101
102// ===== Allocation ====================================================
103
104func nx_aoi_grid_new(
105 cell_size_q14: nx_int,
106 grid_dim: nx_int,
107 origin_x_q14: nx_int,
108 origin_z_q14: nx_int,
109 bucket_cap: nx_int
110) -> *i64 {
111 if cell_size_q14 <= 0 { return 0 as *i64 }
112 if grid_dim <= 0 { return 0 as *i64 }
113 if bucket_cap <= 0 { return 0 as *i64 }
114
115 let g: *i64 = (sys_mmap(NX_AOI_HDR_SIZE * 8)) as *i64
116 let stride: nx_int = 1 + 3 * bucket_cap
117 let num_cells: nx_int = grid_dim * grid_dim
118 let storage: *i64 = (sys_mmap(num_cells * stride * 8)) as *i64
119
120 var i: nx_int = 0
121 while i < num_cells * stride {
122 storage[i] = 0
123 i = i + 1
124 }
125
126 g[NX_AOI_HDR_CELL_SIZE] = cell_size_q14
127 g[NX_AOI_HDR_GRID_DIM] = grid_dim
128 g[NX_AOI_HDR_ORIGIN_X] = origin_x_q14
129 g[NX_AOI_HDR_ORIGIN_Z] = origin_z_q14
130 g[NX_AOI_HDR_BUCKET_CAP] = bucket_cap
131 g[NX_AOI_HDR_STORAGE] = storage as i64
132 return g
133}
134
135// ===== Insert / Remove =============================================
136
137// Returns 1 on success, 0 if entity is outside grid bounds, -1 if the
138// cell bucket is at capacity (caller should resize or warn).
139func nx_aoi_grid_insert(g: *i64, id: i64, x_q14: nx_int, z_q14: nx_int) -> nx_int {
140 if (g as i64) == 0 { return 0 }
141 let cx: nx_int = _aoi_to_cell(g, x_q14, 0)
142 let cz: nx_int = _aoi_to_cell(g, z_q14, 1)
143 if cx < 0 { return 0 }
144 if cz < 0 { return 0 }
145 let cell: *i64 = _aoi_cell_ptr(g, cx, cz)
146 let cap: nx_int = g[NX_AOI_HDR_BUCKET_CAP]
147 let count: nx_int = cell[0]
148 if count >= cap { return -1 }
149 cell[1 + count * 3 + 0] = id
150 cell[1 + count * 3 + 1] = x_q14
151 cell[1 + count * 3 + 2] = z_q14
152 cell[0] = count + 1
153 return 1
154}
155
156// Returns 1 on success, 0 if not found. Linear scan within the cell
157// since bucket sizes are small (max ~64 typical).
158func nx_aoi_grid_remove(g: *i64, id: i64, x_q14: nx_int, z_q14: nx_int) -> nx_int {
159 if (g as i64) == 0 { return 0 }
160 let cx: nx_int = _aoi_to_cell(g, x_q14, 0)
161 let cz: nx_int = _aoi_to_cell(g, z_q14, 1)
162 if cx < 0 { return 0 }
163 if cz < 0 { return 0 }
164 let cell: *i64 = _aoi_cell_ptr(g, cx, cz)
165 let count: nx_int = cell[0]
166 var i: nx_int = 0
167 while i < count {
168 if cell[1 + i * 3 + 0] == id {
169 // Swap last entry into this slot to keep packing tight.
170 let last: nx_int = count - 1
171 if i != last {
172 cell[1 + i * 3 + 0] = cell[1 + last * 3 + 0]
173 cell[1 + i * 3 + 1] = cell[1 + last * 3 + 1]
174 cell[1 + i * 3 + 2] = cell[1 + last * 3 + 2]
175 }
176 cell[0] = last
177 return 1
178 }
179 i = i + 1
180 }
181 return 0
182}
183
184// ===== Radius query ================================================
185//
186// Fills `out_ids` with up to `out_cap` entity IDs whose (x,z) position
187// is within `radius_q14` of (qx_q14, qz_q14). Returns the number of
188// hits written. Order is implementation-defined.
189//
190// Algorithm: compute cell-bounding-box of (q +/- radius), iterate
191// each candidate cell's bucket, distance-check each entry, emit if
192// within radius. Distance test is in Q14-squared units to avoid
193// computing sqrt.
194
195func nx_aoi_grid_query_radius(
196 g: *i64,
197 qx_q14: nx_int, qz_q14: nx_int, radius_q14: nx_int,
198 out_ids: *i64, out_cap: nx_int
199) -> nx_int {
200 if (g as i64) == 0 { return 0 }
201 if radius_q14 < 0 { return 0 }
202 if out_cap <= 0 { return 0 }
203
204 let cell_size: nx_int = g[NX_AOI_HDR_CELL_SIZE]
205 let dim: nx_int = g[NX_AOI_HDR_GRID_DIM]
206 let origin_x: nx_int = g[NX_AOI_HDR_ORIGIN_X]
207 let origin_z: nx_int = g[NX_AOI_HDR_ORIGIN_Z]
208
209 // Cell-bounding-box of the radius circle.
210 let min_x: nx_int = qx_q14 - radius_q14 - origin_x
211 let max_x: nx_int = qx_q14 + radius_q14 - origin_x
212 let min_z: nx_int = qz_q14 - radius_q14 - origin_z
213 let max_z: nx_int = qz_q14 + radius_q14 - origin_z
214
215 var cx_lo: nx_int = min_x / cell_size
216 var cx_hi: nx_int = max_x / cell_size
217 var cz_lo: nx_int = min_z / cell_size
218 var cz_hi: nx_int = max_z / cell_size
219
220 if cx_lo < 0 { cx_lo = 0 }
221 if cz_lo < 0 { cz_lo = 0 }
222 if cx_hi >= dim { cx_hi = dim - 1 }
223 if cz_hi >= dim { cz_hi = dim - 1 }
224
225 // Distance test in Q14-squared. rs = radius_q14 * radius_q14.
226 let rs: i64 = (radius_q14 as i64) * (radius_q14 as i64)
227 var out_n: nx_int = 0
228
229 var cz: nx_int = cz_lo
230 while cz <= cz_hi {
231 var cx: nx_int = cx_lo
232 while cx <= cx_hi {
233 let cell: *i64 = _aoi_cell_ptr(g, cx, cz)
234 let count: nx_int = cell[0]
235 var i: nx_int = 0
236 while i < count {
237 let id: i64 = cell[1 + i * 3 + 0]
238 let ex: nx_int = cell[1 + i * 3 + 1]
239 let ez: nx_int = cell[1 + i * 3 + 2]
240 let dx: i64 = (ex - qx_q14) as i64
241 let dz: i64 = (ez - qz_q14) as i64
242 let d2: i64 = dx * dx + dz * dz
243 if d2 <= rs {
244 if out_n < out_cap {
245 out_ids[out_n] = id
246 out_n = out_n + 1
247 }
248 }
249 i = i + 1
250 }
251 cx = cx + 1
252 }
253 cz = cz + 1
254 }
255 return out_n
256}
257
258// ===== Self-test ====================================================
259
260func main() -> i64 {
261 let Q: nx_int = NX_MAGIC_16384 // Q14 unit (1 metre)
262 let CELL: nx_int = 10 * Q // 10m cells
263 let DIM: nx_int = 32 // 32x32 grid = 320m x 320m world
264 let CAP: nx_int = 64
265
266 let g: *i64 = nx_aoi_grid_new(CELL, DIM, 0, 0, CAP)
267 if (g as i64) == 0 { return __syscall(93, 1, 0, 0, 0, 0, 0) }
268
269 // T1: insert single entity at (50m, 50m), query small radius around
270 // it -- must return the entity.
271 nx_aoi_grid_insert(g, 42, 50 * Q, 50 * Q)
272 let out: *i64 = (sys_mmap(64 * 8)) as *i64
273 let n1: nx_int = nx_aoi_grid_query_radius(g, 50 * Q, 50 * Q, 5 * Q, out, 64)
274 if n1 != 1 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
275 if out[0] != 42 { return __syscall(93, 11, 0, 0, 0, 0, 0) }
276
277 // T2: query OUTSIDE the entity's radius -- must return zero hits.
278 let n2: nx_int = nx_aoi_grid_query_radius(g, 200 * Q, 200 * Q, 5 * Q, out, 64)
279 if n2 != 0 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
280
281 // T3: insert 100 entities in a 10x10 grid spaced 5m apart, query a
282 // 7m radius around (25m, 25m) -- should hit ~5 entities (the
283 // ones within 7m euclidean of (25,25)).
284 var k: nx_int = 0
285 while k < 100 {
286 let row: nx_int = k / 10
287 let col: nx_int = k % 10
288 nx_aoi_grid_insert(g, 1000 + k, col * 5 * Q, row * 5 * Q)
289 k = k + 1
290 }
291 let n3: nx_int = nx_aoi_grid_query_radius(g, 25 * Q, 25 * Q, 7 * Q, out, 64)
292 // Entities within 7m of (25,25): (25,25), (20,25), (30,25), (25,20),
293 // (25,30), plus diagonals (20,20)=sqrt(50)=7.07 (just over),
294 // (30,30)=7.07. So at least 5.
295 if n3 < 5 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
296 if n3 > 9 { return __syscall(93, 31, 0, 0, 0, 0, 0) }
297
298 // T4: query within an empty corner returns 0.
299 let n4: nx_int = nx_aoi_grid_query_radius(g, 300 * Q, 300 * Q, 5 * Q, out, 64)
300 if n4 != 0 { return __syscall(93, 40, 0, 0, 0, 0, 0) }
301
302 // T5: insert + remove round-trips.
303 nx_aoi_grid_insert(g, NX_MAGIC_9999, 100 * Q, 100 * Q)
304 let n5a: nx_int = nx_aoi_grid_query_radius(g, 100 * Q, 100 * Q, 1 * Q, out, 64)
305 var found: nx_int = 0
306 var i: nx_int = 0
307 while i < n5a {
308 if out[i] == NX_MAGIC_9999 { found = 1 }
309 i = i + 1
310 }
311 if found != 1 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
312 if nx_aoi_grid_remove(g, NX_MAGIC_9999, 100 * Q, 100 * Q) != 1 { return __syscall(93, 51, 0, 0, 0, 0, 0) }
313 let n5b: nx_int = nx_aoi_grid_query_radius(g, 100 * Q, 100 * Q, 1 * Q, out, 64)
314 var still_found: nx_int = 0
315 var j: nx_int = 0
316 while j < n5b {
317 if out[j] == NX_MAGIC_9999 { still_found = 1 }
318 j = j + 1
319 }
320 if still_found != 0 { return __syscall(93, 52, 0, 0, 0, 0, 0) }
321
322 // T6: BANDWIDTH PROOF. Place 1000 entities scattered uniformly
323 // across the 320m grid (only ~256 fit -- there are 32*32 = 1024
324 // cells but bucket cap = 64 per cell, so ~1000 fits if spread).
325 // Query a 50m radius from world center. AOI cull should return
326 // a small subset (entities within ~50m), not all 1000.
327 let g2: *i64 = nx_aoi_grid_new(CELL, DIM, 0, 0, CAP)
328 var p: nx_int = 0
329 while p < 500 {
330 // Spread entities roughly uniformly via a simple hash.
331 let px: nx_int = (p * 71) % 320
332 let pz: nx_int = (p * 137) % 320
333 nx_aoi_grid_insert(g2, NX_MAGIC_2000 + p, px * Q, pz * Q)
334 p = p + 1
335 }
336 let n6: nx_int = nx_aoi_grid_query_radius(g2, 160 * Q, 160 * Q, 50 * Q, out, 64)
337 // 500 entities over 320x320 = 0.0049 per square metre. Circle of
338 // r=50 has area ~7854 sqm. Expected hits ~38. Verify we got a
339 // small subset and not the full 500.
340 if n6 <= 0 { return __syscall(93, 60, 0, 0, 0, 0, 0) }
341 if n6 > 100 { return __syscall(93, 61, 0, 0, 0, 0, 0) }
342
343 // T7: NO false positives. Verify every returned hit's actual
344 // position (we'd need a side table; for the smoke we trust that
345 // since insert recorded (id, x, z) into the cell, the distance
346 // check in query_radius is the same data. The strong test here
347 // is: query r=1m around an empty point returns 0.
348 let n7: nx_int = nx_aoi_grid_query_radius(g2, 999 * Q, 999 * Q, 1 * Q, out, 64)
349 if n7 != 0 { return __syscall(93, 70, 0, 0, 0, 0, 0) }
350
351 return 0
352}