I recently hacked together a simple implementation of mantling, which allows the player to grip onto ledges while falling, and climb up onto ledges while standing below them or hanging off of them. It’s simple, but it does add a nice extra bit of mobility. It definitely helps in cases where you just barely miss a jump, because now you can grip onto the ledge and climb up instead of falling and having to try the jump again.

The implementation is pretty simple, so I’ll just summarize it here: While falling, if the player is pushing the dpad towards a nearby wall, I do some simple intersection tests to see if his feet are making contact with the wall, and if there’s room above him for him to climb up onto the surface. If both of these conditions are met, I ‘grip’ him to the wall until the dpad is released. At this point, you can press up to climb up onto the ledge automatically. Climbing up is a simple animation where I lock the player’s input temporarily and interpolate his position along a curve to bring him up onto the ledge, and restore input and normal motion/collision detection.

Tags: csharp, Gruedorf, platformer, xna

After doing some more prototyping, I started to realize that my test level had some serious pacing and playability issues. The most important issue was that flipping switches or standing on pressure plates would sometimes cause things to occur offscreen, which made it difficult to understand what was going on in a puzzle.

To try and solve this problem, I implemented a basic system for automatic camera control. When an object in the game’s state changes, it asks the Game object to make sure the player notices, by calling CameraLookAt and passing in its own position.

Every frame the game runs an UpdateCamera function that scans through all the CameraLookAt requests from the previous frame, and uses a simple algorithm to determine whether it should do anything to the camera, and if so, what point it should center the camera on:

• At least one of the CameraLookAt requests must be for a point that is not currently on-screen.
• If any of the requests is for a point that is on-screen, use all of the requests to determine the point to center the camera on.
• Compute a bounding rectangle that contains all the CameraLookAt requests, and center the camera on the center of that rectangle.

One slight problem this algorithm has is that it only operates on points, not areas of interest. For now, I solve this by excluding 10% of the screen on all sides, assuming that the player is unlikely to notice things changing on the edges of the screen. In the future, I’ll probably change the algorithm to operate on rectangles. The use of a bounding rectangle also means that if a lot of things happen at once, it won’t be able to show them all to the player. I think the only way to solve that problem is to control the camera manually, either with player inputs or with carefully scripted camera controls for each level. The latter is the approach I plan to use in the future.

The camera transitions are also a bit too abrupt. One future improvement will be to adjust the speed at which the camera moves, based on how far it has to move. It might also be good to try and move the camera in advance of changes in the level, so it’s easier for the player to figure out what happened. Since one-way barriers transition instantly it can be a little hard to realize why the camera is looking at them.

protected void UpdateCamera () {
    float screenWidth = GraphicsDevice.Viewport.Width;
    float screenHeight = GraphicsDevice.Viewport.Height;

    if (CameraLookAtQueue.Count > 0) {
        var cameraTopLeft = new Vector2(ViewportPosition.X + (screenWidth * 0.1f), ViewportPosition.Y + (screenHeight * 0.1f));
        var cameraBottomRight = new Vector2(ViewportPosition.X + (screenWidth * 0.9f), ViewportPosition.Y + (screenHeight * 0.9f));

        var minPos = new Vector2(float.MaxValue, float.MaxValue);
        var maxPos = new Vector2(float.MinValue, float.MinValue);
        float duration = 1.0f;
        int offscreenCount = CameraLookAtQueue.Count;

        for (int i = 0; i < CameraLookAtQueue.Count; i++) {
            var la = CameraLookAtQueue[i];

            duration = Math.Max(la.Duration, duration);
            minPos.X = Math.Min(minPos.X, la.Position.X);
            minPos.Y = Math.Min(minPos.Y, la.Position.Y);
            maxPos.X = Math.Max(maxPos.X, la.Position.X);
            maxPos.Y = Math.Max(maxPos.Y, la.Position.Y);

            if ((la.Position.X >= cameraTopLeft.X) &&
                (la.Position.Y >= cameraTopLeft.Y) &&
                (la.Position.X <= cameraBottomRight.X) &&
                (la.Position.Y <= cameraBottomRight.Y))
                offscreenCount -= 1;
        }

        var center = minPos + ((maxPos - minPos) / 2.0f);

        if ((center.X >= cameraTopLeft.X) &&
            (center.Y >= cameraTopLeft.Y) &&
            (center.X <= cameraBottomRight.X) &&
            (center.Y <= cameraBottomRight.Y) &&
            (offscreenCount == 0)) {
            // If all the points are on screen, don't move the camera.
        } else {
            CameraStack.Add(new LookAtCameraController(
                center, duration
            ));
        }

            CameraLookAtQueue.Clear();
        }

        Vector2 pos = new Vector2();

        for (int i = 0; i < CameraStack.Count; i++) {
        var cc = CameraStack[i];
        var newPos = cc.GetCameraPosition(screenWidth, screenHeight);
        var w = cc.GetWeight();

        if (w <= 0) {
            CameraStack.RemoveAt(i);
            i -= 1;
        } else {
            pos = new Vector2(pos.X + ((newPos.X - pos.X) * w), pos.Y + ((newPos.Y - pos.Y) * w));
        }
    }

    ViewportPosition = pos;
}

Solving the visibility problem with the camera made my test level’s puzzles a lot easier to follow.

The pacing issues are more fundamental, unfortunately. My test level has a lot of boring, empty spaces to run through. One thing that will help is adding more content to the level, like enemies to fight in the empty hallways, deadly traps to avoid, etc. But even then, having to trek through lots of areas repeatedly to solve puzzles sucks, so I’m going to have to pay careful attention to this when designing and testing levels. I haven’t come up with a good strategy for making the pacing feel ‘right’ yet.

I also spent some time doing some performance tuning using the CLR Profiler and dotTrace, for memory and CPU profiling respectively – I had reached the point where my game no longer ran at 60FPS on the XBox 360, though it ran fine on my PC, which is kind of to be expected – I hadn’t done much optimization at all up until this point.

Other than basic things like tuning code in hotspots to be more efficient, I also spent a little time trying to control my allocation rate. On the 360, if you allocate temporary objects rapidly enough, the garbage collector will have to interrupt you often, causing your game to stutter. I had to hunt down a few places in my game code where I was accidentally creating temporary instances of things like delegates and boxed value types.

In one case, the compiler had made a clever optimization by moving a new statement further up in the function for performance reasons, without taking into account that it caused a function to always allocate a temporary object instead of allocating one sometimes. At first I thought this was a compiler bug, until I looked at the disassembly and realized that the only impact of the optimization was allocation – no extra code was being run, so it only had GC impact. Regardless, it was kind of unexpected – I was unable to figure it out until I started looking at disassembly in Reflector. Having CLR Profiler‘s call/allocation tree helped a lot in knowing where to look, at least.

I spent a little time tuning my collision detection and motion code, by removing unnecessary calculations, adjusting caching logic, and so on, but I’m also nearing the point where I’ll need to start optimizing my collision detection algorithms instead of just making the code faster. Right now it’s entirely brute-force, but in the future I’ll need to build some sort of a scene graph or quadtree to store my collision geometry, so I don’t have to test the player against the entire level every frame. Right now my CPU usage goes down by about 5-10% any time the player is jumping/falling, just because I perform less collision checks when he’s in that state. The ComputeStandingY algorithm is also kind of a problem here, since as currently implemented it has to walk the entire level 5 times every frame.

The CPU profile wasn’t particularly enlightening – most of the bottlenecks were exactly what I figured they would be – all the looping and floating point calcluations in my motion and collision detection code. However, there were a few things I hadn’t expected to show up:

• Actual CPU time (3-4% of total) was being spent in the constructors for Rectangle, Size, and Vector2 in my drawing routines. Totally unnecessary; most of it was a result of using ‘foo = new Vector2(x, y);‘ when I could have used ‘foo.X = x; foo.Y = y;‘ instead. I’m not quite sure why the compiler wasn’t inling these calls, though.
• Actual CPU time (another 4-5% of total) was being spent looping over all of a level’s tilesets every frame to map a tile index to a texture and rectangle. This was stupid and extremely easy to solve – I just moved that looping operation into a function and cached the result. I could speed it up further by doing all of those lookups once when loading the level, eliminating the need for the caching logic, but it’s so low on profiles now that it doesn’t really matter.
• The GetPolygonAxes function in my collision code had an optimization in it that turned out to be a pessimization: It did some work to avoid adding the same axis to the list twice, so that the collision detection code wouldn’t have to check it twice. On paper, this is a significant performance improvement, since it reduces a rectangle vs rectangle check from 8 iterations to 4. In practice, it actually made my performance worse, because performing an equality check between Vector2 objects has tangible overhead, as does walking over the current contents of the list. I might be able to bring it back using some sort of clever hashing technique, but for now I ended up removing that “optimization” entirely.

Here’s some footage of the camera controls in action, along with more of the test level. I edited out the boring walking sections with a sledgehammer since nobody would want to watch them – hope the cuts aren’t too jarring.

Tags: csharp, Gruedorf, platformer, xna

Today at DevHouse I worked on a couple improvements to the platformer: game state serialization, and one-way barriers.

Game state serialization was the first. My original implementation of saved games only stored the player’s position, so the state of things like switches and doors wouldn’t be persisted – this meant it was trivial to get yourself stuck by loading in an inaccessible location.

The approach I ended up taking was to implement a simple dictionary of named key/value pairs using .NET’s XML Serialization, and then bind that dictionary to all the named objects in the game. I used reflection to tag various properties and fields of objects to indicate that they should be serialized, so that the process of saving and loading the game state was fairly automatic.

What that means is that where before the player’s position was represented by this XML in the save file:

<SavedGame>
  <PlayerPosition>
    <X>128.449982</X>
    <Y>272</Y>
  </PlayerPosition>

Now it’s represented by this XML:

<SavedGame>
  <GameState>
    <types>
      <type id="2" name="Microsoft.Xna.Framework.Vector2, Microsoft.Xna.Framework, Version=3.0.0.0, Culture=neutral, PublicKeyToken=6d5c3888ef60e27d" />
    </types>
    <Vector2 key="player.Position" typeId="2">
      <X>128.449982</X>
      <Y>272</Y>
    </Vector2>

You’ll probably notice that the new XML is more verbose (some XML has been omitted from both examples for clarity). The primary difference is that where previously, the values in the SavedGame object were pre-defined, and had to be manually loaded and saved after XML (de)serialization was complete. Now, the game uses the key attached to each value along with its typeId to automatically locate the appropriate object and property.

Once the XML parsing is all done, the following code does all the work of updating the properties with the new values:

    protected IEnumerator<object> LoadGame () {
        var rtc = new RunToCompletion(Storage.LoadFromStorage<SavedGame>("game.sav"));
        yield return rtc;
        var sg = (SavedGame)rtc.Result;

        var bindFlags = BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.FlattenHierarchy;

        foreach (var item in sg.GameState) {
            var parts = item.Key.Split(new char[] { '.' }, 2);
            var obj = FindNamedObject(parts[0]);
            var t = obj.GetType();

            var prop = t.GetProperty(parts[1], bindFlags);
            if (prop != null) {
                prop.SetValue(obj, item.Value, null);
            } else {

                var field = t.GetField(parts[1], bindFlags);
                if (field != null)
                    field.SetValue(obj, item.Value);
            }
        }
    }

A bit more verbose than I would like, mostly due to the necessity of handling properties and fields separately, but on the other hand, this code currently handles all the necessary work for loading a saved game.

After I had serialization all rigged up, I started working on implementing one-way barriers, that the player can only pass through in one direction.

One-way barriers required some changes to my existing collision detection code – I extended the existing LevelGeometry interface with a new method called ShouldObstruct. When performing collision detection and movement checks the game now calls ShouldObstruct, passing in the player’s current velocity so that the object can determine whether or not the player should be allowed to pass through the object.

Once that was rigged up, it was as simple as defining a new type of geometry called a OneWayRectangle with a configurable PassableAxis property. The player is only allowed to pass through the rectangle when the dot product of the PassableAxis and the player’s velocity is less or equal to 0. This provides the basic constraint of only being able to move through the barrier in a particular direction.

However, one problem came up after I got it working: It was fairly easy to get stuck inside a barrier by jumping while moving through it, because the barrier would reject the downward falling velocity from the jump and prevent you from landing on the ground. The solution ended up being to always allow the player to move through a barrier if he’s already colliding with it, so that once you’ve crossed into a barrier (which is only possible if you’re moving in the appropriate direction), you’re free to move in any direction until you exit the barrier.

One way barriers turn out to be useful for making environments more dynamic by changing the passable axis of a barrier based on other conditions, or by using a barrier to prevent the player from leaving a chamber once entering. They also provide a good foundation for something I plan to implement in the future – the ability to ‘phase’ through platforms by pressing down and jump, like you can do in many modern 2D platformers.

Tags: csharp, Gruedorf, platformer, xna

First of all, I figured out why the camera tended to jitter while moving up or down a pivoting platform. It turned out to be caused by the platform pivoting up into the player’s bounding box. The player’s motion code attempted to move the player and apply standing correction for platforms in the same step, and in this particular case, that would prevent the player from moving at full velocity. The solution was to change the algorithm to work like this:

• Check to see if the platform the player is standing on has moved since the last frame. If so, adjust the player’s Y coordinate to compensate.
• Attempt to apply the player’s X velocity, and adjust the player’s Y coordinate based on his new standing Y coordinate (for the new X coordinate).
• Attempt to apply the player’s Y velocity (falling/jumping).

The duplication of adjusting the player’s Y coordinate twice kind of sucks, but it fixes most of the glitches when moving on a rapidly pivoting surface, and it has the added benefit of making moving platforms work a bit better.

After solving that issue, I started working on implementing an actual puzzle using the level elements I’d built so far.

The first thing I needed to be able to construct an actual puzzle was the ability to attach level elements to each other in complex ways. To do that, I started working on extending the simple expression parser I had built earlier so that I could use it to link platforms, pressure plates, switches and doors together.

The approach I ended up using is similar to the one I was using before, but it’s more sophisticated. The expressions in my level data look like this:

    <pivotPlatform id="platform1" a="8.5,11.5"  b="12.5,12"   minTilt="-3.25" maxTilt="3.25" tiltSpeed="0.065" tilt="plate1.State ? 1.0 : -1.0" />
    <door          id="door2"     a="1.75,9"    b="2.75,14"   openDirection="0,1" state="switch1.State and switch2.State" />

Parsing the expressions and converting them into something the game can use at runtime is a multiple-step process. The first step is to convert the expression string into a stream of tokens. Right now, I’m doing this with a regular expression:

(
  (?'number' (-?) [0-9]+ (\.[0-9]+)? ) |
  (?'identifier' [_A-Za-z][A-Za-z0-9_]*) |
  (?'operator' <= | >= | != | [\-+/*&|^!><=.%?:]) |
  (?'paren' [()])
)

I apply this regex to the expression string and get a string of Match objects as a result, with named groups that determine the type of each token.

After that, I scan through the token stream and convert the tokens into function objects. Number tokens get converted into functions that return their values, like this:

    public static ValueProxy MakeFloat (float value) {
        return () => value;

Identifiers get transformed in a similar, though slightly more complex manner, in order to map them to the set of named objects in the level:

    public static object MakeIdentifier (string identifier, NameResolver resolver) {
        ValueProxy result = () => resolver(identifier);

The NameResolver in use here is defined elsewhere to map a string identifier to an element in the NamedObjects dictionary:

    public Func<T> ParseExpression<T> (string expression) {
        var resolveName = (NameResolver)((name) => this.NamedObjects[name]);

These two bits of code combined allow straightforward connections between named objects in a level, without having to pay attention to order of declaration or having to load a level in multiple passes.

Paren tokens are treated as a signal to the parser that a new subexpression has started. When I hit an open paren, I recurse into a new expression parser that runs until it hits a close paren, at which point it returns a function that can be evaluated to get the result of that subexpression. (I could have implemented this without recursion, but I’m too lazy. )

Operator tokens get mapped to function objects based on the particular operator they represent. Most operators map to unary or binary operator functions that are predefined, like this:

    case "^":
        return (BinaryOperator)(
            (lhs, rhs) => lhs.As<bool>() ^ rhs.As<bool>()
        );
    case "!":
        return (PrefixOperator)(
            (rhs) => !rhs.As<bool>()
        );
    case ">":
        return (BinaryOperator)(
            (lhs, rhs) => lhs.As<float>() > rhs.As<float>()
        );

(The one exception is the ternary operator, which has to be converted to two special ‘placeholder’ objects that a later stage of the expression parser translates into a single callable function.)

Once all the tokens have been converted, the final stage of the expression parser starts. This stage is fairly simplistic – it scans through the stream of converted tokens repeatedly, starting from the beginning each time, looking for operations that it can collapse into a callable function. For example, if it finds:

ValueProxy:2 BinaryOperator:+ ValueProxy:4

It knows that it can collapse that string of operations into a single new function, like this:

    } else if (current is BinaryOperator && prev is ValueProxy && next is ValueProxy) {
        stack.RemoveRange(i - 1, 3);
        stack.Insert(i - 1, ApplyBinary(prev, current, next));

ApplyBinary takes an operator function and a pair of value proxy functions, and returns a new function that applies the operator to the two value proxies when invoked:

    internal static ValueProxy ApplyBinary (object lhs, object binary, object rhs) {
        var b = (BinaryOperator)binary;
        var l = (ValueProxy)lhs;
        var r = (ValueProxy)rhs;
        return () => b(l, r);

This transformation is applied repeatedly to the stack until it contains a single ValueProxy representing the value of the entire expression. You might want to note that this approach doesn’t handle things like operator precedence, type safety, or type conversion – but I don’t currently need any of those things.

One particularly important detail is that I implemented a simple . operator that allows me to access fields and properties of named objects. This allows me to build more complex puzzles by having objects with multiple properties attached to them (for example, pressure plates have both a boolean State and a floating-point Depth). The way the dot operator works is fairly simple:

When the expression parser encounters a dot operator, it scans backwards one token and tries to grab an identifier. After that, it scans forward one token and tries to grab another identifier. If this fails, the expression is assumed to be invalid. At this point, the parser has a pair of identifiers, and the one on the left has already been resolved to point to a variable. The parser constructs a special function that will, when invoked, attempt to look up the value of a named property (the name is on the right) on the contents of the variable (on the left). Right now I do this with some reflection-based code, with a simple dictionary cache to mitigate the performance overhead of doing reflection at runtime by only performing a given reflection lookup once per variable/property pair.

With all this work done, I started experimenting with building a puzzle out of the primitives I already had: Pivoting platforms, switches, pressure plates and doors. As it turns out, being able to wall-jump off the side of a pivoting platform is actually pretty cool.

I’m still going to need to tune the physics some before these types of puzzles feel satisfying (it’s a bit hard to properly perform a wall-jump off the platforms due to how small they are, among other things), but I’m still pretty happy with how the puzzle turned out, considering how quickly I was able to assemble it.

Tags: csharp, Gruedorf, platformer, xna

Most recently I’ve been experimenting with some additional mechanics, for example – pivoting platforms:

As it turns out, building a simple pivoting platform isn’t that hard, because I can reuse most of the code I already wrote for pressure plates and sloped surfaces. Most of the side-effects come out right automatically – as the platform pivots, ComputeStandingY positions the player appropriately to match the new slope of the surface, and collision detection still works right even from below the surface.

As you may notice, though, the motion looks a bit jittery if the slope of the surface becomes steep enough, and some of the details like the speed of pivoting need more tuning for it to really be interesting. But it was still suprisingly easy to build regardless – and I’m happy with how it turned out. Next, I need to figure out how to integrate it with other mechanics – maybe a pivoting platform that triggers a pressure plate, or two pivoting platforms that have linked positions?

Unintended, yet awesome side effect: I recently discovered that if your timing is just right, you can wall-jump off a pivoting platform. I might leave that one in.

Tags: csharp, Gruedorf, platformer, xna