QuadTree

Details
Published on 2011-04-05
Written by John McDonald

Me and a friend of mine, Gary, designed and worked on a QuadTree implementation for our XNA games. A QuadTree is an efficient way to store and retrieve spatial objects by location. You can read about them on the Wikipedia page. The source code, DLL, and testing applications are all available on our project on Bitbucket. I would recommend checking the code out using Mercurial, then adding the project to your game's solution so that you can get all future updates.

I use this project for Asteroid Outpost to quickly see if entities are intersecting, or look for entities in a certain range, or figure out what is visible on the screen.

Here are some screenshots of the testing tools that are provided:

A normal usage example. The rectangle represents what the user can see and moves with the mouseA visual test where the user can see the quads while adding and subtracting objects

 A performance tester that I used to determine performance increases or decreases

Comments:

  • SignpostMarvat 2012-07-22 09:41:09

    I've used this at work but I've been having some issues getting hg-git to play nice so we can push it onto github along with the rest of the stuff I've been doing- I noticed you've got an account there already, any chance you could put quadtree onto github ? :D

    Reply to comment

  • omegat 2012-07-15 09:38:49

    Very nice implementation, by far the fastest among all I've tested. Thanks for sharing! :)

    Reply to comment

Post your comments...