Last weekend, I went to SuperHappyDevHouse 30 with some friends and acquaintances. In between checking out other people’s projects, chatting about technology, and devouring delicious snacks, I got a lot of work done on my editor. The guy next to me with the hat and goggles showed off his extremely clever browser-based zombie MMO and exchanged war stories with us about the horrors of PHP.

The main thing I worked on was getting support for multiple-object selections in the editor, so that you could select multiple tiles or pieces of geometry and manipulate them all at once. After some heavy refactoring, I got it all working, making it possible to edit a property of multiple objects or reposition/delete multiple objects at once, by leveraging some of the MultiSelect support built into the WinForms PropertyGrid class for property editing and extending my existing object manipulation code to work on sequences instead of single object references. Having multiselect makes it much easier to make batch modifications in levels and quickly populate an area with objects, and is a precursor to good clipboard support.

One of the challenges involved in getting this working was the need to improve the logic behind operations like tile movement – previously, I did some work to ensure that the editor would always try and select a non-overlapping location for a tile whenever possible, even while dragging, so that it would be easy to build seamless backgrounds and objects out of individual tiles. Getting this logic to work correctly for grouped selections of tiles was a bit of a challenge and required carefully excluding certain tiles from some intersection tests and not others.

After that, I started doing some work on being able to build more varied puzzles out of the primitives I already had in the engine – making sure that doors could open in all four directions correctly, and making it possible to manipulate entities and non-colliding geometry like switches and pressure plates.

Later in the week I spent a lot of time refactoring code, moving classes around, factoring out duplication in methods, and tweaking and fine-tuning various interfaces. While making these changes I experimented with some basic ideas for puzzles and level design challenges, creating things like sequences of cascading doors or quickly-moving platforms.

After experimenting with puzzle designs for a while, I realized I really needed to get a working implementation of crushing damage and get proper support for entities being pushed around by moving geometry – moving platforms and quickly moving doors simply don’t play well unless they are able to collide with entities and move them around, and being crushed by a door isn’t very threatening if it deals no damage.

Originally, supporting these two things was a bit of a challenge – the rigid nature of my collision detection routines meant it would have been prohibitively expensive and very difficult to get right. As a result of the refactorings I’ve made in the past few weeks, however, it ended up being easy – the Visitor pattern meant that implementing this was as simple as extending the code I already had with a specialized collision visitor for moving level geometry:

internal class RuntimeGeometryMotionResolver : AbstractPolygonMotionResolver {
    public struct CrushedEntity {
        public Entity Entity;
        public float CrushDistance;
    }

    public RuntimeGeometry Geometry;
    public Entity Entity = null;
    public List<CrushedEntity> CrushedEntities = new List<CrushedEntity>();

    public RuntimeGeometryMotionResolver (RuntimeGeometry geometry) {
        Geometry = geometry;
    }

    public void Reset () {
        CrushedEntities.Clear();
    }

    public override CollisionState VisitCollidable (ICollidable obj) {
        if (obj == Geometry)
            return false;
        if (objectVelocity.LengthSquared() <= 0)
            return new CollisionState(true, true);

        Entity = obj as Entity;
        return true;
    }

    public override CollisionState VisitPolygon (Polygon poly) {
        if (Entity == null)
            return base._VisitPolygon(poly, ref objectVelocity, out objectVelocity);

        Vector2 resultVelocity;
        var result = base._VisitPolygon(poly, ref objectVelocity, out resultVelocity);
        var pushDistance = objectVelocity.Length() - resultVelocity.Length();
        var pushVector = Vector2.Normalize(objectVelocity) * pushDistance;

        var pushedVector = Entity.ApplyMotion(pushVector);
        var pushedDistance = pushedVector.Length();
        var obstructedDistance = pushDistance - pushedDistance;

        if (obstructedDistance > 0.0f) {
            CrushedEntities.Add(new CrushedEntity { Entity = Entity, CrushDistance = obstructedDistance });

            var resultDistance = Math.Max(objectVelocity.Length() - obstructedDistance, 0.0f);
            if (resultDistance <= 0.0f) {
                objectVelocity.X = objectVelocity.Y = 0;
                return new CollisionState(true, true);
            } else {
                objectVelocity = Vector2.Normalize(objectVelocity) * resultDistance;
            }
        }

        return new CollisionState(result.Value, false);
    }
}

Larger than I might like, but actually quite low on duplication, and basically a complete solution to the problem. Here’s a basic overview of how it works:

The visitor walks over all the objects in the game world that the geometry can possibly collide with, keeping track of the current velocity of the geometry and a list of all the objects it’s already collided with. Each time it encounters an object (VisitCollidable) it does some basic checks to rule out things that can’t possibly be collided with (for example, itself).

After that, it walks over each of the polygonal shapes in that object’s CollisionList and performs a basic motion resolution operation against that polygon, to determine how far the geometry can move in its desired direction without a collision. This provides a vector that can be compared against the original velocity of the geometry, to determine how far it travelled before colliding with the object. At this point, it then attempts to push the object it’s colliding with far enough to resolve the collision, preserving the geometry’s desired velocity.

If it successfully pushes the entity all the way, the entity is safely moved out of the path of the geometry and no crushing damage occurs. This nicely handles almost all of the possible situations involving collisions between moving geometry and entities, because the entity performs its own collision checks when attempting to apply the motion. If the entity cannot be pushed all the way, the visitor can perform a final calculation to find out how much motion was prevented by a collision between the entity and some other object, and at that point, the visitor adds an item to its results list recording the entity that was struck and how much force was applied to it.

Once this visitor has made a pass over all the possible candidates (or the geometry’s velocity has been reduced to zero), it has a list of objects to deal crushing damage to, and the game can continue. In practice, geometry will typically only be obstructed by a single entity, but in cases where multiple entities are all being pushed by a single large object, keeping track of a list helps make things behave predictably. The performance characteristics of this technique are quite good due to the optimizations already built into the visitor system, which makes it extremely cheap to put lots of moving geometry in a level that’s capable of dealing crushing damage.

One bug I encountered while implementing this technique was a particularly nasty edge case where the geometry’s velocity would be reduced to 0, but it would continue on its collision detection pass. It would then perform motion tests against other objects without having a velocity, and the resulting arithmetic would generate NaNs that then propagated out through the game code, resulting in any entities near the moving geometry getting teleported into nothingness.

NaNs are always painful to deal with and important to avoid, and it took me nearly an hour to finally track down this issue and make sure it wouldn’t happen again. In retrospect I should have anticipated this sort of thing to begin with, as a result of the approach to collision detection i’m using, and it’s a bit of a surprise that I haven’t had it happen before. As a result I’m going to be leaving some IsNaN checks in a few key parts of my code in order to be certain that an exception is thrown as soon as a NaN is generated, so that I’ll be immediately alerted to problems in my code without having to spot subtle issues. If you look carefully, you can actually see a monster being teleported to {NaN, NaN} in the above video.

A few of the other things I implemented this week included basic clipboard support in my editor (cut/copy/paste) and some UI refactorings that eliminated the mostly useless menu bar and added toolbar icons to reduce the amount of screen real estate used by the editor’s chrome.

Clipboard support ended up being much easier than it was in any of my previous tools development projects, due to the fact that I had already built an extremely usable general serialization framework, and the fact that I had already cleanly separated design-time and run-time game data. The WinForms Clipboard API kind of sucks, though.

A couple other random gripes, while I’m on the topic of ‘kind of sucks’:

XNA’s default Game implementation on Windows seems to entirely suppress all Win32 keyboard messages, which makes it difficult to accept text input in an integrated editor like mine. I don’t really blame them, but I wish I had realized this sooner – I had to compromise and move my property grid to a floating dialog in order to allow the user to input text into it, which is not a particularly amazing user experience.

PropertyGrid requires a saddening amount of boilerplate code to be written before you can just point it at a typical piece of game data – by default, it won’t display anything except public properties, and it makes it really difficult to provide a good UI for custom types by requiring you to do an elaborate song and dance involving TypeConverters. I ended up spending a few hours hacking together around 700 lines of code just to get it to properly handle editing fields of various types. On the other hand, multiselect pretty much worked out of the box, so it was still faster than trying to write my own property editor.

Tags: csharp, platformer, shdh, superhappydevhouse, xna