Implementing a pass-through 3.0 vertex shader for games without vertices

I stated earlier that it was impossible to use a vertex shader in XNA when writing an entirely 2D game. Like a lot of things I fervently believe, this turned out to not actually be the case. When fancying up my original wave-distortion shader to make it work in arbitrary directions, I had to do quite a bit more trigonometry, and this pushed me over the maximum of 64 arithmetic slots allowed by shader version 2.0. I had a choice: I could either get smarter about my math, or figure out how to make shader version 3.0 work with XNA sprite batches. It actually didn’t turn out to be that hard once I believed it must be possible.

The problem I was seeing when attempting to implement a vertex shader naively before is that the entire screen would render one solid color during the duration of the Effect. The key seems to be that you need to create an orthographic projection the size of the screen and then multiply it by a half-pixel offset translation matrix, like so:

Matrix projection = Matrix.CreateOrthographicOffCenter(0, spriteBatch.GraphicsDevice.Viewport.Width, spriteBatch.GraphicsDevice.Viewport.Height, 0, 0, 1);
Matrix halfPixelOffset = Matrix.CreateTranslation(-0.5f, -0.5f, 0);
effect.Parameters["MatrixTransform"].SetValue(halfPixelOffset * projection);

For the record, omitting the half-pixel translation will make your full screen post-processing effect a bit blurry. It’s been too long since I took a graphics course to remember precisely why that is, and I’m too lazy to learn it until I absolutely need to.

Anyway, once you have the above in your XNA code, then your version 3.0 vertex shader is as simple as:

float4x4 MatrixTransform; 

void SpriteVertexShader(inout float4 vColor : COLOR0, inout float2 texCoord : TEXCOORD0, inout float4 position : POSITION0) { 
    position = mul(position, MatrixTransform); 
}

The underlying reason that you need to specify a vertex shader for a version 3.0 pixel shader but not a version 2.0 pixel shader seems to be that, when you don’t specify a vertex shader explitly, XNA will give you the default one supplied by the sprite batch, and it uses some ridiculously old version like 1.1, which is incompatible with 3.0 (but not 2.0). I’m the first to admit I find this whole shader business confusing and often counter-intuitive, but surely that will wane with experience.

Implementing a wave-distortion shader with Nvidia FX Composer

I spent most of the day fighting with one of most difficult and arcane pieces of software I’ve ever used: Nvidia FX Composer. I think it was written five or so years ago by members of a suicide cult, who upon releasing it promptly all drank the poison cool aid. Nvidia makes a pretense of running a customer support forum for the product, but most of the posts are desperate questions without a single response. On the other hand, the included documentation is relatively massive… but years out of date and therefore occasionally completely inaccurate, which in many ways is worse than not having any at all. Of course, my own total lack of experience writing HLSL didn’t help, either.

In the end I persevered and got this effect implemented and merged into my game:

Once I finally figured out how to use it, FX Composer was a huge help in being able to rapidly experiment with different effect parameters and see the result. Here’s what the software looks like once it stops kicking you in the balls:

What I had so much trouble with was figuring out how to convince the software that my shader was a post-processing effect to be rendered onto the entire scene, not onto a 3D object in the scene. After a lot of research and experimentation, I started with a working post-processing shader provided as a sample and starting taking things out of it until it broke. That’s when I learned you need these special semantics to tell FX Composer that the shader is for post-processing:

float Script : STANDARDSGLOBAL <
    string UIWidget = "none";
    string ScriptClass = "scene";
    string ScriptOrder = "postprocess";
    string ScriptOutput = "color";
    string Script = "Technique=Main;";
> = 0.8;

If this looks like gibberish to you, it does to me too. But these are the magic words needed to get FX Composer to let you apply a shader to an entire scene. It’s also important that you have a vertex shader defined in your technique, even if you’re only using a pixel shader — nothing will work otherwise. Here’s a pass-through shader you can use:

struct VertexShaderInput
{
    float4 Position : POSITION0;
	float2 Txr1: TEXCOORD0;
};
 
struct VertexShaderOutput
{
    float4 Position : POSITION0;
	float2 Txr1: TEXCOORD0;
};


VertexShaderOutput VertexShaderFunction(VertexShaderInput input)
{
    VertexShaderOutput output;
  
    output.Position = input.Position;
	output.Txr1 = input.Txr1;
    return output;
}

The final piece of the puzzle was getting the updated shader back working in XNA. There are lots of articles on this on Google, so no need for me to repeat it here. But I did discover something interesting: if you have an entirely 2D game, not a single 3D triangle rendered anywhere, then using a vertex shader in your effect, even the pass-through shader, will cause no pixels to get through to your pixel shader. The solution is to just comment out the vertex shader in your pass. Since FX Composer requires this shader and XNA requires it be absent, toggling the comment is an easy way to make both systems happy.

technique Main <
	string Script =
	"RenderColorTarget0=ScnMap;"
		"ClearSetColor=ClearColor;"
    	"ClearSetDepth=ClearDepth;"
		"Clear=Color;"
		"Clear=Depth;"
	    "ScriptExternal=color;"
	"Pass=Pass0;";
> {
    pass Pass0 <
       	string Script= "RenderColorTarget0=;"
			"Draw=Buffer;";
    >
    {
    //VertexShader = compile vs_2_0 VertexShaderFunction();
	PixelShader = compile ps_2_0 PS_wave();
    }

This was a bit more of a rabbit hole than I really intended to climb into, but at least I learned a few somethings.

Also, I filmed the motion-capture sequences for the main character’s animations today in Roark’s back yard. I need to do a lot of video editing on the result, then the hard labor of cleaning up all the pixels and shoving it into the game, but that’s tomorrow. For now, enjoy this outtake from the shoot:

SWT listeners are incompatible with Java lambdas

Programming in C# for the last few weeks has really gotten me to pay attention to all of Java’s inadequacies. One of the biggest ones, which C# handles so well, is lambda functions, or closures. Java has been promising to add support for them forever, and it looks like it’s finally going to happen in Java 8. But I’m not exactly watering at the mouth, mostly because the way they have chosen to implement it is going to make adoption by existing libraries a huge pain in the ass. Here’s the problem:

Interfaces that have just one method are called functional interfaces. Lambda expressions can be used anywhere we have a functional interface.

Sure, there are lots of interfaces with just one method, like Runnable, Callable, FileFilter, etc., and all of these will be able to enjoy the nice new syntactic sugar. This:

button.addActionListener(new ActionListener() { 
    public void actionPerformed(ActionEvent e) { 
        ui.dazzle(e.getModifiers());
    }
});

Becomes this:

button.addActionListener(e -> { ui.dazzle(e.getModifiers()); });
button.addActionListener(e -> { ui.dazzle(e.getModifiers()); });

Pretty nice, huh?

Well, there’s just one problem: you can’t do this if the interface required by the method signature has more than one method defined. In my other life I spend a lot of time writing Eclipse plugins using a pretty nice windowing toolkit called SWT. Most of SWT’s listener interfaces have more than one method defined on them. SelectionListener has two. FocusListener has two. DropTargetListener has five. So any method that takes one of these interfaces can’t join in the syntax sugar party, sorry.

This problem isn’t specific to SWT — all the classes above were basically adapted from analogues in Java’s own AWT. Most libraries declare mostly non-functional interfaces that require you to implement more than one method to use. SWT and other frameworks get around this by providing abstract classes they call Adapters, such as SelectionAdapter. When you don’t want to implement one of the interface’s methods, you just supply an anonymous inner class that extends the adapter, rather than the interface, like so:

button.addSelectionListener(new SelectionAdapter() { 
    public void widgetSelected(SelectionEvent e) { 
        playAnAnnoyingSound();
    }
});

There is absolutely no support in Java 8 for lambdas that use this wide-spread pattern. You won’t be able to use lambdas anywhere you currently do something like this.

I understand that it’s tough to add language features, but people need to be able to use the new features, and use them consistently, for them to be useful. Forcing me to hop back and forth between anonymous inner classes and the nice new lambda syntax is just terrible. I think the attitude I’m supposed to adopt is that whenever I get to use the new syntactical sugar I’m being given a special treat, but I just can’t look at it that way.

As an alternative, the compiler could (this is just off the top of my head) generate an anonymous class for you with the Adapter pattern, allowing you to, in effect, implement only part of an interface as you saw fit. This would dovetail nicely with the new default implementation for interfaces, don’t you think?

If anyone has a tricky way to get around this issue by adding some layers of abstraction, I’m all ears.

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.

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.

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.

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.