The Character Controller: Tile Map Collisions, Part 2

As expected, this one was a little tough to work out.

Basically, I added a diagonal wall collider to the tile map. Like, three times. Because the first two attempts were really hard to understand, built ad hoc and incredibly buggy.
So, I decided to take a step back and formalize my collision system first, with some basic vector math to unify pretty much any collider in a single concept. I then rewrote the Impassable collider within that system, fixed a couple of bugs, and then implemented diagonal walls, which actually kinda work now.
"Kinda", because some arcane collider configurations allow you to faze through walls, but I think I already found the cause of that, I just didn't manage to fix it yet. It'll have to wait until my debugging utilities are overhauled, which I'm considering doing next. Not sure though.

The Theory

Before we jump into the code, let's talk about how this will go down conceptually.

Collision detection is now handled inside a loop. In each iteration, we move the character as far as it can go without causing a collision, and independently of that, store the direction it should go in the next iteration, which is determined by what it would collide with first, and how it is oriented relative to it.
This allows us to suggest a new direction to go, independent of whether going that way would also cause a collision.

To determine how far the character can go, we use a generalized function that finds the intersection point of two line segments in terms of the point's distance from one segment's starting point, relative to the segment's length.
The first line segment starts at the character's hit box (or rather, its corners) before the movement, and ends at the same corner after the movement. The value we get back for every test should be in the range [0, 1] if there's a collision. If we multiply the speed by that value, and move then, we wouldn't get a collision.

To make the character slide along a wall he didn't approach head-on, we need to figure the remaining speed of the character, which is 1 minus the value from before, multiplied by the speed.
We then need to perform what I call a half-reflection about the wall's normal on the remaining speed vector. This is just the average between the original vector and a properly reflected vector, which can be calculated more elegantly by simply leaving out the factor 2 in line 765.

Implementing Helper Functions

As a prerequisite to the actual collision logic, we'll need the two functions mentioned above.
Starting with the line segment intersection test, we'll additionally need a CrossVector2 function, defined as the magnitude of the cross product of two 2D vectors in 3-space.
Sounds a lot scarier than it is:
Next, the actual intersection test function:
Note that floating point values, by their nature as discretized real numbers, are imprecise; you shouldn't just test equality on them as I do here (rather, you should test if they are within a certain margin of error, often called epsilon), but I didn't want to pollute my example code with them.

Finally, the half-reflect operation, which is really quite simple:

Rewriting AABB Collisions

This was actually the hardest part, but after this, implementing new collider shapes became dead simple.
To keep the first steps simple, let's rewrite it so that we simply stop moving on collision, no sliding for now. We can actually keep the outer condition from our old TestSquareCollision function; unless the bounding boxes intersect, we don't need to do anything.
If there is an intersection, however, we need to make some calls to LineIntersection. Which line segments do we test for intersection, though? I already mentioned that lengthA will always be positionOffset, and that startA will be a corner of the character's hit box. The other line segment is obviously an edge of the hit box we're testing against, but which corner and edge, respectively, depends on the direction the character is going.
If they're moving away from an edge, there's little point in performing a collision test. Similarly, if the positionOffset points inside the character's hit box, we don't need to test that corner.

We'll do the axes separately again, testing both corners on the side that lies further into the direction of movement. That does mean that we're testing one corner twice, during diagonal movement, but against different edges.
Great. That won't actually do anything, though, because we're just discarding the results. We want to find the smallest, non-null result that is in the range [0, 1], let's call it the collisionPoint, and then multiply the positionOffset by that.
Finding the minimum is pretty easy, as we already come across every value (no extra looping required); we just need to start with a collisionPoint = 1 and reassign it every time we come across a smaller value that is greater than one.

Running this, it feels horrible to control, so let's add sliding back in. We already did most of the work by implementing HalfReflect, all that's left is reorganizing our code to use that.
Really, we just need to do some additional bookkeeping; maintain a Vector2 wallNormal that points away from the edge whose collisionPoint we use.
At the end, before multiplying the positionOffset, we then calculate the Vector2 remainder, which we optionally return via a ref parameter:
With that, we can go back to our Update method and add the loop that applies the remainder again.

To do that, we wrap pretty much everything after input processing in a for loop - you could use an infinite loop that breaks when there is no remainder, but that's risky and potentially slow - and maintain a Vector2 nextIterationOffset, which we can apply at the end of the loop, like so:

Adding Triangular Colliders

Finally, something new!
To add a new collider type to the tile map, we first of all need to add a new value to the TileCollider enumeration. I'll just do one orientation and leave the rest as an exercise for the reader, so let's call this one CornerNE, meaning the beveled north-eastern corner of a room.
To make the thing functional, we add a corresponding case to the switch statement in CharacterController.Update.

Therein, we can now write LineIntersection(new Vector2(bottomRightOld.X, topLeftOld.Y), positionOffset, newVector2(x, y), Vector2.One); (x and y are the coordinates of the TileCollider, remember?) and can basically treat the result as we did in TestSquareCollision.
There's two problems with this, though;

• If you move up to the wall, such that LineIntersection returns 0, and then move away from the wall, you'll actually slide, even though that shouldn't happen (unless the wall is magnetic, for instance). To fix that, we can add another condition on the positionOffset's direction, only testing when you're moving towards the wall on at least one axis.
• If you approach such a block from the other side (where a wall should be), you can move all the way through, making this a one-sided wall. The trick here is to goto case TileCollider.Impassable if the character's right is right of the tile collider's right, or their top is above the tile collider's top. This covers not only the right and upper side of the wall, but also its lower-right and upper left-corners.

In it's entirety, the new case looks like this:

That wraps up this lesson, but as I said in the beginning, there's still a bug lingering inside this somewhere, so do beware.
The last collider type I wanted to implement are staircases, which are kind of like diagonal walls, except they are entirely passable, and will always reflect the entire position offset. Not sure if that actually works, but either way, it has some huge implications for animations (which I'll have to rethink anyway).
I'm not sure which problem I'll tackle next, but I'll certainly post about it. Until then!