Detect mouse collision on a 2d grid without using loops

Question

I am building a maze solver and recently I wanted to be able to draw over the grid without having to manually build mazes using arrays. Anyway, I sat down and thought "there has to be a more efficient way to figure out which cell the mouse has collided with on click event, instead of having to iterate over the whole grid which at worst case scenario costs O(n^2)." After some thinking I came up with the following solution. I knew that the size of each grid was constant (in my case 16x16) and I knew the position of the mouse. So I decided to divide mouse position by tileSize and then round it down.

My question is if this is a better solution than iterating over the whole grid, cell by cell. I haven't seen anyone do it this way so I am wondering if there's some edge case that I haven't thought of which might not work with this solution.

@PM77-1 tileSize is 16 if your squares are 16x16.. or 32 if they are 32x32 — Feelsbadman, Aug 27 '19 at 22:03
Yes, this is a better solution, and it's used in computer graphics all the time. It's not unique or unusual, it's the standard way to solve this problem. — Chris Tavares, Aug 27 '19 at 22:04

score 1 · Accepted Answer · answered Aug 28 '19 at 10:13

What you did is the standard way to do it. It never occurred to me to do it via looping of any kind honestly.

Since this is tagged javascript I'm gonna go ahead and recommend this answer of mine in case you have any problems getting the right coordinates for a canvas that was stretched or has borders: https://stackoverflow.com/a/27204937/607407

The linked answer determines pixel the mouse is over exactly using the formula in your question, with tileSize being one. For given tileSize, the tile is then [floor(x/tileSize), floor(y/tileSize)].

Detect mouse collision on a 2d grid without using loops

1 Answers1