Getting tile number of background using sprite location

[KennyB]

Hello everybody,

For some while, I've been trying to find the background tile number of the tile based on the location of my sprite.

I've been reading (and learning) in these threads:
8x16 sprite is really a 16x32 pixel image?
Object collision


But I still have some trouble figuring it out and fitting it all together. Maybe someone can give me some pointers ?
Here are the things I think I understand (feel free to correct if somethings wrong):

- Background tiles are stored in an 1D array ==> one after the other
- Sprite location is in 2D (x,y coordinates)
- So we have to use a conversion, depending on the height and width of the background sprites
- For this we can use the formula: (y / MetatilesWidth) * NumberOfMetatilesPerRow + (x / MetatileHeight)
- I have 8x8 tiles as background (so the above formula should say: "tiles" instead of "Metatiles", correct ?)
- So if my sprite location is for example (x,y) = (15,31) it would give: (31/8) * 32 + (15/8) = 3*32 + 1 = 97
- The background tile (at location x,y) is then the 97th one in my 1D array of background tiles
- I may not multiply by 4 instead of 32/8 because the division is used to round the y value of my sprite to a multiple of 8
- I can however do an AND #%11111000 and multiply by 4
- because our 1D-array has values bigger then 255 => we need a 16 bit variable to be able to get it out of the array.


And that's where I'm stuck. I know that all I have to do is load the 97th tile in my background array.
But I'm stuck with converting the (x,y) position to a 16 bit number and then extracting the tile number out of my array with that 16 bit number.

1) The 16 bit variable:

- Do I need to reserve 2 variables ? For example: TempLow and TempHigh.
- I first need to reserve the Low variable (little endian thing ? )
- Or is it allowed to create 1 variable and reserve 2 bytes of space (just Temp) ? Is there then a method to load/store from the high part of this variable ? Or will I run into problem later on by not creating 2 seperate variables ?
- Getting the x-value into the TempLow (or just Temp) will be no problem (I think):

Code: Select all

LDA Sprite_position_X  ; Load A with the X position of my sprite
LSR A ; divide by 2 ==> X/2
LSR A ; divide by 2 ==> X/4
LSR A ; divide by 2 ==> X/8
STA TempLow ; store A now into the TempLow variable (or lower part of Temp)

But converting the Y-value into the TempLow/High part.....

Code: Select all

; we need to divide by 8 (to know the amounts of rows we have)
; and then multiply by 32 (32 tiles a row)

LDA Sprite_position_Y  ; Load A with the Y position of my sprite
AND #%11111000 ; this is the same as dividing by 8 and multiplying by 8. But still necessary to get rid of the last 3 digit's. Only have to multiply by 4
ASL A ; multiply by 2 ==> if we started above with 1111 1111 ==> AND would give 1111 1000 ==> ASL would give 1111 0000
ASL A ; multiply by 2 ==> Next ASL would give 1110 0000
CLC  ; clear the carry 
ADC TempLow ; add the value we got from out of sprite X to A. 
STA TempLow; Store back into TempLow 

; In case the carry is set in the addition ==> add one to the High part of the variable, do not clear carry ? 

LDA Sprite_position_Y  ; Load A with the Y position of my sprite
; 1111 1111 ==> the interesting bits are the 2 most left ones (6 other ones are already added in the low byte part) 
LSR A ==> 1111 1111 ==> becomes 0111 1111
LSR A ==> 1111 1111 ==> becomes 0011 1111
LSR A ==> 1111 1111 ==> becomes 0001 1111
LSR A ==> 1111 1111 ==> becomes 0000 1111
LSR A ==> 1111 1111 ==> becomes 0000 0111
LSR A ==> 1111 1111 ==> becomes 0000 0011

; do not clear the carry here !

ADC $00 ; add the carry to A
STA TempHigh; Store into TempHigh

2) To get the Tile number with the 16 variable ?

To get my background tile I have seen other people use these:

LDA background, x ==> this will load A with the value at background and add x ==> for example 8 + 2
LDA [background], x ==> this will load A with the value at x places beyond background

Do I now need to Load X with the 16 bit variable ? This isn't possible ? x is only 8 bit ?


PS/ Why does ASM 6502 has no LSL and/or ASR opcode ? I assume there is no difference between a Logical Shift and an Arithmetic Shift ?
Why then, haven't they used either LSR+LSL or ASR+ASL ? Instead of a combo of the two ?

[lidnariq]

PS/ Why does ASM 6502 have no LSL and/or ASR opcode ? I assume there is no difference between a Logical Shift and an Arithmetic Shift ?
Why then, haven't they used either LSR+LSL or ASR+ASL ? Instead of a combo of the two ?

The "logical" in the shift instructions mostly means "always shifts in a 0". "arithmetic" mostly means "does something appropriate rather than just always shift in 0". If they actually provided an ASR instruction, it would shift bits 7-1 down to 6-0 and then copy bit 6 back to bit 7. But on an 8 bit micro, it's not clear that's useful; any time you're doing other than 8-bit binary math you'll only use that once, and you may as well force them to write it out longhand (CMP #$80, ROR)

I'm going to arbitrarily guess they chose the pair of ASL+LSR to make the two instructions more visually distinct (and make it easier to catch bugs?).

[thefox]

Well, here are some tips:

One thing first: you seem to be using the term "sprite" for background tiles, don't do that, it's confusing.

1) The 16 bit variable:

- Do I need to reserve 2 variables ? For example: TempLow and TempHigh.

You need to reserve 2 bytes of memory. Whether you use one label or two doesn't matter.

- I first need to reserve the Low variable (little endian thing ? )

Not required, unless you want to use the variable with some of the indirect instructions of 6502 like JMP (ptr) or LDA (ptr),y. But the convention is usually to put the low byte first (and yes, it's called little endian).

- Or is it allowed to create 1 variable and reserve 2 bytes of space (just Temp) ? Is there then a method to load/store from the high part of this variable ? Or will I run into problem later on by not creating 2 seperate variables ?

Yes you can create one label for 2 bytes. To access the low byte, do LDA foo+0 (or simply LDA foo) and for the high byte LDA foo+1

Code: Select all

ASL A ; multiply by 2 ==> if we started above with 1111 1111 ==> AND would give 1111 1000 ==> ASL would give 1111 0000
ASL A ; multiply by 2 ==> Next ASL would give 1110 0000

This you can't do. The result of ASL will not fit in 8 bits, so after ASL you need to shift the discarded bit (in carry) as the lowest bit of TempHigh. Using your example, after first ASL high byte would be %0000 0001 and after the 2nd ASL it would be %0000 0011. You can use ROL to shift the carry into TempHigh (just remember to clear it first), effectively achieving a 16-bit left shift. For more info: http://www.obelisk.demon.co.uk/6502/algorithms.html

2) To get the Tile number with the 16 variable ?

To get my background tile I have seen other people use these:

LDA background, x ==> this will load A with the value at background and add x ==> for example 8 + 2

This will load a byte from address "background + x".

LDA [background], x ==> this will load A with the value at x places beyond background

This code will not work. Only LDA [background], Y addressing mode exists (more commonly written as LDA (background), Y, but do not use this syntax if you're using NESASM). Anyway, it will load a 16-bit pointer from address pointed to by "background" label, and then add Y to that 16-bit pointer, then fetch an 8-bit value from the resulting address.

Do I now need to Load X with the 16 bit variable ? This isn't possible ? x is only 8 bit ?

Yes, it's not possible. Whenever you need to do this, you have to calculate the 16-bit pointer on the zeropage and use LDA (foo), Y or sometimes LDA (foo, X) addressing modes.

[tokumaru]

- Background tiles are stored in an 1D array ==> one after the other

Do you mean in the name table?

- So we have to use a conversion, depending on the height and width of the background sprites

What do you mean "background sprites"? This is very confusing, because on the NES graphics are either sprites or background, they can't be both! There's one thing commonly called "software sprites" which is when sprites (i.e. moving game objects) are drawn with background tiles, but I don't think this is what you're talking about here.

- For this we can use the formula: (y / MetatilesWidth) * NumberOfMetatilesPerRow + (x / MetatileHeight)
- I have 8x8 sprites as background (so the above formula should say: "tiles" instead of "Metatiles", correct ?)

It doesn't really matter what it says (text is just text and doesn't affect the outcome), but as long as MetatilesWidth is 8 and NumberOfMetatilesPerRow is 32 this formula should work for 8x8-pixel tiles in the name tables.

- So if my sprite location is for example (x,y) = (15,31) it would give: (31/8) * 32 + (15/8) = 3*32 + 1 = 97

Sounds correct.

- The background sprite (at location x,y) is then the 97th one in my 1D array of background tiles

It's actually the 98th, since index 0 holds the 1st tile.

- I may not multiply by 4 instead of 32/8 because the division is used to round the y value of my sprite to a multiple of 8
- I can however do an AND #%11111000 and multiply by 4

Yes, you can take shortcuts if you explicitly clear the bits that would normally be cleared during the complete shifting process.

- because our 1D-array has values bigger then 255 => we need a 16 bit variable to be able to get it out of the array.

Yes, you need a 16-bit variable to hold the final offset.

- Do I need to reserve 2 variables ? For example: TempLow and TempHigh.

That depends on how you're reserving RAM for variables. If you're doing the old VARIABLE EQU ADDRESS way, you can just declare the variable that follows this one 2 addresses ahead, instead of just 1. If you're using an assembler directive that reserves bytes, you can just reserve 2 bytes instead of 1 (i.e. VARIABLE .RS 2). You can declare the low and high bytes separately like you wrote, but IMO that looks uglier in the code and will not make it clear whether the bytes are stored back to back (could make a difference for pointers and such).

- I first need to reserve the Low variable (little endian thing ? )

In the NES, the low byte comes first, then the high byte.

- Or is it allowed to create 1 variable and reserve 2 bytes of space (just Temp) ? Is there then a method to load/store from the high part of this variable ?

That's what I would recommend. You can access the low byte with MyVariable+0 (this is for clarity only, since adding 0 to an address doesn't do anything) and the high byte with MyVariable+1.

Or will I run into problem later on by not creating 2 seperate variables ?

Not at all. I recommend creating separate variables for 16-bit (or longer) values only if you can't store them back to back for whatever reason (like if you have an array of low bytes and an array of high bytes).

Code: Select all

LDA Sprite_position_X  ; Load A with the X position of my sprite
LSR A ; divide by 2 ==> X/2
LSR A ; divide by 2 ==> X/4
LSR A ; divide by 2 ==> X/8
STA TempLow ; store A now into the TempLow variable (or lower part of Temp)

That's OK. Don't forget to clear the high byte though.

Code: Select all

ASL A ; multiply by 2 ==> if we started above with 1111 1111 ==> AND would give 1111 1000 ==> ASL would give 1111 0000
ASL A ; multiply by 2 ==> Next ASL would give 1110 0000

Problem here is you're getting rid of important bits. You are multiplying an 8-bit value, meaning the result may not fit into 8 bits, so an 8-bit shift isn't enough to produce correct results. You need a 16-bit shift. You can try this:

Code: Select all

ASL A
ROL Temp+1
ASL A
ROL Temp+1

This will make sure that the bits that extrapolate the 8-bit limit get shifted into the high byte of your 16-bit variable.

Code: Select all

CLC  ; clear the carry
ADC TempLow ; add the value we got from out of sprite X to A. 
STA TempLow; Store back into TempLow

If you cleared Temp+1 to $00, the carry will already be cleared after the last ROL, so you can leave the CLC out if you want to save time, or you can leave it there, just for clarity (what I do in these cases is comment the unnecessary instruction, so that I know it should be there, but isn't really necessary).

LDA Sprite_position_Y ; Load A with the Y position of my sprite
; 1111 1111 ==> the interesting bits are the 2 most left ones (6 other ones are already added in the low byte part)
LSR A ==> 1111 1111 ==> becomes 0111 1111
LSR A ==> 1111 1111 ==> becomes 0011 1111
LSR A ==> 1111 1111 ==> becomes 0001 1111
LSR A ==> 1111 1111 ==> becomes 0000 1111
LSR A ==> 1111 1111 ==> becomes 0000 0111
LSR A ==> 1111 1111 ==> becomes 0000 0011[/code]

Why are you working on the Y coordinate again? None of this is necessary. What you really need is to just add the carry to the high byte:

Code: Select all

LDA Temp+1 ;get the high byte of the adjusted Y coordinate
ADC #$00 ;add to the hight byte of the adjusted X coordinate, plus carry
STA Temp+1

All done.

LDA background, x ==> this will load A with the value at background and add x ==> for example 8 + 2

Ah, so you're loading from ROM, not from VRAM (name tables), got it. Anyway, this only works for 8-bit offsets, you have a 16-bit offset.

LDA [background], x ==> this will load A with the value at x places beyond background

This addressing mode doesn't exist on the 6502, you can only use the Y register in this case.

What you need to do is convert your offset into a pointer. To do this you need to add the base address of your background to the offset, this will get you the final address of the tile you're looking for. Just do a 16-bit addition:

Code: Select all

CLC
LDA #<background
ADC Temp+0
STA Temp+0
LDA #>background
ADC Temp+1
STA Temp+1

The ">" and "<" operators return the low and high bytes of an address, and can vary from assembler to assembler. NESASM for example uses LOW() and HIGH() for this, so you'd use LDA #LOW(background) instead.

Anyway, now you can just do this to get the tile you want:

Code: Select all

LDY #$00
LDA (Temp), Y; or LDA [Temp], Y if it's NESASM

Yes, it's a bit silly that we have to load $00 into Y, but the 6502 doesn't have an indirect load instruction that doesn't use an index, so that's what you get. If you think this is too silly, you can not add the X coordinate to the pointer (i.e. Pointer = Base Address + Y / 8 * 32) and put X / 8 in Y, but that's up to you.

[KennyB]

I had an Eureka moment thanks to you guy's. The pieces are falling together.
Also my apologies for creating confusion by using "Background sprite" instead of "Background tile".

So here is my new code (which I still have to try):

Code: Select all

; declare variable(s)

Temp .rs 2 ; reserve 2 bytes because of 16 bit 

LDA #$00 ; load A with 0
STA Temp+0 ; store in low byte of Temp
STA Temp+1 ; store in high byte of Temp

LDA Sprite_position_X  ; Load A with the X position of my sprite
LSR A ; divide by 2 ==> X/2
LSR A ; divide by 2 ==> X/4
LSR A ; divide by 2 ==> X/8
STA Temp+0  ; store A now into the low byte of variable Temp

LDA Sprite_position_Y  ; Load A with the Y position of my sprite
AND #%11111000 ; this is the same as dividing by 8 and multiplying by 8. But still necessary to get rid of the last 3 digit's. Only have to multiply by 4
ASL A ; multiply by 2 ==> bit 7 is put in the carry, bit 0 = 0
ROL Temp+1 ; All bits are shifted left and the carry (from the ASL above) is used as bit 0 for the High byte of Temp. Carry can be 0 or 1.
ASL A ; 
ROL Temp+1 ; 
CLC ; not necessary to do because bit 7 of high byte from Temp+1 is always 0 
ADC Temp+0 ; Add Temp+0 to A
STA Temp+0 ; store the new Temp+0 value in the low byte of Temp. If overflow (sum to big) ==> Carry is set
LDA Temp+1 ; load A with the high byte of Temp
ADC #$00 ; To add only the carry we just "Add with carry" 0. If carry was set ==> it adds one to high byte.
STA Temp+1 ; Store this new value back into the high byte of Temp

CLC ; clear carry just to be sure
LDA #LOW(background) ; load the low byte of the adress of where my background tiles are saved
ADC Temp+0 ; Add the low byte of Temp. 
STA Temp+0 ; Store it back into the low byte of Temp
LDA #HIGH(background) ; Load the high byte of the adress of where my background tiles are saved.
ADC Temp+1 ; Add the high byte of Temp
STA Temp+1 ; Store it back into the High byte of Temp

; So now we have adress of background + offset stored in the 16 bit variable "Temp"

LDY #$00 ; load Y with zero
LDA [Temp], Y ; load A with the 16 bit adress we have found with the above code. 

; and somewhere in my code I have the background;

background:
  .db $70,$71,$71,$70,$71,$70,$80,$81,$80,$81,$81,$80,$70,$71,$71,$70,$70,$71,$71,$70,$71,$70,$80,$81,$80,$81,$81,$80,$70,$71,$71,$70
  .db $80,$81,$80,$81,$81,$80,$70,$71,$71,$70,$71,$70,$80,$80,$81,$80,$80,$81,$80,$81,$81,$80,$70,$71,$71,$70,$71,$70,$80,$80,$81,$80
 .....

Although I think I understand how it should be done, I still don't get why my code wouldn't/can't work. I made this code for 1 screen of background tiles. It could be that this code does not work when the sprite location of x,y can be bigger then 255 (or if the TileWidth changes). But at this moment: I cannot see the error in my logic (yet). I added some yellow code to explain my logic. In red I used the coordinate (X,Y) = 255,255. Perhaps someone can tell me the flaw in my code ? PS: I don't want to seem ungratefull or anything by asking this. But if I know what I did wrong here (or in my logic), I can even learn more (and possibly prevent mistakes in the future).

Code: Select all

LDA Sprite_position_X  ; Load A with the X position of my sprite
LSR A ; divide by 2 ==> X/2
LSR A ; divide by 2 ==> X/4
LSR A ; divide by 2 ==> X/8
STA TempLow ; store A now into the TempLow variable (or lower part of Temp)

Imagine that Sprite_position_x = HGFEDCBA
By doing 3x LSR ==> it becomes: 000HGFED
This is stored in TempLow = 000HGFED
Let' s assume that Sprite_position_x = 255 = HGFEDCBA:
TempLow will then be: 0001 1111

Code: Select all

; we need to divide by 8 (to know the amounts of rows we have)
; and then multiply by 32 (32 tiles a row)

LDA Sprite_position_Y  ; Load A with the Y position of my sprite
AND #%11111000 ; this is the same as dividing by 8 and multiplying by 8. But still necessary to get rid of the last 3 digit's. Only have to multiply by 4
ASL A ; multiply by 2 ==> if we started above with 1111 1111 ==> AND would give 1111 1000 ==> ASL would give 1111 0000
ASL A ; multiply by 2 ==> Next ASL would give 1110 0000
CLC  ; clear the carry 
ADC TempLow ; add the value we got from out of sprite X to A. 
STA TempLow; Store back into TempLow 

Imagine that Sprite_position_Y = STUVWXYZ
Doing AND #%11111000 ==> it becomes: STUVW000
Doing 2 x ASL = > UVW0000
CLC
ADC with TempLow would give: 000HGFED + UVW0000 = UVWHGFED

Let' s assume that Sprite_position_Y = 255 = STUVWXYZ:
Doing the above makes A = 1110 0000
TempLow was: 0001 1111
Add A and TempLow = 1111 1111
Note: No overflow possible ?!

; In case the carry is set in the addition ==> add one to the High part of the variable, do not clear carry ?

Code: Select all

LDA Sprite_position_Y  ; Load A with the Y position of my sprite
; 1111 1111 ==> the interesting bits are the 2 most left ones (UVW0000 already added above) 
LSR A ==> 1111 1111 ==> becomes 0111 1111
LSR A ==> 1111 1111 ==> becomes 0011 1111
LSR A ==> 1111 1111 ==> becomes 0001 1111
LSR A ==> 1111 1111 ==> becomes 0000 1111
LSR A ==> 1111 1111 ==> becomes 0000 0111
LSR A ==> 1111 1111 ==> becomes 0000 0011

Instead of doing the ASL+ROL trick ==> I have isolated the two biggest bits by doing 6 x ASR

Again, imagine that Sprite_position_Y = STUVWXYZ
Doing 6 x LSR would give:
000000ST


We assumed that Sprite_position_Y = 255 = STUVWXYZ:
Doing the above makes A = 0000 0011

Code: Select all

; do not clear the carry here !
; this code was not correct, should be removed, see below - ADC $00 ; add the carry to A 
STA TempHigh; Store into TempHigh

And here I wanted to add the carry to A in case it was set above with an overflow (addition of TempLow with UVW0000) but just realised that is not possible because my RSL influenced the carry. But I doesn't matter because the low byte cannot overflow UVWHGFED
Then I stored A into TempHigh, giving me in the end:

TempLow = UVWHGFED
TempHigh = 000000ST


Storing A = 0000 0011 into the Highbyte would give us:

TempLow = 1111 1111
TempHigh = 0000 0011

Or if we would think of it in 8 pixel wide tiles:

(x,y) of sprite = (255,255) [PS: I know that Y max can be 240. But for making my example easier, I used 255 for both.]

255 / 8 = 32 collums
255 / 8 = 32 rows
32 x 32 = 1024 tiles ==>

Temp = 0000 0011 1111 1111 = 1023 (offset by one because first tile is 0 and the 1024 tile is then 1023)

[tokumaru]

The code looks correct to me. Are you sure that this is the part that's not working properly? Have you debugged the code and traced through it instruction by instruction to verify where the problem is?

BTW, are you sure that Temp is in ZP? Pointers will only there, and NESASM has been known to silently assemble instructions erroneously when faced with bad addressing modes.

Note: No overflow possible ?!

True... since all the multipliers/dividers we're using to form the offset are powers of 2, this is more a matter of moving bits to the correct locations and combining them than doing any actual math. You could even use ORA to form the low byte instead of ADC, and not care about the carry or adding anything to the high byte.

Personally, I'd do this (not in NESASM syntax):

Code: Select all

	;clear the high byte
	lda #$00
	sta Temp+1
	
	;multiply the Y coordinate
	lda SpriteY
	and #%11111000
	asl
	rol Temp+1
	asl
	rol Temp+1
	
	;add the base address
	adc #<Background
	sta Temp+0
	lda Temp+1
	adc #>Background
	sta Temp+1
	
	;divide the X coordinate and use it as an index
	lda SpriteX
	lsr
	lsr
	lsr
	tay
	
	;get the byte
	lda (Temp), y

This is the fastest way I can think of... there are less accesses to memory and the coordinates are combined by the CPU on the fly, since the X coordinate is small enough to fit in less than 8 bits.

Still, I see nothing wrong with your current logic. Even your "manual trace" led you to the correct result, so the problem must be somewhere else. Like I said before, debug the code as it runs. Add a breakpoint at the start of this code, then follow it instruction by instruction trying to figure out when things go wrong.

[KennyB]

The code looks correct to me. Are you sure that this is the part that's not working properly? Have you debugged the code and traced through it instruction by instruction to verify where the problem is?

BTW, are you sure that Temp is in ZP? Pointers will only there, and NESASM has been known to silently assemble instructions erroneously when faced with bad addressing modes.

Ah ok, I thought that my code for getting the tile number and the code for converting sprite coordinates to tile numbers was faulty.
So if the latter seems correct, I'm going to try and implement the correct code for getting the tile number (with the 16 bit variable) to see if it works.
And then I'll try to improve the code with the ASL+ROL trick.

Thanks a lot guy's !