virtual tilesets

How should I handle tilesets larger than the 1024 tiles the NDS hardware is designed to use? Quick maths show that with 16K unique tiles, I'm already consuming 1MB of RAM. Full 16-bit tile identifiers would address the whole 4 MB of RAM the NDS has.

Unlike in Eric's games, I cannot assume here that the RAM is just a cache for the whole game data (ROM) because the game data may only be accessed through the SD card interface, abstracted through DLDI which -- afaik - - does not support asynchronous reads. And the score-table l implemented lately suffered noticeable lag while accessing the filesystem.

So there will be only main memory and video memory. Echoing what happens on x86 CPUs Virtual memory management, I'll use "logical" for the identifiers related to the full tileset and "physical" for the identifiers related to (temporary) video memory locations.The two functions that deal with translation between the two  sets of tiles are linked to the scrolling updates: since the level map is made of logical identifiers, we need logical-to-physical conversion there. The other(new) function kicks out trees that no longer need to be in VRAM.

I haven't really found a use for a physical-to- logical map. And all my plans for a smart combine-bitmaps system to decide which tile to evict fell flat when I realised it would be smaller to just keep an integer counter for every physical tile. So I will avoid over-complicating things and just go for the array of counters.

I know the logical-to-physical map could use a hash table implementation. It would have at most 1k items present, i'd say that means the main table should be at least 2k entries large. One important thing to consider is that we will have to remove items quite often, which means resolving collisions with chained list would work better than by using the next available entry in the table. Especially given that we will likely find consecutive tiles present, for instance when we have a large structure on screen. Good thing is that since there is an upper limit to the amount of items present, we know an extra 1 k entries for the chained list with always be enough.

Now, one entry in such a table is at least 16-bit logical id + 16-bit physical id + 16-bit next pointer. that takes us close to 18kB for the table, while a plain array of physical identifiers indexed by logical id would take at most 32 kB. Granted, the diffeence is critical for SNEs deving, and likely significant for GBA deving. But here? is it really worth the extra memory lookups ? Is it worth doing divisions to get a good hash function? We'll look into that if I ever need more than 8192 unique tiles in a level.