Multilevel metatile example code

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
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Multilevel metatile example code

Post by tepples »

In [url=https://forums.nesdev.com/viewtopic.php?p=202253#p202253]this post[/url], tokumaru wrote:There are different types of compression that allow almost random access to individual metatiles. I particularly use metatiles (256x256) of metatiles (128x128) of metatiles (64x64) of metatiles (32x32) of metatiles (16x16). Traversing the metatile structure until the 16x16 ones isn't particularly slow.
Is there any public code for doing this quickly, including attributes?
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Multilevel metatile example code

Post by tokumaru »

I don't know what you mean by "quickly", but here's a "GetBlock" subroutine I've used in the past:

Code: Select all

;----------------------------------------------------------------
;DESCRIPTION:
; Finds the code of the block at the specified map coordinates.
;INPUT:
; BlockX, BlockY: pixel coordinates of the block to find;
;OUTPUT:
; A: code of the requested block;
;----------------------------------------------------------------

	Assembler_StartMember Level, GetBlock

	Assembler_StartAbsoluteVariables System::Scratchpad
		BlockX: .res 2 ;horizontal coordinate of the block to find
		BlockY: .res 2 ;vertical coordinate of the block to find
		MapRowAddress: .res 2 ;pointer used to get screens from the level map
	Assembler_EndAbsoluteVariables

	;read the index of the huge structure from the level map (37 cycles)
	lda BlockY+1
	and Level::WrapMaskY
	tay
	lda (Level::MapRowsLow), y
	sta MapRowAddress+0
	lda (Level::MapRowsHigh), y
	sta MapRowAddress+1
	lda BlockX+1
	and Level::WrapMaskX
	tay
	lda (MapRowAddress), y

;HugeStructureFound:

	;read the index of the large structure from the huge structure (19, 20 or 21 cycles)
	tay
	bit BlockY+0
	bmi :++
	bit BlockX+0
	bmi :+
	lda (Level::HugeStructuresPart0), y
	jmp LargeStructureFound
:	lda (Level::HugeStructuresPart1), y
	jmp LargeStructureFound
:	bit BlockX+0
	bmi :+
	lda (Level::HugeStructuresPart2), y
	jmp LargeStructureFound
:	lda (Level::HugeStructuresPart3), y

LargeStructureFound:

	;read the index of the small structure from the large structure (19, 20 or 21 cycles)
	tay
	bit BlockY+0
	bvc :++
	bit BlockX+0
	bvc :+
	lda (Level::LargeStructuresPart0), y
	jmp SmallStructureFound
:	lda (Level::LargeStructuresPart1), y
	jmp SmallStructureFound
:	bit BlockX+0
	bvc :+
	lda (Level::LargeStructuresPart2), y
	jmp SmallStructureFound
:	lda (Level::LargeStructuresPart3), y

SmallStructureFound:

	;read the index of the tiny structure from the small structure (21, 22 or 23 cycles)
	tay
	lda #%00100000
	bit BlockY+0
	bne :++
	bit BlockX+0
	bne :+
	lda (Level::SmallStructuresPart0), y
	jmp TinyStructureFound
:	lda (Level::SmallStructuresPart1), y
	jmp TinyStructureFound
:	bit BlockX+0
	bne :+
	lda (Level::SmallStructuresPart2), y
	jmp TinyStructureFound
:	lda (Level::SmallStructuresPart3), y

TinyStructureFound:

	;read the index of the block from the tiny structure (21, 22 or 23 cycles)
	tay
	lda #%00010000
	bit BlockY+0
	bne :++
	bit BlockX+0
	bne :+
	lda (Level::TinyStructuresPart0), y
	jmp Return
:	lda (Level::TinyStructuresPart1), y
	jmp Return
:	bit BlockX+0
	bne :+
	lda (Level::TinyStructuresPart2), y
	jmp Return
:	lda (Level::TinyStructuresPart3), y

Return:

	;return
	rts

	Assembler_EndMember
I had pointers in ZP pointing to the 4 quadrants of every type of block, and looking at bits from the coordinates I selected which quadrant to read at each step. This subroutine only reads the index of a 16x16-pixel block from the map, if you want more information about the block you still have to look it up.

Now that I'm looking at it again, this does seem to be a bit on the slow side, depending on how many blocks you have to read per frame. I don't see why we can't discuss other possibilities, though. IIRC, this subroutine is meant for random access to anywhere in the map, but when decoding rows and columns of blocks you can probably unroll the code somehow to avoid reading the same blocks over and over (specially the 256x256-pixel block, here called "huge structure"). I never got to do this because at the time I didn't think it was worth the trouble.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Multilevel metatile example code

Post by tepples »

Thanks for showing what you came up with.

Based on statistics gathered from sample backgrounds provided by my artist, I plan to use 64x64 pixels as the coarsest layer, as in Blaster Master.

I'm already using the "separate top left coordinates in world and screen" trick to compensate for 64-pixel-tall large structures not dividing evenly into the 240-pixel height of horizontally arranged nametables. (Even with 4-screen, which I doubt this project can use, 60 is just as much a mismatch.) I just draw a blank as to how to efficiently build a row's or column's worth of attributes. Should I take it as a given that if I'm not keeping a 480-byte cache of 16x16s, I'll have to keep at least a 128-byte cache of both attribute tables in order to combine the attributes on the leading and trailing sides of the seam?
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Multilevel metatile example code

Post by tokumaru »

IIRC, my latest free-scrolling engine used 81 bytes for caching attributes, organized as a 9x9 grid, since that's the bare minimum you need in order to represent what's visible on the screen, so that's a bit better than 128, and much better than 256 (4-screen).

Working with a 9x9 grid can be pretty awkward though, so I kept 2 variables indicating which square in the grid corresponded to the top left corner of the camera. The vertical coordinate (Y) was pre-scaled by 9 and updated in steps of 9 so it could be added to the horizontal coordinate (X) to form the index of the byte to access. These coordinates were updated whenever the camera moved 32 pixels in the corresponding axis. Tables in ROM helped with wrapping around these coordinates so I didn't have to do it manually.
keldon
Posts: 8
Joined: Wed Jun 07, 2017 7:55 am

Re: Multilevel metatile example code

Post by keldon »

Shouldn't you just need two 8-byte attribute caches for top/bottom and two 7-byte attribute caches for left/right, or am I missing something?

You can also store two attribute tables for when row % 4 = 0, and when row % 4 = 2. This way you can just store packed attributes to send straight to the attribute table (even doing away with the 8/7-byte attribute cache).
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Multilevel metatile example code

Post by tokumaru »

keldon wrote:Shouldn't you just need two 8-byte attribute caches for top/bottom and two 7-byte attribute caches for left/right, or am I missing something?
The reason I cache a whole screen is because I also use this when updating destroyed/collected/whatever blocks anywhere on the screen, not only for scrolling.
Post Reply