Best data structure for LTTP-style maps

Hi there! I've been away from the hobby for a few years but now I'm back with a new project idea and hoped I could get some help brainstorming the best way to approach arranging the level data.

What I'm doing now is building a framework for a map that scrolls in all directions, but has transitions every few screens to provide breaks in gameplay and allow for loading of different CHR banks.

When I was experimenting with purely horizontal scrolling in the past, I put my metatiles into 32x32 blocks, arranged those in columns, and loaded 32 pixels and attributes at once. Now, since I'm scrolling in both directions and can only load 8 pixels at a time, there's not a best option that seems obvious to me.

In the past for 4-way scrolling, I went ahead and stuck with either a column or row layout for "meta metatiles", since I knew that I was going to have to deal with them as both rows and columns, it seemed to make sense to me to create a data structure that benefited inputting in at least one direction. Then inside of there I was just using 16x16 metatiles, which surely isn't the most space efficient.

I don't want to overload myself on this and do some crazy compression system or something and get off track, but it would be nice to come up with a clean and relatively fast solution that's easy to manage as things go on. I've got to think about the tiles and attributes that make up the screens in addition to the larger segments that make up the map. It would be nice if the scrolling segments could be somewhat arbitrarily sized and shaped, so maybe a map section will scroll over and up in an "L" pattern instead of just being a square.

Any thoughts?

Thank you!

Speaking strictly from a level design perspective, i find the way metroid does it the most versatile i've tried. It's user friendly and lean on data at the same time (well, depending on how you actually end up using it). Because of its free placement feature, you can conserve lots of room/map data wherever there is blank space or using one or a few big template structure(s) for general background scenery.

-Each area has a shared array of background structures
-Each room consists of a list of structure instances that can vary in amount from a few to a lot. Actually, the total space of the list is shared too. You have total budget to spend.
--This means that the order of the list decides the drawing order. You can get LOTS of variation out of the same structures by ordering them differently and letting them overlap a bit.
-Each structure is of arbitrary x and y size.
-Each structure within a room can be freely offset placed on a 16 pixel grid.
--This is great for conserving space and build levels efficiently at the same time. Ideally you want each room to consist of one or a few big "boiler plate" backgrounds, which you then detail with a bunch of smaller structures
-I *think* there's an array that lists the number of structure instances for each room, so the game knows where to start and stop reading structures.
-Where there is no structure present, just assume tile 00 (blank; no/air property).
-One tile in the set is "see through" blank (ie underlying structures show through here there is overlap), and another is "opaque blank", ie it will overwrite with blanks. The see-through will still superimpose its palette property on underlying structures if is ordered above something else, which is super useful (and underfacilitated in the game).

Collision properties are decided on a per tile level, according to a somewhat limiting "this range is this, that range is that" scheme. One tile is dedicated to "see through" air.
Palette properties are decided for each 2x2 tile on the structure level. The top layered structure gets dibs on calling attributes, like i mentioned above.

Metroid assumes a rather restrictive use of palettes though, which make rooms monotonous. Because it only had 128kB:s and still tried making a large world, rooms are more sparsely populated than could be. Also, it is reusing the same room ID:s plenty of times all over the map, but with different object lists layered on top. This is part of why metroid is so hard to navigate. There's a lot metroids' level format can do, which the game itself doesn't do.

For example, when metroid looks up what room to draw, it looks at both the room ID (0-255) with the area ID. That means that even though they never did so, rooms from different areas could overlap/intersect like they had different z depths, to create more complex maps and traceback shortcuts. Collision can be on an 8x8px grid, which is ever only used on the chozo statues in the original game.

You can try it on for size using snarfblams' editroid and a copy of metroid.


Project Blue, which i'm currently designing rooms for, has a different structure:

up to 64 rooms per area.
each area has:
256 tiles (including text/hud)
256 2x2 tile metas
1024 2x2(2x2) tile metas
-fixed 4x4 grid positions for the 2x2(2x2):s in each room.

---
physics properties on a per tile level. property bits can be combined (unlike metroid), which really helped me be dynamic with later areas. Remove the solid property from a "conveyor belt" tile and suddenly you have a water stream that transports you if you're in it.
palettes decided on the 2x2(2x2) meta level.
inWater bounding boxes are set with x/y 0-255 position coordinates.

it is not scrolling.

I've grown better at using this scheme, but let's just say you spend lots of data (and time) on making near-duplicates with offset positions or variant aesthetics/physics.


====
Edit: What i wanted to propose with the metroid scheme is.. i don't have a solid enough understanding of computer science to know for sure, but i have a feeling that it might be beneficial to scroll seam updates that if no "background structure" is present, just hand the nametables a length of #0:s until next structure comes in the way.

I've never regretted a simple array of 16x16 metatiles and you shouldn't either. Other formats sacrifice quality, developer time, and performance. To me, these are 1000x more important cartridge size.

But regardless, 512K cartridges are really, really cheap. You can fit a Gimmick-sized game in 512K using 16x16 metatiles.


You don't need compression or special formats to do this. Store your levels as rectangles and waste space. Restrict the camera to certain positions to create the shapes you want.

Agreed. But also factor in the time it takes to make levels for a full feature game.

Coming up with a level storage scheme is (hopefully) a one-time exercise, maybe with some adjustments as needs arise. Levels, you do over and over and over. I think the level format choice is the scariest of all, because i find it's really hard to predict what will prove a smart choice in the end if the overall game design isn't clear and fixed. Your level designing toolset is also going to be important.

If your base is 2x2, you might still be well off coming up with a tool that allows you to clonestamp structures into that array of 2x2 meta references, to speed things up. I think that'd be pretty ideal.

+1 to this. Stack a simple compression algorithm (RLE or LZ) on top if you really want to and you're golden.

In their defence, SMB3/Metroid style object-based maps like FrankenGraphics suggested are small and intuitive enough to type into an ASM file manually, no special tools (except a previewer, otherwise known as the game engine itself) required. Tile maps are far too big and fiddly for that, and tile editors are harder to come by than text editors, so you've either got to write one, find and put up with/pay for/emulate an existing one or write a BMP-to-map converter of some kind so the map designer can use an image editor instead.

There's plenty of trade-offs involved, but basically, you need a map editor either way. One ends up in the game and shrinks your maps for you, the other distracts your programmer from working on the game at all. As a programmer myself, I know which one I'd choose, if my level designer will let me get away with it.

Thanks for the suggestions, guys!

It's all been helpful. Here's what I've decided on so far.

I definitely want to have a lot of destructible/modifiable terrain in this one, plus WRAM, so loading the maps into RAM seems like the way to go. At this point, I think 16x16 seems like the most sensible size. 16x16 is the perfect granularity for collision tiles, and seems like the fastest way to go for scrolling without getting nuts and decompressing to individual tiles.

This lets me put off the way my maps will be stored without being decompressed until later, and focus on the game for now. I think the object-based idea is intriguing. If nothing else, I'll probably consider making something to procedurally generate simple rooms to save some time in testing a rough layout.

What I'm working on now is creating a map system that will scroll between arbitrary screen arrangements regardless of their memory addresses. It seems like for that, I need to keep a list of the X and Y position high bytes for my loaded screens, and verify my position is on the list every time the camera scrolls. Should work!

For my project each area is allowed 9 screens which are 16x14 metatiles in size. Metatiles are 2x2 tiles in size. I decompress the entire metatile map to ram, and update the row pointers that are also in ram to reflect the arrangement of the 9 screens. The metatile definitions are also in ram to allow each area to modify them after the base set has been loaded. They can be modified on the fly in response to the player or other triggers placed on the map. Keeping all this in ram is mostly for performance and convenience.

Each area has a hard transition to another area, and a table of what I call connections. Each screen in an area that has an edge that does not touch another screen in the same area has a connection that tells what area it should transition the player to, and if the player X and Y position needs to be set to an absolute value or have a signed value added to them. The signed part is so that areas don't have to line up in a grid and you can have weird shapes like this:



Area 1 has 2 screens arranged 1x2
Area 2 has 6 screens arranged 2x3, with 2 being marked as "non-existent" for the camera
Area 3 has 4 screens arranged 2x2

Even though there is the concept of screens, each map is stored as one area of whatever height and width in metatiles. So area #1 is 16x28, #2 is 32x42, and #3 is 32x28. I do lose some bytes compressing those "non-existent" areas, but it pretty minimal.

I've made a lot of progress and ran into an unexpected snag. I got tiles scrolling in all directions before I started making some changes.

I decided to stick with the arbitrarily shaped maps. I think that might give me some interesting ideas on how to structure areas. It may take a little extra work to make the screen easily scroll into T shaped offshoots, but nothing that should be too awful.

The part that is tripping me up currently is the addition of the scroll bar and how this effects the map layout. At first, I had a map with 16x15 metatiles buffered, which perfectly matches the screen size. This was great, because scroll position, map position, and nametable position were all intrinsically linked. Now, with a scroll bar, I'm testing out screens that are 16x12, and so I'm forced with a choice. Either condense the vertical height into normal, 256 byte pages, or make the pages 192 byes in length, and also buffer attributes into the extra space. 256-byte maps would conveniently equal exactly three pages of data for four gameplay screens, so it would fit nicely in that regard. But calculations will become more time-consuming when converting to this map.

I feel like the ultimate deciding factor for me will be how slow it is to update attributes without having them pre-buffered. If it's really slow, then it might be worthwhile to pre-buffer them so I can use more of the frame for gameplay action. Then again, it's a lot of space, and it's going to be impossible for me to judge how import that is to this project until I get much further.

I think the thing that slows me down the most is when I have to make a call and I know that I don't have enough information yet to know what's really going to be best.

I think I did something pretty similar to yours. Mine is 4x4 screens though, which effectively takes up about half of the WRAM, but I don't have a clue yet if there is anything else I'll need large chunks WRAM for, so I can address that later if necessary.

I spent a little while coming up with a manner of limiting the scroll and what I ended up deciding on was to essentially build a 4x4 collision map that indicates whether or not a screen is present in this section.

I'm a little curious what you mean about the row pointers. You mean that you keep your row pointers in RAM loaded with the address to read the need row? I've always treated these as temporary variables and started from scratch each time. Every time that I scroll, I've got to recalculate the position using my new scroll, so I didn't see any reason to save it. Do you really save time by keeping your row pointer? Maybe I'm misunderstanding.

So let's say the tilemap is at $6000 and the row pointer table (which is split lsb/msb) is at $7000 / $7100.

If a map is 16 metatiles wide (1 screen), then the pointers to the start of each row would be $6010, $6020, $6030, $6040, ... and so on
If a map is 48 metatiles wide (3 screens): $6030, $6060, $6090, $60C0, ...
Or some non-multiple of 16, like 26: $601A, $6034, $604E, $6068, $6082, ...

I can then read or write to the tilemap with a simple:



They are used for scrolling, collision checks, enemy ai, "events", and environmental destruction. For me, it added up to quite a bit of savings to be able to have random access to anywhere in the tilemap without having to use adds or shifts to seek around. You still have to calculate row_num and col_num, but I have that down to:




Which re-uses a table I have for fast multiply by 16.