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.
Implementing your own map
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.
