Collision Prevention

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

lillapojkenpåön
Posts: 20
Joined: Sat Jul 04, 2020 5:27 pm

Collision Prevention

Post by lillapojkenpåön » Sat Jul 11, 2020 5:08 pm

The bg collision example I've found feels way to complicated,
because you move first and undo the move if you collide,
Has anyone made something like this,
were you check next to the sprite (length = your speed) if there's any tiles,
and if there isn't you move,
and if there is you snap to the edge of that tile and skip moving?

Code: Select all

    if (pad & PAD_LEFT) 
	{
        
		
		if(playerY[0] < 0xf0)    //else y out of range
		{
		        temp1 = (playerX[0] - P0XSpeed >> 4);
			temp2 = (playerY[0] - 8 & 0xf0); 

			if (map[temp1+temp2])    // upper left - speed
		        {
		        playerX[0] = temp1 * 4 + 16; 
				P0XSpeed = 0;
				goto dontMove;
		        }
		        
		        
		        
			temp2 = (playerY[0] & 0xf0); 

			if (map[temp1+temp2])    // lower left - speed
			{
			    playerX[0] = temp1 * 4 + 16; 
				P0XSpeed = 0;
				goto dontMove;
			}
			playerX[0] -= P0XSpeed;
		dontMove:;
		}	
    }
playerX[0] = temp1 * 4 + 16;
works good for the first column, but after that it's wrong.

User avatar
tokumaru
Posts: 11761
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Collision Prevention

Post by tokumaru » Sat Jul 11, 2020 7:48 pm

The difference between "moving then testing" and "testing then moving" when it comes to collision detection is mostly semantic, since in both cases you have to calculate new coordinates to verify against the background. Whether you go with assuming that said coordinates are valid and rolling back if they aren't versus validating them before committing the change is of little consequence.

To me it makes more sense to assume that the movement is valid and eject later if necessary, for two reasons:

1- If there's a request for movement (a button press, a speed that's not 0, etc.), this means that something is expected to move, and if there's something blocking that movement, then that's the exception. How much time do you spend in games actually moving around versus pushing walls in vain? Unless you're a really bad player, the former should happen way more frequently. Objects actually moving is the common case, so to me it makes sense to assume that that's what's gonna happen, and handle the less frequent cases of movements being blocked as exceptions.

2- Even if a specific intended movement is not possible in it's entirety, it may still be partially possible. If you're trying to walk 7 pixels but there's a wall 3 pixel in front of you, you don't want to block the movement entirely, you still want to move those 3 pixels, even if the original intended displacement of 7 isn't possible. Ejection is an intuitive way to handle these cases.

But like I said before, it makes little difference whether you're updating the coordinates of an object right away or validating them using temporary variables beforehand. Ultimately, you're pretty much doing the same calculations in both cases, it's just the order that changes a bit.

lillapojkenpåön
Posts: 20
Joined: Sat Jul 04, 2020 5:27 pm

Re: Collision Prevention

Post by lillapojkenpåön » Sun Jul 12, 2020 1:18 am

Well I saw comments in that example like "if this then you're probably stuck in a wall"
and the eject code in this example is pretty huge
also I don't get how you would know what way to eject and how many times reliably?
getting sucked into walls in mario comes to mind
If you're trying to walk 7 pixels but there's a wall 3 pixel in front of you, you don't want to block the movement entirely, you still want to move those 3 pixels, even if the original intended displacement of 7 isn't possible. Ejection is an intuitive way to handle these cases.
Snapping to the edge of the tile in that case is the intuitive way for me, same visual result, without all the invisible moving back and forth,
do you know of any posted examples of either way?
or any tips on how to make 100% reliable eject code?

User avatar
tokumaru
Posts: 11761
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Collision Prevention

Post by tokumaru » Sun Jul 12, 2020 2:26 am

lillapojkenpåön wrote:
Sun Jul 12, 2020 1:18 am
Well I saw comments in that example like "if this then you're probably stuck in a wall"
and the eject code in this example is pretty huge
I don't know what code you're using for reference, but I don't see any reason why ejecting would be any more complex than snapping.
also I don't get how you would know what way to eject and how many times reliably?
getting sucked into walls in mario comes to mind
Say that the player moved past a wall when going right:

Code: Select all

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
00000000000000001111111111111111
0123456789ABCDEF0123456789ABCDEF
                +--------------+
                |     WALL     |
                |              |
                |              |
                |              |
            +-------M          |
            |   |   |          |
            |   +---|----------+
            |   |   |          |
        --> |   |   |          |
            |   |   |          |
            |   |   |          |
            |   |   |          |
            |   |   |          |
------------+---+---N----------+
Points M and N represent the segment that must be checked for collisions in this case. If there are any solid blocks in that line, ejection is necessary. The X coordinate of these points is $14, but the edge of the wall is at $10. You can easily calculate that the difference is 4, and you can add 1 to that since you want the player to *touch* the edge of the wall, not overlap it, so 5 is the amount of pixels you need to push the player back.

The same is true when going left (or up):

Code: Select all

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
00000000000000001111111111111111
0123456789ABCDEF0123456789ABCDEF
+--------------+
|     WALL     |
|              |
|              |
|              |
|          M-------+
|          |   |   |
+----------|---+   |
|          |   |   |
|          |   |   | <--
|          |   |   |
|          |   |   |
|          |   |   |
|          |   |   |
+----------N---+---+------------
The relevant edge of the player is at column $0B, but the edge of the wall is at column $0F. The difference between $0B and $0F is 4, and again you need to add 1 more so the edges are touching and not overlapping.

In actual code, these calculations are really simple (assuming a block size of 16x16 pixels):

Code: Select all

/* When going up: */ EjectY = 0x10 - (PointY & 0x0f)
/* When going down: */ EjectY = PointY & 0x01 + 1
/* When going left: */ EjectX = 0x10 - (PointX & 0x0f)
/* When going right: */ EjectX = PointX & 0x0f + 1
EjectX and EjectY are the amounts of pixels to eject, which you add/subtract to an object's coordinates according to the direction of the movement.
Snapping to the edge of the tile in that case is the intuitive way for me, same visual result, without all the invisible moving back and forth
Like I said before, there's very little difference between one way or the other. If one way feels more intuitive to you and it's working, then by all means stick with it.

lillapojkenpåön
Posts: 20
Joined: Sat Jul 04, 2020 5:27 pm

Re: Collision Prevention

Post by lillapojkenpåön » Sun Jul 12, 2020 3:21 am

Thanks!!!!
Is that possible when using a table of what tiles are on?
* When going left: */ EjectX = 0x10 - (PointX & 0x0f)
I want 0x10 to be a variable, how do I calculate that? would that be (playerX[0] >> 4)?

I tried
EjectX = (playerX[0] >> 4) - (playerX[0] & 0x0f);
but that's not right, what am I doing wrong?

Code: Select all

    if (pad & PAD_LEFT) 
	{
		temp3 = 0;
                playerX[0] -= 3;
		
		if(playerY[0] < 0xf0)    //else y out of range
		{
		        temp1 = (playerX[0] >> 4);
			temp2 = (playerY[0] - 8 & 0xf0); 
			if (map[temp1+temp2]) 
		        {
				temp3 = temp1 - (playerX[0] & 0x0f);
		        }
			temp2 = (playerY[0] & 0xf0); 
			if (map[temp1+temp2]) 
			{
				temp3 = temp1 - (playerX[0] & 0x0f);
			}
			playerX[0] += temp3;
		}	
    }

User avatar
tokumaru
Posts: 11761
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Collision Prevention

Post by tokumaru » Sun Jul 12, 2020 4:10 am

lillapojkenpåön wrote:
Sun Jul 12, 2020 3:21 am
Is that possible when using a table of what tiles are on?
I'm not sure I understand the question...
* When going left: */ EjectX = 0x10 - (PointX & 0x0f)
I want 0x10 to be a variable, how do I calculate that? would that be (playerX[0] >> 4)?
0x10 is just the width/height of each block. In most games this is 16. And 0x0f is just a bit mask for pixels within a block. Since we're working with peers of 2 here, this is just the block size minus 1.
what am I doing wrong?
It's really late here and I'm having a hard time following your code right now, but the basic algorithm I'm describing goes something like this (full code for moving right):

Code: Select all

playerX += displacementX; /* move player horizontally */
blockY0 = (playerY - boxTop) >> 4; /* block where top of bounding box is */
blockY1 = (playerY + boxBottom) >> 4; /* block where bottom of bounding box is */
if (displacementX > 0) { /* if going right */
  edgeX = (playerX + boxRight); /* right edge of bounding box */
  blockX = edgeX >> 4; /* block where right of bounding box is */
  while (blockY0 <= blockY1) { /* check blocks from top to bottom */
    if (blockIsSolid(map[blockY0][blockX])) {
      playerX -= (edgeX & 0x0f + 1) /* eject */
      break; /* no need to check more blocks */
    }
    blockY0++; /* go check the next block down */
  }
} else if (displacementX < 0) { /* if going left */
  /* do the exact same thing, but adjust everything for collisions on the left side */
}
I use 4 separate variables for defining bounding boxes because I like the freedom of putting the hotspots of my objects anywhere I want, but since you probably handle bounding boxes differently, be sure to adjust for that.

Anyway, once the final X coordinate is decided, you can use the exact same logic for vertical movement.

Do note that this is a simplified form of collision detection that only deals with blocks that are either entirely empty or entirely solid. Once you add slopes and different types of collision attributes (solid only from some directions, different materials, etc.) into the mix, things become more complex, obviously.

lillapojkenpåön
Posts: 20
Joined: Sat Jul 04, 2020 5:27 pm

Re: Collision Prevention

Post by lillapojkenpåön » Sun Jul 12, 2020 4:28 am

Thanks!!! got it working now
/* When going up: */ EjectY = 0x10 - (PointY & 0x0f)
/* When going down: */ EjectY = PointY & 0x01 + 1
/* When going left: */ EjectX = 0x10 - (PointX & 0x0f)
/* When going right: */ EjectX = PointX & 0x0f + 1
my sprite is only 8x8 at the moment so I had to do this

//up
temp3 = 16 - (playerY[0] & 15) - 9;
//down
temp3 = (playerY[0] & 15) + 1;

//left
temp3 = 16 - (playerX[0] & 15);
//right
temp3 = (playerX[0] & 15) - 8;

It works like a charm, I just wish I understood how the and works a bit better, thanks for the help!!!!!!!

tepples
Posts: 22017
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Collision Prevention

Post by tepples » Sun Jul 12, 2020 1:34 pm

lillapojkenpåön wrote:
Sun Jul 12, 2020 1:18 am
Well I saw comments in that example like "if this then you're probably stuck in a wall"
and the eject code in this example is pretty huge
also I don't get how you would know what way to eject and how many times reliably?
getting sucked into walls in mario comes to mind
A few years ago, I wrote "Four-corner collision detection". It may help you understand the subproblems and solutions involved in this part of game development.

User avatar
tokumaru
Posts: 11761
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Collision Prevention

Post by tokumaru » Sun Jul 12, 2020 2:21 pm

lillapojkenpåön wrote:
Sun Jul 12, 2020 4:28 am
I just wish I understood how the and works a bit better
AND in this case is used to mask off bits we don't care about. Anything AND 0 equals 0, while anything AND 1 equals anything, so our mask of 0x0f (%00001111) will preserve the lower 4 bits (where the mask contains 1s) as they were, and clear all the others.

We do this because the blocks that form the map are 16x16 pixels large, meaning that their pixel columns/rows are numbered 0 through 15, numbers representable in 4 bits. When doing collision detection, we need to check the solidity of individual blocks, and once a solid one is found, we need to calculate how far the collision point went into that specific block, so we only care about the part of the coordinate that pertains to the inside of that particular block, one of its 16 column/rows, so we clear out the bits that have nothing to do with that.

lillapojkenpåön
Posts: 20
Joined: Sat Jul 04, 2020 5:27 pm

Re: Collision Prevention

Post by lillapojkenpåön » Sun Jul 12, 2020 5:32 pm

Thanks, I'm trying to vizualise a bitcounter, and in my mind when you count from 0 to 255 the low nibble isn't continuously counting from 0 to 15
oh wait, yes ofcourse it does :oops:
and when playerx is 0 it lines up with the first column, so the low nibble is allways how far into the current column you are, got it.

but don't get why I add 16 for up and left, up and right would make sense to me?
Sorry, I have an attention span that allows me to ponder these things for about one second before resetting to zero.
tepples wrote:
Sun Jul 12, 2020 1:34 pm
A few years ago, I wrote "Four-corner collision detection". It may help you understand the subproblems and solutions involved in this part of game development.
Thanks, I will read it!

User avatar
tokumaru
Posts: 11761
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Collision Prevention

Post by tokumaru » Sun Jul 12, 2020 7:07 pm

lillapojkenpåön wrote:
Sun Jul 12, 2020 5:32 pm
but don't get why I add 16 for up and left, up and right would make sense to me?
Because the edge of the block that was crossed is at the other end of the block, on column (or row) 15, rather than column (or row) 0 like it is when moving right/down. We use 16 instead of 15 for the same reason we have that +1 in the other formula, which is because we want the player's bounding box to *touch* the block, not overlap it.

lillapojkenpåön
Posts: 20
Joined: Sat Jul 04, 2020 5:27 pm

Re: Collision Prevention

Post by lillapojkenpåön » Mon Jul 13, 2020 12:08 am

Doh!! Ofcourse!! makes sense now

lillapojkenpåön
Posts: 20
Joined: Sat Jul 04, 2020 5:27 pm

Re: Collision Prevention

Post by lillapojkenpåön » Sun Jul 19, 2020 6:07 pm

bg collision and gravity done, now I will have to do the hard part, enemies, vram buffer and scrolling, I have postponed it for a week since there seems to be many different ways to do it, and I don't get any of them.
hello.nes
(40.02 KiB) Downloaded 10 times

User avatar
Goose2k
Posts: 98
Joined: Wed Dec 11, 2019 9:38 pm
Contact:

Re: Collision Prevention

Post by Goose2k » Mon Jul 20, 2020 10:28 am

Nice work. Feels like I'm controlling a bowling ball made of Iron, but I'm sure that's all tweakable :)

lillapojkenpåön
Posts: 20
Joined: Sat Jul 04, 2020 5:27 pm

Re: Collision Prevention

Post by lillapojkenpåön » Mon Jul 20, 2020 1:06 pm

Haha thanks, yes ofcourse, I just picked some random numbers for the vertical and horizontal acceleration, 32 and 64 I think, I like fast results so I probably won't finetune stuff or graphics until the game is allmost done.

Post Reply