# Redundant checks from spatial partitioning

A simple 2D grid partition system for collision detection divides space into equal-sized tiles. Colliders then map themselves to tiles with their bounding box in O(1) time. Collision detection only has to be performed between objects that occupy the same tile(s).

Collision detection is expensive so the more culled, the better. With a grid partitioning system, how are collisions culled when colliders share multiple tiles?

For example, Circle_A and Circle_B both sit on the edge between Tile_1 and Tile_2. Iterating both tiles would make collision detection between Circle_A & Circle_B run twice.

A global pair hashtable seems performance expensive since it has to be cleared every frame. Tracking pairs inside colliders takes a lot of memory. How do you mitigate redundant pairs when iterating through partition grid tiles?

• Can you clarify why you've chosen to replicate each object in each cell it touches? The guide you've linked recommends storing each object in only one cell (eg. the cell containing its center point), and shows how to iterate adjacent cells to find collisions where objects overlap cell edges, without double-checking any pairs. – DMGregory Mar 2 '19 at 22:38
• Oh interesting. I mistakenly linked the article to infodump spatial partitioning but they have a unique implementation that wouldn't be practical for collision detection. Essentially multiplies by 5 the bounding box/circle checks needed. Large grid cells result in many more O(N2) checks and small cells are dangerous - if a collider is bigger than one cell, you're fked. I will reference a different resource. – JPtheK9 Mar 3 '19 at 1:26
• The new link (buildnewgames.com/broad-phase-collision-detection) tackles the same problem but does it with a global hashtable. I'm digging into @Engineer's answer which seems like it optimizes collection access/management. Ik I'm dangerously close to premature optimization but performance is an absolute requirement. – JPtheK9 Mar 3 '19 at 1:37

how are collisions culled when colliders share multiple tiles?

Pairwise, as you suggest. You can do this in one of two ways: as a global dictionary which you suggested, or as a dictionary per unique neighbourhood.

Global Approach

You need to clear the entire map because you need the boolean "has this pair been checked against one another already" to be reset for each pair, each frame; yet it is likely that iterative, keywise Dictionary clearing would be slow. To solve this, you need:

• a backing array of values of that you can clear quickly, using fast approaches such as Array.Clear() or Buffer.BlockCopy() (see more here and further research elsewhere), pre-sized / pre-allocated to accomodate all unique pairs.
• a map implementation using that backing array, primarily by acting as an indirection table into it.
• a way to key into this map efficiently.

Pairwise keys are assembled in some deterministic manner using unsigned integer-type IDs that you'd have assigned to every body, e.g. lowest then highest. To assemble key, take e.g. two ushort IDs and order as:

uint key = (uint)((highID << 16) | lowID); //2x 16-bit ushorts into a 32-bit uint.

(ushort means you can support up to 65536 unique bodies. If you need more, use uint and make your key a ulong... but see caveat about capacity below.)

As for the map's values, those are just indices into the backing array on which you can perform fast clears. This is called indirection and, provided your data structures are well-allocated, should be very fast. If jumping between the backing array and the key set is slow, then I'd strongly suggest implementing your own interleaved or at least contiguously allocated map of keys and values, which has the possibility to be ultra-fast in terms of cache memory access. However, note for now that your cache ways should handle jumping between the map and the array, admirably, provided they are small enough (test, test, test).

If you could help it, you wouldn't want to do any management on the array except C#'s memset-style clears mentioned above. The backing array's order does not change; no compaction occurs; some entries are simply no longer referenced by the map (as its values, which are indices into the array) if the associated bodies are destroyed or invalidated.

You may rightly ask, "But that still leaves me clearing the map/dictionary?". Not quite: this map will remain unchanged most of the time, except where individual bodies are destroyed or invalidated, in which case you manage only the entries which pertain to them, at that point in time, rather than clearing the whole map constantly. In other words, the map is set up once, at the start, and then modified incrementally as the scene runs.

Caveat: even using (unsigned) byte keys (which support only 256 unique bodies) means you will need (using sigma function) 32k elements in your array to store all possible pairwise combinations; 10k unique bodies would require 50M entries, that is a 50mb array if you use 1 byte entries, or about 6 megabytes if using 1 bit to indicate your usual bool. So this approach is only useful for a relatively small numbers of bodies. As you said:

A global pair hashtable seems performance expensive

More: it's now costly in terms of space, which from a cache-performance perspective is not ideal.

Partitioned Approach

But we're assuming above that we have to lump everything together, when in fact, the entire point of such partitioning schemes is to reduce which bodies can relate to which.

Let's now consider a world where there are 16x16 cells total. What matters to your solution is not every body relating to every other body in the world, but rather relating to every other body in the local cell neighbourhood (2x2). In an n=16 wide cell neighbourhood, you'll note there are exactly n-1=15 unique neighbourhoods (they overlap) per axis. This leads to 15x15=225 neighbourhoods.

Note that in spite of this number, we'd ideally still want a single, contiguously-allocated array for fastest possible access; but sadly we'd then be bound to doing considerable management of the array, since the contents of each cell is utterly dynamic, unlike the combined contents of all cells i.e. the world. This can certainly be automated, but off the top of my head, I'd think the management cost would be quite high.

So in this case, assuming you don't have an exorbitant number of neighbourhoods, I would suggest pre-allocating an individual Dictionary instance for every unique 2x2 neighbourhood in your world, and go from there. If, much later down the line, you feel their non-contiguity is costing you performance, you can look again at the above idea of multiple collections sharing a single contiguous backing array.

Caveat: Managing the multiple dictionaries may be costly; each frame you will need to update them from the changes just made to their constituent cells. Use a delta-based approach to minimise cost.

Coarser Partitioning

There is another option: to reduce the number of Dictionarys, don't use your usual 2x2 for the neighbourhoods but perhaps something larger like 4x4 or 8x8 roughly around the body's centroid; it seems worth a try at least to check performance at different body densities. Fewer, larger allocations this way may lead to better performance.

This is not trivial, but it is doable for an intermediate to advanced coder. You can go with regular hashing or perfect hashing if possible, which is fast but more complicated to implement and with certain limitations. Basically, perfect hashing eliminates the worst case cost of regular hashing, where there is a hash collision. With a single global backing array, this could be the fastest of all possible options, but also by far more time-consuming to implement.

Final notes on such optimisations

There are times when it is better to accept worst case performance as average case, and move ahead in other areas. It may be that none of the overheads that these optimisations (or any others) produce is justifiable in cases where bodies number less than the hundreds of thousands. And if you never reach that sort of body count, you may never see the gains. In other words, it is sometimes better to take the hit. Just be aware of this before you begin deep and complex implementations.

A pattern I've seen over and over in performing algorithmic optimisations and researching the optimisations of others: Sometimes a broad and sweeping optimisation introduces smaller inefficiencies, but the overall gain is so overwhelming that you are satisfied. You are then free to try to tackle those smaller inefficiencies if you like, but at each step this becomes more and more costly in terms of dev-time, for smaller and smaller gains. This is the point at which things stagnate for a period of time, and then whole new approaches are thought up, since we are otherwise stuck in a sort of black-hole of ever-decreasing gains.

Applied to your concrete case: When checking n bodies in a non-partitioned space, you have to do the pairwise check against your Dictionary every time, such that for all n^2 checks, you will do sigma-n actual collisions (I can explain why, if you like). But after the partitioning optimisation, you've greatly reduced that cost. However, partitioning creates the problem of cross-border, redundant checks in that neighbourhood. Having reduced the number of checks by orders of magnitude already, do those few surplus checks within each neighbourhood really make a difference? If so, is it worth reducing the cell/neighbourhood size to be even finer? If not - is it worth optimising a whole lot more for what may be vanishingly small gains? This is up to your own research and testing.

• @JPtheK9 Warning: There will likely be hateful downvotes on my answer. Don't take them seriously till you've read and understood it for yourself. It is due to a recent, unrelated discussion. – Engineer Mar 2 '19 at 19:59
• Thanks for the awesome perspectives about memory impact and the partitioned partitions approach. I will consider both in implementation. Rubber ducking here: what if colliders stored the cells they occupy, e.g. byte[] occupiedCellIDs? When iterating, pairs check to see if they occupy similar cells. The collision check is only run if the iterating cell has the lowest ID of similar cells. – JPtheK9 Mar 3 '19 at 1:54
• @JPtheK9 I'm uncertain as to your final sentence; unsure what you mean by "similar cells"; similar in what sense? But then, even if this answer sparks your thinking to find an alternative solution, then all should be well. P.S. I've edited the final section a bit with some further insight on such optimisations. – Engineer Mar 3 '19 at 8:12
• I should have replaced 'similar cells' with 'shared cells'. Your insight on optimization sinks in for me. The physics engine is currently backlogged but I'm glad I have some details ironed out conceptually. when the sprint starts, I'm not going to obsess over optimization. – JPtheK9 Mar 4 '19 at 9:27
• @JPtheK9 Thanks for the accept. By the way, your lockstep, networked fixed-point math project mirrors something I've been thinking about for several years, so I am looking forward to adapting it for my needs one of these days. Fantastic work! Might even see you on github. – Engineer Mar 4 '19 at 9:35