Optimize Collision Detection in JS with a Grid

[00:00] To optimize our collision algorithm in JavaScript, our main loop is this time step function. What we're doing on each time step is we're looping over every single circle in the entire page. That's 2,000.

[00:11] We're updating its dynamics, and then we're applying collision detection against every other circle. We're doing four million collision detections every single frame, and this is exactly our performance problem.

[00:24] We can improve this collision algorithm by breaking the space up with the grid. We then only need to compute collision detection with individuals cells with the grid. We're going to use an arbitrary width and height for the grid initially. We can optimize this later.

[00:39] In our time step function, we then create the grid on every single time step. We loop through the columns, and the rows each of which is represented by an array. The individual cells are then an array of circles that are contained within that grid cell. For this initialization step, we're just going to set it to an empty array for each cell.

[01:00] The first part of our time step function is computing the dynamics of each circle. We're going to leave this computation in place, but then instead of going straight into the collision detection, we're going to first assign each circle into one of the grid cells.

[01:14] We compute the column for the current circle based on its exposition on the page as a fraction of the total width scaled up to the grid size. We need to round that down since the grid starts at zero, so we can do that using Math.floor.

[01:28] If we look at some of the biggest circles on the right, they're actually contained in multiple grid cells. Instead of computing a single cell for each circle, we need to compute its cell range.

[01:38] We'll compute its leftmost column based on subtracting the radius from the center point, and also compute its rightmost column, and do the same for its topmost row, and its bottom row.

[01:59] Now that we know exactly which cells the given circle belongs to, we need to assign it into the grid. We can do a loop over from the first column to the last column that the circle is in, and then we take those columns directly from the grid. We then loop for the row from the first row that the circle's in to the last row the circle's in, and we get the cell value out of the grid.

[02:22] We pre-assigned already each cell to an empty array of circles, so we can just use an array push to add to the circle to this cell. To reference the circle, we can use the index of the circle, and the circle data array as our unique identifier.

[02:38] If the circle happens to be outside of the browser bounds -- say we're re-sizing the browser window -- we're going to be assigning to an invalid grid, or a negative grid value. Let's just detect if the front column is negative, and set it to zero, and similarly if the two column is greater that the grid width, just snap it back to the grid size.

[02:54] If two circles collide outside of the browser window, we're effectively ignoring those collision detections. With the grid, we no longer need to do collision detection between every circle, so I'm going to close out this loop over every circle that we're currently in.

[03:21] Now, we just have to loop over each of the individual cells in the grid, and apply collision detections for the circle just within that cell. The cell value itself is the array of circle indices which are contained in the cell. You want to loop over this array as well.

[03:42] The iteration values we had for each circle before were an "I" and an "IV" iterated. The "I" going in steps of the three, and the "IV" going into steps of two. To get the "IV" iteration value from the information you have here, I'm just going to divide "I" by three, and multiply it by two.

[03:57] As in the previous code, we can now read out the X1, and our values of the circle from the circle data as well as reading out the external "I" components of the last "T" using these indices. With the variables set up for one circle in the cell, you want to do a comparison with another circle in the cell.

[04:13] We're going to need a final inner loop where we can get the index of this circle that we're comparing with. This loop only needs to start from the circle after the current circle, so we only doing each pair of comparisons once.

[04:26] We're just about there now. With these "J" and "JV" indices set up for the comparison circle, the position and velocity look ups are actually already in our original collision detection code.

[04:36] I'm just going to go ahead, and copy that in. This is now nesting our entire collision detection algorithm within these specific grid cells comparisons.

[04:47] That's the collision algorithm grid optimization. I can assure you, I didn't get this right first time, and there were many hours of reading, rewriting, and debugging in the process.