This is an example of my XNA game’s quad tree collision detection implementation. Each time an enemy moves to another section of the screen, it is placed into a different node in the quad tree, I then draw a box over the part of the screen corresponding to the node of the tree.
In my implementation of the quad tree, I start with an empty tree and create the nodes in the tree as I go. I do not remove nodes when they are empty, so as to minimize garbage collection. I’ll need those nodes later on when new enemies enter that section of the screen.
A little background…
I’m not simply trying to draw a quad tree so it looks like a tree.
The quad tree is the underlying data structure.
Quad trees are used to divide 2d maps and regions into grids so that each square in the grid represents a node on the tree. You can then search the tree fairly quickly. In this case i’m using it to divide my game screen into quads, then those quads into quads, and so on until the quads are just the right size to fit my smallest enemy.
What you see in the video is that when an enemy moves across the screen, it is being placed and then moved around in the quad tree. To show this on the screen I am drawing a square around the section of screen that is represented by that node on the tree the enemy just entered.
Another important thing to mention is that if an enemy overlaps 2 or more quads, it is placed into the parent node on the tree that represents those quads.
When I update the bullets in my gameloop, I find the leaf node the bullet is in, then do collision detection on only the enemies in that leaf node. If i did not hit anything I check the parent node. The, I work my way up the tree till I reach the root.
The entire point of all of this is so you are not checking each bullet against each enemy every time. You are only checking 1 bullet with the enemies that are next to it on the screen.
I worked over the weekend on collision detection between my bullets and enemies on the screen. I decided to use quad trees to split the screen into quadrants, and those quadrants into quadrants, etc etc. Seems to work well. Ill post a video of it working after I get back home from work today.
Oh, I also added some simple enemies.
Here is a page on quad trees in C# as well as some code sample. I didnt use this however, I wrote my own code.
I decided to add 2 pages to the blog up above. One has some information about me, the other has a list of the tools I’m using to create this game, so you can get started as well.
I was sick today so I ended up sleeping for most of the day, but I managed to find time to get the game running on the 360. Unfortunately, I could not for the life of me figure out how to get tile properties using TiledLib on the 360. My code worked great on the PC. I decided to go back to an older version of TiledLib that I know works, but they are very different and I have to rewrite a lot of code. This is going to set me back a day.
I didn’t work much on my project today because I had some BBQ with my girlfriend after i got home from my real job but I did have a chat for 2 hours with one of my good friends from Xona Games. We talked about engine optimizations, game theory, and a lot of game related topics, so I’ll count that as a good days work. Always good to talk to the Xona guys about games. They have a lot of interesting things to say. If you have never played one of their games I very highly recommend you try their game Score Rush here : https://turbulenz.com/scorerush Go ahead, its free and works in your browser. Works great with an xbox 360 controller. There are online leaderboards and community features as well.
I have a full time job but i’m trying to put 4 solid hours/day into developing. Today is the day I start chronicling my development progress. I’ll try and post a new screenshot or video or at least a description of what I have worked on for the day, every day.
I’m using XNA4 and TiledLib currently. I started working on this game 4 days ago using pieces of code from the other 3 times I’ve started working on this game. Today I did bullet/tile collisions. Tomorrow bullet/enemy collisions !