Idea: Animating a huge number of background tiles for "free"

Topics related to the API, programming discussions & questions, coding tips, bugs, etc. should go here.
User avatar
Artcfox
Posts: 1382
Joined: Thu Jun 04, 2015 5:35 pm
Contact:

Idea: Animating a huge number of background tiles for "free"

Post by Artcfox »

So in my quest to reduce the number of cycles that my game currently in progress uses, I've been looking for creative ways, before resorting to reducing the vertical resolution.

Here is what I came up with, though obviously this will only work with games that don't use a lot of tiles, because every non-animated tile will need to be duplicated as many times as you have frames in your background animations, but it will let you animate up to 840 tiles in video mode 3 essentially for "free" (trading flash space for cycles).

Say your tileset looks like this:

Code: Select all

A1, A2, A3, S1, S2, S3, S4, S5, S6
where A1-3 are frames of an animated background tile (say treasure), and S1-6 are static tiles. You don't want to be looping over the entire set of treasures every frame to change their tiles to animate them, because that will take a lot of time, especially if you're in a bonus level where the entire screen is filled with animated cookies (or you have a level where you have 50 different tiles that all need to have different animations, with the restriction that they all have the same number of frames in their animation).

My thought was to split that tileset up into 3 tilesets which duplicate all of the static tiles:

Code: Select all

tileset1 = { A1, S1, S2, S3, S4, S5, S6 }
tileset2 = { A2, S1, S2, S3, S4, S5, S6 }
tileset3 = { A3, S1, S2, S3, S4, S5, S6 }
And then in your code, any time you want to animate all of the animated background tiles, just call:

Code: Select all

SetTileTable()
with the next tileset.

As a quick and dirty proof of concept, since I have 15 different treasure types (in reality they are all the same treasure, but overlaid on 15 different background tiles) that each have 3 frames of animation, and all of those tiles are next to each other in my tileset, I commented out my treasure animating code, and dropped the following chunk of code into my main loop.

Code: Select all

#define TREASURE_FRAME_SKIP 16
#define UNIQUE_TREASURE_TILES_IN_ANIMATION 3

    for (;;) { // main loop
      WaitVsync(1);

      static uint8_t tileCounter = 0;
      static uint8_t treasureFrameCounter = 0;
      if ((treasureFrameCounter % TREASURE_FRAME_SKIP) == 0) {
        SetTileTable(tileset + 64 * tileCounter++);
        if (tileCounter > UNIQUE_TREASURE_TILES_IN_ANIMATION)
          tileCounter = 0;
      }
      if (++treasureFrameCounter == TREASURE_FRAME_SKIP * UNIQUE_TREASURE_TILES_IN_ANIMATION)
        treasureFrameCounter = 0;

      // rest of main loop code...
    }
Since I'm only advancing the tileset by one tile every 16 frames, all of the non-animated tiles go completely crazy, but as far as a proof of concept goes, it is showing me that indeed all of my unique treasure tiles are being animated correctly when they are supposed to. If I actually wanted to use this technique, I'd have to duplicate all of my non-animated tiles, and advance the tileset pointer by 64 * TOTAL_NUMBER_OF_TILES / ANIMATION_FRAMES, which in the above example would be 64 * 7 (A1, S1, S2, S3, S4, S5, S6).

All of the collision testing and other code works without any modifications, because the absolute tile numbers are still the same, the only downside that I can see is that you have to duplicate all of your non-animated tiles, but I currently only have 24 non-animated tiles versus 15 x 3-frame animated tiles. So I would end up duplicating those 24 tiles 3 times for a total tile count of (15 + 24) * 3 tiles used, which is only 117 total, which still leaves me with plenty of room to expand.

The only problem I forsee is gconvert removing the duplicates, so I'd probably have to make each one into a separate tileset, and switch among the tilesets, rather than using offsets within a single tileset, which should actually leave me with even more free tile indicies than before, since at any given point in time, the window of 256 tiles in the tileset only includes 1 frame of every animation, rather than all of them.

Thoughts? Is this really a win-win: no wasted cycles animating background tiles; freeing up extra tile indices because each new tileset only contains a single animation frame of every animated tile, with the only downside being extra flash space consumed because you are now storing multiple tilesets that contain duplicates?
User avatar
uze6666
Site Admin
Posts: 4801
Joined: Tue Aug 12, 2008 9:13 pm
Location: Montreal, Canada
Contact:

Re: Idea: Animating a huge number of background tiles for "free"

Post by uze6666 »

If you are ready to live with lots of waste for non animated tiles, then yes it's a clever trick never mentioned. :) In fact, you can have a single tile set:

Code: Select all

const u8 tiles PROGMEM={A1,A2,A3,S1,S1,S1,S2,S2,S2,S3,...}
And just add an offset in SetTileTable() with something like

Code: Select all

SetTileTable(tiles+(animation_frame_var*64));
It should be possible to add a parameter in Gconvert to keep duplicate tiles. It's been asked a couple time, so we can add it. I've opened an enhancement request on github: https://github.com/Uzebox/uzebox/issues/24

Alternatively, if you have some free, ramtiles can also be used for background tiles. Just needs to blit the ramtiles with the next animation tile each frame and all instances on screen are updated "for free". Lee has lots of experience with this.
User avatar
Artcfox
Posts: 1382
Joined: Thu Jun 04, 2015 5:35 pm
Contact:

Re: Idea: Animating a huge number of background tiles for "free"

Post by Artcfox »

Is placing the SetTileTable() call directly after the WaitVsync(1) call the correct place for swapping the tileset, or do you think it belongs in a UserPostVsyncCallback()?

Code: Select all

//main()..
   SetUserPostVsyncCallback(&VsyncCallBack);
//..
}

void VsyncCallBack(){
   global_frame++;
   SetTileTable(tiles+(animation_frame_var*64*TOTAL_TILES/ANIMATION_FRAMES));
}
I see what you're saying, but if you do it that way, then the 256 tile "window" of tiles you can choose from includes all the duplicates, and the animations that won't be shown, but if you change the organization around a bit, then the 256 tile "window" won't include any duplicates, and you'll have more free tile indices to use for content.

If you make all static tiles contiguous with each frame of an animation tile:

Code: Select all

// Tile 0 is an animated tile, AA1 is the first frame, AA2 the second, AA3 is the third.
// Tile 1 is also an animated tile, AB1 its first frame, AB2 the second, AB3 the third
// Tiles 2, 3, 4 are static tiles: SA1, SB1, SC1,...

const u8 tiles PROGMEM={AA1,AB1,SA1,SB1,SC1,...,AA2,AB2,SA1,SB1,SC1,...,AA3,AB3,SA1,SB1,SC1,...}
Then the offset would be:

Code: Select all

SetTileTable(tiles+(animation_frame_var*64*TOTAL_TILES/ANIMATION_FRAMES));
I guess an easier way to think about it might be to say that all tiles become animated tiles, it's just that some (the static tiles) have each animation frame set to the same bitmap, and by moving the window in large non-overlapping steps, it doesn't encompass any of the previous group of duplicate tiles, so you aren't losing any tile indices due to duplicates. The only thing you're losing is flash space, but you're gaining the ability to potentially animate every single tile, every single frame in O(1) time.

Edit: Made variable names consistent.
User avatar
uze6666
Site Admin
Posts: 4801
Joined: Tue Aug 12, 2008 9:13 pm
Location: Montreal, Canada
Contact:

Re: Idea: Animating a huge number of background tiles for "free"

Post by uze6666 »

Is placing the SetTileTable() call directly after the WaitVsync(1) call the correct place for swapping the tileset, or do you think it belongs in a UserPostVsyncCallback()?
It's pretty equivalent since right after the code in UserPostVsyncCallback() is executed, the vsync interrupt would resumes in your WaitVsync(1) call. If using UserPostVsyncCallback() and your main loop takes lots of CPU spanning more than available in a frame, it will get interrupted before you reach WaitVsync(1). It will render with whatever the state of vram at that point so it may display only half of what is expected for that frame (kinda like shearing). Using WaitVsync(1) in this case is like a FlipPage() in
a double buffer.
I see what you're saying, but if you do it that way, then the 256 tile "window" of tiles you can choose from includes all the duplicates, and the animations that won't be shown, but if you change the organization around a bit, then the 256 tile "window" won't include any duplicates, and you'll have more free tile indices to use for content.
Good points, I just threw whatever I had on my mind during lunch, so not much time to think about it. Your approach is the way to go. :)
User avatar
Artcfox
Posts: 1382
Joined: Thu Jun 04, 2015 5:35 pm
Contact:

Re: Idea: Animating a huge number of background tiles for "free"

Post by Artcfox »

uze6666 wrote:It's pretty equivalent since right after the code in UserPostVsyncCallback() is executed, the vsync interrupt would resumes in your WaitVsync(1) call. If using UserPostVsyncCallback() and your main loop takes lots of CPU spanning more than available in a frame, it will get interrupted before you reach WaitVsync(1). It will render with whatever the state of vram at that point so it may display only half of what is expected for that frame (kinda like shearing). Using WaitVsync(1) in this case is like a FlipPage() in
a double buffer.
Awesome. That exactly what I was thinking. I just wanted to make sure that I didn't need to do it pre-vsync to avoid the "shearing" effect.
User avatar
uze6666
Site Admin
Posts: 4801
Joined: Tue Aug 12, 2008 9:13 pm
Location: Montreal, Canada
Contact:

Re: Idea: Animating a huge number of background tiles for "free"

Post by uze6666 »

Got to rethink my last answer and it was a bit wrong. If you processing takes more than the available cycles in a frame, your program will get interrupted what ever approach you use. If you are reloading say the whole vram each frame and scrolling, I'm pretty sure you will see shearing. Practically though, you rarely see such artifacts.
User avatar
Artcfox
Posts: 1382
Joined: Thu Jun 04, 2015 5:35 pm
Contact:

Re: Idea: Animating a huge number of background tiles for "free"

Post by Artcfox »

I haven't thought about scrolling yet; still trying to wrap my head around how that works.

In this case I'm not scrolling, and the animation trick doesn't touch VRAM, it's just updating the pointer that tells the kernel which tiles to draw based on the numbers in VRAM. The only problem that I can forsee is that the pointer is a 16-bit value, so if the kernel interrupts me when that's half written, bad things would happen. However, I think I'm pretty safe writing to that pointer as long as I do it immediately after:

Code: Select all

WaitVsync(1);
since that happens immediately after the interrupt fires, so that interrupt is probably not going to fire for quite some time.
User avatar
uze6666
Site Admin
Posts: 4801
Joined: Tue Aug 12, 2008 9:13 pm
Location: Montreal, Canada
Contact:

Re: Idea: Animating a huge number of background tiles for "free"

Post by uze6666 »

The only problem that I can forsee is that the pointer is a 16-bit value, so if the kernel interrupts me when that's half written, bad things would happen. However, I think I'm pretty safe writing to that pointer as long as I do it immediately after:

CODE: SELECT ALL
WaitVsync(1);

since that happens immediately after the interrupt fires, so that interrupt is probably not going to fire for quite some time.
Ah yes, in this case, you are right. Updating just the tile table pointer will render the whole image in a clean way.
User avatar
D3thAdd3r
Posts: 3222
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Idea: Animating a huge number of background tiles for "free"

Post by D3thAdd3r »

I meant to comment before, it's a nice trick for special cases. Cycle and indice wise, it scales better than the ram tiles approach, obviously that flash consumption can sky rocket with only small additions or extra frames. If your game fits the niche there doesn't seem to be anything possible that's more efficient than a 16bit write for updating mass tiles, certainly faster than copying to 10+ ram tiles on a tall screen!

Looking forward to seeing this creation of yours, keep at it.
User avatar
Artcfox
Posts: 1382
Joined: Thu Jun 04, 2015 5:35 pm
Contact:

Re: Idea: Animating a huge number of background tiles for "free"

Post by Artcfox »

I finally got around to refactoring things and actually implemented this technique for real, and it works amazingly well!

More surprisingly, it unlocked a huge number of other code optimizations, which I hadn't been able to take advantage of before. Large chunks of code just vanished, and the duplicate tiles don't actually take up as much flash rom as I had feared. One space optimization that I haven't taken advantage of yet is now that I no longer have to iterate over all of the animated tiles every X frames, I no longer need to store them in flash as fast lookup tables. Since I only need their coordinates once when initially drawing the level, they can be compressed, saving me huge amounts of flash space.

Also, it means that every tile is now animated, so I should be able to do some pretty cool effects.
Post Reply