Indexing information across banks.

I'm using a cool little technique to deal with information spread across 32 banks. I'm not sure how common it is, or what other solutions you guys have for the problem, but I thought I'd bring it up here so we can get a discussion going. I'd love to hear about what techniques you guys have for this. Here's how I deal with it:

Bank 0 contains lists (of various things) of 3 byte entries that specify the bank, the low byte of the address, and the high byte of the address. So for example, there is a list of maps that specifies what bank and what address each map occupies. To load a map by number, I just multiply the map number I want by 3, and then grab the bank number and address. I can then switch to the bank and get to work immediately. I feel it's a bit like having a directory structure in a classic operating system, only more primitive of course.

What systems do you guys use to deal with information spread across banks?

I'd probably break this up into 3 individual tables, one for the bank numbers, one for the low, and one for the high bytes of each address, because this way you don't need to multiply anything. It might be a bit more difficult to maintain it this way because you have 3 tables, but you're putting slightly less strain on the system itself. It is debatable which one is worth doing, and probably depends on the situation.

Write a simple command line application to create the three lists from a txt file and you are done. I've done that in one of my engines (for another system, though). The application even packs and fits the binaries into "big files" to be stored directly on memory pages, and keeps track of where every binary is calculating the offset automaticly based on its size, so you don't even have to know where they are placed (within some limits, of course).

Modern day dev chains allow for a lot of pre-calculation to be performed offline during compile time at ease. Adding, rearranging or removing binaries is a matter of doing so in the list of assets, and a custom tool should be doing all the dirty work transparently.

In my case, that was mandatory, as the assets we were dealing with were compressed binaries. You change a metatile in a level, the size changes. Developing such a game without a tool to pack and stuff, and create the indexes for everything automaticly would have been like hell.

Even if you arrange stuff manually, a tool to create three different lists from the list you are using would be a breeze to write and would make your life, and the engine's, easier.

You can also create split tables directly in the assembler, like this:

lowtable: .db <addr0,<addr1,<addr2
hightable: .db >addr0,>addr1,>addr2

Though when you have less than 128 entries, doing one ASL to use a combined table isn't much of a penalty. A multiply by 3, if it's not happening multiple times per frame, probably isn't much to worry about it either.

ca65 has .bank and ^ operators, I've never tried to use them so I don't know if it applies here or not. So far, I've always been entering bank numbers manually. A cleaner solution would be good, I haven't felt much of a need for it though. I don't tend to move stuff around much, and would probably use a defined constant for the bank number if I was.

While I do use takes like these (bank + address) to locate some things, such as level maps and object logic routines, I don't do it for everything, and I certainly don't have all tables reside in a particular bank that would require one extra bank switch just to know what bank actually has to be switched in.

Just to put out some additional options, you can also split your data into two tables, one for the 16-bit pointers, and one for the bank number. You can also burn a byte and have 4-byte entries instead of 3-byte entries (multiplication by 4 is just two ASLs).

Each method has its pros and cons, the 4-byte entry method is the worst unless you can use that 4th byte somehow, but even then you can only have 64 entries before you need extra math to calculate the index to the table. The advantage is that each entry's data is all together in one spot.

The 16-bit pointers table + bank table makes the nicest looking assembly source, since it's just a list of pointers, and then a list of bytes. You need some slight extra code if you want to use more than 128 entries though, but it's nothing horrible; you can just branch on carry after your ASL to load from the second half of the table (table_start + 256) instead of the first.

Splitting each byte into 3 seperate tables is the best option for code efficiency, because you don't need to do any math on the index, and you can have 256 entries with no effort.

I normally use 3 tables. Under normal circumstances, modifying the 3 tables in sync when coding would be a pain in the ass, but with Notepad++'s column mode it's quite simple: If all 3 tables have just 1 entry per line, I can freely edit the labels in the first table and then select all the labels vertically, copy and paste them into the other 2 tables.

Haunted: Halloween '85 uses a similar directory structure to what you describe, except the directory is in the game's main bank (32K bank 15, where 0-11 are graphics data banks), and it stores bank/address pairs for both the map stream and the tile stream.

I too prefer separate table for high/low bytes of address, and bank if needed. I can describe what I have done in Attribute Zone: There are two tables, one for the low byte of the address, and one which stores both the high byte of the address and the bank number; note that these addresses point into CHR ROM, and that mapper 11 is used (the reason being the order of the bits in the bank register). There is also one compile-time constant which is the lowest level number that needs one of the last 8 banks rather than the first 8 banks. This program uses no PRG bankswitching (nor does it use the lockout defeat mechanism), therefore a code can be used like this:

I never thought to break things into three banks to avoid multiplication! That's genius! My data is generated automatically by a custom tool, so it doesn't take any extra work on my end to implement three banks instead of one. Sooo glad I started this thread

Also storing it in the main bank is an excellent idea (not that bank switching is terribly expensive, but still). I use UNROM, so the upper bank is fixed...

It's common practice to take an array of classes and split it up into several arrays, one for each member of the class.

So instead of an array of {A, B, C}, {A, B, C}, ...
You have an array for A, an array for B, and an array for C.

Very useful in general.

Macros/Functions can help you with indexing these data tables from your .incbins. Or you could handle them manually.

So I was considering converting all of my datastructures to use separate arrays for each member when I realized that I think there is one case in which it would be bad to use separate arrays. If the list includes more than 256 items (more items than y or x can represent), then I think it's more efficient to have the data stored sequentially because it would require generating an address for each member rather than generating a single address. Of course, this only applies to very large lists of things, but there are some things I deal with that approach or exceed this limit.

Unless there is some cool way around this that I don't know about (which would be awesome)...

Yes, if you're gonna need pointers, it's generally better to generate a single pointer rather than 2. Unless you're gonna make a lot of accesses using the same pair of pointers before needing to change them, because then the amount of cycles you save from not needing to INY might be more than it takes to setup the second pointer.

Yes, that is a good point. However there is an alternative which might or might not always be suitable, depending on circumstances: If you are only reading the data sequentially and you don't need to enable rendering while loading the data, you can store it in CHR ROM and take advantage of the autoincrement feature of the PPU (this also works if the data to be read consists of records of varying sizes rather than all fixed).