This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

CC65/CA65: Basic Collision Testing

CC65/CA65: Basic Collision Testing
by on (#148300)
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.
Re: CC65/CA65: Basic Collision Testing
by on (#148304)
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.
Re: CC65/CA65: Basic Collision Testing
by on (#148352)
Thanks, that is exacly what I was searching for :D . 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.
Re: CC65/CA65: Basic Collision Testing
by on (#148353)
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.
Re: CC65/CA65: Basic Collision Testing
by on (#148355)
-Basti- wrote:
((SpriteY >> 3) << 5)

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)

0xf8 in binary is 11111000, so AND'ing a number with it clears the lowermost 3 bits.

Quote:
But somehow I am not completly familiar on how to use the bitwise OR for addition.

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.

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
by on (#148578)
Thanks for your comments :D
Re: CC65/CA65: Basic Collision Testing
by on (#158554)
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:

Image
Image
Image

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
by on (#158555)
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.)
Re: CC65/CA65: Basic Collision Testing
by on (#158556)
Well that is new knowledge for me, I will account for that, thanks!
Re: CC65/CA65: Basic Collision Testing
by on (#158557)
Unrelated to the problem you're having but just thought I might point out:
sempressimo wrote:
Code:
  LSR A
  LSR A
  LSR A
  LSR A ; / 16
  ASL A
  ASL A
  ASL A
  ASL A ; * 16

Is equivalent to:
Code:
  AND #$F0

(Except for failing to clear the carry flag, of course, but that's not relevant here.)
Re: CC65/CA65: Basic Collision Testing
by on (#158558)
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
Re: CC65/CA65: Basic Collision Testing
by on (#158559)
rainwarrior wrote:
Unrelated to the problem you're having but just thought I might point out:
sempressimo wrote:
Code:
  LSR A
  LSR A
  LSR A
  LSR A ; / 16
  ASL A
  ASL A
  ASL A
  ASL A ; * 16

Is equivalent to:
Code:
  AND #$F0

(Except for failing to clear the carry flag, of course, but that's not relevant here.)


Great tip rainwarrior!! I just implemented that, I rather see less lines of code :P

Is there a same shortcut for just:

LSR A
LSR A
LSR A
LSR A ; / 16
Re: CC65/CA65: Basic Collision Testing
by on (#158560)
Nope.