Jul 14, 2009 at 8:08 PM

Any feedback?  Suggestions?  :)

Jan 29, 2010 at 4:57 AM

I'm making an XNA game to demo some research; using this I got collision detection working for the game in about four hours, which is awesome.  Most of the work was on the game side and little tweaks to get the code to use classes/structs other than those from System.Windows (which I don't believe are available on the Xbox 360, though I could be wrong) and floats (since floats are the XNA default for most objects).

Haven't done any heavy duty performance tests yet, but it's really easy to use (I've never used a quadtree before, just had heard of them).   Fantastic job!  I'll definitely recommend it to others.

(I signed up for an account just to say this; that's how psyched I am!)

Mar 19, 2010 at 8:58 AM


I searched for a Quad-Tree implementation too (also for XNA). I found this one and modified it to fit my needs.

And I must say:

I'm impressed how simple it is!

Thanks for such a good class!

Oct 31, 2013 at 5:28 PM

First of all, thanks for providing this really great implementation of quad tree. It is really well designed and consequently easy to read and understand.

I have one suggestion regarding the code, which leads to a performance improvement. I am not really an expert or anything close to that, but there two methods from the QuadTree class which do not need to be locked:
public List<T> Query(Rectangle bounds)
private void Query(ref Rectangle bounds, QuadNode node, ref List<T> results)
The reason is that in these two methods you do only readings from the main collection, which is perfectly okay for concurrency. The only writing done is when you a new results List is created and you add items to it, but that is also fine because each thread has its own call to the Query method, i.e. its separate List of results and it will be the only one writing to it. Unless I am missing something, there is no need these two methods to be locked. And here is where I am calling the Query method using the Task Parallel Library in .NET:
Parallel.ForEach(this.circles, circle =>
                    var neighbouringCircles = this.quadTree.Query(circle.Bounds);
I am doing collision detection of 1000 circles. With the original code it runs with 5-6 FPS, while with the suggested modification 60FPS. The CPU is i7-720QM.

Once again, this is a great implementation of QuadTree. Thank you very much!

Apr 22, 2014 at 3:02 PM
Performance could certainly be improved, but not in the way you suggest. The ReaderWriterLockSlim class is what should be used there to address the less frequent case when modifications are being made.

As for your testing, as soon as you start adding/removing from the QuadTree while you're doing your queries you should encounter issues.