Background collision detection optimization

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Background collision detection optimization

Post by DRW »

I've written a function that checks whether a character can walk to a certain position on the screen.
(Characters are always 16 x 16 pixels. And the playfield data is also divided into blocks of 16 x 16 pixels.)

However, I'm asking myself whether these checks and the function in general can be optimized.
I'm not talking about compiler-related stuff like using global variables instead of local ones etc. Those are things I can easily change after finishing the function.
I'm talking about actual algorithm-related things: Can I re-structure the code to make it more simple?

The thing that bothers me the most is the loop:
Let's say a character shall move five pixels to the right. But there's a wall.
Now, it's not enough to simply check for the collision and finish the function when finding the wall. Instead, I have to check: If he cannot walk five pixels, can he walk four pixels? Three? Two? One?

Is there some way to find out how many pixels the character can walk until he hits a wall, without using a loop?
And do you see any other possible optimizations in the function?

(The current code is only for moving right and left since vertical collision detection would pretty much have equivalent code again anyway.)

Code: Select all

void CheckBackgroundCollisionAndUpdatePosition(byte pixels)
{
    byte collisionX;
    byte collisionTile16X;
    byte collisionTile16YTop;
    byte collisionTile16YBottom;
    byte newCollisionX;
    byte newCollisionTile16X;
    byte previousCollisionTile16X;

    switch (Char.HorizontalDirection)
    {
    case DirectionNone:
        return;

    case DirectionLeft:
        collisionX = Char.X;
        newCollisionX = collisionX - pixels;
        break;

    default: /* DirectionRight */
        collisionX = Char.X + (16 - 1);
        newCollisionX = collisionX + pixels;
        break;
    }

    collisionTile16X = collisionX / 16;

    collisionTile16YTop = Char.Y / 16;
    collisionTile16YBottom = (Char.Y + (16 - 1)) / 16;

    newCollisionTile16X = newCollisionX / 16;

    while (true)
    {
        if (newCollisionTile16X == collisionTile16X
         || (GetPlayfieldValue(newCollisionTile16X, collisionTile16YTop) == TileStatusWalkable
          && GetPlayfieldValue(newCollisionTile16X, collisionTile16YBottom) == TileStatusWalkable))
        {
            Char.X =
                Char.HorizontalDirection == DirectionLeft
                    ? newCollisionX
                /* Char.HorizontalDirection == DirectionRight */
                    : newCollisionX - (16 - 1);

            return;
        }

        do
        {
            if (--pixels == 0)
            {
                Char.HorizontalDirection = DirectionNone;
                return;
            }

            if (Char.HorizontalDirection == DirectionLeft)
                ++newCollisionX;
            else /* Char.HorizontalDirection == DirectionRight */
                --newCollisionX;

            previousCollisionTile16X = newCollisionTile16X;
            newCollisionTile16X = newCollisionX / 16;
        }
        while (newCollisionTile16X == previousCollisionTile16X);
    }
}
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: Background collision detection optimization

Post by calima »

Sure you can calculate the amount, as long as your character moves < 16 pixels per frame. If the movement crosses the 16px border, and the new tile is not walkable, you move up to the border. Mod 16 magic.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Background collision detection optimization

Post by DRW »

Thanks. Yeah, that really simplifies the situation.

My new version is shown below. Any more suggestions?

Code: Select all

void CheckBackgroundCollisionAndUpdatePosition(byte pixels)
{
    byte collisionX;
    byte newCollisionX;
    byte newCollisionTile16X;

    switch (Char.HorizontalDirection)
    {
    case DirectionLeft:
        newCollisionX = Char.X - pixels;
        newCollisionTile16X = newCollisionX / 16;

        if (newCollisionTile16X == Char.X / 16
         || (GetPlayfieldValue(newCollisionTile16X, Char.Y / 16) == TileStatusWalkable
          && GetPlayfieldValue(newCollisionTile16X, (Char.Y + (16 - 1)) / 16) == TileStatusWalkable))
        {
            Char.X = newCollisionX;
        }
        else if (Char.X % 16 != 0)
            Char.X &= Bin(1,1,1,1,0,0,0,0);
        break;

    case DirectionRight:
        collisionX = Char.X + (16 - 1);
        newCollisionTile16X = (collisionX + pixels) / 16;

        if (newCollisionTile16X == collisionX / 16
         || (GetPlayfieldValue(newCollisionTile16X, Char.Y / 16) == TileStatusWalkable
          && GetPlayfieldValue(newCollisionTile16X, (Char.Y + (16 - 1)) / 16) == TileStatusWalkable))
        {
            Char.X += pixels;
        }
        else if (Char.X % 16 != 0)
            Char.X = (++collisionX) & Bin(1,1,1,1,0,0,0,0);
        break;
    }
}
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: Background collision detection optimization

Post by calima »

The if is not necessary, at least in some cases, your math in the other case may require it.

Code: Select all

if (Char.X % 16 != 0)
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Background collision detection optimization

Post by Oziphantom »

fast way to detect if you have crossed a power of 2 boundary

(oldValue & (!POW2-1) ^ newValue & (!POW2-1)) != 0

so in your case you are 16 which puts you into a mask value of $F0 or probably as you are 16bit values? $FFF0

Example

Code: Select all

23 -> 24
00010111  00011000
11110000  11110000 AND
------------------------
00010000  00010000 

00010000 EOR
00010000 
-----------
00000000

23 -> 33
00010111  00100001
11110000  11110000 AND
------------------------
00010000  00100000 

00010000 EOR
00100000 
-----------
00110000
Now this can be simplified to newValue ^ oldValue & !(POW2-1)
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Background collision detection optimization

Post by DRW »

Thanks for the replies so far. I'm still working on the function and I'll post it when it's done.

However, in the moment, I've got some general conceptional issues with diagonal movement. This seems to be quite complicated.

If you only have one movement direction, you need to check two points:

Code: Select all

Move left:
x - pixels | y +  0
x - pixels | y + 15

Move right:
x + 15 + pixels | y +  0
x + 15 + pixels | y + 15

Move up:
x +  0 | y - pixels
x + 15 | y - pixels

Move down:
x +  0 | y + 15 + pixels
x + 15 | y + 15 + pixels
But if I have diagonal movement, it seems to be massively more complicated. Not only do I have to check straight horizontal and vertical movement anyway. (After all, if there's one block above you and one block to the left, then you cannot move to the top left, even if the actual place to the top left is free.)
I also have to check four more points:

Code: Select all

x - pixels | y +  0
x - pixels | y + 15

x +  0 | y - pixels
x + 15 | y - pixels

x +  0 - pixels | y +  0 - pixels
x +  0 - pixels | y + 15 - pixels
x + 15 - pixels | y +  0 - pixels
x + 15 - pixels | y + 15 - pixels
Not only does this mean a massive function with eight different cases (up, down, left, right, up/left, up/right, down/left, down/right) who pretty much all do the same stuff (setting the point variables, doing the checks, adjusting the actual new x and y poisition), only with slightly different variables and parameters.
But diagonal movement is four times more time-consuming than straight movement.

And I haven't even considered stuff like:
The character shall move five pixels diagonally. If we moved step by step, pixel by pixel, then we would see that he hits a wall horizontally after three pixels. If that wall wasn't there, he would hit a wall vertically after four pixels. Now, without moving him step by step, we have to find out that the maximum possible number of pixels in this specific constellation is three, and not four or five.

Does anybody have any general tips on how to simplify this approach?
Both as far as the semi-redundant code amount of the function is concerned. (Do I really need to set up eight different situations who do almost the same, only slighty different?)
And the CPU usage. (Does vertical movement really require eight checks as opposed to straight movement that only requires two?)
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Background collision detection optimization

Post by tepples »

After moving the actor both X and Y, eject the actor from walls like this by first reading the contour of the area surrounding the actor from the collision map

1. read the four corners of the actor's bounding box, giving a 2x2 matrix of solidity
2. OR the column that the actor's center is in onto the column that the center is not in
3. OR the row that the actor's center is in onto the row that the center is not in

You have four cases:

A. four cells are filled (something previously went wrong in the physics, or the environment telefragged the actor)
B. no cells are filled (mid-air)
C. one cell is filled, and it's diagonally opposite to the actor (response varies)
D. two or three cells are filled, to be treated as follows
D1. if both bottom cells are filled, push the actor up
D2. if both top cells are filled, push the actor down
D3. if both right cells are filled, push the actor left
D4. if both left cells are filled, push the actor right
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Background collision detection optimization

Post by DRW »

Thanks for your reply.
However, I don't really understand your points 2 and 3.

So, you suggest that I first update the x and y position, check for collision then, and finally adjust the x and y position if necessary, right?

O.k., let's say after moving the character to the desired position, I create these variables (I'm not sure whether I'll need all, but let's do this for now):

Code: Select all

left = x;
right = x + 15;
horizontalCenter = x + 8;
top = y;
bottom = y + 15;
verticalCenter = y + 8;

tile16Left = left / 16;
tile16Right = right / 16;
tile16HorizontalCenter = horizontalCenter / 16;
tile16Top = top / 16;
tile16Bottom = bottom  / 16;
tile16VerticalCenter = verticalCenter / 16;
What do you mean with OR the column that the actor's center is in onto the column that the center is not in?

Let's assume I access the data of a 16x16 block by the following function/macro:

Code: Select all

GetPlayfieldValue(tile16X, tile16Y)
What would I do next?

I could imagine that I now call GetPlayfieldValue with all four corner values:

Code: Select all

topLeftValue = GetPlayfieldValue(tile16Left, tile16Top);
topRightValue = GetPlayfieldValue(tile16Right, tile16Top);
bottomLeftValue = GetPlayfieldValue(tile16Left, tile16Bottom);
bottomRightValue = GetPlayfieldValue(tile16Right, tile16Bottom);
And if topRightValue or bottomRightValue is blocked, then I move the character left to the previous tile-16 x position.
Same with right, top and bottom.

But I'm still curious what you mean with OR the column that the actor's center is in onto the column that the center is not in.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Background collision detection optimization

Post by tepples »

"OR top into bottom" means do this:
1. if topLeftValue is solid, make bottomLeftValue solid
2. if topRightValue is solid, make bottomRightValue solid

"OR bottom into top" means the same thing except with top and bottom swapped.

"OR left into right" means do this:
1. if topLeftValue is solid, make topRightValue solid
2. if bottomLeftValue is solid, make bottomRightValue solid

"OR right into left" means the same thing except with left and right swapped.

"OR the row that the actor's center is in onto the row that the center is not in" means do this:
A. If the center of the actor's bounding box is above the horizontal line between the top cells and the bottom cells, OR top into bottom
B. If the center of the actor's bounding box is below the horizontal line between the top cells and the bottom cells, OR bottom into top

"OR the row that the actor's center is in onto the row that the center is not in" means do this:
A. If the center of the actor's bounding box is to the left of the vertical line between the left cells and the right cells, OR left into right
B. If the center of the actor's bounding box is to the right of the vertical line between the left cells and the right cells, OR right into left
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Background collision detection optimization

Post by DRW »

I tried your approach of setting the new destination position first and then pushing the character to the side accordingly. But I ran into the problem that if a character moves diagonally partly into a block, I have difficulty pushing him to the correct position. If I push him horizontally and vertically out of the block again, this means he ends up in a way that, for example, his top right corner is next to the block's bottom left corner.
But if the character is four pixels below the block and two pixels to the left side of it and he shall move seven pixels diagonally up right, you obviously don't want him to end up at the corner of the block, but somewhere at the bottom side of the block.

After trying out several things, I did the following:

Firstly, I don't move him to the destination location and do adjustments from there, but I check how far he can move before updating the coordinate.

And secondly, for diagonal movements, I do the simple thing of moving the character first horizontally and then vertically. It might have a bias in a way that the character will more often land on the top or bottom of a block instead of on its sides. But I guess in the final game, characters will only move two or three pixels diagonally at most, so it doesn't really matter.

You can find my current function below. If there's still stuff to optimize, I'd be interested to hear it.

Please note:

The game has vertical, but not horizontal scrolling, that's why the y position uses an offset.

And when moving upwards, the characters can have their upper bodies half in the wall while bottom and side collision are at the actual borders of the character sprite. (Like in "The Legend of Zelda" for the NES.) That's why eight pixels are added to the top y position and the AND-check is against %11111000 instead of %11110000.

Code: Select all

void CheckBackgroundCollision(byte pixels)
{
    byte yWithOffset;
    byte collisionPosition;
    byte newCollisionTile16Position;

    yWithOffset = Char.Y + CharOffsetY;

    switch (Char.HorizontalDirection)
    {
    case DirectionLeft:
        newCollisionTile16Position = (Char.X - pixels) / 16;

        if (newCollisionTile16Position == Char.X / 16
         || (GetPlayfieldValue(newCollisionTile16Position, (yWithOffset + 8) / 16) == TileStatusWalkable
          && GetPlayfieldValue(newCollisionTile16Position, (yWithOffset + (16 - 1)) / 16) == TileStatusWalkable))
        {
            Char.X -= pixels;
        }
        else
        {
            Char.X &= Bin(1,1,1,1,0,0,0,0);
            Char.HorizontalDirection = DirectionNone;
        }
        break;

    case DirectionRight:
        collisionPosition = Char.X + (16 - 1);
        newCollisionTile16Position = (collisionPosition + pixels) / 16;

        if (newCollisionTile16Position == collisionPosition / 16
         || (GetPlayfieldValue(newCollisionTile16Position, (yWithOffset + 8) / 16) == TileStatusWalkable
          && GetPlayfieldValue(newCollisionTile16Position, (yWithOffset + (16 - 1)) / 16) == TileStatusWalkable))
        {
            Char.X += pixels;
        }
        else
        {
            if (Char.X % 16 != 0)
                Char.X = (Char.X + 16) & Bin(1,1,1,1,0,0,0,0);

            Char.HorizontalDirection = DirectionNone;
        }
        break;
    }

    switch (Char.VerticalDirection)
    {
    case DirectionUp:
        collisionPosition = yWithOffset + 8;
        newCollisionTile16Position = (collisionPosition - pixels) / 16;

        if (newCollisionTile16Position == collisionPosition / 16
         || (GetPlayfieldValue(Char.X / 16, newCollisionTile16Position) == TileStatusWalkable
          && GetPlayfieldValue((Char.X + (16 - 1)) / 16, newCollisionTile16Position) == TileStatusWalkable))
        {
            Char.Y -= pixels;
        }
        else
        {
            Char.Y = (yWithOffset & Bin(1,1,1,1,1,0,0,0)) - CharOffsetY;
            Char.VerticalDirection = DirectionNone;
        }
        break;

    case DirectionDown:
        collisionPosition = yWithOffset + (16 - 1);
        newCollisionTile16Position = (collisionPosition + pixels) / 16;

        if (newCollisionTile16Position == collisionPosition / 16
         || (GetPlayfieldValue(Char.X / 16, newCollisionTile16Position) == TileStatusWalkable
          && GetPlayfieldValue((Char.X + (16 - 1)) / 16, newCollisionTile16Position) == TileStatusWalkable))
        {
            Char.Y += pixels;
        }
        else
        {
            if (yWithOffset % 16 != 0)
                Char.Y = ((yWithOffset + 16) & Bin(1,1,1,1,0,0,0,0)) - CharOffsetY;

            Char.VerticalDirection = DirectionNone;
        }
        break;
    }
}
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
olddb
Posts: 188
Joined: Thu Oct 26, 2017 12:29 pm
Contact:

Re: Background collision detection optimization

Post by olddb »

Hello DRW!

What type of game are you making?
...
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Background collision detection optimization

Post by DRW »

A vertically-scrolling top-down game. Why are you asking?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
olddb
Posts: 188
Joined: Thu Oct 26, 2017 12:29 pm
Contact:

Re: Background collision detection optimization

Post by olddb »

Just curious
...
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Background collision detection optimization

Post by DRW »

I’ll tell you if you tell me the current status of your game.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
olddb
Posts: 188
Joined: Thu Oct 26, 2017 12:29 pm
Contact:

Re: Background collision detection optimization

Post by olddb »

DRW wrote: Wed Apr 20, 2022 10:54 am I’ll tell you if you tell me the current status of your game.
sure
...
Post Reply