It is currently Fri Dec 14, 2018 7:52 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 13 posts ] 
Author Message
PostPosted: Wed May 27, 2015 12:46 pm 
Offline
User avatar

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
 Profile  
 
PostPosted: Wed May 27, 2015 1:43 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11012
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
 Profile  
 
PostPosted: Thu May 28, 2015 4:57 am 
Offline
User avatar

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


Top
 Profile  
 
PostPosted: Thu May 28, 2015 5:21 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7604
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
 Profile  
 
PostPosted: Thu May 28, 2015 7:02 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11012
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
 Profile  
 
PostPosted: Sun May 31, 2015 10:30 am 
Offline
User avatar

Joined: Sun Sep 26, 2010 10:29 pm
Posts: 40
Thanks for your comments :D


Top
 Profile  
 
PostPosted: Fri Nov 06, 2015 10:52 am 
Offline
User avatar

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:

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


Top
 Profile  
 
PostPosted: Fri Nov 06, 2015 11:00 am 
Offline
User avatar

Joined: Mon Jan 03, 2005 10:36 am
Posts: 3141
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
 Profile  
 
PostPosted: Fri Nov 06, 2015 11:04 am 
Offline
User avatar

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


Top
 Profile  
 
PostPosted: Fri Nov 06, 2015 11:05 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7015
Location: Canada
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
 Profile  
 
PostPosted: Fri Nov 06, 2015 11:11 am 
Offline
User avatar

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
 Profile  
 
PostPosted: Fri Nov 06, 2015 11:16 am 
Offline
User avatar

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 :P

Is there a same shortcut for just:

LSR A
LSR A
LSR A
LSR A ; / 16


Top
 Profile  
 
PostPosted: Fri Nov 06, 2015 11:29 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7015
Location: Canada
Nope.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 13 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group