It is currently Thu Sep 20, 2018 5:40 am

 All times are UTC - 7 hours

 Page 1 of 1 [ 13 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: CC65/CA65: Basic Collision TestingPosted: Wed May 27, 2015 12:46 pm

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

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Wed May 27, 2015 1:43 pm

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

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Thu May 28, 2015 4:57 am

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

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Thu May 28, 2015 5:21 am

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7517
Location: Chexbres, VD, Switzerland
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.

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Thu May 28, 2015 7:02 am

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

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Sun May 31, 2015 10:30 am

Joined: Sun Sep 26, 2010 10:29 pm
Posts: 40

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Fri Nov 06, 2015 10:52 am

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

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Fri Nov 06, 2015 11:00 am

Joined: Mon Jan 03, 2005 10:36 am
Posts: 3127
Location: Tampere, Finland
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

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Fri Nov 06, 2015 11:04 am

Joined: Wed Nov 04, 2015 7:13 am
Posts: 46
Well that is new knowledge for me, I will account for that, thanks!

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Fri Nov 06, 2015 11:05 am

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6808
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.)

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Fri Nov 06, 2015 11:11 am

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

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Fri Nov 06, 2015 11:16 am

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

Is there a same shortcut for just:

LSR A
LSR A
LSR A
LSR A ; / 16

Top

 Post subject: Re: CC65/CA65: Basic Collision TestingPosted: Fri Nov 06, 2015 11:29 am

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6808
Nope.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 13 posts ]

 All times are UTC - 7 hours