My spare time for the last week or so has been spent working on a small personal project for a game idea that’s been buzzing around my head for some time. This small idea requires me to write some 2d collision code for convex and non-convex shapes.
Now, as somebody who has written 3d collision code across multiple platforms in the past, I thought that this particular task should be a doddle. After all, it’s just 2d collision, what could go wrong? I know what I’m doing, and besides, given that I was working on this in my spare time, often late at night, I didn’t have time to waste on silly distractions that I didn’t need.
Why bother writing code to allow me to easily visually verify that the data I passed to my code was going to be correct? After all, I could rely on my tired eyes and brains, figuring out if the data was valid by looking at numbers in the debugger!
It’s probably no surprise to you at this point, dear reader, that I could not have been more wrong.
Just a normal box…
I started out by testing my collision code using simple boxes. After all, boxes are easy to define. What could go wrong? As it happens, everything, Because even though boxes are easy to define, some additional information about the box is required to be calculated for it to be used the collision code.
In my case, I thought I could take a short cut and make a custom “AxisBox” shape that made a lot assumptions about the shape topology so I didn’t have to calculate things like the normals. After all, I’m smarter than the computer and know better, right?
Building a box
Let’s take a look at the process of calculating the convex shape information from an axis box. It’s pretty straight forward, and looks like this;
Step 1: Take the minimum and maximum bounds of the box and expand them to vertex corners, so that the vertices are listed in clock-wise order.
Step2: Calculate the edge vectors, so that each edge vector points towards the next vertex in the list that was generated in step 1.In the case of the last vertex (v3), the next vertex is the first vertex in the list (v0)
Step3: Calculate the edge planes (normal and distance), so that the plane normals point towards the outside of the shape.
At this point, we should have all of the information required to use the box in the collision system. As I mentioned, for a static (does not move or rotate) axis box, I took some shortcuts and missed out step 2 and parts of step 3 by plugging in the values myself. After all, the plane normals for a box are either <1, 0>, <-1, 0>, <0, 1> or<0, -1> and all I had to do was to put those value in the right slots in the edge list.
Where I went wrong
How could I possibly get that wrong? As it happens, I got it all very wrong. I found two very silly bugs in my code that meant;
- The vertices were not in the right order, so that they did not match the layout/ordering expected in Step 1
- My normals were assigned to the wrong edges. For example The edge formed by v0, v1 should have the normal <-1, 0> but instead had the normal of <0, 1>.
- Because of the above issues, the plane distances were calculated incorrectly.
The end result being that the SAT overlap test wasn’t working as expected. I spent quite a bit of time looking over the code to test if convex shapes were overlapping, scratching my head. Over the course of two evenings where I was already tired, I stayed up quite late and using what little free time I had, drilling down through my code to uncover where I was going wrong.
It wasn’t until around midnight on the second evening where I finally discovered my error, and cursed my stupidity at screwing up something so straightforward. The very information required for the collision system to work correctly, was wrong right from the beginning.
Could I have done better? Well, as it happens, I could have. In fact, I could have done MUCH better.
A picture paints…a lot of debugging info…
One of the things that has been true during my career is that you can never have too many debugging tools. It doesn’t really matter how simple or complex your code is, or how simple (or complex) the platform that you’re working on is; having tools that help you home in on the cause of the problem are a god send.
And this is where I messed up. I didn’t even provide myself with the simplest of tools to verify that the input I was providing my collision system was actually valid. I just assumed it would be.
I didn’t exactly spend a lot of time on the rendering side of things for my small project. All I needed it to do, was to render the edges of the shapes, as can be seen for the below screenshot.
Everything looks pretty sane, right? After all, the lines obviously form the intended boxes but there is noinformation to give me visual clues about the additional topology of the convex shapes formed by the boxes.
So I added a debug render functionality that I can enable and disable. This debug render mode renders two important features of the shape;
- The direction of the edges. The lines that form the edges are rendered using the colour white for the first vertex in the edge, and white for the second colour. This gives me a nice visual clue about the direction of the edges.
- The edge normals are rendered – this gives me a very direct visual clue to tell me that the normals are facing the correct direction.
Here’s the same screen shot with the debug info turned on;
Let’s be honest; the debug rendering here isn’t really all that complex or special. But it provides and nice, quick and easy way to ensure that the shape topology makes sense and is valid for the collision system.
This is much better than stopping the app in the debugger and trying to see how the numbers match up to how the shape should look. And in the case of parts of the topology of the shape that are calculated, we can more easily see if the results make sense with respects to the rest of the shape.
The rather unfortunate truth here is that in not implementing the debug render straight away, I violated one of my critical rules in dealing any sort of bug or problem that is related to content. And that rule is; if content is involved in the issue in some way or form, then it’s the first thing that is checked and verified. Whether it’s audio, animation, textures, collision data or any other sort of content input; its the first thing that should be checked.
And in this case, it was the last thing. I spent two rather frustrating evenings muddling around in the debugger until I decide to verify the inputs.
But let’s not pretend that this is only an issue when you’re working on a personal project, late at night with only a few hours to spare here and there. Exactly the same problem with making simple mistakes can easily happen when your brain is fresh, and working on something that is required for your job during normal hours.
Having a visual representation of the information that was used for the input, as well as the information that is calculated gives a very direct method of communication. It doesn’t require much interpretation on the part of the programmer, which relies on said programmer being alert and not making even more mistakes in the interpretation. Drawing debug information can save a lot of time in eliminating or identifying if the input data as cause of an issue, leading to solving the issue in a much smaller time frame.
It make take a few minutes to implement some sort of visual debugging tool for your input data, and those few minutes along with the chance of context can seem like an unnecessary distraction. But ultimately, it could save a couple of hours tracing the problem back to the input data via the debugger.
If there’s a take away lesson here, it’s that there’s no such thing as a waste of time or effort if it makes your life easier. And I have to admit that I am slightly ashamed that I failed to heed this lesson, one that I had learned more than 22 years ago, when I first started my career as a programmer.