Method 2 makes it easy to find all objects in a given map. But if I wanted to do something like .. find all objects from 2,2 to 3,3, I would need to do a brute force search through my object structure to find them all (although if they were sorted, I could easily stop once I reached 3,4).

It doesn't work like that. You can't sort a single array simultaneously by several dimensions of a continuous space. If you use my suggestion and just depth sort the array direction, you only have to brute force search objects with similar depth. Let's say you want to find objects within radius 1.2 from coordinates [5.5 2.1]. This gives us depth limits of 2.1 - 1.2 = 0.9 and 2.1 + 1.2 = 3.3. Then you binary search the array for the indices at 0.9 and 3.3 depth, which is practically free. Finally you brute force search only between those indices. If your map is 50x50 and objects are distributed evenly in the depth direction, only about 5% of them have to be searched in this case. Most of those 5% will be inspected very cheaply because their horizontal distance falls outside the radius.

Using method 3 helps alleviate this. I agree that it is messy though, but I feel like the solution still *has* to be to index the objects by location.

You haven't even defined a problem, other than the overlap one which was trivially solved by depth sort. It's pointless to talk about acceleration data structures, much less implement bad ones, before you have defined what operations you need them to accelerate. For instance, how many objects will there be at most, and is anything known about how they will be distributed spatially? How many "adjacent objects" queries will be made per tick at most? How many other objects will fall under the average radius of such a query? There is no universal data structure that is good for everything.

If you just want to dig into the technology that exists for this purpose, read about BSP trees, quadtrees or other serious acceleration structures and implement one of them.

It doesn't work like that. You can't sort a single array simultaneously by several dimensions of a continuous space. If you use my suggestion and just depth sort the array direction, you only have to brute force search objects with similar depth. Let's say you want to find objects within radius 1.2 from coordinates [5.5 2.1]. This gives us depth limits of 2.1 - 1.2 = 0.9 and 2.1 + 1.2 = 3.3. Then you binary search the array for the indices at 0.9 and 3.3 depth, which is practically free. Finally you brute force search only between those indices. If your map is 50x50 and objects are distributed evenly in the depth direction, only about 5% of them have to be searched in this case. Most of those 5% will be inspected very cheaply because their horizontal distance falls outside the radius.

Well I wouldn't have done it simultaneously, it would have required multiple loops to take into account both X and Y, but you're right - I really only need to take Y into account. Any overlap that would occur on the X axis would be dealt with when I implement collision... but that's a completely different topic.

You haven't even defined a problem, other than the overlap one which was trivially solved by depth sort.

The problem described there was referencing objects by location rather than URN. However, it is another example of me underestimating how fast these sorts and searches will actually be. I'll try to let it go and deal with more optimization later.

For instance, how many objects will there be at most, and is anything known about how they will be distributed spatially? How many "adjacent objects" queries will be made per tick at most? How many other objects will fall under the average radius of such a query?

Unfortunately, I don't have answers for these. The game doesn't have a purpose right now. I'm trying to set up a 'skeleton' of a game. If I can get multiple players connected, drawing correctly, and can add/remove objects from the world (and have them be updated/drawn correctly), I will take a step back and determine what direction I want to take this in.

I get the point you and thok are making - there's no point in worrying about optimization when

1) The function doesn't even exist yet and

2) The implementation isn't even DEFINED yet.

I'll stop worrying about it.

There is no universal data structure that is good for everything.

No, I'm sure. But changing data structures is not easy. This is one of the reasons I'm trying to be careful about this part in particular. I know I will not get it 100% right the first time, but the closer I can get, the less I will need to convert later. This is another one of the things I get from dealing with my current proprietary language, except one I think is more global.

I think all of my questions here have been sufficiently answered, and I want to thank you guys again for taking the time to respond.

Thank you. Seriously. You guys rock.

But changing data structures is not easy.

Changing data structures in unoptimized code should be easy. If it's not, that's a warning sign about code quality. Keep things simple, generic and decoupled until you have real reason to do otherwise. (One more reason to not do premature optimization: it makes it harder to later do optimization you actually need.)