CC65/CA65: Basic Collision Testing
Moderator: Moderators
CC65/CA65: Basic Collision Testing
It´s quite a while (nearly 5 years) since my last post in this forum. Meanwhile I finished a whole computer science degree and am working in the busines for about 4 years.
Somehow I never could quit thinking about developing for the NES and now I am back on the train, much more experienced.
I started working with Shirus' NESLib, based on the CC65 cross-compiler. Now I am stucked at implementing a collision test, for over two days.
Therefore I would like to ask for help here. I think its more of a general game design question, but I can't come up with an idea to solve my problem:
1. Before the game-loop I am reading the background, more specific the nametable (first nametable, ASM default $2000 - $23C0) into an array of unsigned chars.
After this, I got an 960-element long array, each element holding the value of one single tile.
2. Now I want to check, if my player (for simplicity one single sprite, 1 tile) hits a brick-tile. My idea is an algorithm which calculates in which bg-tile the players x/y coordinate is.
More exactly I want to calculate the correct index of my bg-array. If I got this index, I can check if the value in my array is the value of a brick-tile.
Any idea how such a basic hit detection function should be implemented? Pseudocode or a verbal explanation should do the job for me.
Somehow I never could quit thinking about developing for the NES and now I am back on the train, much more experienced.
I started working with Shirus' NESLib, based on the CC65 cross-compiler. Now I am stucked at implementing a collision test, for over two days.
Therefore I would like to ask for help here. I think its more of a general game design question, but I can't come up with an idea to solve my problem:
1. Before the game-loop I am reading the background, more specific the nametable (first nametable, ASM default $2000 - $23C0) into an array of unsigned chars.
After this, I got an 960-element long array, each element holding the value of one single tile.
2. Now I want to check, if my player (for simplicity one single sprite, 1 tile) hits a brick-tile. My idea is an algorithm which calculates in which bg-tile the players x/y coordinate is.
More exactly I want to calculate the correct index of my bg-array. If I got this index, I can check if the value in my array is the value of a brick-tile.
Any idea how such a basic hit detection function should be implemented? Pseudocode or a verbal explanation should do the job for me.
Re: CC65/CA65: Basic Collision Testing
Assuming the simplest possible scenario (i.e. no scrolling), converting sprite coordinates into tile coordinates is just a matter of dividing them by 8, since each tile is 8 pixel wide/tall.
If the tile array is 2D (an array containing 30 arrays of 32 elements), you can access a tile like this: tiles[SpriteY / 8][SpriteX / 8]
If the array is 1D, you have to multiply the Y coordinate by the number of tiles in each row, and then add the X coordinate: tiles[(SpriteY / 8) * 32 + (SpriteX / 8)]
Note that these divisions and multiplications are all by powers of 2, so they can be implemented with bit shifts.
You often need to check more than one tile to do proper collisions with the background though. it goes kinda like this:
1- Move the object horizontally;
2- Scan all tiles between (SpriteRight / 8, SpriteTop / 8) and (SpriteRight / 8, SpriteBottom / 8) or (SpriteLeft / 8, SpriteTop / 8) and (SpriteLeft / 8, SpriteBottom / 8), depending on whether the object moved right or left;
3- If any of the tiles is solid, eject the object so that SpriteRight or SpriteLeft touches but doesn't invade the solid column;
4- Move the object vertically;
5- Scan all tiles between (SpriteLeft / 8, SpriteTop / 8) and (SpriteRight / 8, SpriteTop / 8) or (SpriteLeft / 8, SpriteBottom / 8) and (SpriteRight / 8, SpriteBottom / 8), depending on whether the object moved up or down;
6- If any of the tiles is solid, eject the object so that SpriteTop or SpriteBottom touches but doesn't invade the solid row;
SpriteTop, SpriteBottom, SpriteLeft and SpriteRight are the coordinates that define the bounding box of an object. These are used for collisions with the background, but also for collisions against other objects.
If the tile array is 2D (an array containing 30 arrays of 32 elements), you can access a tile like this: tiles[SpriteY / 8][SpriteX / 8]
If the array is 1D, you have to multiply the Y coordinate by the number of tiles in each row, and then add the X coordinate: tiles[(SpriteY / 8) * 32 + (SpriteX / 8)]
Note that these divisions and multiplications are all by powers of 2, so they can be implemented with bit shifts.
You often need to check more than one tile to do proper collisions with the background though. it goes kinda like this:
1- Move the object horizontally;
2- Scan all tiles between (SpriteRight / 8, SpriteTop / 8) and (SpriteRight / 8, SpriteBottom / 8) or (SpriteLeft / 8, SpriteTop / 8) and (SpriteLeft / 8, SpriteBottom / 8), depending on whether the object moved right or left;
3- If any of the tiles is solid, eject the object so that SpriteRight or SpriteLeft touches but doesn't invade the solid column;
4- Move the object vertically;
5- Scan all tiles between (SpriteLeft / 8, SpriteTop / 8) and (SpriteRight / 8, SpriteTop / 8) or (SpriteLeft / 8, SpriteBottom / 8) and (SpriteRight / 8, SpriteBottom / 8), depending on whether the object moved up or down;
6- If any of the tiles is solid, eject the object so that SpriteTop or SpriteBottom touches but doesn't invade the solid row;
SpriteTop, SpriteBottom, SpriteLeft and SpriteRight are the coordinates that define the bounding box of an object. These are used for collisions with the background, but also for collisions against other objects.
Re: CC65/CA65: Basic Collision Testing
Thanks, that is exacly what I was searching for . In my case, I use an 1-dimensional array, so the formula I use is like you said:
(SpriteY / 8) * 32 + (SpriteX / 8)
I also went after your hint to implement this with bitshifting and came up with this working example:
((SpriteY >> 3) << 5) | (x >> 3))
I found some great documentation on how to use bitshifting for replacing arithmetic multiplication and division.
But somehow I am not completly familiar on how to use the bitwise OR for addition. Maybe someone can shortly explain it to me.
Also I am interested, if there is a way to implement substraction with bitwise operation.
(SpriteY / 8) * 32 + (SpriteX / 8)
I also went after your hint to implement this with bitshifting and came up with this working example:
((SpriteY >> 3) << 5) | (x >> 3))
I found some great documentation on how to use bitshifting for replacing arithmetic multiplication and division.
But somehow I am not completly familiar on how to use the bitwise OR for addition. Maybe someone can shortly explain it to me.
Also I am interested, if there is a way to implement substraction with bitwise operation.
Re: CC65/CA65: Basic Collision Testing
When using a normal C compiler, it doesn't matter if you use the bitshift or multiplication/division notation, as those are optimized out anyway. CC65 is absolutely terrible when it comes to optimisation, some of the most basics optimisations steps like this are not even always done, so beware, you'd want to use bitshift notation.
There is nothing special about using bitwise OR for additon. When you add parts of the numbers and know that bits are all 0s in other parts (i.e. bits are not overlapping) it is the same as doing OR. It stops to work as soon as bits are overlapping. Just do it by hand and you'll understand. This isn't really an optimisation, but on the 6502 using ORA instead of ADC can avoid a CLC instruction in some cases.
There is nothing special about using bitwise OR for additon. When you add parts of the numbers and know that bits are all 0s in other parts (i.e. bits are not overlapping) it is the same as doing OR. It stops to work as soon as bits are overlapping. Just do it by hand and you'll understand. This isn't really an optimisation, but on the 6502 using ORA instead of ADC can avoid a CLC instruction in some cases.
Re: CC65/CA65: Basic Collision Testing
This part can be optimized a bit: instead of shifting right 3 times and left 5 times, you can just shift left twice, and clear the bits that would be discarded during the 3 shifts you didn't do: ((SpriteY & 0xf8) << 2)-Basti- wrote:((SpriteY >> 3) << 5)
0xf8 in binary is 11111000, so AND'ing a number with it clears the lowermost 3 bits.
OR can be used to combine values whose bits don't overlap, which is effectively the same as an addition. For example, 0xf0 | 0x0f is 0xff, the same as 0xf0 + 0x0f.But somehow I am not completly familiar on how to use the bitwise OR for addition.
In the case of combining NT coordinates, OR can be used because X always uses bits 0-4 and Y always uses bits 5-9.
Re: CC65/CA65: Basic Collision Testing
Thanks for your comments
- sempressimo
- Posts: 46
- Joined: Wed Nov 04, 2015 7:13 am
Re: CC65/CA65: Basic Collision Testing
I have been having a small issue with this; might collisions against left and right of a tile are perfect, but I have a weird offset when up and down, see the images:
This is my code;
CalculateTileIndex:
; To calc index in .db array do...
;(SpriteY / 8) * 32 + (SpriteX / 8)
; NEW ATTEMPT
LDA object_y
LSR A
LSR A
LSR A
LSR A ; / 16
ASL A
ASL A
ASL A
ASL A ; * 16
STA object_tile_y
LDA object_x
LSR A
LSR A
LSR A
LSR A ; / 16
CLC
ADC object_tile_y ; + y tile pos
STA tile_to_check
RTS
This is my code;
CalculateTileIndex:
; To calc index in .db array do...
;(SpriteY / 8) * 32 + (SpriteX / 8)
; NEW ATTEMPT
LDA object_y
LSR A
LSR A
LSR A
LSR A ; / 16
ASL A
ASL A
ASL A
ASL A ; * 16
STA object_tile_y
LDA object_x
LSR A
LSR A
LSR A
LSR A ; / 16
CLC
ADC object_tile_y ; + y tile pos
STA tile_to_check
RTS
Re: CC65/CA65: Basic Collision Testing
Are you taking into account that sprites are drawn one scanline lower than the Y coordinate that you specify for them? (If you specify Y=0, it will be drawn starting from the second scanline.)
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi
- sempressimo
- Posts: 46
- Joined: Wed Nov 04, 2015 7:13 am
Re: CC65/CA65: Basic Collision Testing
Well that is new knowledge for me, I will account for that, thanks!
- rainwarrior
- Posts: 8735
- Joined: Sun Jan 22, 2012 12:03 pm
- Location: Canada
- Contact:
Re: CC65/CA65: Basic Collision Testing
Unrelated to the problem you're having but just thought I might point out:
(Except for failing to clear the carry flag, of course, but that's not relevant here.)
Is equivalent to:sempressimo wrote:Code: Select all
LSR A LSR A LSR A LSR A ; / 16 ASL A ASL A ASL A ASL A ; * 16
Code: Select all
AND #$F0
- sempressimo
- Posts: 46
- Joined: Wed Nov 04, 2015 7:13 am
Re: CC65/CA65: Basic Collision Testing
Made it work like this; by adding 1 to y before the formula, I was actually expecting to subtract 1 given that rendering thing works...
; To calc index in .db array do...
;(SpriteY ( + 1 ?) / 8) * 32 + (SpriteX / 8)
; NEW ATTEMPT
LDA object_y
CLC
ADC #$01 ; Sprites are drawn one scan lower than the specified Y coordinate
LSR A
LSR A
LSR A
LSR A ; / 16
ASL A
ASL A
ASL A
ASL A ; * 16
STA object_tile_y
LDA object_x
LSR A
LSR A
LSR A
LSR A ; / 16
CLC
ADC object_tile_y ; + y tile pos
STA tile_to_check
; To calc index in .db array do...
;(SpriteY ( + 1 ?) / 8) * 32 + (SpriteX / 8)
; NEW ATTEMPT
LDA object_y
CLC
ADC #$01 ; Sprites are drawn one scan lower than the specified Y coordinate
LSR A
LSR A
LSR A
LSR A ; / 16
ASL A
ASL A
ASL A
ASL A ; * 16
STA object_tile_y
LDA object_x
LSR A
LSR A
LSR A
LSR A ; / 16
CLC
ADC object_tile_y ; + y tile pos
STA tile_to_check
- sempressimo
- Posts: 46
- Joined: Wed Nov 04, 2015 7:13 am
Re: CC65/CA65: Basic Collision Testing
Great tip rainwarrior!! I just implemented that, I rather see less lines of coderainwarrior wrote:Unrelated to the problem you're having but just thought I might point out:Is equivalent to:sempressimo wrote:Code: Select all
LSR A LSR A LSR A LSR A ; / 16 ASL A ASL A ASL A ASL A ; * 16
(Except for failing to clear the carry flag, of course, but that's not relevant here.)Code: Select all
AND #$F0
Is there a same shortcut for just:
LSR A
LSR A
LSR A
LSR A ; / 16
- rainwarrior
- Posts: 8735
- Joined: Sun Jan 22, 2012 12:03 pm
- Location: Canada
- Contact: