gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Graphics > optimizing sprite sizes

#45168 - SmileyDude - Wed Jun 08, 2005 5:24 am

hello,

I'm playing around with some larger images implemented using sprites on the GBA. I'm currently trying to figure out a way to calculate the optimal sprite sizes to use to cover the entire image. I want to use the least possible amount of OAM entries for each image, and the image can have multiple areas where it is transparent for an whole tile. Being that it's transparent, I really don't want to have it be a part of a sprite.

So, basically, what I am looking for is an algorithm that can take a tilemap, and spit out a set of sprite sized rects (64x64, 64x32, 32x32, 32x16, etc, etc, etc) that are optimally packed into that area while working around the transparent tiles.

As an example, lets say I have the following tilemap:
Code:
+--+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |XX|
+--+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |XX|
+--+--+--+--+--+--+--+--+--+
|  |  |XX|XX|  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+
|  |  |  |XX|  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+


The XX marks the transparent tiles. If I wanted to break these up into OAM entries, I could make a 32x32 chunk that would take up this space:
Code:
+--+--+--+--+--+--+--+--+--+
|  |  |  |  |OO|OO|OO|OO|XX|
+--+--+--+--+--+--+--+--+--+
|  |  |  |  |OO|OO|OO|OO|XX|
+--+--+--+--+--+--+--+--+--+
|  |  |XX|XX|OO|OO|OO|OO|  |
+--+--+--+--+--+--+--+--+--+
|  |  |  |XX|OO|OO|OO|OO|  |
+--+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+


Then, I could use a 32x16 chunk:
Code:
+--+--+--+--+--+--+--+--+--+
|AA|AA|AA|AA|OO|OO|OO|OO|XX|
+--+--+--+--+--+--+--+--+--+
|AA|AA|AA|AA|OO|OO|OO|OO|XX|
+--+--+--+--+--+--+--+--+--+
|  |  |XX|XX|OO|OO|OO|OO|  |
+--+--+--+--+--+--+--+--+--+
|  |  |  |XX|OO|OO|OO|OO|  |
+--+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+


and a 16x16 chunk:
Code:
+--+--+--+--+--+--+--+--+--+
|AA|AA|AA|AA|OO|OO|OO|OO|XX|
+--+--+--+--+--+--+--+--+--+
|AA|AA|AA|AA|OO|OO|OO|OO|XX|
+--+--+--+--+--+--+--+--+--+
|BB|BB|XX|XX|OO|OO|OO|OO|  |
+--+--+--+--+--+--+--+--+--+
|BB|BB|  |XX|OO|OO|OO|OO|  |
+--+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+


followed by a 6 8x16/16x8 chunks to fill in the rest:
Code:
+--+--+--+--+--+--+--+--+--+
|AA|AA|AA|AA|OO|OO|OO|OO|XX|
+--+--+--+--+--+--+--+--+--+
|AA|AA|AA|AA|OO|OO|OO|OO|XX|
+--+--+--+--+--+--+--+--+--+
|BB|BB|XX|XX|OO|OO|OO|OO|HH|
+--+--+--+--+--+--+--+--+--+
|BB|BB|DD|XX|OO|OO|OO|OO|HH|
+--+--+--+--+--+--+--+--+--+
|CC|CC|DD|EE|EE|FF|FF|GG|GG|
+--+--+--+--+--+--+--+--+--+


That would use 9 OAM entries to display that entire image. I don't know if that's the most efficient way to set those tiles up in OAM, but it certainly would work. Hopefully, a computer would be able to try other combinations out to find possibly more efficient ways to pack them.

What I am trying to accomplish is that I want to conserver OAM entries, because there will be multiple images on the display at once, and it's possible that I might get really close to the 128 limit. I also want to avoid having to copy transparent tiles into VRAM just to fit them into the sprite for two reasons. One is the overhead in copying an empty tile. The other is to conserve space in VRAM. Otherwise, I would just simply make the sprites 64x64, and make some multiple to cover the entire image. Basically, I want to be able to copy as little as possible from the cart to VRAM when I change the image.

I plan to do this processing when building the program -- not at runtime. The pre-processing would basically build a tileset, and OAM entries ready to load (well, mostly ready -- only minor tweaks at runtime, like different tile numbers to reflect where the tiles actually loaded into VRAM, etc, etc). The runtime would load the tiles required for the image, load the OAM entries, and be done.

I did some google searching on optimal rectangle placement algorithm. There might be something there, but I'm still digging through it. Any suggestions would be appreciated.
_________________
dennis

#45206 - ScottLininger - Wed Jun 08, 2005 5:07 pm

Wow, that's an interesting problem. My first "gut" reaction would be to use a modified A* algorithm. This is usually used for path finding, but the basic idea could probably be used for this problem. You'd start with the top left and "try" all of the possible shapes that could fill the area without overlapping your transparent areas. Your "target end state" would be when the entire image is covered.

The hard part is your "estimated steps until finish" function, but something as simple as the total 8x8 blocks remaining to be covered might suffice. If you've never used A* before, this probably sounds like gibberish. Just do a [url=http://www.google.com/search?hl=en&lr=&q=%22a*%22+algorithm+pathfinding]search on google[/url] and you'll find lots of info.

But before you go down that path, I'm curious why you need to do this. I can't think of a situation where a simple grid of 64x64 or 32x32 sprites wouldn't result in fewer OAM entries. Sure, you're wasting some tiles on those transparent areas, but that seems like a reasonable tradeoff if OAM entries is your key goal, and the code to manage all of your sprites would
be simpler.

Cheers,

-Scott

#45208 - poslundc - Wed Jun 08, 2005 5:27 pm

SmileyDude wrote:
What I am trying to accomplish is that I want to conserver OAM entries, because there will be multiple images on the display at once, and it's possible that I might get really close to the 128 limit.


1. "Really close to" or "go over"? If you're only worried about getting close, then don't. You've got 128 objects, don't be afraid to use them.

2. The sprites you are talking about are really big, and take up a lot of screen real-estate. The 128-object limit is most frequently encountered with much smaller sprites. Don't know what kind of game you are making, but if you find you are really over the 128-object threshhold then odds are you will be able to cull enough of those objects to get under the limit without affecting your display.

3. If you really don't think you can comfortably live within the 128-object limit, consider sprite multiplexing.

Quote:
I also want to avoid having to copy transparent tiles into VRAM just to fit them into the sprite for two reasons. One is the overhead in copying an empty tile. The other is to conserve space in VRAM.


OK. I don't know if the example you gave is typical, but if it is, I'm concerned that you're going to such lengths to optimize away the blank tiles when they consume under 12% of your entire sprite. Unless that 12% of VRAM is mission-critical, I wouldn't bother with it.

Second of all, writing a blank tile is not very time-consuming. If you want to optimize the process, ARM code running in IWRAM could potentially take 8 cycles to set up, and then 18 cycles to output each tile to VRAM. (You have 83,776 cycles in VBlank.) Tile data DMA'ed in directly from the ROM shouldn't be significantly worse.

If you've got any really large, complicated bitmaps, consider using a BG-layer instead, which can be optimized for tile usage.

...

I'm not saying that writing such a utility is a bad idea or even (perhaps) not entirely necessary for your project to function. But consider the alternatives as well.

Dan.

#45210 - SmileyDude - Wed Jun 08, 2005 5:32 pm

ScottLininger wrote:
But before you go down that path, I'm curious why you need to do this. I can't think of a situation where a simple grid of 64x64 or 32x32 sprites wouldn't result in fewer OAM entries. Sure, you're wasting some tiles on those transparent areas, but that seems like a reasonable tradeoff if OAM entries is your key goal, and the code to manage all of your sprites would be simpler.


well, i haven't completely tossed out that idea yet... it may end up being the way to go, in fact. It's not very likely that I'm going to have 1024 sprite tiles loaded up in memory at once -- even with a lot of transparent tiles mixed in. I'm slightly concerned about the wasted effort to actually put the transparent tile into VRAM, but it could just be unnecessary worry on my part.

BTW -- I originally planned to do this as BG layers. But, I really didn't want to limit myself to a single palette of 256 colors. At least with this method, I can use 256 colors (or even 32768, since I could use Mode 3) for the background and another set of colors for the sprites themselves. Hence the usage of sprites in the first place.
_________________
dennis