The collision system is one of the areas worth investing time into to get rid of all the bugs and ensure it’s 100% robust. However, it is not trivial to do that. I can test it by walking the character all over the map, but that’s a lot of manual work and it is extremely likely many cases will not be caught. Furthermore, this method of testing only confirms whether or not my collision is bugged, but doesn’t help me answer why the bug occurs or how to fix it. Once the character is stuck, I lose the information of the input that triggered it. In addition, the same exhausting test will have to be applied every time I make an adjustment to the collision system. This makes a debug infrastructure that automatically tests and records the collision system very desirable.

Rapidly Exploring Random Trees

Thanks to Casey’s blog, I have discovered Rapidly Exploring Random Trees, an algorithm that’s very useful in this case. It is an algorithm that randomly expands a tree out to explore a given space, often used in pathfinding. I think it’s a fitting algorithm to use here because my collision testing process is literally “exploring” the whole map in order to find places where players falls through ground or gets stuck, then investigate why that happened.

Here’s how the algorithm works: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
explore_tree tree = {};
for (int i = 0; i < iteration_count; ++i)
{
    vertex rand_vertex = random_sample(space);
    if (tree.is_empty())
    {
        tree.add_vertex(rand_vertex);
    }
    else
    {
        vertex neighbor_vertex = find_closest_vertex(tree, rand_vertex);
        vertex new_vertex = move_towards(neighbor_vertex, rand_vertex, delta); 
        tree.add_vertex(new_vertex);
        tree.add_edge(neighbor_vertex, new_vertex);
    }
}


Basis of debug system

In order to adapt this algorithm to test the game’s collision, I’ve made a couple of changes to it. Instead of storing the entire tree as a hierarchy of vertices, I store the vertices and edges in memory separately, both as linear arrays. I want the edges to be stored explicitly because they represent movements, and are therefore required by the debug system. Vertices are used to generate new edges, but besides that they hold no valuable information.

When a new vertex is connected to the graph, the closest vertex will move towards the new vertex using the exact same movement code that the player uses, which will then expose any hidden bugs. In other words, move_towards() function in the above pseudocode will be replaced by player’s movement code. In doing that, each edge in the tree becomes a movement simulation of the player.

In addition, each edge in the tree records information beyond just movement. It also records if the movement itself is successful and what velocity input is used, since neither of these pieces of information can be inferred solely by looking at starting point and ending point of the edge.

I can use this algorithm as the basis to construct a network of movements, highlighting the movements that provoke bugs. Therefore, I retain the inputs required to reproduce the bug and am able to step through the code to see what’s going on.

First attempt

Here’s a screenshot of the exploration tree in action:


I’m surprised by the results. The tree doesn’t give perfect coverage, but it does expose collision bugs quite fast. After about a ten thousand iterations, it finds about 200 movement inputs that will trigger a bug in the collision system. The bug-triggering edges are labelled as orange in the picture (If you are having trouble seeing it in the small picture, you can watch the video I linked later in the post instead).

There are some bizzare moments when the generated tree just doesn’t make sense:


The map is well covered by the exploring tree, but there is a small patch of ground that is never even touched by it. Turned out, because the exploring tree uses the exact same movement code, it has fallen through the ground and branched out in the underground instead:


It is both interesting and useful because it exposes the bugs in my movement system. I fixed these issues by marking the end vertices of bug-triggering movements as defects, so that it won’t be used to branch out the tree.

Further enhancement

I am happy with the results. It gives me a good idea of where the bugs usually occur and therefore helps me infer how they occur. To further help me investigate the collision bugs, I added features such as auto-focusing the camera on selected bug-triggering edges and the option to step through the movement code in the debugger by feeding the inputs recorded inside each edge.

On a side note, I found __debugbreak() super useful and somehow I never discovered it until recently. All it does is setting a breakpoint by writing code. With it, I can just write:

1
2
3
4
5
6
if (Button(“run code in debugger”))
{
    __debugbreak();
    RunMovementCode(Input Recorded In This Edge);
    __debugbreak();
}


I just have to start the application inside Visual Studio and press the button, no manual work needed to set the breakpoints.

Seeing it in action

I also recorded a video where I demonstrated the debugging system in detail. You can see the exploration tree search for bugs in real time and how it's extremely useful in debugging: