If you have a bunch of objects that know their location, there are times when you to go the opposite direction: given a location, what are the objects? That’s called a spatial index. On this page I tried two spatial index libraries.
This gamedev.stackexchange question[1] uses zufallsgenerator/spatialhash.js[2] for a grid-based spatial hash. I wanted to recreate the demo in the question — given a location, find all objects that would be visible near the player. Try dragging the rectangle that represents the area visible to the player:
It sometimes catches circles that aren’t in the area of interest. Why? Grid-based approaches effectively enlarge the area of interest first to fit the grid, then find all circles that are in those grid squares.
I also tried with the rbush[3] library, which uses an r-tree instead of a grid, and isn’t subject to the same imprecision:
However, notice that if you change the position even slightly, the r-tree may return different results, whereas with the grid, it will often be the same results. That makes the grid results more cacheable.
Which should you use? It depends on the project! Mikola Lysenko compared algorithms[4] including grids and r-trees. He writes, “it is important to remember that when grids work they are effectively optimal”. He also compared libraries[5] and speaks highly of rbush. Also see Bob Nystrom’s Game Programming Patterns book, which has a chapter on spatial partitioning[6], covering access patterns and tradeoffs between different styles of data structures.
Both libraries I’m using on this page are MIT licensed.