Map Collision Detection and Slope Implementation

I’ve been asked about how the collision detection of slopes is done in Thornbridge Saga. So I thought I would write a blog post about how I did that.

I’ve essentially followed the #2 algorithm that Rodrigo Monteiro describes here: The guide to implementing 2D platformers

First, a bit about architecture. I have a dynamics object which performs the basic physics update, and passes that update to a map collider object. The method which does that looks something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
private void Update(IGameEntity entity, GameTime time)
{
    var physics = entity.Physics;
    var parms = entity.Dynamics;

    var seconds = (float)time.ElapsedGameTime.TotalSeconds;

    // Apply gravity and friction, then allow each entity to calculate its own forces
    SetForces(entity, time);

    Vector2 acceleration = physics.Force / physics.Mass;
    var angularAcceleration = physics.Torque / physics.InertialMoment;

    Vector2 deltaPosition =
            physics.Velocity * seconds +
            acceleration * (0.5f * seconds * seconds);

    physics.Velocity += acceleration * seconds;

    if (physics.Velocity.Y > parms.TerminalVelocity)
        physics.Velocity.Y = parms.TerminalVelocity;

    physics.AngularVelocity += angularAcceleration * seconds;
    physics.Angle += physics.AngularVelocity * seconds;

    mapCollider.MoveEntity(Map, entity, deltaPosition);
}

Here I’m using a coordinate system typical of 2D games, with Y increasing going down the screen. The function mapCollider.MoveEntity performs the actual constrained update of moving the character on the map, checking for collision against the map itself as well as any movable objects on the map. The code for that function is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void MoveEntity(IMap map, IGameEntity entity, Vector2 deltaPosition)
{
    if (entity.Dynamics.IgnoreGround)
    {
        entity.Physics.Position += deltaPosition;
    }
    else
    {
        if (entity.IsOnGround)
        {
            MoveEntityY(map, entity, deltaPosition);
            MoveEntityX(map, entity, deltaPosition);
        }
        else
        {
            MoveEntityX(map, entity, deltaPosition);
            MoveEntityY(map, entity, deltaPosition);
        }

        InspectLedges(map, entity);
    }
}

entity.Dynamics.IgnoreGround is a parameter that allows my game entities to ignore walls and floors. It’s used sparingly, because I feel like creatures and projectiles that can pass through walls when the player can’t is a bit unfair. On the other hand, entity.IsOnGround is a simple property that to indicate whether

1
public bool IsOnGround => !Dynamics.IgnoreGround && MapContact.TouchingFloor && Physics.Velocity.Y >= -1e-2;

I’ve experimented a bit with varying the order of the X & Y steps, and this seems to work well because in my algorithm, the player is slowed when moving uphill. The InspectLedges function is a function I’ve written to provide AI with information about the map, ie. is the creature close to a ledge and in danger of falling off? I won’t show the code for it here because it has a couple of bugs currently that I haven’t gotten around to fixing yet.

The meat of this algorithm is in the MoveEntityX and MoveEntityY functions. Here they are, in all their ridiculously long glory :/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
private void MoveEntityY(IMap map, IGameEntity entity, Vector2 deltaPosition)
{
    if (deltaPosition.Y != 0)
    {
        bool movingUp = deltaPosition.Y < 0;

        var forwardEdge = movingUp
            ? entity.BoundsF.Top
            : entity.BoundsF.Bottom;

        var collisionBoundary = entity.BoundsF;
        collisionBoundary.Height += Math.Abs(deltaPosition.Y);

        if (movingUp)
            collisionBoundary.Y += deltaPosition.Y;
       
        var startTile = map.PixelToTile(new Vector2(entity.BoundsF.Left, forwardEdge - 1));
        var endTile = map.PixelToTile(new Vector2(entity.BoundsF.Right, forwardEdge + deltaPosition.Y + 1));

        Rectangle searchArea = RectangleX.FromLTRB(
            startTile.X, Math.Min(startTile.Y, endTile.Y) - 1,
            endTile.X, Math.Max(startTile.Y, endTile.Y) + 1);

        Point searchDirectionShort = new Point(1, 0);
        Point searchDirectionLong = new Point(0, Math.Sign(deltaPosition.Y));

        float distanceToObstacle = float.MaxValue;
        Func<CollisionArea, float> distanceToEdge;

        if (movingUp)
        {
            distanceToEdge = collisionArea =>
            {
                var bottomEdge = collisionArea?.BottomEdge(entity.BoundsF.Left, entity.BoundsF.Right);

                if (bottomEdge == null)
                    return float.MaxValue;

                if (entity.BoundsF.Bottom < bottomEdge.LineSegment.Start.Y &&
                    entity.BoundsF.Bottom < bottomEdge.LineSegment.End.Y)
                {
                    return float.MaxValue;
                }

                return forwardEdge - bottomEdge.LineSegment.Start.Y;
            };
        }
        else
        {
            distanceToEdge = collisionArea =>
            {
                var edge = collisionArea?.TopEdge(entity.BoundsF.Left, entity.BoundsF.Right);

                if (edge == null)
                    return float.MaxValue;

                if (entity.BoundsF.Top > edge.LineSegment.Start.Y &&
                    entity.BoundsF.Top > edge.LineSegment.End.Y)
                {
                    return float.MaxValue;
                }
                Vector2 edgeStart, edgeEnd;
                EdgeEndpoints(edge, out edgeStart, out edgeEnd);

                if (edgeStart.Y == edgeEnd.Y)
                {
                    if (collisionArea.TopEdgeOnly)
                    {
                        if (entity.Dynamics.IgnoreTopEdge)
                            return float.MaxValue;

                        if (edgeStart.Y < forwardEdge)
                            return float.MaxValue;
                    }

                    return edgeStart.Y - forwardEdge;
                }

                float x;

                if (edgeStart.Y < edgeEnd.Y)
                {
                    x = edgeStart.X;
                }
                else
                {
                    x = edgeEnd.X;
                }

                x = Math.Max(x, entity.BoundsF.Left);
                x = Math.Min(x, entity.BoundsF.Right);

                if (x < edgeStart.X)
                    return float.MaxValue;
                if (x > edgeEnd.X)
                    return float.MaxValue;

                var edgeSlope = (edgeEnd.Y - edgeStart.Y) / (edgeEnd.X - edgeStart.X);

                var edgeValue = edgeStart.Y + (x - edgeStart.X) * edgeSlope;

                if (collisionArea.TopEdgeOnly)
                {
                    if (entity.Dynamics.IgnoreTopEdge)
                        return float.MaxValue;

                    if (edgeValue < forwardEdge)
                        return float.MaxValue;
                }

                return edgeValue - forwardEdge;
            };
        }

        SearchArea(searchArea, startTile, searchDirectionShort, searchDirectionLong, testPoint =>
        {
            var collisionArea = TileCollisionArea(map, testPoint);

            distanceToObstacle = Math.Min(distanceToObstacle, distanceToEdge(collisionArea));
        });

        IMapObject contactCandidate = null;

        SearchMapObjects(map, collisionBoundary, obj =>
        {
            if (!(obj.Collision.AllowPlayerPassage && entity is IPlayerEntity))
            {
                var distance = distanceToEdge(obj.Collision);

                if (distance < distanceToObstacle)
                {
                    distanceToObstacle = distance;
                    contactCandidate = obj;
                }
            }
        });

        if (contactCandidate != null && movingUp == false)
        {
            var args = new MapCollisionEventArgs(entity);

            contactCandidate.RaiseEvent().OnMapObjectCollision(this, args);
        }

        var step = deltaPosition.Y;

        const float floorSnapDistance = 6;

        if (distanceToObstacle < Math.Abs(step) ||
            (!movingUp
            && entity.IsOnGround
            && distanceToObstacle < floorSnapDistance))
        {
            step = Math.Sign(step) * distanceToObstacle;

            if (movingUp)
                entity.MapContact.TouchingCeiling = true;
            else
            {
                entity.MapContact.TouchingFloor = true;
            }
        }
        else
        {
            entity.MapContact.TouchingCeiling = false;
            entity.MapContact.TouchingFloor = false;
        }

        var newtop = entity.BoundsF.Top + step;

        entity.Physics.Position.Y += step;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
private void MoveEntityX(IMap map, IGameEntity entity, Vector2 deltaPosition)
{
    if (deltaPosition.X != 0)
    {
        bool movingLeft = deltaPosition.X < 0;

        var forwardEdge = movingLeft
            ? entity.BoundsF.Left
            : entity.BoundsF.Right;

        var collisionBoundary = entity.BoundsF;
        collisionBoundary.Width += Math.Abs(deltaPosition.X);

        if (movingLeft)
            collisionBoundary.X += deltaPosition.X;

        var startTile = map.PixelToTile(new Vector2(forwardEdge, entity.BoundsF.Top));
        var endTile = map.PixelToTile(new Vector2(forwardEdge + deltaPosition.X, entity.BoundsF.Bottom));

        Rectangle searchArea = RectangleX.FromLTRB(
            Math.Min(startTile.X, endTile.X), startTile.Y,
            Math.Max(startTile.X, endTile.X), endTile.Y);

        Point searchDirectionShort = new Point(0, 1);
        Point searchDirectionLong = new Point(
            Math.Sign(deltaPosition.X), 0);

        Func<CollisionArea, float> distanceToEdge;
       
        if (movingLeft)
        {
            distanceToEdge = collisionArea =>
            {
                var edge = collisionArea?.RightEdge(entity.BoundsF.Top, entity.BoundsF.Bottom);

                if (edge == null)
                    return float.MaxValue;

                Vector2 edgeStart, edgeEnd;
                EdgeEndpoints(edge, out edgeStart, out edgeEnd);

                if (entity.BoundsF.Bottom <= edgeStart.Y
                    && entity.BoundsF.Bottom <= edgeEnd.Y
                    || entity.BoundsF.Top >= edgeStart.Y
                    && entity.BoundsF.Top >= edgeEnd.Y)
                {
                    return float.MaxValue;
                }
                if (entity.BoundsF.Right < edgeStart.X)
                {
                    return float.MaxValue;
                }

                if (edgeStart.X == edgeEnd.X)
                {
                    return forwardEdge - edgeStart.X;
                }

                if (edgeStart.X > entity.BoundsF.Right && edgeEnd.X > entity.BoundsF.Right)
                    return float.MaxValue;
               
                if (edgeStart.Y > edgeEnd.Y)
                {
                    // going downhill.
                    return float.MaxValue;
                }
                else
                {
                    // going uphill.
                    var penetration = deltaPosition.X;
                    var normalCorrection = penetration * edge.Normal.X * edge.Normal.X;

                    return -(penetration - normalCorrection);
                }
            };
        }
        else
        {
            distanceToEdge = collisionArea =>
            {
                var edge = collisionArea?.LeftEdge(entity.BoundsF.Top, entity.BoundsF.Bottom);

                if (edge == null)
                    return float.MaxValue;

                Vector2 edgeStart, edgeEnd;
                EdgeEndpoints(edge, out edgeStart, out edgeEnd);

                if (entity.BoundsF.Bottom <= edgeStart.Y
                    && entity.BoundsF.Bottom <= edgeEnd.Y
                    || entity.BoundsF.Top >= edgeStart.Y
                    && entity.BoundsF.Top >= edgeEnd.Y)
                {
                    return float.MaxValue;
                }
                if (entity.BoundsF.Left > edgeStart.X)
                {
                    return float.MaxValue;
                }
               
                if (edgeStart.X == edgeEnd.X)
                {
                    return edgeStart.X - forwardEdge;
                }

                if (edgeStart.X < entity.BoundsF.Left && edgeEnd.X < entity.BoundsF.Left)
                    return float.MaxValue;
               
                if (edgeStart.Y < edgeEnd.Y)
                {
                    // going downhill.
                    return float.MaxValue;
                }
                else
                {
                    // going uphill.
                    var penetration = deltaPosition.X;
                    var normalCorrection = penetration * edge.Normal.X * edge.Normal.X;

                    return penetration - normalCorrection;
                }
            };
        }

        float distanceToObstacle = float.MaxValue;

        SearchArea(searchArea, startTile, searchDirectionShort, searchDirectionLong, testPoint =>
        {
            var collisionArea = TileCollisionArea(map, testPoint);

            distanceToObstacle = Math.Min(distanceToObstacle, distanceToEdge(collisionArea));
        });

        SearchMapObjects(map, collisionBoundary, obj =>
        {
            if (!(obj.Collision.AllowPlayerPassage && entity is IPlayerEntity))
            {
                distanceToObstacle = Math.Min(distanceToObstacle, distanceToEdge(obj.Collision));
            }
        });

        var step = deltaPosition.X;

        if (distanceToObstacle < Math.Abs(step))
        {
            step = Math.Sign(step) * distanceToObstacle;

            if (movingLeft)
                entity.MapContact.TouchingLeftWall = true;
            else
                entity.MapContact.TouchingRightWall = true;
        }
        else
        {
            entity.MapContact.TouchingLeftWall = false;
            entity.MapContact.TouchingRightWall = false;
        }

        entity.Physics.Position.X += step;
    }
}

I’ve done some small amount of refactoring to isolate some common code. There are enough differences between collisions in each direction that it’s tough to do a lot of isolation without introducing gobs of parameters.

The most important support function here is SearchArea. It iterates through the set of tiles that the entity might collide with. It does this in a particular order – if you’re moving up, you need to iterate through each row of tiles to find the bottom edge before moving to the next row. If you’re moving right, you need to iterate through each column of tiles to find the left edge before moving to the next column. The distanceToEdge lambdas in each MoveEntity* function compute the distance from the leading edge of the entity’s bounding box to the edge of the tile. Here’s SearchArea:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private void SearchArea(Rectangle searchArea, Point startPt, Point searchDirectionShort, Point searchDirectionLong, Action<Point> action)
{
    searchArea.Width++;
    searchArea.Height++;

    var testPoint = startPt;
    var shortSearchStart = testPoint;

    while (searchArea.Contains(testPoint))
    {
        action(testPoint);

        testPoint += searchDirectionShort;

        if (!searchArea.Contains(testPoint))
        {
            shortSearchStart += searchDirectionLong;

            testPoint = shortSearchStart;
        }
    }
}

SearchMapObjects is a similar function which iterates through the movable objects on the map. This one is simpler than the above because you simply need to test everything. One optimization it uses is to do an axis-aligned bounding box check on the polygons.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void SearchMapObjects(IMap map, RectangleF collisionRegion, Action<IMapObject> objectAction)
{
    const float margin = 4;

    collisionRegion.X -= margin;
    collisionRegion.Y -= margin;
    collisionRegion.Width += 2 * margin;
    collisionRegion.Height += 2 * margin;

    foreach (var obj in map.MapObjects.Where(x => x.Collision != null && x.Collision.BlockPolygon != null))
    {
        if (obj.Collision.BlockPolygon.Count == 0)
            continue;

        if (obj.Collision.BlockPolygon.BoundingRect.IntersectsWith(collisionRegion))
        {
            objectAction(obj);
        }
    }
}

EdgeEndpoints is a simple function that normalizes the start/end points of a polygon edge so that the point on the left is considered the start and the one on the right is considered the end.

1
2
3
4
5
6
7
8
9
private void EdgeEndpoints(PolygonEdge edge, out Vector2 edgeStart, out Vector2 edgeEnd)
{
    edgeStart = edge.LineSegment.Start;
    edgeEnd = edge.LineSegment.End;
    if (edgeEnd.X < edgeStart.X)
    {
        Swap(ref edgeStart, ref edgeEnd);
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *