w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
Collision detection algorithm

The loop will not increase exponentially but quadratically, which can be still bad.

There are several solutions, depending for example on how many rectangles are moving and how many of them are fixed.

A solution very simple to code is

  • build a grid of NxN cells where each cell can contain a list of rectangles touching the cell
  • loop over the rectangles and for each of them put the rectangle in the list of every cell they touch. While doing so you can also check if the rectangle is colliding with others that are in the same list of a cell.

This grid data structure is very easy to maintain updated when you move a rectangle: simply remove it from the current lists and insert it in the lists of the new position.

What is the optimal N really depends on the application.

© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.