It is currently Sun Oct 22, 2017 7:00 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 15 posts ] 
Author Message
PostPosted: Wed May 17, 2017 8:43 pm 
Offline
User avatar

Joined: Sat Jan 09, 2016 9:21 pm
Posts: 213
Location: Central Illinois, USA
Just curious how everyone likes storing metatile definitions?

Arrays of structs? (a struct that defines a metatile, and have an array of them)
Struct of arrays? (an array of top-left tiles. an array of top-middle-left tiles. and so forth)

I can see pros and cons of different methods, but curious what everyone else likes. I'm playing with the idea of using 4x4 tile metatiles for an in-progress game, and am playing with options now, but figure some of y'all might have some good advice about what's worked well or hasn't worked well for you in the past. I'm leaning towards the struct of arrays, as that's often the right answer on the 6502, but curious if others have thoughts or experiences that I might not have thought of.

Thanks!

_________________
My games: http://www.bitethechili.com


Top
 Profile  
 
PostPosted: Wed May 17, 2017 10:00 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10066
Location: Rio de Janeiro - Brazil
I'm a big fan of structures of arrays. There's no simpler/faster way to access up to 256 items than with structures of arrays. Also, if you need to add more fields, just create new arrays without the need to modify the existing code/data.


Top
 Profile  
 
PostPosted: Wed May 17, 2017 11:58 pm 
Offline

Joined: Tue Oct 06, 2015 10:16 am
Posts: 558
I've used both. In simple cases arrays, in a more complex one where metatiles were made of metatiles and had collision + color info too, there I used an array of structures and a LUT for the multiplication for quick access.

Then in a third case I had arrays, but as they were big I added a skiplist of pointers.


Top
 Profile  
 
PostPosted: Thu May 18, 2017 2:50 am 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1404
gauauu wrote:
Just curious how everyone likes storing metatile definitions?

Arrays of structs? (a struct that defines a metatile, and have an array of them)
Struct of arrays? (an array of top-left tiles. an array of top-middle-left tiles. and so forth)

First of all, don't use an array of a struct. This counts for everything, not just for meta tiles.
Always use structs with arrays in them instead, even if it makes less logical sense.

Because accessing a struct inside an array means that the CPU has to do two runtime calcuations:
The address of the array item (if it's a variable like array[index].Value).
And from that address, the address of the desired struct property.

If you use a bunch of arrays inside a struct, you only have one runtime calculation: The array offset. Because if your struct is a global variable, then the address of each property/array inside it is known at compile time.


Now to your actual question:

It depends on whether you're talking about metatiles of background or of sprites.


In my first game, I simply stored meta sprite definitions by specifying the height (width was hardcoded to 2 tiles, but you could of course also store the width) and the color palette (hence one palette per meta sprite) and then writing each tile number right after another. I.e. simple arrays.

So, in my game, the tiles were always aligned to 8 x 8 pixels, I didn't do arbitrary placement.


For the next game, I'll do it a bit differently:

I simply store the width and the height and the first tile index.

From there, it is a rule that the tiles for the meta sprite have to be in CHR in order.

Disadvantage: You cannot reuse duplicate tiles from CHR. If a certain sprite tile in two meta sprites looks identical, you have to store them twice in CHR. (In this case, it's not so bad since I use UNROM with CHR RAM while my first game was NROM where I only had 256 tiles for the whole game.)

Advantage: No matter how big your character is and no matter how many animation phases it has, you only need to store width, height and one tile index. That's it. (O.k., maybe some palette data, but one byte can be used for the palette values of four tiles.)


About the background:

In my new game, I use meta tiles for objects: Width, height, palette and all tiles in an array.

Then I have an array that stores all the addresses of the meta tile arrays.

And a single screen consists of a bunch of meta tiles: x position, y position and the index of the array that contains the array addresses.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Thu May 18, 2017 7:16 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7234
Location: Chexbres, VD, Switzerland
(Just typing off what I remember - to be verified one I'm at home and I have access to the actual code).
EDIT : This post is almost entierely wrong - proof that I don't even remember how I coded my game engine all those years ago

My game engine works with meta-metatiles, a 32x32 meta-metatiles is made of four 16x16 metatiles, which are made of 4 tiles. The smaller metatiles themselves are just here to gain ROM space in the meta-metatile definition, I could use 16-tiles metatiles directly but it would be more ROM wasting.

Each meta-metatile definition is 6 bytes, 4 for metatiles access, one byte for colour (gets copied "directly" to attribute table, or is split into two nybbles when necessary, depending on alignment), and one byte for collision.

There is basically no advantage of the "array of struct" method, except that it is humanly more intuitive. Only if the array is a power of two and if you already need to shift the value anyway then it doesn't add additional cost to 6502 asm code reading the data. As such, I originally used "array of struct" because it was more intuitive but eventually optimized into "struct of arrays" in order to save ROM.

Collision is single-bit and on 16x16 area, however it is very gross so I'm thinking about improving it to 8x8 area, if possible. Either that or keep 16x16 but support diagonal slopes.

Quote:
It depends on whether you're talking about metatiles of background or of sprites.

"Metatiles" always refers to background, the term used when compounding sprites is "metasprite". So half of your post was off-topic.


Last edited by Bregalad on Tue May 30, 2017 2:46 am, edited 1 time in total.

Top
 Profile  
 
PostPosted: Thu May 18, 2017 12:55 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1404
Oh, about collision: I'm using an array with 240 (16 x 15) entries since all meta tiles have to have an even number of tiles in width and height anyway and since each meta tile has to be aligned to 16 pixels on the screen (with an eight pixels alignment, the palette assignment wouldn't work).

With this array, I can check whether the character can walk to a certain location from his current location.

I might change the array to 30 entries (240 / 8) if required RAM space gets too big, but in the moment, I'm still fine storing the status values one byte per 16 x 16 square and therefore saving ROM space for not needing to do bit shifting whenever the array is accessed.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Thu May 18, 2017 1:03 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5730
Location: Canada
Bregalad wrote:
There is basically no advantage of the "array of struct" method, except that it is humanly more intuitive. Only if the array is a power of two and if you already need to shift the value anyway then it doesn't add additional cost to 6502 asm code reading the data. As such, I originally used "array of struct" because it was more intuitive but eventually optimized into "struct of arrays" in order to save ROM.

When your data has more than 256 entries, an array of structures has an advantage for serial access. (Both better speed and code complexity.)

Otherwise, yes, the only other advantage is to do with code organization, though that is a valid advantage too. (Worse speed and code complexity, but often easier to read/type the array data as assembly or C code.)


Top
 Profile  
 
PostPosted: Thu May 18, 2017 1:25 pm 
Offline
User avatar

Joined: Sat Jan 09, 2016 9:21 pm
Posts: 213
Location: Central Illinois, USA
rainwarrior wrote:
When your data has more than 256 entries, an array of structures has an advantage for serial access. (Both better speed and code complexity.)


The only other advantage I can think of is for iterating through the different actual-tile definitions in the metatile definition. If it's an array of structs, once you find the base address of the metatile you want, it's trivial to lookup or iterate through any of the 16 actual-tiles within it. Otherwise, for a struct of arrays, going from looking up tile[3,2] to looking up tile[3,3] isn't quite as trivial.

That said, I still think (like most of you are saying) that a struct of arrays is the right answer. Thanks for your thoughts!

_________________
My games: http://www.bitethechili.com


Top
 Profile  
 
PostPosted: Thu May 18, 2017 1:36 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1404
I'm still not quite sure in how far structs are needed for meta tile definitions at all. I only have simple byte arrays for this.

Can you elaborate please?

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Thu May 18, 2017 2:01 pm 
Offline
User avatar

Joined: Sun Nov 09, 2008 9:18 pm
Posts: 983
Location: Pennsylvania, USA
Here's some actual map data from my current game. Just like suggestions above, it's all structures of arrays. (except for the row_offsets array, that's just an array of words with row offsets typically used for horizontal maps, but also for horizontal transitions into vertical maps) It's a pretty simple format where I've got "big metatiles" which are full 32x32 pixel sized chunks which contain regular "metatiles" which are just 16x16 pixels or a square containing 4 nametable tiles. Each metatile has additional metadata such as the color attribute, and properties which is a bitfield with information about which direction to eject the character and an action to perform, if any.

Code:
.scope
map_header:
    .byte MAP_MODE_VERTICAL
    .word 0
    .word 240
    .word row_offsets  ;note for a vertical map the only row offset that is provided is row[1] which is the stride, used for decoding columns when doing a horizontal transition into a vertical map). otherwise this is used for horizontal maps so no multiplication by row width must be done.
    .word metatile_table_properties
    .word metatile_table_params
    .word metatile_table_attributes
    .word metatile_table_top_left
    .word metatile_table_top_right
    .word metatile_table_bottom_left
    .word metatile_table_bottom_right
    .word big_metatile_table_top_left
    .word big_metatile_table_top_right
    .word big_metatile_table_bottom_left
    .word big_metatile_table_bottom_right
    .word map
row_offsets:
    .word 0
    .word 8

;metatile properties for collision and actions to perform upon decoding or collision
metatile_table_properties:
    .byte $80 | MAP_ACTION_LADDER
    .byte $f0
    .byte $00 | MAP_ACTION_LOAD_MAP
    .byte $00 | MAP_ACTION_LOAD_MAP
    .byte $f0
    .byte $f0
    .byte $f0
    .byte $f0
    .byte $00 | MAP_ACTION_LOAD_MAP
    .byte $f0 | MAP_ACTION_SPAWN_ENTITY
    .byte $f0
    .byte $00
    .byte $f0
    .byte $80 | MAP_ACTION_LADDER
    .byte $00
    .byte $f0
    .byte $00
    .byte $00
    .byte $00 | MAP_ACTION_LEAVE_LADDER
    .byte $00
    .byte $f0
    .byte $f0 | MAP_ACTION_SWAP_UPPER_2K_BANK
    .byte $f0
    .byte $00
;parameters for actions that require them
metatile_table_params:
    .byte $00
    .byte $00
    .byte >1024
    .byte <1024
    .byte $00
    .byte $00
    .byte $00
    .byte $00
    .byte map_index_carnival_a
    .byte entity_type_load_map
    .byte $00
    .byte $00
    .byte $00
    .byte $00
    .byte $00
    .byte $00
    .byte $00
    .byte $00
    .byte $00
    .byte $00
    .byte $00
    .byte 2
    .byte $00
    .byte $00

;color to apply to a 16x16 chunk on the screen
metatile_table_attributes:
    .byte $00,$aa,$00,$00,$55,$ff,$ff,$ff,$00,$00,$aa,$00,$aa,$00,$00,$ff,$00,$00,$00,$00,$aa,$00,$00,$00

;these are all nametable tiles describing a 16x16 square on the screen
metatile_table_top_left:
    .byte $4d,$50,$83,$80,$01,$5c,$5e,$5e,$80,$03,$54,$80,$73,$4c,$83,$71,$83,$91,$80,$81,$52,$03,$03,$80
metatile_table_top_right:
    .byte $4e,$51,$84,$80,$02,$5d,$5f,$60,$80,$04,$55,$80,$74,$4d,$84,$72,$84,$92,$80,$82,$53,$04,$04,$80
metatile_table_bottom_left:
    .byte $4d,$56,$87,$80,$01,$66,$68,$6a,$80,$03,$5a,$80,$7a,$4c,$87,$79,$87,$96,$80,$85,$58,$03,$03,$80
metatile_table_bottom_right:
    .byte $4e,$57,$98,$80,$02,$67,$69,$6b,$80,$04,$5b,$80,$7b,$4d,$88,$72,$98,$97,$80,$86,$59,$04,$04,$80

;All big metatiles are are 4 indices into regular metatile arrays above.
big_metatile_table_top_left:
    .byte $0b,$12,$0e,$0b,$0b,$0b,$0f,$0b,$0f,$0b,$13,$0b,$17,$0b,$0b,$02,$0b,$10,$0a,$08,$0b,$0b,$0b,$0a
    .byte $0f,$0b,$0b,$14,$0b,$0b,$0f
big_metatile_table_top_right:
    .byte $17,$0c,$0b,$0c,$0b,$0b,$0f,$0b,$0b,$0b,$11,$13,$17,$0b,$0b,$0b,$01,$0b,$0b,$12,$0b,$0b,$0b,$0b
    .byte $0f,$0b,$0b,$0a,$0b,$0b,$0b
big_metatile_table_bottom_left:
    .byte $0b,$00,$0a,$0b,$10,$0b,$16,$0a,$0f,$14,$0b,$01,$11,$16,$0b,$03,$0b,$0b,$15,$09,$07,$11,$0b,$0a
    .byte $0f,$13,$01,$0b,$05,$0e,$16
big_metatile_table_bottom_right:
    .byte $13,$04,$0b,$0c,$0b,$13,$04,$17,$0b,$0a,$0b,$14,$11,$04,$0b,$0b,$0b,$0b,$04,$0d,$0b,$11,$01,$0b
    .byte $0f,$11,$14,$0b,$06,$0b,$04
map:  ;this is just a rectangle of big metatile indices
    .byte $17,$0e,$0e,$0e,$0e,$0e,$0e,$03
    .byte $17,$0e,$0e,$0e,$0e,$0e,$0e,$03
    .byte $17,$0e,$0e,$0e,$0e,$0e,$0e,$03
    .byte $17,$0e,$0e,$0e,$0e,$0e,$0e,$03
    .byte $17,$0e,$0e,$0e,$0e,$0e,$0e,$03
    .byte $17,$0e,$0e,$0e,$0e,$0e,$0e,$03
    .byte $17,$0e,$0e,$0e,$0e,$0e,$0e,$03
    .byte $17,$0e,$0e,$0e,$0e,$0e,$0e,$03
    .byte $17,$0a,$11,$0e,$0e,$16,$09,$03
    .byte $17,$0e,$0e,$0b,$02,$0e,$0e,$03
    .byte $17,$1a,$07,$0e,$0e,$05,$1d,$03
    .byte $17,$00,$0c,$15,$04,$10,$1b,$03
    .byte $17,$0e,$0e,$1c,$14,$0e,$0e,$03
    .byte $17,$19,$04,$18,$08,$0a,$0f,$03
    .byte $12,$0d,$0d,$06,$1e,$0d,$13,$01
.endscope



Top
 Profile  
 
PostPosted: Thu May 18, 2017 2:13 pm 
Offline
User avatar

Joined: Sat Jan 09, 2016 9:21 pm
Posts: 213
Location: Central Illinois, USA
DRW wrote:
I'm still not quite sure in how far structs are needed for meta tile definitions at all. I only have simple byte arrays for this.

Can you elaborate please?


When it comes down to it, everything is just a byte array. But logically, my metatiles have:
Code:
paletteAttributes
collisionInfo
tile_0_0
tile_0_1
tile_0_2
tile_0_3
tile_1_0
tile_1_1
...etc


Sure, that's just an array of bytes, but it has a structure. Which is what I'm talking about.


GradualGames wrote:
Code:
...
    .word metatile_table_properties
    .word metatile_table_params
    .word metatile_table_attributes
    .word metatile_table_top_left
    .word metatile_table_top_right
    .word metatile_table_bottom_left
    .word metatile_table_bottom_right

...



This is basically the type of thing that I ended up with. (without the meta-meta)

_________________
My games: http://www.bitethechili.com


Top
 Profile  
 
PostPosted: Sun May 21, 2017 1:00 pm 
Offline

Joined: Mon May 27, 2013 9:40 am
Posts: 351
I have five byte arrays to store each one of the 4 patterns in every metatile (2x2) plus the palette used. I have a sixth byte array to store each metatile behaviour (obstacle, platform, water, lava, slippery surface, etc). Behaviours are bit-mapped and can be combined. Each metatile always have the same behaviour. I never needed more complexity, and this makes my engines fast and tight, considering I'm a C coder.

Maps, once unpacked, are a series of indexes to all those arrays. Lately I've been using simple 4.4 or 3.5 bits RLE.

I use this arrangement for flick screen or scrolling games whenever I use 2x2 metatiles.

Yes, everything is "synchronized": metatile size, collision layer, attributes. Easy, yet effective.

_________________
http://www.mojontwins.com


Top
 Profile  
 
PostPosted: Mon May 22, 2017 3:45 am 
Online
Formerly WheelInventor

Joined: Thu Apr 14, 2016 2:55 am
Posts: 908
Location: Gothenburg, Sweden
Some years ago i was a bit suprised to see (from snowbro's disassembly) that metroid organized properties tile-level, seeing that it's never used on anything other than one singular two structures (the spawning pipes & lava spitters). they could just aswell have done without it. But it's good for level hacks, with a small fix in the collision detection.

_________________
http://www.frankengraphics.com - personal NES blog


Top
 Profile  
 
PostPosted: Mon May 22, 2017 4:52 am 
Offline
User avatar

Joined: Mon Oct 06, 2014 12:37 am
Posts: 183
I do something somewhat similar to the "standard", but with 5 bytes, because I think using a 6th byte just for color is silly. It can really add up over time!

Here's my metatile format:
Code:
$T1,$T2,$T3,$T4,%CCCCSSPP
T = tile number
C = tile collision
S = tile type
P = tile palette


When loading a map, I do some bitwise shenanigans (0,1,0,1,0,1... 2,3,2,3,2,3...), to keep track of which attribute quadrant I'm on, zeroing out the upper 6 bits, before using both the quadrant number, and the palette index, to read the pre-shifted values from a table.

This sacrifices 13 cycles per iteration, and only uses 16 bytes for a table, instead of (potentially) up to 256 bytes of potentially wasted ROM space. I'd rather use that space for maps/music. At least for an NROM game.

(This trick may have been devised, by working on the VCS hardware, with more extreme restrictions.)


Top
 Profile  
 
PostPosted: Tue May 30, 2017 2:39 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7234
Location: Chexbres, VD, Switzerland
So I just checked how my game did it, and actually it doesn't do what I mentionned at all :)

To define a 32x32px metatile, I use the "evil" array-of-structure scheme, with each structure being 5 bytes. The reason I never switched to structure-of-array is that this wasn't necessary. I copy the definitions from ROM (in this case, CHR-ROM) to RAM, and I change it to an "structure of array" during this operation. As such, when I'm either rendering a screen or checking collision, I just use values in RAM and I don't have to worry in which stage I am, to read the appropriate table. This simplifies the runtime code greatly.

The first byte correspond directly to the value written to the attribute table. (Except in some alignements where it might be separated between 2 nibbles). Then the next 4 bytes are references to 16x16 intermediate metatile indexes, and the 7th bit is used for collision, so that if the value is negative they are walkable and if it's positive they are unwalkable. The 6th bit seems unused (I never use more than 64 16x16px metatiles) so in theory I could use it for improving collision, how exactly I don't know.

The 16x16 intermediate metatiles are defined separatedly, and use 4 consecutive bytes to define metatiles. As thus, I never use the "structure-of-arrays" scheme.


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

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 6 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