Most of my work on the platformer this week has been focused on improving the Entity class and all the related code. I made a number of changes and improvements to SpatialCollection aimed at improving its performance, and completely overhauled all my collision detection code to reduce the number of passes I make over the level when doing things like computing an entity’s StandingY or testing for a collision. The efforts have mostly paid off so far; my framerate with 6 entities walking around on curved surfaces right now is about the same as it was before with a single entity walking around on sloped surfaces, even though I’ve improved my collision model significantly. The optimizations ended up bringing my game’s performance profile back to where it was before the addition of entities, with the majority of CPU time being spent doing raw number-crunching to perform intersection checks on polygons.

My previous approach to collision detection was fairly brute-force: I had a few special methods defined in the Game class named things like FindObstruction and ResolveMotion, that took a bunch of parameters to control a collision detection sweep of the entire level. The addition of SpatialCollection<T> as mentioned in last week’s post made those functions faster, but that didn’t completely eliminate the performance issues – the most visible offender was ComputeStandingY. The original implementation of ComputeStandingY had to make four complete passes over the level to come up with a result, and I ended up invoking it twice per frame when updating an entity. The end result was that no matter what, it accounted for a significant amount of my CPU usage, no matter how efficient I made the underlying collision detection routine.

In order to address this problem, I set out to refactor my collision detection code. The first step was to unify the different collision test routines – they all shared many common elements, the most obvious one being the task of walking over the contents of the level. Using SpatialCollection meant that each routine had about 8 lines of boilerplate in order to do iteration, in addition to all of the code for actually performing collision tests, so my first step was to factor that out into a baseline ObstructionTest function that performed the simple task of walking over the contents of the level and invoking a ‘Collision Visitor’ delegate on each item.

    public ICollidable ObstructionTest (ICollisionVisitor visitor, ObstructionFlags flags) {
        ICollidable result = null;
        var bounds = visitor.GetBounds();

        if ((flags & ObstructionFlags.Geometry) == ObstructionFlags.Geometry) {
            using (var e = Level.Geometry.GetItemsFromBounds(visitor.GetBounds()))
            while (e.MoveNext()) {
                var current = e.Current;

                if (!Bounds.Intersect(ref bounds, ref current.Bounds))
                    continue;

                var rg = current.Item.GetRuntimeGeometry(this);

                if (visitor.Visit(rg, ref result))
                    return result;
            }
        }

        if ((flags & ObstructionFlags.Entities) == ObstructionFlags.Entities) {
            if (bounds.Intersects(Player.Bounds))
                if (visitor.Visit(Player, ref result))
                    return result;

            using (var e = Entities.GetItemsFromBounds(bounds))
            while (e.MoveNext()) {
                var current = e.Current;

                if (!Bounds.Intersect(ref bounds, ref current.Bounds))
                    continue;

                if (visitor.Visit(current.Item, ref result))
                    return result;
            }
        }

        return result;
    }

After that, I refactored all the existing routines to be built on top of ObstructionTest. After that I iteratively refined things down until I didn’t need any of the specialized routines anymore, and ObstructionTest ended up operating on specialized ICollisionVisitor objects that had two ‘Visit’ methods, one for ‘Collidable Objects’, and one for individual collision polygons. The pair of visit methods allowed a visitor to reject entire objects before any complex collision tests were performed, in addition to rejecting individual polygons due to non-collision. The use of visitor objects also meant that a visitor could record a list of the objects it encountered, or reject collision with an entire list of entities instead of just the entity that was performing the check. These improvements not only resulted in better performance, but they allowed me to address a bug in the Entity class that prevented entities from walking up sloped surfaces while the player was standing on them.

    public class StandingSurfaceVisitor : ICollisionVisitor {
        public Entity Entity;
        public Bounds Bounds;
        public List<IStandable> Results;

        public StandingSurfaceVisitor (Entity entity) {
            Entity = entity;
            Results = new List<IStandable>();
        }

        public Bounds GetBounds () {
            return Bounds;
        }

        public CollisionState VisitCollidable (ICollidable obj) {
            if (obj == Entity)
                return new CollisionState(false, false);

            var standable = (obj as IStandable);
            if (standable != null)
                Results.Add(standable);
            return new CollisionState(false, true);
        }

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

        public CollisionState VisitPolygon (Polygon poly) {
            throw new NotImplementedException();
        }
    }

One of the other things I invested some time into was an overhaul of the logic for standing on surfaces. Previously, the Player class had a StandingOn property that held one of the entities/surfaces he was currently standing on. I used this to determine whether the player was standing on a pressure plate, and cause him to move with things he was standing on. The problem was that in almost all cases the player would be standing on multiple surfaces, so the nondeterministic nature of the collision detection code meant that sometimes you could be atop a pressure plate but not trigger it. I also had no easy way of determining whether entities were standing on top of each other, which meant that an entity being ridden by another entity could not walk up a sloped surface (his path would be blocked by his rider).

To solve those two problems, I defined a pair of simple interfaces called IRider and IRideable. These interfaces provided a simple way for me to manage all the logic around riding surfaces – entities could automatically build and update a list of rideable objects that they were currently occupying, and rideable objects were able to automatically maintain a list of rider objects on top of them, making it simple to exclude those riders from collision checks. This not only fixed pressure plates, but also made it easy for monsters to set off pressure plates, and meant that monsters could walk up sloped surfaces while being ridden by other entities, and that you could stack entities on top of each other to create big riding chains without any major issues (though in the video below, it was still unfinished and somewhat busted):

One of the other fixes I was able to make as a result of the new system for handling rideable surfaces was to the code for mantling up onto surfaces. Previously, if you tried to mantle up onto a moving surface, like a moving platform or an entity, you’d mantle up onto the space it previously occupied and typically fall right back down, making it pretty useless. With the new riding system I was easily able to adapt this so that you could mantle up onto a moving surface without being left behind by its motion or causing it to become obstructed. Since the mantling code doesn’t currently distinguish between different types of surfaces, this means you can basically crawl up on top of a crowd of enemies and run across it, which is pretty fun.

The video below shows how entity mantling looks, though it’s from before I implemented the riding system (so you can see it get broken in a couple places):

Tags: collision, csharp, performance, platformer, xna