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.

R-trees are great for some situations, but games don't usually have the situations they are best at.

An R-tree is great for arbitrarily-sized rectangles found in clusters. So for a city map you might have a bunch of rectangles for the city blocks, then nested inside each city block are rectangles indicating buildings, inside those rectangles are businesses. This makes it easy to find nearby items based on their rectangles, but the data sizes are irregular. One search may be very deep in the tree, another search may be shallow. The individual rectangle trees need to be clustered and built into a hierarchy which can take processing time. The irregular shape can be good or bad depending on the density of objects. Being irregular you might get better clustering and more efficient encoding of dead space, but you also get worse in other situations. Also being irregular the processing needs may vary wildly.

Games are more likely to use a loose quadtree. The data is regular (with all the associated pros and cons) and it is automatically built into a full hierarchy based on position (rather than needing to sweep to find nearby nodes).

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.

I don't think there is a math trick here.

You have a 2D problem, and are trying to mamgle it into a 1D problem. In the latter space, you would need to search in 4 directions due to symmetry between X and Y, while you only have 2 directions available.

Simplest solution here is probably a 2D grid with cells to store the objects. Finding neighbours is easy then. Quad tree is a generalization of that where you don't have loads of empty cells, or very full ones.

Another solution I have come across is 2 sorted lists, one on X coordinate, and one on Y coordinate. From an object find its neighbours in X direction (by walking both directios in the X list), and its neighbours in Y direction (by using the Y list), Discard those which are not neighbour in both directions. Done.

Perhaps even simpler is to sort on X only (or Y only), then walk the list as before in both directions from the object, but check the Y (or X) from the neighbour object itself. You will find some false positives, but depending on the spread in the direction of the list, this should often be less bad than all objects (the worst case).

Edit: After pressing "Post" I came up with another one, which works only if you have integer coordinates (at least in one direction). You can sort on x*width + Y, the standard solution to map a 2D coordinate onto a 1D array. Searching in Y increments or decrements by 1, searching in X increments or decrements by 'width'.

Make a coarse grid, with squares of width equal to the radius of interest. For each object X, you only ever need to examine the grid square that includes the object or the 8 that border on it. Done.

Theoretically there are weird and wonderful algorithms that would allow you change this 2D problem into a 1D problem, involving space-filling curves, but I can almost guarantee you that the cost of creating and maintaining the structure will far exceed any benefit you get from it.

You don't even need to make their size equal of the radius, but just have them a fixed-known size. Then it will just be a matter of factor (fixed and known too) compared to what Kylotan said.

there is no mathmagic, what you have is a problem of sets, which is discrete math. In other words a data structure. Google hierarchical spatial hashing. This can limit how many objects you search for based on distance.

While I agree with Alberth's ideas, I also want to bring up, have you profiled? How many objects are we talking about? How often are you doing the search? Can you brute force it and forget about it? Could be a case of overengineering. (Might not be, but I think it's important to think about before going hog wild on a system when you have maybe 100 objects and/or are only doing this search once every sixty frames.)