CC65/CA65: Basic Collision Testing

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
-Basti-
Posts: 40
Joined: Sun Sep 26, 2010 10:29 pm

CC65/CA65: Basic Collision Testing

Post by -Basti- »

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.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: CC65/CA65: Basic Collision Testing

Post by tokumaru »

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.
User avatar
-Basti-
Posts: 40
Joined: Sun Sep 26, 2010 10:29 pm

Re: CC65/CA65: Basic Collision Testing

Post by -Basti- »

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.
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: CC65/CA65: Basic Collision Testing

Post by Bregalad »

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.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: CC65/CA65: Basic Collision Testing

Post by tokumaru »

-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.
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.
User avatar
-Basti-
Posts: 40
Joined: Sun Sep 26, 2010 10:29 pm

Re: CC65/CA65: Basic Collision Testing

Post by -Basti- »

Thanks for your comments :D
User avatar
sempressimo
Posts: 46
Joined: Wed Nov 04, 2015 7:13 am

Re: CC65/CA65: Basic Collision Testing

Post by sempressimo »

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
User avatar
thefox
Posts: 3134
Joined: Mon Jan 03, 2005 10:36 am
Location: 🇫🇮
Contact:

Re: CC65/CA65: Basic Collision Testing

Post by thefox »

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
User avatar
sempressimo
Posts: 46
Joined: Wed Nov 04, 2015 7:13 am

Re: CC65/CA65: Basic Collision Testing

Post by sempressimo »

Well that is new knowledge for me, I will account for that, thanks!
User avatar
rainwarrior
Posts: 8735
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: CC65/CA65: Basic Collision Testing

Post by rainwarrior »

Unrelated to the problem you're having but just thought I might point out:
sempressimo wrote:

Code: Select all

  LSR A
  LSR A
  LSR A
  LSR A ; / 16
  ASL A
  ASL A
  ASL A
  ASL A ; * 16
Is equivalent to:

Code: Select all

  AND #$F0
(Except for failing to clear the carry flag, of course, but that's not relevant here.)
User avatar
sempressimo
Posts: 46
Joined: Wed Nov 04, 2015 7:13 am

Re: CC65/CA65: Basic Collision Testing

Post by sempressimo »

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
User avatar
sempressimo
Posts: 46
Joined: Wed Nov 04, 2015 7:13 am

Re: CC65/CA65: Basic Collision Testing

Post by sempressimo »

rainwarrior wrote:Unrelated to the problem you're having but just thought I might point out:
sempressimo wrote:

Code: Select all

  LSR A
  LSR A
  LSR A
  LSR A ; / 16
  ASL A
  ASL A
  ASL A
  ASL A ; * 16
Is equivalent to:

Code: Select all

  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
User avatar
rainwarrior
Posts: 8735
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: CC65/CA65: Basic Collision Testing

Post by rainwarrior »

Nope.
Post Reply