Hello! Today I am going to talk about a few rather specific problems with our collision detection and response handling that we wrestled with for a long while.
Physics in Backworlds is made up of three different primitives – boxes, lines and “planes” or one-sided lines. While boxes are axis-aligned, they can be sized arbitrarily and although lines and planes have no volume they can have any orientation and length – this gives us a lot of freedom in sizing levels but opens us up to floating-point precision issues. In addition, since a lot of the physics in the game is malleable due to the frontworld/backworld mechanic the solutions need to be very robust since we can’t change level designs to avoid problem cases.
A common attitude in real-time collision handling – or real-time anything, really – is that plausibility, stability and consistent performance are more important than realism. With that in mind, we handle collision by moving objects to where they want to go and then resolve collisions and separate them rather than doing sweeping tests to prevent intersection altogether. Assuming you will have intersections and dealing with them is good to keep code complexity and performance from snowballing, but an additional benefit is that objects never end up stuck in each other if they are teleported or spawned into other objects – we just let the separation code sort it out as it normally would.
It does create a few issues as you will typically have options when separating objects though. The first being one-world physics and planes.
For planes, they work like lines but we only separate in the direction the plane is facing – having a platform you can jump up to from below but not fall through is a staple in platform games and conceptually simple, but since we move objects and then separate they will constantly be falling through the planes – with no prior state, how do we know if we came from below the plane and should be allowed to fall or above and should be forced back on top?
For one-way physics, we actually do want objects to get stuck if the player paints over the level when the object is already there, how do we determine if the object ended up in physics due to a large velocity versus if it ended up there due to the player painting it in?
While we could solve both these problems by analyzing the larger state of the world (the original position of the object and the changing state of the level painting respectively), these require a lot more coupling and come with their own edge cases. Also, it might not be in our best interest to do so – if the player can almost reach a platform we would rather just let them land on it than push them back down, and if the player paints physics along the edge of an object we would not want to immediately make it stuck rather than smoothly move it out of the way. So our solution here is simply to use separation thresholds – if the distance we need to separate is small enough, we separate. Otherwise, the object falls/is stuck in one-world physics.
This does create some issues with tunneling (objects moving fast enough that they penetrate deep into other objects in a single frame that they cross this threshold) but we already split up large movement to deal with this for general purposes. Doing this more creates a bigger performance hit but as we do not have many fast-moving objects in the world this rarely occurs and has yet to be a problem.
For the sake of simplicity, we resolve collisions between two objects at a time – we detect if the objects intersect, and if so separate them by moving the active object the shortest possible distance to free them. This creates a problem when we actually intersect several objects – separating from one might cause us to push further into another. It should be noted that sweeping collisions have an advantage here as we always know the order of collisions and can resolve them one at a time.
Our solution here is very practical – knowing that we will have intersections and sometimes even intersections we cannot resolve, we start with the least harmful ones and continue in order of importance. This way, should two different objects want to separate the active object in different directions, the most important one will have precedence. After some testing, we figured this order as follows;
- Dynamic objects – objects that are free to move by themselves in some fashion. Should these fail to separate they will typically either separate out themselves or ignore collision, as in the case where moving platforms attempt to push an object through the ceiling – the ceiling wins.
- One-world physics – if we fail to separate an object from physics that exist only in one of the worlds, we can always just set the object to be stuck and have the player paint to free it. We don’t want this to happen if a moving object pushes another one into the physics though, so this takes precedence over the dynamic objects.
- Planes – while we do not typically end up in situations where priority matters when we get this far, planes are not solid from all sides and as such it is less bad if objects move through them even from the ‘wrong’ side. Note that one-world planes are processed before one-world boxes and lines but dual-world planes are processed after one-world boxes.
- Solid physics – typically boxes. We handle these last as they are the most important physics making up the world.
It should be noted that most of the time all collisions separate as intended and the priority only matters in very specific cases such as when a moving platform attempts to push an object through a block of static physics. It should also be noted that it is still possible to create problem cases – for instance, by putting an object in a space built with solid physics and without room enough to house it. These cases do not break the game but they look weird and could potentially create opportunities for zip exploits, luckily we can get around them by not designing broken levels.
A problem that is very specific to using float-based movement without sweeping collisions is that of corner intersection – in the left image above, you would expect the avatar to move over the ground as if the floor was one solid piece of physics but when they hit the edge in the middle there may be issues. Since the avatar is moving to the right due to player input but also down due to gravity, the shortest separation distance just when it passes the gap may actually be to the left for the right box and if that intersection gets processed first it will stop the avatar in its tracks. Since the avatar acceleration is less than that of gravity, if this happens the avatar will get stuck in place until the player jumps over the crack or walks back, builds up speed and is more lucky on a second attempt.
While we can typically solve this problem by making sure any player-facing surfaces are single blocks – and we did for a long while – this adds unnecessary overhead to level design and is not always possible.
Our first solution to this problem, one that lasted for several years, was to introduce a separation bias to each of the X and Y axes – in short, when processing the collision we always attempt to find the shortest separation distance, but when evaluating all distances we add or remove a small value to each option depending on the direction of separation, thus making certain directions a bit more likely.
At first, we based the bias on the object velocity – this way, objects were more likely to keep their momentum. This made it less likely that you would get stuck on corners while moving across a floor, but exacerbated the problem where if you did get stuck you would stay stuck as the downward speed from acceleration would be greater than that to the sides.
The solution we ended up going with was to bias separation along the direction of gravity. Balanced properly, this completely removed all instances of getting stuck on the floor but it did make it more likely that you would intersect corners along walls. As this was not a huge issue and we could build around it when we encountered it most of the time, we left it as is for several years.
While the separation bias solution worked, edge cases kept popping up and in some cases there were no ways to build physics around them without redesigning the levels. In addition, it was a fundamentally inelegant solution where magic constants were used for threshold values making the system obtuse and weak to changes in velocities or new objects. We recently did some experimentation and came up with a solution that replaced it.
A key insight of the corner issue is that it only occurs when intersections are so small that the separation along different axes are all so short as to make the decision arbitrary, and it only becomes a problem when these intersections are processed before others. In other words, if the left floorpiece in the example above handles its intersection first the avatar will not need to be separated by the right floorpiece and the problem vanishes.
With that in mind, we went back to the idea of primitive ordering and added the secondary sorting condition of primitive overlap – intersections with a larger overall overlap would be processed before intersections with a smaller one.
This solved most of our problems and allowed us to completely remove the bias code, but one problem remained – lines do not have any volume so any collision involving them would automatically be put at the end of the list. Luckily, this was an easy fix as we can just use the separated volume rather than the overlap volume. There is still a theoretical issue where you could have a separation along the length of a line, but we rarely use them and have no places in the game where it could become an issue.