thought microsecond wasif I remember correctly:
5us =
µs
^^
Yes you have to check every item, but cost is still linear because every sector have fixed maximum number of elements ^^ (that's like cheating, it is, but may works too).
(wikipedia): modern CPUs can execute hundreds of instructions in the time taken to fetch a single cache line from main memory. Various techniques have been employed to keep the CPU busy during this time.
(one way to keep it busy is doing 2D square distance test, very fast to compute and even faster if you know right assembly instructions.)
In a quadtree you can have to fectch a single line for every node you iterate over. Grid already have all children cached, if they are not enough checkin all of them (2D square distance is very fast to compute) should be still faster. And as additional case, if a Sector Completely Fit into your range, then all its entities needs no check. So for biggest ranges values, most of checks can be simply skipped. (since when range increase linearly the circle area increase quadratic, only sectors on borders need a full check, and perimeter increase linearly with range so the cost is still linear, constant access for 1 element, linear for multiple elements. Iterating over N is linear cost, iterating over 100 is constant cost. so NxN quadratic, but Nx100 is linear, and in average it will be Nx(number lesser-lesser than 100) )
If grid does not work for you even after the finest tuning of cell size, then there's nothing faster of 2DRangeTree, so or improve your RangeTree Implementation (not very hard to do, unless you already have the "optimiziest" code), or go parallel, or invent a new algorithm and sell it to game industries
Edit: another important point too.
2D range tree is limited to Square areas, with grid you can have automatically Circle area. Searching for units in a circulare radius in RangeTree will have the same cost of that check for the Grid, but with all the additional overhead of the LogN algorithm+ cache misses.
