Not a whole lot interesting to show for this week; mostly some performance adjustments and tuning changes.

I spent a day or so wrestling with some weird floating-point accuracy issues. In one case, a routine I was using to convert a convex polygon into a list of triangles wasn’t working correctly in Release builds of the game – rounding errors resulted in a point being represented as outside a triangle when it was actually right on the edge, which ended up causing the routine to iterate forever. (Whoops.)

After a little experimenting, I ended up changing all the variables in the point-in-triangle check routine to use double precision floats, which fixed my test case. Unfortunately, I’m still pretty sure that the routine is broken; doubling the precision just reduced the magnitude of the error. This is particularly annoying since I have had trouble with rounding errors in my collision detection routines in the past, and I still haven’t found a robust approach for deailng with those either. I suspect I’m going to have to spend a while reading up on techniques for reducing error. One upside is that I haven’t seen any rounding errors while running the game on the 360, so if all goes well I won’t ever have to debug PowerPC floating point error issues on my x86 development machine – my understanding is that PPC’s instruction set for floating point arithmetic is far less sensitive than the x86’s, so I’m hoping it won’t be a problem.

I also did a little bit of experimenting with improving the quality of particle effects in the game. I recently added a little effect that causes one-way barriers to emit sparks when their passable axis changes, so that the player’s attention is drawn to the change to avoid confusion in puzzles that rely on barriers. It was pretty, but it also made it obvious that sparks were flying through walls and other geometry, which looked kind of ridiculous. So, in order to address that, I did some work on making sparks not spawn inside of geometry, and making them able to bounce off walls. The end result looked a lot more convincing, but had some unfortunate performance consequences I haven’t managed to get a handle on yet – I spent an hour or two trying to optimize the code responsible for bouncing sparks off walls, and basically got no performance improvement out of it whatsoever; I suspect the profiling I did generated incorrect data for some reason.

Implementing support for sparks bouncing off walls involved some changes to the UpdateSpark routine, mostly the addition of an obstruction test using a new type of obstruction resolver:

        protected bool UpdateSpark (ref SparkParticle particle, int index) {
            particle.Opacity -= 0.01f;

            _ParticleResolver.position = particle.Position;
            _ParticleResolver.velocity = particle.Velocity;
            _ParticleResolver.Reset();
            var result = ObstructionTest(_ParticleResolver, ObstructionFlags.Geometry);
            particle.Position = _ParticleResolver.resultPosition;
            particle.Velocity = _ParticleResolver.resultVelocity;
            if (result == null) {
                particle.Velocity.Y += 0.025f;
            }
            particle.Rotation = (float)(Math.Atan2(particle.Velocity.Y, particle.Velocity.X) + (Math.PI / 2.0f));

            return (particle.Opacity <= 0.0f);
        }

Fairly simple in concept; perform an obstruction test between the particle and nearby level geometry, and use that to determine the new position of the particle. The new resolver looks like this:

    internal class ParticleMotionResolver : ICollisionVisitor {
        public Vector2 position, velocity, resultPosition, resultVelocity;

        public void Reset () {
            resultPosition = position + velocity;
            resultVelocity = velocity;
        }

        public Bounds GetBounds () {
            return new Bounds(position, resultPosition);
        }

        public CollisionState VisitPolygon (Polygon poly) {
            Vector2 intersection;
            bool result = false;

            for (int i = 0; i < poly.Count; i++) {
                var edge = poly.GetEdge(i);
                var normal = Vector2.Normalize(edge.End - edge.Start).Perpendicular();

                if (Geometry.DoLinesIntersect(position, resultPosition, edge.Start, edge.End, out intersection)) {
                    result = true;
                    velocity -= (intersection - position);
                    position = intersection;
                    Vector2.Reflect(ref resultVelocity, ref normal, out resultVelocity);
                    velocity = Vector2.Normalize(resultVelocity) * velocity.Length();
                    resultPosition = position + velocity;
                    if (velocity.LengthSquared() <= 0)
                        return new CollisionState(true, true);
                }
            }

            return result;
        }

        public CollisionState VisitCollidable (ICollidable obj) {
            if (velocity.LengthSquared() <= 0)
                return new CollisionState(true, true);
            else
                return CollisionState.True;
        }
    }

Fairly straightforward, really: For every polygon within the particle’s bounding box, I test the particle’s velocity vector against the polygon’s edges, to see if the particle is going to intersect the edge. If it is, I move the particle so that it’s lying directly on the edge, and then compute a reflection vector so that I know which direction it’s going to bounce in. After that, I apply the particle’s remaining velocity (if any) to bounce it off the edge, and change its direction.

This new routine has the unfortunate side effect of revealing some of the rounding errors lurking in my code – sparks are able to slip through some curved surfaces since the triangles that make up their edges are so small. The end result was definitely an improvement regardless, though.

The last significant thing I worked on was getting moving platforms working correctly again. While moving platforms were one of the first things I implemented originally, A few weeks back I ended up taking them out because they didn’t make sense with my current collision detection model, and they were a constant hassle. Now that my collision detection is more sane, it was easy to adapt the existing code for doors to create a moving platform class that behaves more or less the way I want: You can grip onto the edges of moving platforms just like ledges without falling off; you can climb up onto them; you can ride them; etc. I had to do some tweaking here and there to ensure that you couldn’t ride moving platforms through geometry that’s supposed to obstruct you, and there are still some usability issues – right now the only way to control a platform’s movement is by writing complex vector expressions, which isn’t fun at all; good moving platforms really require a system for defining paths for them to follow, and that’s still on the todo list. Regardless, it’s nice to have platforms working again, since they’re an essential part of my arsenal for designing good puzzles.

Tags: csharp, Gruedorf, particles, platformer