3
\$\begingroup\$

Background

The sweeping method for detecting and resolving collision has proven to be very versatile to implement collision for our game, and I have this GameDev.net article to thank for that: https://www.gamedev.net/tutorials/programming/general-and-gameplay-programming/swept-aabb-collision-detection-and-response-r3084/

The article was very helpful and I learned a lot from it. It did have some bugs in its example code (thankfully we don't have them ourselves), but the concept was the important part. I suggest you read it since it's a very important reference for this post.

The Conflict

The problem I am presented is an unwanted, yet expected behavior. Basically the player is unable to fall into tile-sized gaps if the player is also tile-sized (unless there is something at the end of the hole to block the player).

While the code works in accordance to the GameDev article (I have a demo further down this post), there is a subtle issue with the method of "sliding".

Sliding is a method of collision resolution so that the entity does not stick to the surface of the other physics bodies. It basically allows the player to walk on the ground and slide along walls when jumping on them without being stuck on the surface. This image from the article describes it better than I do:

GameDev article: sliding

This is an ideal solution, but restricts the tile-sized player from falling into tile-sized holes and instead allows the player walk over it.

Tile gap problem

As you can see, you would expect the player to fall into those holes, but Lo and behold he walks right past them! I have tested with various walking velocities, even lower than one pixel per frame and the player still walks past them.

In addition, I'd like to clarify that this is not a problem with just one axis, since the player can't jump into tile-sized holes either.

Tile gap jump

Note that the player is still capable of falling into those holes, there just needs to be a blockade to allow it.

Blockade example 1

...and the same goes for walking into one.

Blockade example 2

The Root of The Problem

I suggest you read some of the code in the demo I have provided, since the following code snipped is relevant for this section:

resolveCollisionOrMove(deltaTime, movement = this.vel, remainingTime = 1, collisionStack = this.collisionStack) {
    // Sort collisions in the correct order: First by distance, then by
    // time of impact to correct the order a bit.
    collisionStack.sort((a, b) => a.distance - b.distance);
    collisionStack.sort((a, b) => a.collisionTime - b.collisionTime);
    let hit = collisionStack.shift();

    // If a collision is detected at all, resolve for the closest AABB. Otherwise add velocity to position.
    if (hit) {
        this.center.x += movement.x * hit.collisionTime * deltaTime;
        this.center.y += movement.y * hit.collisionTime * deltaTime;

        // Calculate the correct time of impact for the remaining
        // collisions or to apply movement
        let time = remainingTime - hit.collisionTime;

        // Calculate the collision normal (vector used to slide the object that collided)
        let dotProduct = p5.Vector.dot(movement, hit.normal) * time;
        hit.normal.mult(dotProduct);

        // Handle events after each respective side that collided
        this.onCollision(hit.side);

        if (time > 0) {
            // If the time of impact happened to be above zero, then recalculate
            // collision for all other potential collisions with respect to the normal vector
            let stack = [];
            for (let sweep of collisionStack) {
                // Pass the normal vector as the movement vector for the next possible collision
                if (this.createMovementBoundary(deltaTime, hit.normal).overlaps(sweep.aabb)) {
                    let newSweep = this.calculateSweepData(sweep.aabb, hit.normal, deltaTime);
                    stack.push(newSweep);
                }
            }

            // Keep resolving collisions for the other potential collisions
            this.resolveCollisionOrMove(deltaTime, hit.normal, time, stack);
        }
    } else {
        this.center.add(p5.Vector.mult(movement, deltaTime));
    }
}

I presume this is a problem caused by the collision normal calculated for the sliding effect. Assume the player walks towards a tile-sized hole from the left (the hole is now to the right of the player). My collision resolution algorithm takes into account other potential collisions based on the sliding vector applied to the player upon the closest detected collision. This means the tile before the hole is what collides with the player first, which in turn applies a movement vector (the slide) with a y-component of zero. This makes the collision algorithm ignore the tile to the left of the hole as a potential collision since according to the logic, the player does not collide with its left side.

Illustration

The green line is the normal vector used for sliding (which is used in the next collision calculation) while the red one is the actual velocity applied to the player before resolving collision...

The issue is I don't know how to solve this problem without breaking the code. I know this problem can be solved by simply reducing the player size. That is not something I'm willing to accept as a solution since it limits many gameplay mechanics which I won't get into here.

The Code

Here is the link to a JSFiddle I made where all the magic happens: https://jsfiddle.net/uwg0m9zp/

I've written it in JavaScript in a single HTML file where I use the p5.js library for simplifying input, graphics and vector calculation. Most of the p5.js function calls are not important for this problem, except for the vector mathematics, but if the structure of the code confuses you just look up the documentation (or ask in the comments): https://p5js.org/

Demo instructions

This demo features a blue rectangle who is our player. He can walk, fly and have collision with the purple tiles in the map.

The controls are:

  • A: Walk Left
  • D: Walk Right
  • Space: Fly

Use these controls to walk/fly into the tile gaps

Final words

I hope I explained my problem well. Please do not hesitate to ask questions if I came across a bit confusing. Note that I have also tested to see if this is a float imprecision problem (using epsilon, etc.) and had no luck.

Thanks for reading this and for any help in advance!

\$\endgroup\$
  • 1
    \$\begingroup\$ Have you considered making the player's collider slightly smaller than the gaps, so they can drop in more easily? Even close-fitting machine parts in reality are manufactured with tolerances so air can escape around the part as it's inserted into the hole. \$\endgroup\$ – DMGregory Sep 9 at 13:14
  • \$\begingroup\$ @DMGregory♦ Yes, but as I said in my post, that is not a solution I'm willing to take. Reducing the collision box size means reducing gameplay possibilities. Imagine a game where the player can't jump and there is a tile-sized hole preventing him from completing the level. He has a square tile-sized crate that he can push into that hole in order to create a bridge over the hole and walk past it. Having a square crate smaller than that hole would mean the crate is not tall enough to create a bridge thus having the player fall slightly down and be blocked by the tile next to the crate. \$\endgroup\$ – Alan Rostem Sep 9 at 13:37
  • \$\begingroup\$ You can solve that by placing a tiny spacer at the bottom of the hole, or treating your corner collisions as though they have a slight radius to let the player climb up a miniscule lip like that when you don't want it to impact gameplay. \$\endgroup\$ – DMGregory Sep 9 at 13:43
  • \$\begingroup\$ The rounding of corners sounds like it could work. I have thought about it, but I have never gotten around to testing it out mainly because I have a slight suspicion it might interfere with the smoothness of gameplay. I will try it out and report back later! \$\endgroup\$ – Alan Rostem Sep 9 at 13:55
  • \$\begingroup\$ But, to reiterate. I'd rather solve the problem I've posted at hand and not discuss raw gameplay mechanics. The problem I'm presented with in my collision algorithm is consistency, since these holes can be passed through if there is a wall to be collided with, but not when running across the hole alone... \$\endgroup\$ – Alan Rostem Sep 9 at 14:00
2
\$\begingroup\$

Since you have a tiled world and an exactly tile-sized character, a first step to sort out this problem can be to recognize when the character aligns with a tile. In the falling-into-a-hole case, this occurs when

  • The Y coordinate is integer (assuming your tiles are side length 1), which should be true whenever sliding on a tile-aligned obstacle is happening.
  • The X coordinate computed by sliding, rounded down to an integer, changes to be a different integer than it was at the beginning of the sliding portion of the movement.

Jumping is the same with the coordinates reversed.

When you recognize that your collision calculation has happened upon a tile-alignment, break the movement into two parts:

(Diagram of a cube sliding across a gap with the point at which it aligns marked.)

Now, you can pretend you're doing a physics step that starts at the dotted box position in this diagram, handle the situation however you like, and if the answer is not "fall down the hole" (for example, in the case where there isn't a hole!), continue to apply the second part of the motion (solid framed box in the diagram) to preserve velocity.


The second part of the problem is interesting: how do we decide the character should fall down the hole? If we look at the moment it's aligned with the tile, it could go right or it could go down, and its velocity vector is mostly aligned with going right with a infinitesimal contribution of gravity pointing down (infinitesimal because it's been in freefall for zero time; or perhaps in simulation, one frame's worth of velocity). Similarly, in the jumping case, the velocity is upward and there's a sideways force but no sideways velocity. A resolution based on the alignment of the velocity vector will consistently give the answer you don't want!

So, for the gameplay you want, you should detect the case where all of these conditions are met:

  • character is aligned with tile (as discussed above),
  • velocity is pointing in a certain direction and gravity or player-input force is pointing perpendicularly
  • and there is open space in that perpendicular direction;

and always choose to take the perpendicular path! You can implement this by proceeding as if there was a blocking tile that stops the character moving the regular direction (might be tricky in the jumping case), or you could simplify the implementation and yet add flair by giving the character an extra kick into the hole (one frame of position shift + some velocity in that direction), maybe even with a special animation.

(Diagram 2)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Great answer! Thanks for posting it! I will accept this answer as soon as I get it working in my example. I want this to work with entities of varying sizes as well, though I should have specified it in this post (and not shown a tile world as an example). But I think your concept will work just fine, I just need to modify how I detect these holes so that it works with entities of varying sizes. \$\endgroup\$ – Alan Rostem Sep 11 at 15:08
  • \$\begingroup\$ Alright! I can say for certain your answer did the trick for me! Thanks again. Basically my solution takes into account varying sizes of entities (along with tiles of course) by simply computing if the distance between the two entities is the same size as the player to detect this case, and then I apply the logic in your answer. I want to post how I solved the problem on this post as well. Would it be okay to do that here as an answer? (I'm kinda new on stackexchange so I'm not too sure.) \$\endgroup\$ – Alan Rostem Sep 11 at 21:07
  • \$\begingroup\$ @AlanRostem It's totally fine and encouraged to post your own answer explaining how you solved the problem for your particular case, when there's something to be said with some technical detail to it (i.e. not just "Kevin's answer worked for me. Thanks!" — which is a message that should be conveyed with upvote/accept, instead). \$\endgroup\$ – Kevin Reid Sep 11 at 21:26
1
\$\begingroup\$

After countless hours of finding the problem through trial and error and asking around on Discord servers and, of course, here, my friend and I found a very versatile solution for a particularly irritating problem.

Credit is due to Kevin Reid who took his precious time to answer this post. He made a well written answer that explained a crucial concept within this solution. I also want to thank a fellow I talked to on the SFML Discord server who was very helpful to show us how we should approach this problem.

What did we learn?

There is one simple thing that I was afraid of which, funny enough, solved it all: adding a special case.

Special cases, special cases, special cases! I was very afraid of breaking the flow of an algorithm I never came up with in the first place (sweeping), but all it needed was to add something extra to check for these tile-sized hole situations while still keeping in touch with how the algorithm "thinks".

This solution takes into account not only holes of equal size to a tile, but pretty much any size of any entity that is about to walk into one.

Detecting such a case

I will explain the detection with a simple example that can be applied to movement in any axis. Assume the player walks from left to right and is approaching a hole that is of equal horizontal size to him in this particular frame. The broadphase portion of the algorithm will always detect potential collision with the two following tiles:

  • the one the player is currently walking on
  • the one (potentially) next to the hole

This is useful information since the collision resolution portion of the algorithm resolves collision in the order of the closest tile to the player.

fixEqualSizedHoleCollision(hit, potentialMovement, time, collisionStack) {
     if (collisionStack.length > 0) {
         // The tile/entity the player currently stands on
         let standingOn = hit.aabb;

         // The tile/entity assumed to be next to the player-sized hole
         let nextToHole = collisionStack[0].aabb;
                ...

By the way, I call this function in the collision resolution portion in my new demo (further down this answer)

Since I pop out the first potential collision, I pass it in as a parameter for this function so that the following potential collision is the first one in the stack.

Now what we need to do is check if these tiles are actually under the player in the first place! This can be done by checking if both of these tiles are half a vertical player size plus half a tile size away from the player on the y-axis. This diagram illustrates this best

Illustration

The green lines are what represents the distance I was talking about. All of those green lines need to be equal to determine if these tiles are exactly beneath the player on the y-axis.

You may have noticed a red line too! This will be used to determine if there is even a player-sized hole at all. Simply make sure the x-distance between the two tiles are the exact same as the player's horizontal size. And bingo! Now we know if there is a hole.

Resolution

Resolving the case was surprisingly less complicated than the detection. Simply stop the player so that it can perfectly fit into the hole, stop all x-movement and slide it downwards with the same magnitude as the gravity. Stopping the player can be simulated with a "barrier" that is right on top of the tile next to the hole.

Barrier illustration

The green line is now the player's new movement vector and the white box is the simulated barrier which stops the player in its tracks! Here is the part of the code which solves that:

barrierOffset.x = (this.extents.x - nextToHole.extents.x) * -movementDir;
if (areBothUnderMe && isHoleBetween) {
    // Create a simulated barrier that will block the player and make him fall
    // into the hole.
    let barrier = new AABB(nextToHole.center.copy(), this.extents.copy());
    barrier.center.sub(barrierOffset);
    this.center.x = barrier.center.x + (barrier.extents.x + this.extents.x) * (-movementDir);
    hit.normal.x = 0; // The player should now fall into the hole and no longer walk
    hit.normal.y = potentialMovement.y; // The sliding should now be applied to the hole wall
}

The New Demo

Here is the new link to a JSFiddle with the new code: https://jsfiddle.net/2bnv510x/

There are some new additions to the previous one. First of all, you can pass in to tile-sized holes (obviously) and secondly I've added two large entities a tile-size apart from each other. I also added some new controls that let you change your velocity:

  • Shift: Move super slow
  • Q: Move super fast

Enjoy!

Final Words

I would like to thank everyone who helped us with this problem. We learned a lot from this problem, and I hope anyone reading this does too.

What got me posting in the first place was the lack of information on swept AABB collision detection and barely information on this problem at all. So I want this post to help anyone who struggles with the same problem.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.