3
\$\begingroup\$

A bit of context about my game:

I'm nearly 2 years deep into development of my game called Cosmorists. It's programmed in C# using the .NET 7.0.11 framework, and MonoGame 3.8.1 game framework and it's a top-down tile-based game with regularly repeating square tiles. One problem has been weighing me down throughout the course of my development journey, and that's collision resolution.

Some context for implementation:

The game uses a tilemap, and it stretches to the 32-bit signed integer limits in both directions. They're stored as 16x16 chunks, and tile positions are represented as complex integers with real and imaginary values. Each tile is stored as a 16-bit unsigned integer representing the tile's index called "decor tiles". 0 is an empty tile.

Since it uses a tilemap, I know that this problem will be much easier for my case, as each tile is a 1x1 square, and the player's position is stored as a complex 64-bit floating point tile position.

What I know about this problem:

I know that this problem involves rays casting outwards, where the ray starts at the player's previous tile position, and ends at the current tile position. If the ray's endpoint is inside of a solid tile, the player's position will have to be set somewhere in between the start and endpoints of the ray, and one of the dimensions of the speed vector will be set to zero. This is where most of the struggles lie, or I may be wrong somewhere in there without knowing.

The C# code:

Here's the code that I have that handles collision resolutions:

void HandleCollisions() {

    if (!vehicleTarget.IsNull) {
        return;
    }

    ComplexDouble previousPreciseTilePosition = preciseTile;
    MoveX(frameLengthSeconds);
    MoveY(frameLengthSeconds);
    ComplexDouble currentPreciseTilePosition = preciseTile;

    if (GameDebug.NoPlayerCollision || (GameDebug.FastMovement && MaxTileMovementSpeed != defaultMaxTileMovementSpeed)) return;

    //Leave the method if the previous and current positions are equal, meaning that the player hasn't moved.
    if (previousPreciseTilePosition == currentPreciseTilePosition) return;

    //These two shift the coordinates to the correct positions depending on the sign of the tile positions.
    int xShift = currentPreciseTilePosition.A < 0 ? 0 : 1;
    int yShift = currentPreciseTilePosition.B < 0 ? 0 : 1;

    ushort GetDecor(ComplexInt tileOffset) {
        try {
            return MainWorld.GetDecorTile((ComplexInt)(preciseTile + (xShift - 1, yShift - 1)) + tileOffset, worldLayer);
        } catch (KeyNotFoundException) {
            return 0;
        }
    }

    //Take the mod one of the number, if it's negative, add one, so that the modulus doesn't go negative and is consistent with the positive modulus.
    double ModOne(double num) {
        double result = num - (int)num;
        if (result < 0) {
            result++;
        }
        return result;
    }
    //Rounds down the double to an integer similar to Math.Floor, this is so that the negative values are consistent with positive values.
    int RoundDown(double num) {
        int result = (int)num;
        if (num < 0 && result != num) {
            result--;
        }
        return result;
    }

    ushort topLeftTile = GetDecor((0, 0));
    ushort topRightTile = GetDecor((1, 0));
    ushort bottomLeftTile = GetDecor((0, 1));
    ushort bottomRightTile = GetDecor((1, 1));

    ComplexInt movementNormal = (Math.Sign(unnormalizedMovementSpeed.A), Math.Sign((float)unnormalizedMovementSpeed.B));

    bool IsSolidTileID(ushort tileID) => tileID != 0
    && (TileDecorProperties.ClassificationOf(World.IDToDecor[tileID]) == TileDecorProperties.Classification.Solid ||
        TileDecorProperties.ClassificationOf(World.IDToDecor[tileID]) == TileDecorProperties.Classification.Tree);

    if (movementNormal.A == -1 && (IsSolidTileID(topLeftTile) || IsSolidTileID(bottomLeftTile))) {
        if (ModOne(currentPreciseTilePosition.A) > 0.5) {
            preciseTile.A = RoundDown(currentPreciseTilePosition.A) + 1;
            unnormalizedMovementSpeed.A = 0;
        }
    }
    if (movementNormal.A == 1 && (IsSolidTileID(topRightTile) || IsSolidTileID(bottomRightTile))) {
        if (ModOne(currentPreciseTilePosition.A) <= 0.5) {
            preciseTile.A = RoundDown(currentPreciseTilePosition.A);
            unnormalizedMovementSpeed.A = 0;
        }
    }
    if (movementNormal.B == -CMath.I && (IsSolidTileID(topLeftTile) || IsSolidTileID(topRightTile))) {
        if (ModOne((double)currentPreciseTilePosition.B) > 0.5) {
            preciseTile.B = RoundDown((double)currentPreciseTilePosition.B) + 1;
            unnormalizedMovementSpeed.B = 0;
        }
    }
    if (movementNormal.B == CMath.I && (IsSolidTileID(bottomLeftTile) || IsSolidTileID(bottomRightTile))) {
        if (ModOne((double)currentPreciseTilePosition.B) <= 0.5) {
            preciseTile.B = RoundDown((double)currentPreciseTilePosition.B);
            unnormalizedMovementSpeed.B = 0;
        }
    }
}

Some context in the code above

The variable preciseTile is the player's current tile position, and it's a complex value with real and imaginary 64-bit float values.

frameLengthSeconds is a 32-bit float value representing how much time has passed between the previous and current frame in seconds.

vehicleTarget at the start doesn't relate to the problem, as it's responsible for knowing if the player is in a spaceship or not, and is merely an optimization.

GameDebug.NoPlayerCollision ||... This is a boolean that simply turns collision on or off when I debug the game, also doesn't relate to the problem.

Complex number context

The x position correlates to A, and the y position correlates to B, and the complex numbers can either be ComplexInt, ComplexFloat, or ComplexDouble. Here's example code demonstrating my implementation of them.

ComplexInt num = (10, 4);
num += 1;
//num: 11 + 4i
num += CMath.I;
//num: 11 + 5i
num += (2, -3);
//num: 13 + 2i
Console.WriteLine(num.A);
//num: 13
Console.WriteLine(num.B);
//num: 2i
Console.WriteLine(num.B * num.B);
//num: -4

Here are the methods that handle player movement.

private void MoveX(float frameLengthSeconds) {
    ComplexInt leftTile = (ComplexInt)preciseTile;
    ComplexInt rightTile = leftTile + 1;
    ushort leftDecorIndex;
    ushort rightDecorIndex;
    try {
        leftDecorIndex = Game1.MainWorld.GetDecorTile(leftTile, worldLayer);
        rightDecorIndex = Game1.MainWorld.GetDecorTile(rightTile, worldLayer);
    } catch (KeyNotFoundException) {
        leftDecorIndex = 0;
        rightDecorIndex = 0;
    }
    //Slows down the player if walking on a tile like water/oil, or speeds up if walking on a floor
    if (leftDecorIndex * rightDecorIndex != 0) {
        double xLeft = preciseTile.A - (int)preciseTile.A;
        if (xLeft < 0) {
            xLeft++;
        }
        double xRight = 1 - xLeft;
        xLeft = 1 - xLeft;
        xRight = 1 - xRight;
        TileDecor leftDecor = TileDecorProperties.ToDecor(leftDecorIndex);
        TileDecor rightDecor = TileDecorProperties.ToDecor(rightDecorIndex);
        double movementMultiplier = TileDecorProperties.SpeedMultiplierOf(leftDecor) * xLeft;
        movementMultiplier += TileDecorProperties.SpeedMultiplierOf(rightDecor) * xRight;
        preciseTile += movementSpeed.A * frameLengthSeconds * movementMultiplier;
    } else {
        preciseTile += movementSpeed.A * frameLengthSeconds;
    }
}
private void MoveY(float frameLengthSeconds) {
    ComplexInt upperTile = (ComplexInt)preciseTile;
    ComplexInt lowerTile = upperTile + CMath.I;
    ushort upDecorIndex;
    ushort downDecorIndex;
    try {
        upDecorIndex = Game1.MainWorld.GetDecorTile(upperTile, worldLayer);
        downDecorIndex = Game1.MainWorld.GetDecorTile(lowerTile, worldLayer);
    } catch (KeyNotFoundException) {
        upDecorIndex = 0;
        downDecorIndex = 0;
    }
    //Slows down the player if walking on a tile like water/oil, or speeds up if walking on a floor
    if (upDecorIndex * downDecorIndex != 0) {
        double xUp = (double)preciseTile.B - (int)preciseTile.B;
        if (xUp < 0) {
            xUp++;
        }
        double xDown = 1 - xUp;
        TileDecor upDecor = TileDecorProperties.ToDecor(upDecorIndex);
        TileDecor downDecor = TileDecorProperties.ToDecor(downDecorIndex);
        double movementMultiplier = TileDecorProperties.SpeedMultiplierOf(upDecor) * xUp;
        movementMultiplier += TileDecorProperties.SpeedMultiplierOf(downDecor) * xDown;
        preciseTile += movementSpeed.B * frameLengthSeconds * movementMultiplier;
    } else {
        preciseTile += movementSpeed.B * frameLengthSeconds;
    }
}

The current implementation of the collision resolution only sort of works. It does succeed in keeping the player out of solid tiles most of the time, but it still has bugs.

The bugs I've found so far:

  1. The player will often clip to the corners of tiles when close to them.
  2. If the framerate is low, the player can penetrate through solid tiles.
  3. If the player moves very fast, they'll also penetrate through solid tiles.

My current implementation in action

The bug in action

In the gif above, the player will often teleport over small distances to the nearest tile to resolve to, and the player won't slide against a wall and they'll just clip against them when I try to move diagonally.

What I'm looking for:

Since I tried to make this problem easier for me by utilizing the fact that it's a square tilemap, I'll go with single point to tilemap collision resolutions instead to keep things simple.

Here's the approach that's the most promising for me, but I also had a hard time trying to implement. I have a ray in a square grid, where the size of each square is 1 and I want to get all the points that are intersecting this grid, and for the resulting list of points to be in order from the start to the end of the ray.

I'm looking for these blue points in the example images below ordered from the first number to the last one just before the arrow:

enter image description here enter image description here

After getting these blue points and determining if the player has collided with a solid tile, I also somehow have to figure out which side the point it's on to know whether to set either the x or y velocity vector to 0 to enable the player to slide against a wall, as well as enabling travel through 1 tile wide gaps. I also want this solution to get rid of the bug where the player will clip to the edges of the tile, and go through solid tiles at low frame rates or high speeds, even if it means that this solution will allow the sprite to partially overlap walls.

The question that I have, is how do I obtain these blue points in order from the start to the end of the ray as 64-bit float values, and figure out which side of the tile the point is colliding with in order to allow wall sliding and 1 tile wide gaps?

\$\endgroup\$
1
  • \$\begingroup\$ You may also be interested in Intersection of thick line with a grid (and the paper linked in the question, which covers the non-thick case of an infinitely small point swept across a grid). \$\endgroup\$
    – DMGregory
    Oct 7, 2023 at 17:23

0

You must log in to answer this question.

Browse other questions tagged .