I decided to take a little break off my map editor and trying to test the raw data that I can produce in it's current stage.
Let's say I want to make a side scroller that scroll from left to right. My map data is based on metatile (2x2) that contains metatiles (2x2). My default export option is the data is exported from left to right in a one dimension array. This mean if you want to find the location of metatile N, you have to do (Y * WidthOfMap) + X. This is propably what I would do something on PC but for some reason, I have doubts if its the right way for the nes.
The reason for that doubt is because the NES can allow to write tiles from Top to bottom. But.. If I was dealing only with tiles, that's what would make the most sense since I would add one line of extra tiles on the right/left when the character is scrolling but with meta-metatiles.. hmm...
So the question is how do people would store their map data for a side scroller and what advantage/issues to do it that way. I may try both way but for now I cannot see the pitfall of doing one way or the other because of my lack of experience on the nes yet.
The docs on romhacking.net make interesting reading if you're looking for architecture ideas.
Blaster Master stores its levels as a 32x32 grid of 64x64 pixel "blocks", which are 2x2 metatiles of 2x2 metatiles of 2x2 metatiles of 8x8 pixel tiles.
A Sonic the Hedgehog 2 level is a 256xn grid of 128x128 pixel quarter-screens, which are 8x8 metatiles of 2x2 metatiles of 8x8 pixel tiles.
Maps in the Super Mario Bros. games are stored as a list of objects on each screen, and decoding involves finding which objects intersect each 16-pixel column.
The Zelda 1 overworld is made of 16x8 screens, each made of 16x176 pixel "columns".
The most professional games usually have a few depths of indirection between the level map and the metatiles. Many not-so-professional games place 16x16-pixel metatiles directly in the level map.
Sonic games on the SMS/GG place the metatiles directly in the level map (which is decompressed to RAM and limited to 4096 bytes, IIRC), but the metatiles are 32x32 pixels large, so the levels are not so small.
Still, most games with large levels will have more depths of compression. I believe the Mega Man games (NES and SNES) encodes individual screens (256x256-pixel blocks) and places those in the level map. Sonic 1 on the MD/GEN does the same (but like tepples said, from Sonic 2 on they switched to 128x128-pixel blocks). Each 256x256-pixel (or 128x128, from Sonic 2 on) block is composed by 16x16-pixel metatiles.
Personally, I adopted this idea of placing 256x256-pixel blocks in the level map. But each of them is composed by 4 128x128-pixel blocks, wich are composed by 4 64x64-pixel blocks, which are composed by 4 32x32-pixel blocks, which are finally composed by 4 16x16-pixel blocks (the so called metatile). But that's because I plan on having quite large levels while trying to save as much ROM and RAM as possible. This can still be decompressed on the fly (no need for large RAM buffers) without much impact on performance.
For a side-scroller, I'd probably use a column-based compression scheme. The level map could index columns, and they would actually be stored somewhere else in compressed form (RLE would probably work well). To decompress this level I would use the X coordinate as an index into the level map (which is just a 1-D array of columns), and then decompress the whole column. The ability to reuse columns would probably result in great compression. Just look at any side-scroller and you'll see many areas that repeat.
If you can use ram to store levels, use LZ77 (history compression) or LZ78 (dictionary compression). If it's good enough for Zelda Oracle of Ages, it's good enough for you.
LZ78 is better if you're more memory constrained.
Of course, this completely depends on what your levels look like. If there are frequently appearing sequences of tiles across multiple maps, LZ78 is the one to pick.
I actually came up with a format for my side scroller (only scrolls side to side, not vertically) that is flexible, yet still saves some space. It is actually an idea derived from an idea derived from Tokumaru's suggested method. My original idea was to compose levels of columns which contain different 64x64 pixel tiles (256 to choose from), which were made of 32x32 pixel ones (256 to choose from), which were made of 16x16 pixel tiles (256 to choose from). So there were 4 columns per screen, 4 64x64 tiles per column (16 tiles per screen) However, in an NROM game with 8 levels, I allowed myself to choose from 256 for the entire game. This wasn't flexible enough at all, as each level would be repetitive looking, and each level is supposed to be very different. Also, my screens were only 26 tiles tall, as there is a 4 tile tall status bar, so only 2 tiles of the last defined 8x8 metatile in each column were displayed (huge waste).
So I came up with another format that was more flexible, though it takes up a bit more space. Composing levels of 4x4 tiles (32x32 pixels) was still not flexible enough, and wasn't very efficient, as it still wasted tiles that wouldn't be displayed on bottom. So my newest format actually composes levels of 8x2 (64x16 pixel) tiles, for which the attribute data can be defined with one byte as they are made of 4 2x2 (16x16 pixel) metatiles. Since there are 26 tiles of map data displayed in each column, this works out well, not wasting any bytes as there are 13 8x2 tiles in each column, 4 columns per screen (52 bytes per screen). Though it's a bit more space-consuming, it allows me to create very flexible levels, and it's easier to decode.
Also, my levels are stored in an "interleaved" format, as Tokumaru would say. Each row of metatiles for level 1 is stored seperately. So all one has to do is find which row of metatiles they are in (with the Y coordinate), and then find which column they are in (with the X coordinate) and use that as an index for the row of metatiles array.
Thanks everyone for the suggested way of doing it. This is not what I was expecting (i.e. I was not expecting to talk already about compression) but they are all interesting answers.
One thing for sure is this is telling me, again, that it will be hard to make a generic editor like I wanted to. The only way to avoid the issue on how to format the data will be to either have a plug-able architecture for the export function and use the right plug-in for the data format required or to export generic data that can be parsed later in the desired format.
Since for my first game I want to make a simple side scroller for learning how to approach the nes (I like to make things complicated I guess), a column based approach seems appropriate. I was surprised to see that answer because the first side scroller I made/tried long time ago under dos (hmm, around 1994, when I didn't know much about programming), was using a "stripe based" approach. I would draw a level in deluxe paint, divide it in multiple vertical stripes and make the map out of those stripes. I would re-use the stripes often since the stage was very generic. There was no compression, the data was completely raw. Today I would never do it that way but that was an indirect way to compress things.
If people have other format, I will be more than happy to hear about them. The more format you can see, the more it helps to learn the different ways for solving this data structure problem.
<walloftext>
I always thought it would be pretty tough to make a generic map editor, because of all the different formats people use for their level maps. But I've been thinking and it might be possible to do it (or at least get closer to).
Maybe the editor could have multiple blocksets available, and provide the option to specify if a blockset is based on another one. That way you could have unlimited levels of indirection, as many as the user desires.
For example, the user would first have to load the pattern and palette data. The user would then be prompted for the width and height (in tiles) of the blocks in the first blockset. This will usually be 2x2, but just let the users pick what they want. Even 1x1 should be valid, if they decide to have single tiles as the basic building blocks.
It should be possible for the user to add other information about each block in the blockset, so you should allow for him to add fields of data. The user could for example add a "type" field and a "height map" field.
Now there's another important step: The editor doesn't know what palette to use for the blocks yet, so there must be a setting somewhere to specify this. Palettes can't come from multiple places, so this is a single setting no matter how many blocksets are there. The user has to pick one blockset that contains the palette information (note that it should be possible to define the palette bits in any blockset, not necessarily the first), and specify which bits from it's fields affect which tiles. Now, attributes are tough. If the user decides to apply different palettes to single tiles, you'll have to assume he is making something for the MMC5 and let it be. Or you'd have the user pick the attribute resolution beforehand, 1x1 or 2x2. Anyway, this is just so that the colors show up right, the user is the one that will make the 6502 code.
Anyway, after the first blockset is ready, it should be possible to place the blocks in the level map. Once you placed tiles, it's a bit hard to add new blocksets, because the level map contains references only to the last type. If the user tries to add a new blockset, you can provide the options to clear the level map or to automatically convert it, creating as many of the new blocks as necessary to accommodate the old layout.
Whenever you create a blockset, you can define on what blockset it's based on (this could default to the one created before this one). In fact, the level map itself could just be treated like another block in it's own blockset (or an objectset, read below).
The interface could have two sets of tabs, one for source and one for destination. Source is where you pick your blocks from, and destination is where you'll place them. It's possible to select all but the largest blockset as source, and it's only possible to pick as destination blocksets larger than the current source. Automatic intermediary block generation is used when blocks smaller than the ones that make the one being edited are used.
Everything I said so far works for grid-based maps. However, there's another fairly common level format that's based on objects. For those to work as well, the user should be able to pick if his map is grid-based or coordinate-based. In coordinate-based maps are just lists of positions and ID of blocks/objects, that can be placed anywhere (aligned only to the dimensions of the first blockset).
I imagined you could have 2 types of sets. All items of the blockset have the same dimensions, while the items of an objectset would each have their own dimensions. This even makes the objectsets candidates for holding groups of level maps. I don't know if it should be possible to build objects from other objects or if they should only be built with blocks. Well, at lest the level map (which is an object) has to accept objects if it's set as coordinate-based.
OK, so far I've talked about editing, there is still the big problem of saving, as everyone wants their data arranged in a certain way. I'd say each set (block or object) should be saved to a different file and this is set by the user when configuring each set. It should also be possible to select interleaved and non-interleaved per set. You should also offer a padding option, in case a person plans on having a certain number of blocks and requires the file to occupy the full size but doesn't have them all yet. Only blocksets can be padded, objectsets can't because theirs size varies. Oh, you should also allow blocks to be column-oriented or row-oriented (this affects the order in which the sub-blocks are saved, should only matter when the data is not interleaved).
If you are feeling generous, you could implement a few compression options, so that users can select different compressions for each blockset/objectset. You'd then have to document the compressed format very well, and preferably provide decompression routines in assembly.
Since each blockset/objectset goes to their own file, the user can just have your editor output directly to their source folders, where the binary files are incbin'ed to their projects. After editing something, it's just a matter of saving the files from the editor (a single click should do it) and reassembling the project to see it in action.
OK, now I'm done. If you liked any of the ideas in this post, I'd be glad to discuss them further.
</walloftext>
That was quite an answer
In the points you mentioned, my editor do some of them like objects out of objects (I call this a metatile set). When you create a new set, you are offered a list of existing set to use as building blocks for the new ones. There is no limitation on size or how many level lower you can go (metatile out of metatile).
Every set can have their own palettes and the derived one can overide the parent one. For attributes, that part of code is not made yet and still in planning phase (so is coloring).
Many of the points your mentioned are in my task list. You brought many interesting ones too. One of the biggest issue when developing a software of this kind is when you don't know clearly it's scope: I cannot write down the specs if I'm not sure how I will use it yet and what it will produce in the end. But it make quite an interesting challenge, if you can find the time to work on it.
I could always show it someday, it just that I consider it still in an alpha phase and not ready for production use (I'm quite picky on that). Too many things are missing for the editing like state of document for undo, more error handling, memory management issues etc. One thing I learned is that it's hard to make a user friendly interface. I had to change it often and I still doesn't like it completely. The other thing that maybe people will not like (maybe) is the fact it was done in dot net.
If there is some interest I can always show some version someday, as long people recognize that it only a very early alpha.
I figured I'd toss my hat into the ring.
MapEd. The editor spits out raw files that are ready to be incbin'ed into a source.
Metatiles are 4x4 tiles, screens are 8x8 metatiles. Maps max out at 8x8 screens.
There is a basic tile attribute (not palette attribute) editor that allows you to assign a value ($0-$F) to a 2x2 subtile. Its up to the game engine to interpret what it means. In the picture, they are used as movement penalties.
Banshaku: I belive I sent you an early version of this app. I went back and redid most of the file handling part because it was a mess. It was difficult to mix and match chr files, metatile sets, palettes, etc.
never-obsolete wrote:
I belive I sent you an early version of this app. I went back and redid most of the file handling part because it was a mess. It was difficult to mix and match chr files, metatile sets, palettes, etc.
Yes you did and I do remember it. I still have it. I can see that is changed a lot. I will try the latest version to see how it changed. One thing for sure, try to document the data format since it will be useful for your future users
Maybe I should post a few screen shots of my current alpha so people could give me their feedback too.
Sorry for the double post. Here's the screen shots in it's current stage.
My goal is to make an editor with have a look similar to Visual studio. This mean you will have more than one project type possible and can work on more than one project at the same time in a solution. In it's current state, you can only make map collections:
Once you set the basic information about your project/solution, a wizard will help you create the project:
I made my editor with tab so you can decide how to put the windows any way you want. If you have a widescreen, you may want to do something like this:
If you don't, or don't like it to be to big, you can opt for a more minimalist way:
You can hide the project explorer and all the panels if you don't like them at all.
This is the editor I want to make. It's a pain since there is so many state/options to make but I hope I can finish it someday and add the extra projects type too (sprite editor, raw name table editor, etc).
One comment I read on the board is about the file format. All project files format are in XML. So if for some reason the exporter doesn't do the job, you still have access to the data.
If someday it get stable enough, I may release it. For now, it's mostly a project that I experiment adding all the options I would like in my editor.
edit:
Forgot to say, for the metatile, you decide any size you want. If you feel that 13x1 tile is what you want then you can do it. And if you decide to make a 4x5 metatile out of this metatile format (13x1) it will allow it too.
In developing the section at the moment so you can define a template of attributes (1 to N) for a metatile set. Once defined, you can set the appropriate flags on every metatile based on the template for that set. I'm still in the thinking phase on how to make a screen flexible enough to edit this information.
never-obsolete wrote:
I figured I'd toss my hat into the ring.
MapEd. The editor spits out raw files that are ready to be incbin'ed into a source.
Metatiles are 4x4 tiles, screens are 8x8 metatiles. Maps max out at 8x8 screens.
There is a basic tile attribute (not palette attribute) editor that allows you to assign a value ($0-$F) to a 2x2 subtile. Its up to the game engine to interpret what it means. In the picture, they are used as movement penalties.
(Pics of a seriously useful utility)
Great job on the Map editor, Never-Obsolete!
Though there is one of the things that I need before I use this: Support for 2x2 tiles (16x16 pixel metatiles), I would really appreciate it if that was the default metatile size!
Hamtaro126 wrote:
I would really appreciate it if that was the default metatile size!
What Banshaku is trying to achieve here is an editor where you can define the size of your metatiles, and even use metatiles within metatiles (like is done on many commercial games with large maps), as deep as you'd like.
As long as people keep hardcoding the format of the generated levels, they will not be generic enough for general use. The only thing Banshaku could do better is not limit the editor for NES use. I believe this could be done by allowing other formats for patterns (besides CHR) and being more flexible when handling palettes. Then it will be generic enough to be a big hit in the homebrew/hacking scene.