Spatial Hashing: Evenly divide the worldspace into a grid. Assuming objects aren’t physically large enough to be within more than 4 grid spaces at the same time (8 in 3D), we can “hash” grid spaces to quickly identify possibly-adjacent objects. Now that we can quickly get objects within a grid space, we’ll check for overlaps in a grid space and all adjacent grid spaces using AABB tests. Besides hash collisions, objects in non-adjacent grid spaces are ignored, reducing the number of AABB tests.

• What is hashing? It’s the idea of taking data and converting it into a “hash” number. For example, how can we hash the data of a position: (10,32)? Well, we could do x*2+y*3, getting 116. Ta-da! We just converted an arbitrary position into a single number! Note that it’s now possible to have a “hash collision.” This is where two different pieces of data result in the same hash. For example, (1,38) also results in a hash of 116, as 1*2+38*3=116.
• Why do we want to use hashes? Couldn’t we store objects within the same grid space, then query from that? Well, that won’t scale well. For example, we’ll make a list of objects for all the objects in the grid space (0,0), another for (1,0), another for (2,0), …, and finally another for (999,0). Then another for (999,1), … See why that won’t work? In large worlds, this is too much to remember. Using hashes, we can quickly query objects that are within a grid space without having a separate container for each grid space. We’ll first decide how many “buckets” we want, being the number of lists we’ll have. For example, we could have 10 buckets, one for each digit 0 through 9. Hashes that end in a digit have that physics object put into that bucket. In practice, we’d use the modulo operator to expand this to any number of buckets. While we’ll have hash collisions, this won’t result in incorrect behavior; we’d just be performing unnecessary AABB checks on non-near objects. Increase the number of buckets to reduce the probability of this occurring.