Collision Part II: Sweep and Prune Detection

65 days ago by MrMisinput

Share this post:

September 10th, 2024

Hello! In this blog post, I want to cover a broad-phase collision detection algorithm called sweep and prune. This version of sweep and prune has an average time and space complexity of O((n + m) * a), where n is the number of objects, m is the number of collisions, and a is the number of axes. This will be much more performant than the naive detection with an average time complexity of O(n^2).

Overview

The basic idea of the algorithm is to create a list of all the edges of every object in the world. We can then sort this list. As the list is being sorted, we can use the swaps to determine if a collision has occurred. If an object's lower edge (from the west) swaps with a higher edge, a collision has begun. Otherwise, if the higher edge (from the west) swaps with the lower edge, a collision has ended. if a Two lower or two higher edges swapping will indicate no change in the two object's "overlapped" state. In the following example, the lower edge is the left edge and the higher edge is the right edge.

Begin:

Ended:

We can do this check separately for the x and y axes. You can check out the Resources section at the bottom of this post for further reading. I followed the tutorial by Lean Rada who gives an interactive explanation of the algorithm.

CollisionComponent

First, I'll introduce the Edge struct:

The edges represent the upper and lower bounds of an AABB on a specific axis. The "CollisionComponent* cc" and "bool isLower" will be accessed by the Collision Manager later in the algorithm and the "float coord" is the position value for the edge. I'll initialize these edges in the Init function and update their position:

Note that in my game, the actual coordinate is the top left of an object, so the left edge will be the x coordinate while we'll have to add the width to the x coordinate to get the right edge:

Collision Manager

As stated in the last devlog, I've revised my CollisionMap and added a few more typedefs for the Sweep and Prune:

The CollisionPair holds two objects that could be colliding, which are stored in the CollisionMap. The KeyMap will be used to keep track of unique potential collisions so we don't check collisions between two objects twice.

Here are the new members:

Like last time, the mPrevOverlappingMap is used to determine if two objects were colliding last frame. The two vectors will point to the relevant edges of each Collision Component.

Onto the Sweep and Prune, I've broken up the algorithm into these functions:

I'll start with the Add/Remove functions. These are called by the Collision Component to add/remove themselves from the mEdgesX/Y vectors. The Collision Component adds itself on Init and removes itself in it's destructor. This ensures the Collision Manager is always checking active objects:

The SweepAndPrune function is just a wrapper for the two primary functions:

Detecting Overlaps

The CheckOverlaps function is where all of the magic happens. The algorithm sorts the vector using an Insertion sort. We use an insertion sort because the same array is being sorted every frame. It's unlikely the mEdges' array will need to be sorted every single frame and the Insertion sort has a time complexity of O(n) on a sorted array.

If the two edges are not sorted, we know that a collision has either begun or ended:

This means that if the two edges are already sorted, there's no work to be done. Getting past this point means there is some kind of collision event, so we can build the key.

The bool parameter checkPrev becomes relevant when we check any dimension past the first one. I put an early continue here because if the current key is already in the map, there's nothing more to do with this pair of objects:

After this point, we check if the objects just started overlapping or if they stopped. We can add/remove them from the currOverlappingMap and keysToCheck accordingly.

This concludes the CheckOverlaps function. Now that we have all the overlaps, we can process them.

Processing Overlaps

The first step is to make sure we check the keys that were overlapping the previous frame:

Now we can loop through every key to check:

At the top of the loop, we make sure to grab the correct CollisionPair, whether it was in the previous map or the current one. Then we can check if they were colliding and build the CData to pass to each collider. The IsColliiding function does the AABB collision check. Here is the first if-check to perform:

Ongoing is called any time the two objects are colliding, while Begin is only called the first time. If it's the first time, we cache that value in the previous map.

Here is the else if detection for End:

Similar to last time, we can remove the two from the previous map, since the two objects aren't overlapping anymore.

Conclusion

One of the biggest hurdles for me was trying to determine how to integrate the CollisionOngoing scenario into this algorithm since it only detects Begin and End. I tried a few different data structures, but I think the combination of an unordered map for the collision components and a set for the keys worked pretty well.

I highly recommend checking out Lean Rada's website, it was very helpful in my understanding of this algorithm. The coolest part of the algorithm to me is the use of Insertion sort. I tend to always look at the worst time complexity, so I would have never considered using Insertion sort over Quicksort. Thanks if you made it to the end, next time I'll show off my collision resolution for when an object collides into a wall.