GSoC-SpriteSheets Gabba

This page is related to Summer of Code 2010

See the list of Summer of Code 2010 Ideas

This is a Summer of Code 2010 student page

Description

Gabba - Sprite Sheets

I developed an approach to introduce sprite sheets to Wesnoth with minimal hassle for artists, and as little modifications to game code as possible. I support generation of various sizes of optimized sprite sheets, so we can adapt to various platform and memory/disk requirements. My system will rely on a single external tool based on an existing open-source solution.

Updated 03/28/2010

About Me

See http://wiki.wesnoth.org/User:Gabba.

Project

The general idea of this project is to introduce sprite sheets and their memory, loading time and disk space benefits, while disturbing the workflow of artists as little as possible. They shouldn't need to go through any more hassles than now to keep contributing.

How I'll achieve this is by introducing a distinction between source material (what artists work with) and generated material (what the game engine actually uses). Note that the differences between the two will be small enough that the game engine will still be able to run using source material directly, as if sprite sheets had never been added.

Source material

• Keep individual pngs on svn. Makes it easier for artists. If some artists prefer to work directly with spritesheets, no problem, I'll accept that as input as well, by taking them apart and treating them as a set of individual images.
• Keep WML .cfg files for unit animations as they are now, i.e. have them refer to individual .png files. (Artists can instead use a part of their own sprite sheet through the already implemented ~CROP() functor.) Makes it easier to create animations and see what are the frames of an animation.

Generated material

Optimized sprite sheets will be generated as part of the wesnoth build process, and new WML animation files will be produced, which are identical to the source ones, except for image data which now refers to the correct location within sprite sheets. This will be done with a single, highly configurable command-line tool based on the ClanLib texture packer, that will get called from the current build scripts (scons, cmake, autoconf).

The new tool will work by following those steps:

1. Take command line parameters:
   • A number of existing WML (.cfg) animation files as input (could be a whole directory, a set of directories, individual files, whatever)
   • A target sprite sheet size, for instance 512x512 (optimal size probably depends on target platform memory capabilities)
2. Extract the list of image locations from those WML files
   • If some image locations are actually references (through ~CROP) to part of a hand-made sprite sheet, each individual reference will be treated as an individual image in the following steps
3. Use the image list to build sprite sheets of the size specified, cramming as many images as possible into each one using a bin-packing algorithm (by default: the one already implemented in the ClanLib tool)
4. Output copies of the original WML files, updating the image references to point to the proper location within my sprite sheets.

There are several design choices to make here:

• do we mix all sprites from official content together? (Best for disk space, but wastes memory as you may load a whole sheet for a single image.)
• do we do per-campaign/per-faction sprite sheets? (Probably best for memory, still ok on disk space, and we're forced to do this for non-mainline content)
• we should probably allow a mix of both and let the packagers enter a set of directories with WML animation descriptions, and out come the corresponding sprite sheets.

When distributing the game (except in source form), we'd include only spritesheets and the generated .cfg files, not original .png or .cfg files.

• This said, we could consider doing an "artist distribution" of the game, that includes the unprocessed images and WML files, so they can browse this material in a more friendly format, without having to use svn. I would also give them a better idea of the preferred format in which to submit their work.

Caching adjustments

The ~CROP() functor (or something equivalent) is an essential part of making sprite sheets work in Wesnoth. However some new info surfaced, indicating that a spritesheet mechanism built around ~CROP() as it is now would actually cause the caching mechanism to use more memory. Definitely not a good thing, therefore some adjustments to the caching mechanism will be in order, so the spritesheet is loaded only once and then referenced as needed, instead of each sub-image being cached individually in addition to the sprite sheet.

Code relevent to ~CROP:

• The locator::locator() constructor calls locator::init_index(), that calculates an image hash from the whole image path, including functors. I'll introduce special treatment for the ~CROP functor here, so that it is ignored in the hash generation if the image path only contains ~CROP functors. This will allow crops of the same image to be considered as identical by the caching system. A mix of ~CROP and other functors can't be ignored in the hash, since the result of those operations is potentially too complex to quickly regenerate from the original image.
• In locator::parse_arguments(), the presence of functors sets the SUB_FILE locator type, and stores the various functors in a string. I'll add here a new property to locators to identify if they are an image crop; this property will be returned via locator::cropped().
• In image::get_image, the following checks if the image locator is cached, and then returns the corresponding surface immediately if it's the case:

 if(i_locator.in_cache(*imap))
     return i_locator.locate_in_cache(*imap);

I'll modify this to get special treatment for crops:

 if(i_locator.in_cache(*imap)) {
     if (i_locator.cropped()) {
         // GET THE RIGHT SUB-SURFACE FROM CACHED IMAGE
         // AND USE IT AS BASE FOR THE OPERATIONS IN THE REST OF get_image()
     } else {
         return i_locator.locate_in_cache(*imap);
     }
 }

There's another issue to consider: if functors that make the image significantly different from the original, such as recoloring, flipping, are used a lot, it reduces the memory gains of using sprite sheet image files. If Wesnoth uses those functors massively, it could even invalidate the idea of sprite sheets created externally through tools -- the only alternative would be to build the sprite sheets dynamically, adding each individual image or functor-modified image to some in-memory sprite sheet when it's loaded. But if we give up on the external sprite sheets, we give up on huge potential savings in disk space and loading time.

I've gathered some data to measure the inpact of functors; those commands were run in the Wesnoth "data" directory checked out from svn:

 $ find . -name '*.cfg' -exec grep '.png~' {} \; | wc -l
 $ 257

So there are 257 uses of functors in all of Wesnoth's official data files. Let's compare that to the total image references:

 $ find . -name '*.cfg' -exec grep '.png' {} \; | wc -l
 $ 11958

From this data, we can conclude that the impact of functors is currently insignificant (2,15% of all image references), and doesn't justify giving up on external sprite sheets generated during the build process.

The tool

As far as generating the sprite sheets themselves, I'll borrow a maximum of code from the program below (licence is BSD) and adapt their GUI for testing and to complement the automated process:

ClanLib texture packer

   http://www.rtsoft.com/forums/showthread.php?t=2518
   http://www.clanlib.org/beta/index.php/Examples#Screenshots_from_ClanLib-2.0.2FUtilities

• This program takes .png with transparency as input and output, so no problem there.

• I'll modify the GUI and especially provide a command-line interface, to allow integration with the build process. Unless there's a very good case for introducing a new dependency, the modified program won't add any new dependencies to Wesnoth or its build process.
  Planned command line features (syntax will be determined after implementing and testing):
  • Defines sets of folders with WML files from which to extract image references and build the sprite sheets: sprites from different sets are not mixed on the same sprite sheets. Those sets can be read from standard input or a text file.
  • Possibility of launching multiple jobs to work on independent image sets (how this interacts with the build system options needs to be determined).
  • Configurable name generation for the sprite sheet files
  • Configurable sprite sheet size, i.e. 512x512

• The program currently outputs XML with info of where individual images ended up in the sprite sheets; I'll adapt this code to output modified WML .cfg files, as explained above.

Note: before picking the ClanLib tool as the base for my work, I evaluated the following ones:

   http://spritesheetpacker.codeplex.com/
   http://www.imagemagick.org/script/montage.php
   BlitzBasic ImagePacker
   http://slick.cokeandcode.com/demos/packer.jnlp
   http://homepage.ntlworld.com/config/imagepacker/

Artists' workflow

So, how would implementing this system affect how artists work now? In short: not at all, once they've understood the distinction between source and generated content, as you can see below:

Concrete example from the drake glider (Glider.cfg):

• What it'll look like on svn or in the potential "artists' distro" (i.e., same as now):

  [attack_anim]
      (...)
       [frame]
           duration=100
           image="units/drakes/glider-kick-1.png"
       [/frame]
      (...)
  [/attack_anim]

• What it'll look like after processing through my system, and therefore in your packaged copy of the game:

  [attack_anim]
      (...)
       [frame]
           duration=100
           image="units/drakes/drakes_sprite_sheet.png~CROP(0,0,20,20)"
       [/frame]
      (...)
  [/attack_anim]

• What an artist can change it to (in any version of the game, be it svn, artists' distro or regular package), in order to test a new image:

  [attack_anim]
      (...)
       [frame]
           duration=100
           image="units/drakes/My_New_Fancy_Glider_Kick_1.png"
       [/frame]
      (...)
  [/attack_anim]

• Or she could use this, too, to refer to her own image sheet or strip (this is already possible):

  [attack_anim]
      (...)
       [frame]
           duration=100
           image="MY_OWN_SPRITE_SHEET.png~CROP(10,10,30,30)"
       [/frame]
      (...)
  [/attack_anim]

Optional Features

The algorithm(s)

Once all the above is done, I want to improve the placement of images in the sprite sheets, which may seem to be nitpicking but could get crucial for low-memory devices. Misc research links about this:

   http://en.wikipedia.org/wiki/Bin_packing_problem
   http://code.google.com/p/caparf/
   http://scholar.google.com/scholar?q=%22Packing+Rectangular+Pieces+-+A+Heuristic+Approach.%22

If I really, really have extra time to kill and the space benefits seem to be worth it, I'll investigate the possibility of overlapping identical parts of images (such as transparent areas) so I can pack the sprites even closer together. For sprites that have a lot of emtpy corner space, it could have a measurable effect.

Improved support for custom sprite sheets

Since some people including the wesnoth art director would prefer to work with their custom sprite sheets for future work, I would like to add a new tag that can define several frames at a time, provided the user specifies the rectangular area and the padding. This could be an example of WML for the new tag, but interactions with the whole image loading and animation system will have to be studied before deciding on an implementation:

[attack_anim]
      (...)
       [frame_group]
           id="drakeB"
           image="units/drakes/drake_spritesheet.png"
           pad=3   #gap between frames in both x AND y directions
           rect=2,2,33,34
           frames=3
           frames_per_row=1
           duration=100 #or for individual durations: duration={100,200,150}
       [/frame_group]
      (...)
[/attack_anim]

Milestones and Calendar

GSoC start according to Google's calendar: May 24

• Modify the Wesnoth caching code so that ~CROP actually saves memory with sprite sheets. Test whether it's better to modify ~CROP directly, or add a separate ~SPRITESHEET() functor.
  • Deadline: June 7
• Add a command line interface to the ClanLib app, and test generations of sets of spritesheets of various sizes, using a list of image folders as input. Adapt the ClanLib app's current interface to testing needs.
  • Deadline: June 21
• Integrate parsing of WML files with animation data to harvest the list of images (and parts of images) to use as input. Output updated WML files with the new location of images within spritesheets.
  • Deadline: July 5
• Start integration of the tool with the Wesnoth build process. Expand command line interface.
  • Deadline: July 16 (Mid-term evaluation)
• Finish integration with the build process, do final cleanup of modified ClanLib tool, do memory benchmarks, document stuff
  • Deadline: August 9
• If things go faster than planned, implement as much as possible from Optional Features above.