Detecting collision between browser window middle point and other sprites visible in the window

Question

In HTML5 canvas, I have an object which is always in the middle point. On the big map there are other moving objects. I want to detect if the middle point of the window hit any shape we see on the window. I wonder if there is a way to only detect collision between the middle point and the shapes that are visible in the window so I don't have to iterate through all shapes on the map (could be many thousands of shapes).

Is there a good solution to this kind of collision detection? Assume that I have already known how to write the collision detection code for the middle point and shapes.

Answer 1

This is solved by the same kind of spatial partitioning we use for other collision checks.

Rather than treating your objects as one long undifferentiated list, sort them into a data structure that you can query based on a position or region.

For example, you could divide your game world into a coarse grid, and in each grid cell store a list of collision objects that overlap or have their origin in that cell. When you want to look for collisions at a given point, you look up the grid cell that contains that point, and check only the objects in that cell (and adjacent cells, if you're not duplicating entries when they overlap multiple cells)

A more adaptive strategy is to use something like a quadtree, k-d tree, BSP tree, or R-tree to partition your world more finely where objects are dense, and sparsely where there are few objects. These can reduce your search time to a logarithm of your number of objects.

Answer 2

If you dont want to do the iteration what pops to mind is drawing it (those particles) on invisible canvas (maybe smaller one for performance) and then reading the middle pixel is it colored or black.