I'm familiar with BSP trees, quad trees, octrees and other variations of space partitioning data structures typically used in games. Currently trying to wrap my head around R-trees.
But something keeps bugging me, I think these data structures are way overkill for what I'm trying to achieve. I really think there's a much simpler way for me but I cant quite figure out the math.
I have a big grid of objects, and for any one of the objects, I want a quick way to find the other objects that are "close" to it, without having to loop through every object and check it's coordinates. "Close" will be some radius that I'll choose based on the viewport of the game or something.
It seems to me there should be some math magic that can be done on the coordinates to arrange things properly in a data structure. Like maybe a doubly linked list, where the items to the left and right of any item are the ones close to it.
I thought about simply adding the X and Y coordinates together, and using that as some sort of hash for the location of items. So for eg an item at (40, 290) would hash to 330. But then I realized that (290, 40) would also hash to 330 even though they're nowhere near eachother. So I also tried thinking about multiplying the coordinates together, and other math operations but nothing seems to work.
Then I started thinking about storing each item in 2 lists. One list sorted by the X coordinate, and the other sorted by the Y coordinate. Then given any item, you can find the close items by searching the first list for X coordinates that are close, and the second list for Y coordinates that are close, and the intersection of those 2 results are the close items. You would use a binary search on the lists of course, instead of looping through each item. This method seems promising in my head, but I dont know if this is slower or faster than just using a standard quad-tree type data structure.
I hope this makes sense. Basically I'm hoping the people who have already thought about all of this, can tell me whether I'm wasting my time and maybe I should just use a tried-and-true quad-tree.