When building a large enough game, it will become increasingly harder to be sure that all parts of the game work as intended. That is why you will want to have some kind of automatic tests that you can run to verify that things are still working as expected. As you start to do performance tests and perhaps re-iterate existing code to increase performance or add a new feature, there is always a risk that your new code broke something.
How granular you want to make your test cases can be tricky to determine. As your test-suite grows, maintenance of the tests grows as well which you need to keep in mind. Otherwise there is a big risk that you end up having test that either report false errors or dose'nt even run any more.
We will start with the quad-tree as it is an important part of our collision detection system. If someone was to try and rewrite parts of it and made a misstake we could get collision detection bugs. Because of the nature of the quad-tree, it is possible that this would go unnoticed if the developer did not test all different cases of the quad-tree which is both tedius and prone to error (high risk of missing some of the tests cases).
The useage of quad trees was covered in the Collision Managment page. Here, we will try to map out the different use cases of the quad tree and how we can test so that the quad tree works as expected. We will start with the settings for the quad tree.
unsigned int QuadtreeDucks::s_quadTreeMaxOjbs = 10; unsigned int QuadtreeDucks::s_quadTreeMaxLevels = 4;
Here we can see a couple of things:
The first item should be a test - we should be able to insert 9 ducks into the tree and it should not split it, when we insert the 10th duck a split should occur. This could be combined with the second item - a tree can not have more than 4 levels.
This test is found in mainTestQuadTree.cpp, testNoSplitBeforeLimitAndDepth.
With the basic part covered, its time to look further at what can be done with the quad tree. There are two basic operations that you can perform with the tree:
Lets try and think about the different cases of placing a duck inside the quad tree. There are two outcomes when placing the duck in the tree:
A duck could be:
The last one, spanning quadrants could be broken into two more cases:
The image bellow illustrates the different possible outcomes.
The other aspect we want to look at is finding possible candidates that a duck can collide with using the quad tree. Lets start with imagining the simplest case, all ducks fit inside a quadrant of the tree (ie - there are no ducks spanning any splitting lines). In this case, all we need to do is take the duck we want to find other possible candidates for and try and figure out which quadrant it would belong to, and the ducks inside that quadrants are the possible candidates.
So how do we deal with ducks splitting the crossing lines? We assign them to an internal node (i.e. not a leaf). This way, when we are in the process of finding which quadrant the duck we want to find possible candidates for is, we can get the ducks spanning quadrants (this is covered in the section "Finding set of collidable ducks")
We want to make sure that we are getting ducks that split lines to when asking for possible candidates. In a simple scenario, we only have one split. This would be the scenario in the image above (illustrating the different possible outcomes). If we were asking for possible candidates here, we would expect to always get the ducks illustrated by the green circles (the idea here is that we dont know which quadrant they belong to, so we always need to check them) plus one of the ducks represented by white circles.
We also have to consider the fact that the duck we are trying to find possible candidates for could be spanning a splitting line as well. In the simple scenario above, we would then be expecting to get all the ducks in the picture as possible candidates (all the ducks that are spanning lines, green cirlces, plus everything in the children - the white circles).
The last thing, that makes it more complicated is the hierarchy represented by a quad tree that has more than one level. If a duck is spanning a split line at level 1 in such a tree, we would always get that duck as a possible candidate. But if a duck spans a splitting line at level 2, we would only get that duck as a possible candidate if the duck we are investigating belongs to the same quadrant as the duck spaning the split line at level 2. The picture bellow illustrates the problem
The green circle represents a duck splitting a line, the white circles represents ducks that are not splitting any lines. The red circle represents the duck we are trying to find possible collision candidates for in case 1. The blue circle represents the duck we are trying to find possible collision candidates for in case 2. The children of Q1..Q4 will be noted as Q11..Q14, Q21..Q24 and so on.
The ducks are located in the following quadrants:
Possible candidates for the red circle will be the green circle, because it spans the splitting lines of the quadrant of Q4. But if we look at possible candidates for the blue circle, that will only contain the white circle found in Q24. The green circle that spans a splitting line is not relevant, because it only spans a splitting line inside of quadrant Q2.
If we instead placed the green circle so that it spans one of the yellow lines, then we would get the green circle as a possible candidate for both the red and the blue circle. The green circle would now belong to the top node of the quad tree (where it currently says "0 Ducks".)
Now that we have a map of our different possible outcomes, we can start plotting down some test cases.
Lets create a quad tree with with 2 levels and insert ducks into it so that we:
Then, lets create a second test also with a quadtree with 2 levels and insert ducks into it so that we:
Both the test above are quite lengthy since they require a bit of setup. They are found int mainTestQuadTree.cpp, testInsertAndGetCollidables and testInsertAndGetCollidablesCrossingSubQuadrants.
This concludes the verification of the quad tree. At first it can seem like a bit of a daunting task to try and map out possible outcomes of your game core functions but I hope this page inspired you to consider it. It usually helps to give you a more solid understanding of your own code and potential problems in it while also future proving it for when others try to rewrite or update it.