A spatial hash can still have a quadratic build step

A spatial hash can reduce how many possible neighbors each agent examines. That does not automatically make the whole update linear. The cost of building the index still matters, especially when every simulation step must wait for it.

I traced the public Unity Flying AI Swarm project from FixedUpdate to its flocking job. The README describes an O(N) spatial grid and reports a 90+ FPS result with 1,000 agents. The source contains a useful distinction: neighbor lookup is local, while the current grid-build job sorts its input with nested bubble-sort loops.

Follow one fixed update

When agents are active, FlockingSystem.FixedUpdate completes the previous job chain, copies live entity data into a native buffer, and schedules the next update. The spatial-grid builder receives _flockingData, a NativeArray allocated to _maxEntities. The flocking job is scheduled for _currentEntityCount agents and depends on the grid-build handle.

That dependency makes the order important. The per-agent flocking work can run in parallel, but it cannot begin until the grid has been built. A serial preprocessing stage is therefore part of the frame’s critical path.

The grid builder sorts the whole buffer

BuildSpatialHashJob first calculates a cell hash for each entry. It then sorts the hashes and their corresponding indices with two nested loops. The code labels this a bubble sort for small datasets; the loop bounds perform C × (C − 1) / 2 comparisons for a buffer of length C.

The field’s code default is 500 entries. At that capacity, one grid build runs 124,750 comparison iterations before grouping the sorted hashes into cell ranges. That count comes directly from the loop bounds. It is not a timing measurement, and the actual buffer length can be changed by serialized configuration.

The hash map can still make neighbor lookup cheaper by limiting each agent to nearby cells and then checking exact distances. But that local lookup does not remove the quadratic sort that happens before those parallel jobs can use the index. The end-to-end path needs to account for both stages.

Capacity and active count need to agree

The same code path passes the full capacity-sized array to the grid builder, while it schedules the flocking job only for the active count. UpdateEntityData writes the active prefix; the remaining native-array entries are unused rows. The grid builder still hashes every row because it iterates Entities.Length.

This means work scales with configured capacity even when only a few agents are registered. It also deserves a correctness check: unused rows begin with default data at the origin, and the neighbor job filters candidates using the current agent’s perception radius. A real agent close to (0, 0, 0) could therefore encounter unused rows as candidate neighbors. I have not reproduced that case in a Unity scene, so this is a source-derived risk to test, not a reported runtime defect.

The loop bounds give an exact comparison count for any chosen capacity. The chart below compares the field’s 500-row default with two capacity scenarios; those counts are derived from the code, not measured frame times.

Treat the FPS number as a claim until it can be repeated

The README reports a 90+ FPS result at 1080p with 1,000 agents on a Ryzen 5 5600X, RTX 3060, and Unity 2022.3.10f1. I did not find a checked-in benchmark harness, captured profiler data, or automated test workflow in the reviewed repository tree. I therefore treat that figure as a result stated by the README, not as an independently reproduced portfolio measurement.

That distinction matters because a frame includes more than the neighbor loop: data preparation, grid construction, job scheduling and completion, raycasts, avoidance, and applying transforms all contribute. A single FPS number does not show which stage dominates or whether the same result holds at a different agent count, cell density, build configuration, or machine.

What I would measure and change

I would first make the grid builder process only active rows, or give it a buffer whose length matches the active count. That removes spare-capacity work and prevents unused entries from becoming part of the neighbor index.

Next, I would replace the nested bubble sort with a grouping strategy designed for the expected sizes, then compare neighbor results against a simple brute-force reference. Test positions should include the world origin, negative cell coordinates, cell boundaries, sparse swarms, and dense clusters.

Finally, I would profile the build step, neighbor job, raycast batch, and result application separately in a release player. A repeatable report should name the Unity version, target hardware, active-agent count, configured capacity, scene, warm-up, sample duration, and frame-time distribution. Until those measurements exist, I would not use the README’s headline FPS as proof of the current algorithm’s scaling. The source review establishes a quadratic comparison count and a dependency on grid construction; it does not establish the cost in milliseconds.

For the implementation, see the grid-building job and the job scheduling path; the README’s performance claim is reported separately from those code paths. For a related example of separating a code structure from what has actually been validated, read how Arcglass Engine’s build graph differs from an integrated frame pipeline.

← All notes