Box2D floor sensors with destructible terrain

I’ve been running into lots of interesting issues while experimenting with character control. One of the most basic ones in a platformer, which I have solved a handful of different ways so far, is the “can I jump” question. Basically, you only want to allow jumping if your character is standing on the ground — and if you’re allowing for air control of the character (I am), then you’ll also need to know whether it’s airborne to differentiate between moving on the ground v. in the air.

The way I started answering this question was to examine the list of contacts on the character’s Body object, then looking for one with a normal vector pointing straight up. This worked fine, but I was a little worried about scenarios I hadn’t envisioned, and it also seemed to be a relatively expensive calculation to perform every frame. The solution that most people online suggest, the above tutorial included, was to use a floor sensor attached to the character’s feet. Here’s what mine looks like (along with a ceiling sensor) in the debug view:

Floor and ceiling sensors attached to the main character’s fixture

But after implementing this scheme, I quickly found some buggy behavior that I couldn’t figure out, and went through several iterations of different approaches before finally solving the mystery. First, here’s an approach which is guaranteed not to work for you:

private bool IsSensorTouchingWall(Fixture sensor) {
    var contactEdge = sensor.Body.ContactList;
    while ( contactEdge != null && contactEdge.Contact != null ) {
        if ( contactEdge.Contact.IsTouching() && contactEdge.Contact.FixtureA == sensor || contactEdge.Contact.FixtureB == sensor ) {
            return true;
        }
        contactEdge = contactEdge.Next;
    }
    return false;
}

You might expect, as I did, that you could figure out whether a given sensor was overlapping another world object with this function, but that’s not how sensors work. As I discovered, Box2D plays very fast and loose with its contact edges, so that whenever the main body of my character was touching any other object, all the fixtures attached to him (including the sensors) would report this contact as well.

To make sensors useful, you have to register collision and separation handlers on them like so:

_floorSensor.OnCollision += (a, b, contact) => {
    _floorSensorContactCount++;
    Console.WriteLine("Hit floor");
    return true;
};
_floorSensor.OnSeparation += (a, b) => {
    if ( _floorSensorContactCount > 0 ) {
        _floorSensorContactCount--;
        Console.WriteLine("Left floor");
    }
};

Then to determine whether you’re standing on solid ground, you just ask whether the current contact count for the floor sensor is greater than zero.

Or, at least, that’s how literally every tutorial I discovered claimed it was supposed to work. What I was seeing in practice, however, is that occasionally this counter got out of sync, and my character could jump in the air. After a lot of painful debugging, I finally figured out the problem: when you destroy a Body, Box2D doesn’t trigger an OnSeparation event for any sensors touching it. Of course, if you then create a new body in exactly the same place, Box2D will happily send an OnCollision event from the new fixture. Consider what happens in the scenario below when the character shoots out the corner block to his left.

I know, the gun doesn’t line up with the block

Internally, what happens is that the body on which he’s standing is destroyed, then recreated as two different bodies to accommodate the now-missing tile. The floor sensor gets a new OnCollision event, but no OnSeparation event when the original Fixture is destroyed. In my humble opinion, this is a bug, so I went in and fixed it in Box2D. Here’s the patch, in Box2D’s World.cs file, with my added lines highlighted:

private void ProcessRemovedBodies()
{
    if (_bodyRemoveList.Count > 0)
    {
        foreach (Body body in _bodyRemoveList)
        {
            Debug.Assert(BodyList.Count > 0);
 
            // You tried to remove a body that is not contained in the BodyList.
            // Are you removing the body more than once?
            Debug.Assert(BodyList.Contains(body));
 
            // Delete the attached joints.
            JointEdge je = body.JointList;
            while (je != null)
            {
                JointEdge je0 = je;
                je = je.Next;
 
                RemoveJoint(je0.Joint, false);
            }
            body.JointList = null;
 
            // Delete the attached contacts.
            ContactEdge ce = body.ContactList;
            while ( ce != null ) {
                ContactEdge ce0 = ce;

                Fixture fixtureA = ce0.Contact.FixtureA;
                Fixture fixtureB = ce0.Contact.FixtureB;
                if ( fixtureA.OnSeparation != null ) {
                    fixtureA.OnSeparation(fixtureA, fixtureB);
                }
                if ( fixtureB.OnSeparation != null ) {
                    fixtureB.OnSeparation(fixtureA, fixtureB);
                }
 
                ce = ce.Next;
                ContactManager.Destroy(ce0.Contact);
            }

I don’t understand nearly enough about Box2D to know if this is the right approach to this problem, but it seems to work for me. Hopefully this post will help someone else running into the same issue. One issue with this patch is that sometimes, for reasons I don’t understand, the OnSeparation event gets triggered more than once. The fix is easy: just make sure the contact counter never drops below zero. But the fact that this happens at all makes me wary, and it’s definitely possible I’ll return to the less complicated, less efficient solution I implemented before I knew about sensors.

Nailing character controls

Every great action-exploration game has one thing in common: tight, responsive controls. If the character doesn’t respond in a consistent, intuitive way to your commands, the game is going to be frustrating to play at its most basic level. Control is so crucial that I’m spending quite a bit of effort early on to make sure it’s perfect. There are project dependency reasons to focus on this up front as well — knowing how high and far a character can jump, for example, can profoundly influence level design.

Like everyone who saw it, I was deeply inspired by Bret Victor’s talk about game development at Inventing on Principle. The most relevant portion is reproduced below:

I’m not nearly as fancy as Victor is, mostly because I don’t want to spend as long on my tool chain, and because my choice of language (C#) makes his demo slightly more complicated. But the basic idea of being able to play around with simple variables at runtime, without having to recompile or restart the program, struck me as absolutely vital. So I built my own small system to let me do that.

This version allows you to increment or decrement various character control parameters as you experiment with them. The hardest part is actually knowing which parameters might be important and how to use them to produce engaging control characteristics.

Just as a simple example, what happens when the character is standing still and the player presses right on the stick? Do you start accelerating to the right at a constant rate? In practice I found this makes the control feel beyond sluggish. I have my character instantaneously accelerating to a pretty good clip right away, then accelerating smoothly afterwards up to a maximum speed. Both these parameters are configurable so I can play around with them to see what feels right.

Jumping is even more fraught. It’s important to the player’s sense of control that holding down the jump button longer makes the character jump higher, but how to implement this behavior is anything but straightforward. For now, I have a few parameters controlling it: the initial jump speed; how much to accelerate the character for every frame the button is held once airborne; and how long this effect should persist. It’s interesting to play around with very high values for the latter two variables — setting the air boost variable above the acceleration due to gravity turns you into a rocket.

I’m also realizing that I really need to be able to fool around with gravity in this sandbox. At the moment the jumps feel downright floaty, which is an artifact of the character launching off at over 10 meters a second — it’s gonna take you a while to fall back to earth with that kind of kick. For reference, each of the tiles in the game world are one meter wide, and the character is two meters tall. Since you want a brief tap of the jump button to result in a tiny little jump, it’s becoming clear to me that the initial jump speed will need to be much, much smaller, and that the air-boosting effect will need to be much more prominent, probably involving a fade function of some sort to diminish its effect over time.

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.

Tile regeneration

I mostly had a vacation-y day today, but did some refactoring of earlier parts of the project that struck me as a bit crufty. I also changed the map system to slowly regrow tiles:

It basically works, except that when the tiles regrow they aren’t properly integrated into the physics model. Since this process is exactly what happens when a tile is destroyed and that works fine, I’ve been banging my head against the wall trying to figure out what’s wrong. Sometimes you have to know when to call it a night — often I find I can suss out the bug in five minutes the next morning.

As an aside, I learned that setting the alpha channel of the color given to SpriteBatch.draw() does nothing. You have to multiply the color itself by your alpha, between 0 and 1. This is convenient, but I don’t know how I was supposed to figure it out.

Blind refactoring to get Tiled integration

Like most estimates in software development, it turned out that integrating with the Tiled Map Editor format was trickier than I expected. I finally got it working:

Other than switching map formats, the only other change I made was to double the tile size to 64 pixels on a side. I’ll be doing some experimentation with character control this week to see if this is a good idea or not, but my gut feeling at this point is that showing too much of the world at once will be bad for fundamental aspects of gameplay.

The biggest stumbling point in the integration was the fact that the library I was using reads the map data as gzip-compressed, and newer versions of Tiled use zlib compression by default. There were also a couple minor bugs in the source itself that I may release corrections to at some point if someone wants them, although at the moment my version of the code is a little entangled with my game-specific logic.

But overall things went surprisingly smoothly, once I figured out how the map reader library worked. This was a “blind refactoring,” where the change I was making was so large and fundamental that there was no clear step-wise progression of small, testable changes to get from where I started to where I wanted to go. I went way, way out in the weeds: I made a copy of my existing level system, changed the name, switched a couple using statements around, then went hunting for red squigglies in Visual Studio. This style of refactoring is more effective than you might expect, and is one of the main reasons that I prefer statically typed languages for large projects. Still, even after all the red squigglies were taken care of, it took quite a bit of head-scratching and experimentation to find my way back in from the weeds. And as it turns out, I introduced a new graphical artifact, which you can see in the video above: when using single-sheet tilesets with floating point drawing operations, it’s possible for your graphics card to draw a little more of the area than what you wanted. Like many floating-point problems, it takes place at the hardware level and is basically unavoidable, although several good workarounds exist. In my case, the answer is to simply provide a buffer margin of one pixel around each of the tiles in the sprite sheet. That seems to be a lot more palatable than translating everything to be integer-based, especially since Box2D uses floating point math.

Tomorrow is dedicated to getting the controls to feel nice and tight, locking down things like horizontal acceleration curves, jump height and speed, bullet speed, and so on. After that I’ll begin experimenting with different weapons and enemies, possibly moving into screen overlays at the same time.

The death of a hand-rolled mapping system

I started this project with the conceit that I was going to write my own, custom mapping system using PNG files. I got the idea watching this video by notch a couple years ago:

You can see how I became so enamored of the concept. What could be easier than drawing your levels as PNG images, pixel by pixel? Also, it seemed like it would be pretty fun to code up. And it was!

All progress videos so far use this system of level creation / editing. Here’s what the map from the last post looks like as a PNG.

Shit's so cash

It’s really simple in this incarnation: every black pixel gets turned into a solid tile, white ones get a starry backdrop. In the full version, now destined to never be written, each different color would correspond to a different tile in the tile set. Sadly, I kind of knew before I started writing this system that it wasn’t going to be sufficient for the game I want to write — but sometimes you have to ignore little doubts and bull ahead. The main problem is that I need to attach various bits of metadata to map tiles, like “you can destroy this tile using your gun” or “this is actually in the foreground” or “this tile turns into an enemy when you walk within 4 tiles of it.” Of course, I contemplated going full retard and seeing this technique through to the bitter end despite its obvious drawbacks. Here are some of the workarounds I considered, along with my reaction to considering them:

  • Cram a bunch of metadata into the alpha channel of each pixel. Only 8 bits of info there, and it’s basically impossible to see while editing, but this is my best idea…
  • Choose a different color for every permutation of tile type and metadata. I can’t decide if that’s stupider than using the alpha channel or not
  • Make each map consist of several PNG layer files. This is going to be impossible to coordinate without writing my own level editor, which kind of defeats the purpose of using PNG
  • Put metadata into a separate data file naming each tile by its coordinates. Same objection as above, but also shoot me in the face

Then I discovered Tiled Map Editor, which does everything I want except let me draw arbitrary shapes with paint-like tools. Specifically, it supports arbitrarily many layers of tiles, with the ability to add additional non-tiled objects on top of them. It even has a variety of XNA integration libraries; I chose the one that seems to be the most straightforward and stable, written by Kevin Gadd.

I hope to finish integrating with the Tiled map format tomorrow, but since I’m leaving town for the weekend relatively early it might bleed over into Monday.

Disaster averted for now

Yesterday I said I was going to scale-test the way I was destroying game tiles, so I built a relatively large map to see how it would perform when I started blowing holes in it:

This is the end result, which has good enough performance to convince me that I can make this scale to a per-room basis, with possible hacky subdivision of surfaces as necessary.

The gristly details

To get this to be performant for this large a room, I needed to do some performance tweaking. The first time I successfully ran the test, each block destroyed off the largest connected surface took over a second. I dug in for some performance testing with the magic of Stopwatch, where I confirmed my worst fear: over 99% of the performance was asking Box2D to create the loop shapes. I was beginning to think that this negative result would force me to drop Box2D altogether, but then I hit upon the idea of eliminating redundant co-linear loop vertices — my naive first implementation just added a new segment to the loop for every tile it processed. This reduces the number of vertices in the chain by a couple orders of magnitude and brings the complexity of the shape down to where Box2D can easily chew it. I’ll be coming up with other tests of Box2D’s fundamental capabilities in the next few days.

C# is not actually just a nicer version of Java

This is part one in what I feel certain will be a long-running series.

Most of the time I feel like C# is a better version of Java, but some language choices strike me as utterly foreign. For example, variable scope and declaration space are not the same thing! This means that you cannot reuse a variable with the same name as another one inside the same declaration space (like a method), even if those two separate declarations are in different scopes. This stack overflow question asks if it’s just nanny-state compilerism, and the very snarky top answer acts like it’s not completely counter-intuitive that this should be an error, rather than a warning. Here’s an example of the issue, reproduced from the stack overflow question:

for (int i = 0; i < 10; i++)
{
    Foo();
}
for (int i = 0; i < 10; i++) // Works just fine!
{
    Bar();
}

-----------------------------------------

for (int i = 0; i < 10; i++)
{
    Foo();
}
i = 10 // Error: The name 'i' does not exist in the current context

-----------------------------------------

for (int i = 0; i < 10; i++)
{
    Foo();
}
int i = 10; // Error: A local variable named 'i' cannot be declared in this scope because it would give a different meaning to 'i', which is already used in a 'child' scope to denote something else

-----------------------------------------

The top code fragment runs fine in both C# and Java. The middle one is a compile error in C# and Java. The bottom code compiles and runs fine in Java, since the first i is lexically scoped to the loop block. In C# it gives you the error in the comment. Gleaned from around the web, the justification for this being a compiler error appears to go something like this:

Look at it this way. It should always be legal to move the declaration of a variable UP in the source code so long as you keep it in the same block, right? If we did it the way you suggest, then that would sometimes be legal and sometimes be illegal!

My response: so? It's an imperative language. Yes, the order of declaration of members in a class is order independent, but the order of statements in a block is the program. No one expects to be able to arbitrarily move chunks of code up and down the page without changing the behavior.

In short: this absolutely is nanny-state compilerism. If I want to reuse a name in an independent scope, let me do it! You're going to end up with a lot of vector2s otherwise.

Exploring destructible terrain with Box2D

An important part of Escape from Enceladus is destroying parts of the game world through various means in order to solve puzzles and find secret passages. It’s absolutely essential that the level engine I build support this very well, and I’m still evaluating if Box2D is up to the task. Today I hacked together a rudimentary test of shooting at walls and making them vanish from the game model:

The green lines around the walls are the debug view of Box2d, showing the loop / chain shapes that bound each connected block of tiles. It would have been much simpler to model each tile in the game world as its own solid body, but because Box2D evaluates each shape independently when modeling collisions, this results in the buggy behavior of a character tripping over an interior vertex of perfectly flat terrain. The solution is to find the bounding box of each connected island of solid tiles and give it to Box2D as a chain shape.

However, as I learned when researching this critical aspect of gameplay, you cannot modify the number of vertices in a Box2D shape without risking crashing the entire engine. This means that I need to destroy and recreate the shape every time it’s modified, which has the potential to be pretty memory / CPU intensive. I had a couple ideas to tackle the issue.

The first was to take the existing shape, expressed as a list of vectors, and permute it to snip out destroyed segments and insert new borders. In practice, this turned out to involve a nightmarish labyrinth of manually coded special cases and nested logic. I decided there must be a better way.

The method used in the above video is to simply redetermine the boundary of the shape or shapes after they have been modified, just as I do when building the level in the first place. I’m more than a little worried that this practice won’t scale, which is why I plan to test it on a very, very large map as soon as I get some of the other bugs ironed out.