This is a broad question, so a broad answer is required. You can follow up individual implementations / algorithms yourself, and post separate questions if you need to.
The basic approach for games
Create some sort of grid in space. This grid can be either:
- flat (literally, a 2D grid or 3D grid)
- hierarchical (2D: quadtree or bounding box hierarchy, 3D: octree or bounding volume hierarchy)
These are implemented as an array of containers. Hierarchical grids are arrays of containers of arrays of containers, ad nauseam, down the tree.
For now let us focus on flat structures, as these are easier to conceptualise.
Each grid cell or "bucket" groups a set of bodies. This approach is simple and generally works well enough in most cases, and I would recommend it as a starting point for beginners. We determine (naively) whether a body is within a cell as follows:
for each body
get xmin and xmax for this body
xcentre = xmin + (xmax - xmin) / 2
find the cell which holds this body:
xcell = xcentre / numcols //integer division, round down (in this case, numcols=4)
repeat for y (and if in 3D, also for z).
So in the case of our bottom-most point in the image above, cx == 1 and cy == 3 (remember this is zero-based, so cols and rows each run 0-3).
Thus the boxes or volumes that we use to contain bodies, are defined by a fixed, repeating grid. Note also that the size of the cells are directly influenced by the size of the bodies they can contain. Too small, and you will not create good-sized clusters; too large, and you may not get enough reduction in the number of body-body checks.
Problems, and more advanced approaches
A problem arises in pathological cases like this:
...This will be less than optimal since we'd ideally have liked the four red bodies, and maybe even the orange one, grouped together. This way we'd have only had to process one bucket instead of four, which would have reduced processing costs.
This can also happen in a quadtree, which is also defined by a fixed grid structure (quadtrees are otherwise much more performant for large numbers of bodies, than flat grids):
Where such pathological cases are of crucial importance, e.g. they are a performance bottleneck, we prefer something that clusters more dynamically. A graph connectivity approach such as Kruskal's Spanning Tree Algorithm which DMGregory mentioned, or any other which creates a dynamic, connected clustering. If a maximum edge distance is used, long edges are eliminated, dividing output into localised subgraphs / clusters:
Or we can use an iterative classification method such as K-means clustering, which again creates dynamic groupings with no regard to rigid boundaries:
(K-means animation attributed to Chire under Creative Commons)
Once we have clustered using e.g. K-means or Kruskal's, we can use these clusterings to determine bounding box or volume limits. We could also use this as an input to a flexible bounding volume hierarchy (actually area, not volume, in 2D). There are countless ways to subdivide the space, but only a few that cluster efficiently, it all depends on the use case. This shows a space-filling bounds structure vs a sparse structure:
