It is currently Thu May 23, 2019 2:44 pm

 All times are UTC - 7 hours

 Page 2 of 2 [ 23 posts ] Go to page Previous  1, 2
 Print view Previous topic | Next topic
Author Message
 Post subject: Re: Help with getting collision rightPosted: Wed Jan 02, 2019 8:24 am

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1287
After sleeping, I guess I can write some code!

So you want a tile position. Which is player position divided by 8 (tile size). But then you want to multiply the Y tile position by 32 (to make room in the lowest bits for X).

So dividing by 8 is 3 bitshifts right. Multiplying by 32 is 5 bitshifts left.

After each "multiply" by two the lowest bit will be cleared.
It follows that after 5 multiplies by two, the lowest 5 bits will be cleared.
So it follows that 2 bitshifts left of Y, and anding out the lowest 5 bits is the same as multiplying Y's tile position by 32. The AND does the job the divide would do, and you only need two left bitshifts since the 3 right bitshifts didn't need to happen.

Before going too much further, here's what a 16bit bit shift (of a starting 8 bit value) looks like:
Code:
lda #0
sta highbyte;High byte of an unsigned 8 bit value is 0.

lda lowbyte
asl a;multiply by 2, highest bit is in the carry
sta lowbyte
rol highbyte;carry from low byte now in lowest bit, all other bits are shifted

So now let's write some code for this practical purpose.
Code:
;Store the actual positions to temp RAM
;This makes it so that you can make collision a subroutine
;and check arbitrary pixels with this very small prep work

lda \$0203;X position
sta tempRAM

LDA \$0200;Y position
sta tempRAM2

jsr checkCollision

Code:
checkCollision:
;JSR here with an X position in tempRAM
;and a Y position in tempRAM2
;On return, branch on equal succeeding means a collision happened.

lda #\$00
sta playerTileHigh;High byte of an unsigned 8 bit value is 0.

lda tempRAM2;Get the Y position
asl a;multiply low byte by 2
rol playerTileHigh;multiply high byte by 2

asl a;multiply low byte by 2 again. So by 4.
rol playerTileHigh;multiply high byte by 2 again. So by 4;

and #%11100000;Make room for the X tile position
sta playerTileLow

;Y divided by 8, * 32 is now in playerTileLow/High

lda tempRAM;Get the X position
lsr a;2
lsr a;4
lsr a;8
ora playerTileLow
;X and Y are now combined in the low byte
;and no bits are needed from X in the high byte

clc
sta playerTileLow

lda playerTileHigh
sta playerTileHigh

ldy #0
LDA (playerTileLow), y
CMP #\$24

rts;On return, you can branch on equal or not

Let me know if you have questions about that! (Or if it's broken somehow!)

_________________
https://kasumi.itch.io/indivisible

Top

 Post subject: Re: Help with getting collision rightPosted: Wed Jan 02, 2019 1:39 pm

Joined: Tue Dec 18, 2018 9:48 pm
Posts: 13
Kasumi wrote:
Which may make the problem slightly more obvious? Mario's head is in row 15. That's not a collision tile. Cool! Well, one row below that is also not a collision tile. Cool! We can walk.

Row 15 is empty (except the far away mushroom stem on the right). Row 16 is also empty (except for the far away mushroom stem on the right). So until Mario's head dips into Row 16, he can freely walk halfway through those blocks.

Your code checks one row, and the row below it. But Mario can occupy THREE rows of tiles. Fixing it is not quite as easy as just checking a third column below the second because that will make him land too soon. You have to make sure you're checking the tile his feet are actually in. (Which is not always the tile below his head)

Yeah, that was what i tried to show with the screenshot, also i guess i really didn't explain it well, sorry

Kasumi wrote:
[...]But the simplest way is just do the playerTileLow/playerTileHigh math (the multiply by 32 and everything) for every point you want to check, rather than doing it once and trying to offset with y from this. It is possible to do it purely with offsets, but it's a bit tougher.

tokumaru wrote:
Yeah, that's how I normally do it. Doing collisions all in tile space is troublesome because of the different ways in which the sprites may align to the tile grid. Defining each exact point you need to test for solidity in pixel space before converting them to tile space will also make it easier to implement finer collision detection in the future, so you'll be able to implement things like slopes more easily, if you decide to.

Tried to do that, adapted the subroutine to check collision for each part of Mario's sprite, though it seemed like it got harder to find the bug, it was still there, guess i'll try doing the "go back if you shouldn't be here" route and start using pixel space instead of doing collision based on the tiles from the nametable, But then i need to ask: how would i check if there's something on pixel 60, 50 for example? Every time i think about it i just go back to the tile base collision which kind of isn't working right now (The nearest thing i could think was using an invisible block in front of the player and when it hit something the player would stop, but to find out if it is on a tile it shouldn't be i would do basically the same thing as right now).

Edit
Just saw you posted new stuff, gonna check it out.

Top

 Post subject: Re: Help with getting collision rightPosted: Wed Jan 02, 2019 2:25 pm

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11348
Location: Rio de Janeiro - Brazil
Evaghetti wrote:
But then i need to ask: how would i check if there's something on pixel 60, 50 for example? Every time i think about it i just go back to the tile base collision

Well, you absolutely have to check the tiles at some point, we're just suggesting you do it as late as possible. Instead of converting the sprite's top left corner into tile space and doing all in that space, find all 4 corners in pixel space and then convert those to tile space separately.

For example, if Mario's top left corner is at (60, 50) and he's 16x16 pixels large, the other points will be at (75, 50), (60, 65) and (75, 65). Converting those 4 pairs to tile space (i.e. dividing by 8) you get (7, 6), (9, 6), (7, 8) and (9, 8). So, if Mario's moving down, you can check all tiles between (7, 8) and (9, 8). If any of those is solid, you have to eject Mario up.

Similarly, if moving right, you have to check all tiles between (9, 6) and (9, 8). If any of those is solid, eject Mario left.

The exact amount of pixels to eject can be calculated using the pixel coordinates, which will tell you how far into the solid block the sprite went.

When moving right or down, the first pixel inside the block is pixel 0, in which case you need to eject 1 pixel. The second pixel inside the block is pixel 1, in which case you need to eject 2 pixels. From that we conclude that the amount to eject when moving right is (RightX AND 7) + 1. The AND is there to get rid of the bits we don't need. We don't need to know which tile the X coordinate is in (we already used that information before), we need to know how far into the tile the coordinate is. The formula when moving down is the same, but using BottomY instead, obviously.

When moving up or left, things are a bit backwards: the first pixel inside a tile is pixel 7, in which case we eject 1 pixel. The second pixel inside a tile is pixel 6, in which case we eject 2 pixels. From that we conclude that the amount of pixels to eject is 8 - (LeftX AND 7). Same thing for up, but using TopX, obviously.

Top

 Post subject: Re: Help with getting collision rightPosted: Wed Jan 02, 2019 3:42 pm

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1287
Evaghetti wrote:
Yeah, that was what i tried to show with the screenshot, also i guess i really didn't explain it well, sorry

The problem (Mario being halfway in a thing) was clear, but why did not reveal itself to me until I put the grid on it.

More code
Code:
LDA control
AND #%00000001
BEQ endRight

lda playerX;Move the player
clc
sta playerX
clc
adc #15;0 is leftmost pixel, 15 is rightmost for a 16 pixel wide sprite
sta tempRAM
lda playerY
sta tempRAM2

jsr checkCollision;check topright point
beq collidedRight
;if here, the top right didn't collide, but the right middle/bottom right still can

lda tempRAM2
clc
sta tempRAM2
jsr checkCollision;check right middle point
beq collidedRight
;If here, the middle right didn't collide, but the bottom right still can

lda tempRAM2
clc
sta tempRAM2
jsr checkCollision;check bottom right point
bne endRight;If there was no collision, done, we already moved
collidedRight:
;This isn't good ejection, I'll explain that in another post, probably
;edit: Or I guess tokumaru's last post sort of covers it.
;It works for how things are now.
lda playerX
sec
sbc #\$01
sta playerX
endRight:

lda playerX
sta \$0203
sta \$0207
clc
sta \$020B
sta \$020F
;ETC

Edit: Changed the above code to make it so an 8x8 solid wall would not pierce Mario's center by adding a third collision point check. You actually don't need to check a third point in some cases. To know whether or not you need to, you store the right middle y position, add the 7, then check if they have the same bit in the 8s place. If they have the same bit, you'd be checking the same tile for bottom right that you did for right middle, so skip. Otherwise, you need to do the check.

edit2:
Evaghetti wrote:
how would i check if there's something on pixel 60, 50 for example?

Code:
lda #60
sta tempRAM
lda #50
sta tempRAM2
jsr checkCollision;check topright point
beq collided_on_60_50

_________________
https://kasumi.itch.io/indivisible

Last edited by Kasumi on Wed Jan 02, 2019 4:01 pm, edited 1 time in total.

Top

 Post subject: Re: Help with getting collision rightPosted: Wed Jan 02, 2019 4:01 pm

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11348
Location: Rio de Janeiro - Brazil
Instead of adding extra collision points explicitly, which may require extra logic or data, I simply check all tiles between one point and the other... sometimes it'll be 2 tiles, other times 3.

Top

 Post subject: Re: Help with getting collision rightPosted: Wed Jan 02, 2019 4:57 pm

Joined: Tue Dec 18, 2018 9:48 pm
Posts: 13
My god there's a bunch of stuff for me to reply, sorry for taking so long, was messing around with the code you guys posted and wrapping my head around it, i'll respond in the order which you posted the replies.
(Before that just a personal note: i really need to study binary operations like left shift and the AND operation, that stuff still gives me a lot of confusion when begin coding).
Kasumi wrote:
Code:
;Store the actual positions to temp RAM
;This makes it so that you can make collision a subroutine
;and check arbitrary pixels with this very small prep work

lda \$0203;X position
sta tempRAM

LDA \$0200;Y position
sta tempRAM2

jsr checkCollision

Code:
checkCollision:
;JSR here with an X position in tempRAM
;and a Y position in tempRAM2
;On return, branch on equal succeeding means a collision happened.

lda #\$00
sta playerTileHigh;High byte of an unsigned 8 bit value is 0.

lda tempRAM2;Get the Y position
asl a;multiply low byte by 2
rol playerTileHigh;multiply high byte by 2

asl a;multiply low byte by 2 again. So by 4.
rol playerTileHigh;multiply high byte by 2 again. So by 4;

and #%11100000;Make room for the X tile position
sta playerTileLow

;Y divided by 8, * 32 is now in playerTileLow/High

lda tempRAM;Get the X position
lsr a;2
lsr a;4
lsr a;8
ora playerTileLow
;X and Y are now combined in the low byte
;and no bits are needed from X in the high byte

clc
sta playerTileLow

lda playerTileHigh
sta playerTileHigh

ldy #0
LDA (playerTileLow), y
CMP #\$24

rts;On return, you can branch on equal or not

That's really awesome!, since the beginning when i wrote the previous subroutine i thought that it would be really slow, but since (like i stated on the personal note) a i didn't really have a good understanding on how to do proper multiplication and division with assembly i simply let it slide, now i am using this instead of the old subroutine).
tokumaru wrote:
Well, you absolutely have to check the tiles at some point, we're just suggesting you do it as late as possible. Instead of converting the sprite's top left corner into tile space and doing all in that space, find all 4 corners in pixel space and then convert those to tile space separately.

Oh, then i'm happy i was not so far fetched on how to do the collision
tokumaru wrote:
When moving right or down, the first pixel inside the block is pixel 0, in which case you need to eject 1 pixel. The second pixel inside the block is pixel 1, in which case you need to eject 2 pixels. From that we conclude that the amount to eject when moving right is (RightX AND 7) + 1. The AND is there to get rid of the bits we don't need. We don't need to know which tile the X coordinate is in (we already used that information before), we need to know how far into the tile the coordinate is. The formula when moving down is the same, but using BottomY instead, obviously.

Ok, i kind of get the idea, though i kind of am having a bad time thinking about how to code it, also with the comment Kasumi made
Quote:
Code:
;This isn't good ejection, I'll explain that in another post, probably
;edit: Or I guess tokumaru's last post sort of covers it.
;It works for how things are now.

i gotta ask, why is this better than the "just decrease the x/y position when collision happens" method? I'm still a noob when it comes to NES development but it seems like more complex code when a simple DEC/SBC (in the case of walking right) would do the same thing (at least the way i'm seeing it, probably not the right way kkk).
Kasumi wrote:
More code(not gonna copy and paste it to keep this already huge post a little bit shorter)

This corrected the issue and actually made it in a really sweet way! Thanks! Gonna keep an eye out to not just check the left-top most corner of the sprites but their bottom also.
Oh yeah, and thanks for helping me out guys!

Top

 Post subject: Re: Help with getting collision rightPosted: Wed Jan 02, 2019 5:38 pm

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1287
Evaghetti wrote:
i gotta ask, why is this better than the "just decrease the x/y position when collision happens" method? I'm still a noob when it comes to NES development but it seems like more complex code when a simple DEC/SBC (in the case of walking right) would do the same thing (at least the way i'm seeing it, probably not the right way kkk).

In a more complicated game, you could move 3 pixels one frame, 4 pixels the next (because of acceleration, or just sub pixel speeds).
How do you know how many times to DEC or how many pixels to SBC? You can't just eject as many pixels as you moved. Say you're 3 pixels from the wall, but you moved 5 pixels. If you eject 5 pixels, the character is 2 pixels from the wall when they should be right next to it.

You could eject a single pixel, and do the collision check again. Imagine a character that can move 8 pixels per frame! It'd be super expensive.

Given power of 2 tiles, a pixel in a wall will always have low bits of 0 when ejected right, and low bits of 1 when ejected left. (How many low bits depends on the tilesize) Knowing that makes ejection very easy with bitwise stuff.

As for why I think move into wall then eject is better than check before move... it's been hard for me to put into words. Not ejecting is usually the common case, and to get the position to check you already have to do the math to move the object. So you may as well commit that as the position since ejection is less likely.

_________________
https://kasumi.itch.io/indivisible

Top

 Post subject: Re: Help with getting collision rightPosted: Thu Jan 03, 2019 6:12 pm

Joined: Tue Dec 18, 2018 9:48 pm
Posts: 13
Got it, guess that's the next thing i should be trying to do then.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 2 of 2 [ 23 posts ] Go to page Previous  1, 2

 All times are UTC - 7 hours