Ohh I'm so sad I missed the meat of this topic!
I love me some spatial partitioning.
To address a few things:
For dynamic entities, grids should be better. Quadtrees are fast to traverse but slow to make.
You don't need to make a Quadtree each frame, it's stupid simple to adjust them. I used to LOVE grids, until I spent some time implementing a QuadTree... I actually like it more now. It's simpler (yes I said it) and it's a little faster.
Traversing (quad) trees is incredibly inefficient due to cache misses.
Like I said previously, I've experienced them being faster. I'm fairly confident my Grid & Quad spatial structures are pretty optimized. I'll post them below. In theory you're right, it definitely depends on the processor and the implementation as well.
it's easier to code
I think QuadTrees are easier, mostly because the case where an object lies on a border you just push it up until it's completely contained within a node. The only efficient way I've found to combat entities on the borders for a Grid is to maintain lookback distances (based on the entities contained in a cell, account for all overlapping entities efficiently by optimally looking at surrounding cells while minimizing false positives).
I have a couple implementations I've been working on for a Steering Behavior/Spatial Database library (Steerio) I've been working on:
1. Brute Force
2. Dual Tree (something I call the hamburger/hotdog tree)
5. Sweep and Prune
And of course the interface they all implement so you get an idea on how I have it working:
public interface SpatialDatabase
public void add( SpatialEntity entity );
public void clear();
public int refresh();
public int handleCollisions( CollisionCallback callback );
public int intersects( Vector offset, float radius, int max, long collidesWith, SearchCallback callback );
public int contains( Vector offset, float radius, int max, long collidesWith, SearchCallback callback );
public int knn( Vector point, int k, long collidesWith, SpatialEntity nearest, float distance );
AND if you checkout my project because you want to watch them do their thing (and tinker with the variables live) here's my example:SpatialDatabaseExample
AND finally some stats on how it performs:Steerio README
Hopefully my code helps you, let me know if you have anymore questions.
ALSO! I challenge someone to improve the performance of my Grid implementation to beat out my Quad and Dual tree implementations.