Ironing physics integration bugs out of the mapping system

As the saying goes, you can never prove the absence of bugs in a program, only their presence — unless you’re Knuth, but so few people are these days. I proved the existence of several systemic bugs in my mapping system today, and although it was pretty frustrating and tedious to figure out their root cause, it felt awesome to fix them. Here’s the end result.

The way the enclosing Box2D loop shifts and morphs as blocks come and go is a thing of unspeakable beauty. I might be too close to this.

The problem from yesterday’s post did turn out to be pretty simple after all: I wasn’t destroying the existing shape before creating a new one. The gritty details are obscure and have to do mostly with me being a terrible programmer. I tooled around with the debugger for about an hour this morning, then had the crucial moment of insight at about the third mile of my run around the lake.

But having fixed that bug, I was free to notice a much more serious one: once in a while, when randomly shooting up the terrain as I like to do when I’m testing, the game would freeze (infinite loop) or crash. I had noticed this behavior a few times before, but the mapping system has been in such constant flux that I kept thinking I had fixed it, when really it had been getting buried under other less serious issues. In the end I had to sit down with pen and paper and laboriously draw the process of assembling the Box2D chain from the world tiles. And that’s when I found the tile pattern that broke my chain-building algorithm.

You mother futon.

What’s interesting about this shape, and what caused it to crash the algorithm, is that it’s an adjacency island (transitive closure of simple 4-way adjacency) whose enclosing chain shape intersects itself at some corners. The wasn’t a case that I had considered when writing the original algorithm, which goes something like this:

  1. Do a simple depth-first search to find an adjacency island (this part is easy)
  2. Look at each tile in the island and determine which of its edges, if any, need to contribute to the enclosing chain shape
  3. Create a map (or dictionary, if you’re a C# guy) from vertices to these edge segments
  4. Choose a random vertex and start walking around the data structure, segment by segment
  5. When you reach your initial starting point again, you are done

#4 is kind of vague. Here’s what the code actually looked like:

while ( edges.HasEdges() ) {
        Vector2 initialVertex = edges.GetInitialVertex();
        Vector2 currentVertex = initialVertex;
        // Pick a random edge to start walking.  This determines the handedness of the loop we will build
        Edge currentEdge = edges.GetEdgesWithVertex(currentVertex).First();
        Edge prevEdge = null;
        Vertices chain = new Vertices();
        IList<Vector2> processedVertices = new List<Vector2>();
        Vector2 offset = new Vector2(-TileSize / 2); // offset to account for different in position v. edge
 
        // work our way through the vertices, linking them together into a chain
        do {
            processedVertices.Add(currentVertex);
 
            // only add vertices that aren't colinear with our current edge
            if ( prevEdge == null || !AreEdgesColinear(prevEdge, currentEdge) ) {
                chain.Add(currentVertex + offset);
            }
            currentVertex = currentEdge.GetOtherVertex(currentVertex);
            foreach ( Edge edge in edges.GetEdgesWithVertex(currentVertex) ) {
                if ( edge != currentEdge ) {
                    prevEdge = currentEdge;
                    currentEdge = edge;
                    break;
                }
            }
        } while ( currentVertex != initialVertex );

        Body loopShape = BodyFactory.CreateLoopShape(_world, chain);  
        edges.Remove(processedVertices);
}

See the problem? I sure didn’t. That’s why I’ve highlighted the two issues for you.

But even when I understood what the problem was, for some reason I thought it would be too hard to fix, so I tried to fudge things by making the shape not overlap itself. This idea was… poorly conceived.

It made perfect sense in my head

Back to the bugs above. The first bug is how I was choosing the next edge in the shape to walk: at random. This works fine for simple shapes, where each vertex has exactly two edges hanging off it, but not self-intersecting ones, which can have four edges per vertex.

The solution is to walk the shape systematically, in a handed fashion. For my implementation, this means taking a right-hand turn whenever possible:

public Edge GetNextEdge(Edge edge, Vector2 initialVertex) {
    var otherVertex = edge.GetOtherVertex(initialVertex);
    Edge down = new Edge(otherVertex, otherVertex + new Vector2(0, 1));
    Edge up = new Edge(otherVertex, otherVertex + new Vector2(0, -1));
    Edge left = new Edge(otherVertex, otherVertex + new Vector2(-1, 0));
    Edge right = new Edge(otherVertex, otherVertex + new Vector2(1, 0));                

    if ( otherVertex.X > initialVertex.X ) { // walking right
        return new[] { down, up, right }.FirstOrDefault(e => _edgesByVertex[otherVertex].Contains(e));
    } else if (otherVertex.X < initialVertex.X) { // walking left
        return new[] { up, down, left }.FirstOrDefault(e => _edgesByVertex[otherVertex].Contains(e));                    
    } else if (otherVertex.Y > initialVertex.Y) { // walking down
        return new[] { left, right, down }.FirstOrDefault(e => _edgesByVertex[otherVertex].Contains(e));                                        
    } else if (otherVertex.Y < initialVertex.Y) { // walking up
        return new[] { right, left, up }.FirstOrDefault(e => _edgesByVertex[otherVertex].Contains(e));                    
    } else {
        throw new Exception(String.Format("Illegal state when walking edge {0} from {1}", edge, initialVertex));
    }
}

The second bug, on line 30, is that it’s not vertices that I need to remove from the set of edges waiting to be processed, it’s the edges themselves. In the shape above, it’s clearly necessary to process the same vertex more than once.

Overall, a good, solid day. I wouldn’t have thought so this morning, but the sense of triumph at having held these bugs down and given them a stern talking to makes all the aggravation they caused worthwhile. Since I’m so clearly incapable of knowing what I’ll actually get around to working on tomorrow, I won’t make any promises.

Leave a Reply