Most efficient way to detect and act upon collision (Specific for my 2d game)

Question

Currently, mainly just for fun, I'm working on a 2d game where I have all collide-able blocks (background) assorted into an array when its loading, along with the player put into a different part of the 3d array. The player object gets put in with the AI array. It looks like this -->

    var world_objects = [
  [], //All 'background' collide-able objects. Such as stones and the border ~~ Code name: bg
  [], //All AI ~~ code name: ai
  []  //Projectiles ~~ Code name: ps
];

The map is set up into a bitmap that I've made using another 3d array, that currently is made into a 15x15, but that is subject to change. The brown border is included in the bitmap and world_objects array. And when the blocks/ai/projectiles are inserted, they all will have a basic object properties of:

x, y(2 variations, one with just normal x,y according to the exact pixel in the canvas, and the other is according to which cell its in for the bitmap)

Width, height (Both width and height for ai and projectiles are recorded as percentages according to the size of each cell, because the size is made to change depending on screen size)

Along with other properties not related to collision. What would be the most efficient way of detecting all objects and whether they collide or not? If needed, I could add additional properties to each object if that would make it easier and more efficient.

Click to see all of the code

Answer 1

As long as your game stays in a 15x15 grid, the naïve way of just checking collisions by comparing every object position with every other object position is likely a "good enough" solution. I would recommend you to just stick to this until you actually run into measurable performance problems.

Those problems might show up when the number of objects in your game increases a lot, because the computational cost of this solution increases quadratically with the number of objects you check for collisions with each other.

When you need to improve the performance, you can use a data-structure which allows you to quickly get all objects in a given area. Possible candidates for this are spatial hashing or the various variants of 2d-trees. There is no "best" solution, because all solutions have cases where they work good and cases where they work bad. For example, spatial hashing isn't very useful when objects cluster a lot in individual boxes and keeping 2d trees up-to-date becomes expensive when objects move around a lot. There is only the best solution for your game.