Reduce video memory consumption by merging animation frames

[Nicolai Hähnle]

The game currently requires a lot of video memory to store all the animation frames of in-game objects.

In many cases, there is a lot of redundancy in those frames. For example. the barbarian headquarters animation has 20 frames, each of size 120x120, adding up to 288000 pixels or slightly more than 1MB of video memory. However, those frames differ only by the fairly small animation of the building's flags.

It could be quite beneficial to extract one base texture plus difference images. In the case of the barbarian headquarters, this could probably get video memory consumption down to about 40000 pixels or around 160kB, an improvement by a factor 6. Admittedly, this particular example is probably one of the cases that would benefit most, but the concept seems worthy of investigation.

Any implementation would have to be as transparent as possible, and should especially avoid putting any additional work on the graphics developers.

Conversion Status:
Yet to be converted: all global animations, plus
 atlantean: armoursmith, baker, bakery, blackroot_farmer, builder, burner, burners_house, carrier, constructionsite, crysatalmine, farmer, fish_breeder, fisher, forester, geologist, goldmine, horse, horse_breeder, hunter, ironmine, mill, miller, miner, flags, sawmill, sawyer, scout, scouts_house, ship, shipwright, shipyard, smelter, smoker, smokery, soldier, spiderbreeder, stonecutter, toolsmith, trainer, weaponsmith, weaver, woodcutter

 barbarian: baker, barrier, blacksmith, brewer, builder, burner, carrier, cattlebreeder, chief-miner, citadel, coalmine, constructionsite, deep_coalmine, deep_goldmine, deep_oremine, deeper_coalmine, deeper_goldmine, deeper_oremine, deer, donjon, farmer, ferner, fisher, flags, fortress, gamekeeper, geologist, gold_mine, granitemine, headquarters_interim, helmsmith, helmsmithy, hunter, innkeeper, lime-burner, lumberjack, lumberjacks_hut, master-blacksmith, master-brewer, master-miner, miner, oremine, ox, flags, port, quarry, ranger, rangers_hut, scout, sentry, ship, shipwright, smelter, soldier, stonemason, stronghold, trainer, trainingscamp, weaver, well, wildboar

 empire: arena, armoursmith, armoursmithy, baker, bakery, brewer, builder, burner, carpenter, carrier, constructionsite, donkey, donkeybreeder, farm, farmer, fisher, forester, fortress, geologist, hunter, innkeeper, lumberjack, master-miner, miller, miner, outpost, flags, pig-breeder, scout, scouts_house, shepherd, ship, shipwright, smelter, soldier, stonemason, toolsmith, tower, trainer, vinefarmer, weaponsmith, weaponsmithy, weaver, weaving-mill

[SirVer (sirver)]

I already talked with chuck about this a long time ago. I actually suggested the same idea that you propose - it is also the way S2 did things. The code coud be improved by generating a densely packed sprite map from the individual animation parts - that would improve blitting speed I think (but maybe this is not even needed).

I was suggesting doing this as a preprocessing step - a script which you basically feed the current graphics config and which outputs suitable graphic files. I even stared coding on this - unfortunately this will kill the nice graphics dir we currently have and will make understanding the graphics much harder for new contributors. This is not as much of a problem though as all animations are done in 3d anyways, so a post processing step would not hurt graphic dev as much (chuck said).

[Chuck Wilder (chuckw20)]

I still have no qualms if the move to sprite maps (or something similar) can be accomplished by one (or more) additional step AFTER the production work that is now done in Blender (namely the modeling and animation that creates the original png files before their cropping and resizing). Of course, it stands to reason that the graphics should be game-ready before being amalgamated.

I'd like to avoid modifying any processes WITHIN Blender at this point because we are still formulating the migration from Blender v2.49 to v2.5+ which involves new scripts and changes to the .blend native file format.

I naturally wish any new graphics production processes will be as painless and efficient as possible.

[SirVer (sirver)]

I started working on this because I could't sleep tonight for some reason.

[Chuck Wilder (chuckw20)]

I linked this bug to the spritemaps development branch.

Pushed in rev #6531 around 29 conversions that I was able to perform either manually or with SirVer's Python make_spritemap script.

None have yet been tested, but I wanted to make them available if others wished to try them.

[Chuck Wilder (chuckw20)]

Pushed 27 more conversions in rev #6532.

[Chuck Wilder (chuckw20)]

Approximately 31 more conversions pushed in rev #6533. None yet tested. I'm having some "challenges" with my ubuntu box and I am not set up to do builds for Windows.

[Chuck Wilder (chuckw20)]

I have successfully tested in linux all graphics that have been converted to date.

[Tino (tino79)]

On win32 starting a game results in an error:

...
No version file found
Parsing world bobs...
Parsing global bobs in world...
Parsing map gen info...
Fata exception: Stamm barbarians: coal="Kohle": [c:/data/repo/trunk/src/graphic/animation.cc:59] Invalid point definition: <correct w and height>
lastserial: 0

Spieldatenfehler
Stamm barbarians: coal="Kohle": [c:/data/repo/trunk/src/graphic/animation.cc:59] Invalid point definition: <correct w and height>
sound_handler 1 mal geschlossen. freq 22050, format 32784, chan 2
SDL_AUDIODRIVER dsound

[Chuck Wilder (chuckw20)]

Sorry about that, Tino. That problem should be corrected now in rev #6534

[Kiscsirke (csirkeee)]

The problem also appears in tribes\barbarians\iron\conf, tribes\barbarians\raw_stone\conf and tribes\barbarians\reed0s\conf.

SirVer, how come it doesn't cause a problem on Linux? Or is it a Debug/Release build difference?

[Chuck Wilder (chuckw20)]

Found 3 more (much to my embarassment). Will notify when corrected.

[Chuck Wilder (chuckw20)]

Conf files corrected for iron, raw_stone, and reed0s with rev #6535. I don't know how these could have run in linux.

[Kiscsirke (csirkeee)]

There were some further erroneous conf files, I corrected them in rev #6536.

I think the difference isn't Windows/Linux, but that you built a Release version, and that does less checks? If so, try compiling a debug build and testing with that. (The compile.sh script asks if you want a debug or release build.)

I don't know what your current process for editing these is, but I guess it could be more automatized, from seeing the number of potential mistakes?

Also 2 other comments on the branch:
 - Is there any reason for 'dimensions' and 'base_offset' to be a different format from 'hotspot'? (They use commas instead of spaces.) Being the same would be more logical to me. I would think it could also use the same code?
 - I think we should set some conventions on the image file naming. Right now there are folders where it's "idle_xx" and so on, and there are folders where the image files are named after the object too. With the conversion in this branch, some were converted from the former to the latter. I would actually prefer the former, it makes it easy to search for files "idle*" in all those folders, and the folder name already describes the object anyway. But again, setting some convention and sticking with it would be better in either case.

[Chuck Wilder (chuckw20)]

On Mon, Mar 18, 2013 at 8:43 PM, Kiscsirke <email address hidden> wrote:

> There were some further erroneous conf files, I corrected them in rev
> #6536.
>

Thanks. I thought I caught them all with a text search I did. I know this
isn't exactly "Testing in production", but I still hate to produce sloppy
work.

> I think the difference isn't Windows/Linux, but that you built a Release
> version, and that does less checks? If so, try compiling a debug build
> and testing with that. (The compile.sh script asks if you want a debug
> or release build.)
>

I'll do that from now on. Thx

>
>
I don't know what your current process for editing these is, but I guess
> it could be more automatized, from seeing the number of potential
> mistakes?
>

In all of these

incidents, it was/is entirely manual owing to the limitations of SirVer's
script currently. (You KNOW that I didn't write it. Right? Pythonxy?
Me?!! Yeah, sure..) :) I wish I DID know some Python, though, to handle
just this type of situation. I don't know of any keyboard macro utility
that could glean image dimensions and enter them in an edited text file.
Heck, I don't know any keyboard macro utilities PERIOD outside of Lotus
123. You probably don't remember that product. ;)

> Also 2 other comments on the branch:
> - Is there any reason for 'dimensions' and 'base_offset' to be a
> different format from 'hotspot'? (They use commas instead of spaces.) Being
> the same would be more logical to me. I would think it could also use the
> same code?
>
>

Again, the make_spritemap.py script is SirVer's baby. The hotspot has
always been space delimited. I couldn't even guess why he uses a comma for
the dimensions and offset.

>
> - I think we should set some conventions on the image file naming. Right
> now there are folders where it's "idle_xx" and so on, and there are folders
> where the image files are named after the object too. With the conversion
> in this branch, some were converted from the former to the latter. I would
> actually prefer the former, it makes it easy to search for files "idle*" in
> all those folders, and the folder name already describes the object anyway.
> But again, setting some convention and sticking with it would be better in
> either case.
>

I agree there should be some standard. SirVer's current approach is to map
all of the animation images, (i.e. build, idle, working, etc.) into one
common png file (plus a _pc file if there is playercolor). Therefore, he
elected to use the folder name as the file name. For now, I don't see him
changing this approach.

He's frightfully busy right now. So, I have been trying to document the
errors the script is currently encountering for him and manually converting
the single image pngs for consistency until the mapping script is modified
to handle them, too, if ever.

It's not just single-image pngs that are giving us errors. I've yet to
successfully run it for a traveling bob. Even some buildings are
generating errors I'm guessing because the input images are of differing
dimensions. Hence the still lengthy list of barbarian buildings and
workers that are yet to be converted.

There is a lot to do (well o...

[Tino (tino79)]

Nice, it is working now on win32, too.
For the brave i've uploaded a recent build: http://widelands.8-schuss.de/Widelands-bzr6536-spritemaps-nomusic-win32.exe

[Chuck Wilder (chuckw20)]

Thanks for the Windows build, Tino! Now I have no excuses if I push erroneous files. ;)

[Kiscsirke (csirkeee)]

Yeah, most of the comments were meant toward SirVer :)

Well, there's already python code to read and change conf files in crop_animation.py, so reusing that, I think it shouldn't be too hard to make the script change the conf file itself automatically. I'm probably going to be a bit more busy too from now on, but I know python, so I'll try to look into it this week maybe.

[SirVer (sirver)]

I agree that the script should do more automatically and I also agree that consistency in the naming would be nice (in fact, I would love to get rid of the pics= entry completely and deduce the name of the animation image directly from the animation name). This just seemed to be too much work for a cleanup - so I didn't do it.

Also, one has to keep in mind that the new script is now used to convert animations, but in the future we will have new animations, so it must also be able to create new where there is no conf entry yet - I designed with this goal in mind mainly and we have to keep it in mind while changing the script.

That there is an inconsistency between "," and " " as a separator is just stupid. I used "," for the region descriptions, so I also used that for the new lines - but I agree that this should be changed back to space.

Sorry chuck that the script is less than an ideal experience right now. :/ I am also very swamped at this point in time, so I cannot make any promises when I will get to anything - I'll try to improve the experience as quickly as possible.

[Chuck Wilder (chuckw20)]

On Wed, Mar 20, 2013 at 3:55 AM, SirVer <email address hidden> wrote:

> Sorry chuck that the script is less than an ideal experience right now.
> :/ I am also very swamped at this point in time, so I cannot make any
> promises when I will get to anything - I'll try to improve the
> experience as quickly as possible.
>

I am happy that we have SOME functionality in the script as it stands now
even if it is hit-and-miss with the animations. :)

In hope of a timely merge of spritemaps, I just wish I had a (reasonable)
manual workaround for those models that the script can't currently handle
on its own. Then I could hope to complete the conversions independently
and free you (i.e. SirVer and/or Andras) to devote your time elsewhere, at
least until new animations are introduced.

A thought: In lieu of one giant spritemap for each *model*, would there be
benefits in creating individual maps for each unique animation
*sequence*(i.e. a spritemap file for a [walk] sequence, a second
spritemap file for a
[walkload] sequence, a third for a [working] sequence, etc.)?

Speaking of ",", " " and scripts,... it would be *ideal* if one wouldn't
have to revisit and manually change all of those conf files that now
contain the commas. ... I'm just saying. :)

For the time being, I have more than enough work yet that I CAN do.

We should consider if/how the road flags, terrain, and global animations
will be addressed at this time. Hey! It's conceivable I could get through
the tribes relatively soon even if I have to do it "one-handed". ;)

Most important to remember, I think, is the fact that it has been
individual conf files that were altered manually (*mea culpa*) and not the
code changes to the game engine that have resulted in the errors to date.

[Chuck Wilder (chuckw20)]

rev #6537 contains 96 atlantean models now converted to spritemaps, and THESE have been tested under Windows. :)

[Tino (tino79)]

I've revisited the point representations for those new values and regions. All conf files should be changed accordingly and the spritemaps python script is changed, too.

Now let's see what i can do to adapt the script for more models...

[SirVer (sirver)]

Tino, the script needs to be changed to do things in the following order:

- [detect and] load all animations in the directory
- crop each animation individually (retaining/updating the hotspot)
- group animations into "similar" groups. E.g. build animation is different, but idle and work animation are similar (e.g. same size and 80% common pixels). We then have groups (build,) and (idle, work).
- Now, try packing
build + (idle, work with idle as base picture)
build + (idle, work with work as base picture)
build + idle + work individually
and see which one gives the smallest image. This is the optimal solution.

That is the logic I meant to write in the script, but it is very ugly and full of bugs - so it doesn't quite do that. Let me know when you work on it, so that we do not overlap.

[Chuck Wilder (chuckw20)]

Great! I'll try out that new script ASAP. Thanks!

On Thu, Mar 21, 2013 at 3:20 PM, Tino <email address hidden> wrote:

> I've revisited the point representations for those new values and
> regions. All conf files should be changed accordingly and the spritemaps
> python script is changed, too.
>
> Now let's see what i can do to adapt the script for more models...
>
> --
> You received this bug notification because you are subscribed to the bug
> report.
> https://bugs.launchpad.net/bugs/1121982
>
> Title:
> Reduce video memory consumption by merging animation frames
>
> Status in Widelands:
> Confirmed
>
> Bug description:
> The game currently requires a lot of video memory to store all the
> animation frames of in-game objects.
>
> In many cases, there is a lot of redundancy in those frames. For
> example. the barbarian headquarters animation has 20 frames, each of
> size 120x120, adding up to 288000 pixels or slightly more than 1MB of
> video memory. However, those frames differ only by the fairly small
> animation of the building's flags.
>
> It could be quite beneficial to extract one base texture plus
> difference images. In the case of the barbarian headquarters, this
> could probably get video memory consumption down to about 40000 pixels
> or around 160kB, an improvement by a factor 6. Admittedly, this
> particular example is probably one of the cases that would benefit
> most, but the concept seems worthy of investigation.
>
> Any implementation would have to be as transparent as possible, and
> should especially avoid putting any additional work on the graphics
> developers.
>
> Conversion Status:
> Yet to be converted: all global and empire animations, plus
> atlantean: armoursmith, baker, bakery, blackroot_farmer, builder,
> burner, burners_house, carrier, constructionsite, crysatalmine, farmer,
> fish_breeder, fisher, forester, geologist, goldmine, horse, horse_breeder,
> hunter, ironmine, mill, miller, miner, flags, sawmill, sawyer, scout,
> scouts_house, ship, shipwright, shipyard, smelter, smoker, smokery,
> soldier, spiderbreeder, stonecutter, toolsmith, trainer, weaponsmith,
> weaver, woodcutter
>
> barbarian: baker, barrier, blacksmith, brewer, builder, burner,
> carrier, cattlebreeder, chief-miner, citadel, coalmine, constructionsite,
> deep_coalmine, deep_goldmine, deep_oremine, deeper_coalmine,
> deeper_goldmine, deeper_oremine, deer, donjon, farmer, ferner, fisher,
> flags, fortress, gamekeeper, geologist, gold_mine, granitemine,
> headquarters_interim, helmsmith, helmsmithy, hunter, innkeeper,
> lime-burner, lumberjack, lumberjacks_hut, master-blacksmith, master-brewer,
> master-miner, miner, oremine, ox, flags, port, quarry, ranger, rangers_hut,
> scout, sentry, ship, shipwright, smelter, soldier, stonemason, stronghold,
> trainer, trainingscamp, weaver, well, wildboar
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/widelands/+bug/1121982/+subscriptions
>

[Tino (tino79)]

Thanks SirVir, that helps much!
Til now i only figured out, that the script crashes with a memory execption.
This is because it creates distinct groups for not only the groups you described, but also takes the orientations into account which results in e.g. 9 groups (8x walking + 1 idle).
Generating the permutations for this to do the "try packing" crashes even before it can try ;) . I think this a NP-hard problem...

We can't produce a optimal solution in linear time, so i will try to bring that down to a sub-optimal solution based on less groups. (e.g. don't try base walk_NE with walk_SW as base....)

[Chuck Wilder (chuckw20)]

rev #6549 - error message encountered when tarting game with one tribe(barbarians)

tribe barbarians: axe="Axe":[c:/data/bzr/widelands/trunk/src/profile/profile.cc:724]
[tribes/barbarians/axe/conf] Section [idle]. key 'packed' not used (did you spell the name correctly?)

I received a similar error on the advanced_shield when I tried to run with atlanteans. Both are first tribal image loaded.

[Tino (tino79)]

@Chuck:
r6549 is the trunk version. It looks like some mixup between the trunk executable and the spritemaps conf files...

[Chuck Wilder (chuckw20)]

You are correct, of course. (I never was good with numbers.) :)

I´ll try to pay closer attention to what I am actually running in the
future. (May be asking a lot from me, but I'll try.) :D

On Fri, Mar 22, 2013 at 2:30 AM, Tino <email address hidden> wrote:

> @Chuck:
> r6549 is the trunk version. It looks like some mixup between the trunk
> executable and the spritemaps conf files...
>
> --
> You received this bug notification because you are subscribed to the bug
> report.
> https://bugs.launchpad.net/bugs/1121982
>
> Title:
> Reduce video memory consumption by merging animation frames
>
> Status in Widelands:
> Confirmed
>
> Bug description:
> The game currently requires a lot of video memory to store all the
> animation frames of in-game objects.
>
> In many cases, there is a lot of redundancy in those frames. For
> example. the barbarian headquarters animation has 20 frames, each of
> size 120x120, adding up to 288000 pixels or slightly more than 1MB of
> video memory. However, those frames differ only by the fairly small
> animation of the building's flags.
>
> It could be quite beneficial to extract one base texture plus
> difference images. In the case of the barbarian headquarters, this
> could probably get video memory consumption down to about 40000 pixels
> or around 160kB, an improvement by a factor 6. Admittedly, this
> particular example is probably one of the cases that would benefit
> most, but the concept seems worthy of investigation.
>
> Any implementation would have to be as transparent as possible, and
> should especially avoid putting any additional work on the graphics
> developers.
>
> Conversion Status:
> Yet to be converted: all global and empire animations, plus
> atlantean: armoursmith, baker, bakery, blackroot_farmer, builder,
> burner, burners_house, carrier, constructionsite, crysatalmine, farmer,
> fish_breeder, fisher, forester, geologist, goldmine, horse, horse_breeder,
> hunter, ironmine, mill, miller, miner, flags, sawmill, sawyer, scout,
> scouts_house, ship, shipwright, shipyard, smelter, smoker, smokery,
> soldier, spiderbreeder, stonecutter, toolsmith, trainer, weaponsmith,
> weaver, woodcutter
>
> barbarian: baker, barrier, blacksmith, brewer, builder, burner,
> carrier, cattlebreeder, chief-miner, citadel, coalmine, constructionsite,
> deep_coalmine, deep_goldmine, deep_oremine, deeper_coalmine,
> deeper_goldmine, deeper_oremine, deer, donjon, farmer, ferner, fisher,
> flags, fortress, gamekeeper, geologist, gold_mine, granitemine,
> headquarters_interim, helmsmith, helmsmithy, hunter, innkeeper,
> lime-burner, lumberjack, lumberjacks_hut, master-blacksmith, master-brewer,
> master-miner, miner, oremine, ox, flags, port, quarry, ranger, rangers_hut,
> scout, sentry, ship, shipwright, smelter, soldier, stonemason, stronghold,
> trainer, trainingscamp, weaver, well, wildboar
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/widelands/+bug/1121982/+subscriptions
>

[Tino (tino79)]

I really don't get on with the script.
At the moment i just try to understand if it is possible to pack animations which different size. For simpliticity i am working with the babarian barrier, which has only 3 animations:
  barrier_i => 79x76px
  barrier_u => 76x76px
  barrier_b => 76x76px

So, while it is not possible to base u/b on i or i on b/u because of the different size it should be able to base u on b and pack then together with i?
=> but pack_animations( (('barrier_i_',), ('barrier_b_', 'barrier_u_')) ) does not work

So it is necessary that all animations/pics in one directory have to be the same size?

[Nicolai Hähnle (nha)]

@Tino (#28):
Yes, it is necessary that the frames be of the same size. In fact, the script tries to check for that, but the check is buggy :)
Look at function _load in load_animations; the check should read `if seen_shape and seen_shape != img.shape` instead of what is there now.

Now why is it necessary that all frames are of the same size? Basically, because the script assumes that it only makes sense to share image data of pixels that are in the exact same position. When the frames are of different sizes, then one would somehow have to figure out how to line them up properly. In principle, this could be inferred from the hotspots, but I suppose for the future workflow it makes more sense to just generate equal-sized frames for everything in Blender.

@all:
I took a look at the code in the spritemaps branch now. Great work overall! I do have one comment regarding the design of this functionality. I believe that instead of having a bunch of regions, with each region using different images in each frame, it would be better for every frame to have a list of images that need to be blitted to assemble the frame.

The rationale is that this allows to have (a) a different number of sub-images and (b) different sizes and positions of sub-images for different frames. Looking at the barbarians/carrier/idle animation, this could be a big win. Even a very naive spritemap generation algorithm which merely crops every frame individually, without sharing anything between frames, would probably save around 25% of the pixels. Similar advantages would apply also to soldiers' battle animations, and to a smaller extent to almost all other bobs.

It is true that storing the coordinates for the blitted images would take up slightly more space, but this should be made up for by those increased opportunities for reducing the image data.

[SirVer (sirver)]

It is necessary for an number of animations to be separated into one base pic and regions for them to be the same size. However given you have two sets of animations as tino describes, you should not need them to be of the same size to be packed into the same image - so this is very likely a bug in the sprite generation script. I try to find some time today to look at the script again and do some refactorings.

Nicolai, I understand what you are saying, but this is much harder to find a spritemap generator for: essentially you first have to determine a 'good' base picture for an animation, and then you have to find the differences to this base picture for each frame (essentially the regions for each frame). You then also have a lot more numbers in the conf file. But the current approach will also crop the pixel data for each animation frame and will therefore also save the 25% you are talking about - so I do not know if the extra complexity will also buy us much.

It would be pretty easy to add this into the blitting code as it stands now - it is essentially just regions per frame instead of regions per animation set.

[Nicolai Hähnle (nha)]

The current approach _doesn't_ do this cropping. It requires all frames in an animation to have the same size. Also, the current method for decomposing the frames could still be used even with the different data format. It is true that figuring out how to best use the full potential of having "regions per frame" is more difficult, but doing so just requires incremental improvements to the make_spritemap scripts; it doesn't require any further changes in the renderer.

[Nicolai Hähnle (nha)]

I don't have too much time these days, and I will be away over the Easter holidays, but I am currently experimenting with writing a script that could leverage the more flexible format that I have in mind.

It is true that the general problem of finding the optimal way to use the more flexible format is very difficult. The first problem is: How do you even measure how good a certain decomposition is? With the flexible format, it is possible to minimize the size of the pixel data simply by putting every non-transparent pixel into its own 1x1 rectangle, but that's obviously a terrible idea.

So for now, I think the objective function we should keep in mind is something like C * Number of Rectangles + Total Area of Rectangles.

I have written some code that finds a good rectangle covering for a "delta" between frames according to this objective function, based on the standard set cover heuristic and a (right now very simplistic and brute force) algorithm for computing the minimum rectangle of average cost (i.e.: C + Area of Rectangle divided by Number of Pixels Covered).

Ultimately I want to plug this into an algorithm that segments the frames of an animation (or even multiple animations) into sets of "frame groups", where each frame group will be stored as a base picture plus delta rectangles for each frame. This approach is targeted for things like the carrier/idle animations.

Right now the code is a bit of an ad-hoc mess, but I hope to be able to show something in the next two weeks or so.

[SirVer (sirver)]

Nicolai, I am not that concerned about the size of the final images - the current images without any compression take 380MB in RAM right now - with this improvements this should go down by a factor of 5 or 6 - my current laptop has 16GB of RAM, my Phone has 1Gig - so I do not care at all about this footprint. The main reason I want this change in is that loading the graphics goes quicker and we do not need the on-demand loading anymore - because this makes a noticeable lag in the game which is very annoying.

However, if you make a better packaging script in two weeks, all work of packaging the animation needs to be redone, which seems pretty wasteful. So speak now or be forever quiet :): Should we wait for you to deliver a more powerful packager or should we move forward with what we have now and ignore the few MB that we can save more?

[Nicolai Hähnle (nha)]

In that case, I ask for you to wait. And having a deadline can't be a bad thing ;)

[SirVer (sirver)]

Alright - looking forward to you changes :). I am also glad if I do not have to work on the script again, it is not really pleasant to look at at this point in time.

If I can help with anything, just let me know.

[Chuck Wilder (chuckw20)]

Converted about 106 empire tribal objects with rev #6547 to the branch. That is about all I can do manually for now for the tribes at any rate. I'll take a look at the global stuff to see if I can do anything on my own there.

[SirVer (sirver)]

Nicolai, two weeks are almost over. Any progress to report?

[Nicolai Hähnle (nha)]

I'm behind what I had planned because I was sick for much of the last week, but I have implemented most of the actual algorithmic part to demonstrate the potential. You can take a look at the current state, which is pretty hacked up and attached. The only reasonable way to use it right now is interactively, e.g.:

>>> import make_spritemap
>>> frames = make_spritemap.load_animations(['path/to/animation_'])
>>> make_spritemap.pack_frames_greedy(frames)

This will show you which frames will be packed together and what the total cost is, measured as 32 * # of rectangles + area of rectangles. The 32 for encoding the fixed-cost overhead for rectangles is more or less arbitrary. The memory overhead for the rectangle coordinates should be less than 32 pixels most of the time, but there is overhead in terms of rendering at runtime, which makes it reasonable to have higher fixed costs.

It does not run on animations with large frames yet. This is due to an inefficient subroutine which I already know how to replace, but the implementation is a bit tricky.

In addition to the greedy strategy shown above I have implemented two simpler strategies for benchmarks:

pack_frames_global_bbox simply dumps every frame entirely into its own rectangle of the same size and position for every frame. For worker animations, this is essentially what the code in the spritemap branch ends up doing (the results in the previous approach may be slightly better because it recognizes a handful of frames that are exactly equal).

pack_frames_bbox reduces each frame individually to its bounding box. That is, instead of having one bounding box for the entire animation, there is an individual bounding box for each frame.

pack_frames_greedy attempts to greedily combine similar-looking frames into a base picture plus delta rectangles for each frame.

The scores on barbarians/carrier/idle, which I have used as a guide for the development are:
pack_frames_global_bbox: 59900
pack_frames_bbox: 36056 (39.8% reduction)
pack_frames_greedy: 28851 (51.8% reduction)

The scores on atlanteans/carrier/walkload_ne are:
pack_frames_global_bbox: 5360
pack_frames_bbox: 4406 (17.5% reduction)
pack_frames_greedy: 4205 (21.5% reduction)

The scores on empire/soldier/atk_ok_e are:
pack_frames_global_bbox: 14320
pack_frames_bbox: 8843 (38.2% reduction)
pack_frames_greedy: 7231 (49.5% reduction)

I would expect most of the walking animations to have similar results to the atlantean carrier, and even 20% are nothing to look down on. And as you can see, the improvement is more drastic for some other, less regular animations.

The next steps are to re-integrate your original strategy into the script and actually bake the frames including player colours; change the Widelands code to allow arbitrary rectangles; and adjust the animations. Eventually, I also want to fix the greedy strategy to be able to process larger frames.

[SirVer (sirver)]

That is very good progress - congratulations. Let me know when you can use a hand with any of the remaining steps - I am always short on time, but an hour here and there should be available.

I'll nag you about your progress in a week again :).

[SirVer (sirver)]

How are things going nicolai? I am eager to mark this thing Fix committed.

[Nicolai Hähnle (nha)]

Progress was slow because I was at a workshop - that also explains my lack of a reply, sorry about that.

I've hooked up some code to read and write conf files nicely - the idea is that we should be able to run the script in-place and re-optimize animations if we notice something. In particular, the new code should be able to re-expand the frames into individual .pngs.

On the way, I noticed that the existing rectangle packing code isn't exactly great when packing rectangles of greatly varying shape. For example, just taking bounding boxes of frames individually, the packing algorithm loses over 20% of pixel area sometimes, and in ways that clearly look "dumb" to the human eye.

Nevertheless, I understand that you want to get *something* committed, so I'll continue first with hooking everything up in the renderer as well.

[Nicolai Hähnle (nha)]

I forgot to ask: It seems that you took the rectangle packing code from somewhere else - may I ask from where? (Given the problem noted above, I may end up rewriting it eventually anyway, but for the time being it would be nice to fix that "give credit here" remark)

[Nicolai Hähnle (nha)]

I've implemented the new format in src/animation.cc in my own branch, and converted various barbarian workers to the new format - things seem to be working well so far.

My todo list is, roughly in order:
1) Get some minor quirks of the conversion script that prevents automatic conversion of some workers figured out
2) Hook up your region-based decomposition for buildings
3) Convert the rest of buildings and workers and world objects.
4) Work through remaining "NOCOM" comments and clean up the Python code a bit
5) Improve the spritemap packing algorithm and get the in-place modification / re-optimization of things working better

I think a first merge to trunk should be possible at point 4.

One more question though: I noticed that the spritemap branch loads all animations directly during loading again, rather than delaying loading until an animation is actually blitted for the first time. Was this intentional, or is this just a temporary artefact of the refactoring?

[Tino (tino79)]

Hi Nicolai,

if you have time you could have a look at my spritemap-testing branch, specifially rev 6549+6550.
I am on vacation the next 3 weeks and won't be able to make a proper merge request for this until then.

[Nicolai Hähnle (nha)]

Hehe... I wanted to avoid a huge commit adding those [global] things everywhere, which is one of the reasons I ended up not using the ConfigParser module from Python. (The other, arguably more important reason was that I wanted better control over the formatting and comments and how they are preserved).

[SirVer (sirver)]

note that there is a conf parser in the website branch: http://bazaar.launchpad.net/~widelands-dev/widelands-website/trunk/files/head:/widelandslib/

Nicolai: I took the basic ideas from this blog post: http://codeincomplete.com/posts/2011/5/7/bin_packing/

Is your work in a public branch (i.e. owned by widelands-dev)? Can I help out with anything?

[Nicolai Hähnle (nha)]

Thanks for the pointer to the existing parser, I did not know that and will take a look at it. I've uploaded my branch, but I haven't put it into widelands-dev. I'll change that though - still need to fix some local changes I have first though. I hope to get around to it this weekend.

I don't really see a good opportunity for parallelization of this work right now, but I'll let you know if I think of anything. Go and fix all those other bugs ;)

P.S.: Any word on this loading-spritemaps-on-startup question?

[SirVer (sirver)]

> P.S.: Any word on this loading-spritemaps-on-startup question?

Yes, sorry. I reverted this on purpose. The reason is that I test played a very long game and together with the surface cache (which routinely drops old images) the game is no fun to play when using a normal hd (i.e. not solid state). the cache drops images and the game reloads them resulting in a noticeable lag when moving around the map.

But also for loaded games the feature killed happiness: without dropping frames from the cache (i.e. by making the cache infinite in size) it needed a move over the whole map before the game stopped being choppy - otherwise the game will freeze whenever you visit a place on the map for the first time after loading.

I generally am of the opinion that a longer startup time is less painful than choppy play. The surface cache needs still changing to not drop stuff that is loaded from disk though to really fix this problem. I think it would be ideal to have both - maybe by background loading of the graphics or so.

[Nicolai Hähnle (nha)]

I have merged my changes into the ~widelands-dev/widelands/spritemaps branch and will continue to do my work there.

Done:
1) Reimplement region-based packing in make_spritemap.py, should work properly across different animations as well now.
2) New format used for barbarians/sentry, i.e. the first building works.

Todo:
1) Read 'packed=true' animations from existing conversions
2) Convert all objects (using parameters -o greedy -i -b), fixing remaining quirks in the make_spritemap.py script as they are encountered
3) Address all NOCOM comments and scan the code for some cleanup opportunities (perhaps removing PackedAnimation and some legacy DirAnimations stuff eventually?)

Once these are done, I think we're ready to do another Merge Review pass and get this into trunk. Once everything is in trunk, we can still think about improving the packing algorithms further, but that should be doable without changing the graphics formats again.

As for the caching: I agree that having the cache not eject images loaded from disk would be great. I was a bit disappointed because my old laptop got incredibly slow startup times again, but the spritemaps branch might actually be enough to fix this. Reducing the number of loaded files by a factor of 50 or so should help! In the long run, asynchronous loading from a background thread would probably give the best results.

[SirVer (sirver)]

Cool news! Sounds like progress.

Could you elaborate on 1) in the todo section? I do not grasp what is needed here.
2) Is this something that chuck could help with? What are the dependencies for the script as it stands now?
3) Yes please, let's kill those DirAnimations.

I agree fully on the last paragraph. Background loading is not completely trivial though as all OpenGL stuff must happen in one thread. I had a hacked together version of this running already though, so it is doable.

[SirVer (sirver)]

What is the state of this work now?

[Teppo Mäenpää (kxq)]

What happens if two frames in an animation are the same? Should it be possible to use a single memory chunk to host both frames?

Example: The following files are the same (tribes/barbarians/traningscamp. binary diff. More matches might be found with a more sensible search)

trainingscamp_i_05_pc.png and trainingscamp_i_12_pc.png
trainingscamp_i_08_pc.png and trainingscamp_i_15_pc.png
trainingscamp_i_09_pc.png and trainingscamp_i_16_pc.png
trainingscamp_i_10_pc.png and trainingscamp_i_17_pc.png
trainingscamp_i_11_pc.png and trainingscamp_i_18_pc.png

With limited random sampling, I found also other _pc matches here and there.

[Teppo Mäenpää (kxq)]

At least tribes/empire/stonemason/ has some non- "_pc" images that are identical with each other.

[SirVer (sirver)]

Don't bother reducing individual images. There is a basically complete (like 90%) implementation in these branches:

https://code.launchpad.net/~widelands-dev/widelands/spritemaps
https://code.launchpad.net/~nha/widelands/spritemaps

they just need cleanup and some small bug fixes and then should be ready to roll.

[SirVer (sirver)]

Setting to incomplete for bug sweeping.

[SirVer (sirver)]

Still not implemented, but I can still imagine that a pre-baking step for our graphics could buy us performance and memory - and a lot too. This will not happen for b19 and since I have no immediate plans of working on this, I am unassigning myself for now.

[SirVer (sirver)]

assigning Gun, as she is working on this recently.

[GunChleoc (gunchleoc)]

Good idea, we should integrate this into the new spritemap code right away.

[GunChleoc (gunchleoc)]

See also https://bugs.launchpad.net/widelands/+bug/1121982

[GunChleoc (gunchleoc)]

Migrated to https://github.com/widelands/widelands/issues/1947