Comment 38 for bug 1121982

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.