SoC2011 Automagic

This page is related to Summer of Code 2011

See the list of Summer of Code 2011 Ideas

This is a Summer of Code 2011 student page

Project: SoC_Ideas_Sprite_Sheets2011

Description

Karol Kozub - Spritesheets

I would like to implement a tool that would pack images into spritesheets. The tool would use an optimization algorithm to propose an arrangement to the artist, who then would be able to modify it using a GUI. It would also support adding/removing sprites to/from existing spritesheets. I would also implement an spritesheet manager in C++ that would load the images from spritesheets using configuration files generated by the tool.

Timeline

Stage 0	April 25 - May 22	Getting to know the codebase, reading the documentation, discussing project details with my mentor and the artists.
Stage 1.1	May 23 - June 14	Implementing the sprite packing tool's core
Stage 1.2	June 15 - June 21	Implementing the C++ spritesheet manager.
Stage 2.1	June 22 - July 7	Implementing the GUI base and spritesheet loading, modifying and saving (Around the end of June I will have to defend my bachelor's thesis)
Stage 2.2	July 8 - July 21	Implementing the spritesheet packing/unpacking and adding/removing images to/from spritesheets through the GUI.
Stage 3	July 22 - August 7	Implementing optimization algorithms for suggesting sprite arrangements. (I will probably be on holidays between Aug 1 - 7)
Buffer time	August 8 - August 22	Filling gaps in the documentation.

Implementation details

Stage 1 :: Sprite packing tool

Abstract

The sprite packing tool's purpose would be spritesheet management. The tool's core would have to include commands for packing and unpacking spritesheets and adding and removing sprites to/from them.

The tool would be written in python. It would use PyPNG or some other similar library to open and save PNG images. The packing algorithm would be very simple - it would pack the images in one row one by one. It would later be raplaced by more elaborate solutions. The tool would generate configuration files describing how the sprites are packed.

Some artists may prefer to work on single images rather than whole spritesheets (see small mail ...). The tool would allow spritesheets to get split back into seperate images. The config for that spritesheet wouldn't be removed, so it could be later repacked using the same images and arrangement.

At this stage the tool would be usable only from the command line.

Substages

The tool's implementation could be divided into these features:

• creating a new spritesheet
• unpacking a spritesheet
• packing a spritesheet back
• adding images to a spritesheet
• removing images from a spritesheet
• listing the contents of a spritesheet
• renaming a spritesheet

Use examples

This command would create a spritesheet leader-spritesheet.png containing all the sprites of an orc leader and modify the spritesheet config file accordingly.

 utils/spritesheet_manager.py --create data/core/images/units/orcs/leader-spritesheet.png \
                              --add data/core/images/units/orcs/leader*.png

This command would also add an entry in the spritesheet configuration file that would look something like this:

 [spritesheet]
   name=data/core/images/units/orcs/leader-spritesheet.png
   state=packed
   [image]
     name=data/core/images/units/orcs/leader-attack-1.png
     x=1
     y=1
     width=72
     height=72
   [/image]
   [image]
     (...)
   [/image]
 [/spritesheet]

Notice that the first image starts at (1, 1). The images would have a one pixel thick pink border to make distinguishing the images on the spritesheet easier.

This command would unpack a spritesheet creating seperate png images and removing the leader-spritesheet.png image (after the previous command succeeds - the tool would not allow image loss due to errors).

 utils/spritesheet_manager.py --unpack data/core/images/units/orcs/leader-spritesheet.png

To remove the saved information about the spritesheet an --unpack-and-remove flag could be used instead.

This command would pack a spritesheet back using the saved information about the images and their coordinates.

 utils/spritesheet_manager.py --pack data/core/images/units/orcs/leader-spritesheet.png

This command would modify the spritesheet adding all the grunt images and removing the leader-ranged.png image.

 utils/spritesheet_manager.py --modify data/core/images/units/orcs/leader-spritesheet.png \
                              --add data/core/images/units/orcs/grunt*.png \
                              --remove data/core/images/units/orcs/leader-ranged.png

This command would rename the spritesheet's name to leader-and-grunt-spritesheet.png

 utils/spritesheet_manager.py --rename data/core/images/units/orcs/leader-spritesheet.png \
                              data/core/images/units/orcs/leader-and-grunt-spritesheet.png

C++ spritesheet handling

To be able to use this tool an image loader would have to be implemented in C++. It would be responsible for loading single images from spritesheets using the configuration files.

Restructuring the modifications

The first step toward integrating the spritesheet system into the current image loading code would be restructuring the image modification handling. Currently image modificators are stored as WML strings, and handled inside a giant loop. I would like to create a image::modificator class hierarchy that would provide a simpler and more elegant way to represent and manipulate modifications. The modification class would look similar to this:

namespace image {
  class modification
  {
  public:
    static modification* decode(const std::string&);

    virtual ~modification() {}
    virtual surface operator ()(const surface&) const = 0;
  };
}

All the modification functors would be based on functors from image_function.cpp with the difference that every modification would be able to decode itself from a string.

The decode function would process the string and create an appropriate modification. If the string has more then one modification in it an instance of a composite_modification would be created. The composite_modifiation would hold many modifications in itself and call all of them in order when called. This change would make some parts of the code simpler and more readable. For example this part from display.cpp:

mod << "~CS("
    << tod.red << ","
    << tod.green << ","
    << tod.blue
    << ")"; // CS

would be changed to a simpler

mod.push_back(new image::color_shift_mod(tod.red, tod.green, tod.blue));

The giant loop in load_image_sub_file would be changed to something similar to

foreach(modification* mod, val_.modifications_) {
 surf = (*mod)(surf);
 delete mod;
}

Important. Introducing the modification functors isn't in any way essential for the spritesheet manager. If you don't like the idea, the proposal can be easily implemented without them.

Spritesheet management

Having the modifications implemented in this way would make the spritesheet management code a little bit cleaner, since it would use the crop_modification to load the images. The code would be fairly simple. There would be a spritesheet manager singleton class, which would load a WML spritesheet configuration file. The main part would be in the image::locator constructors. All the constructors taking filenames as arguments would have to run the parse_arguments method (atm only two of them do). The parse_arguments method would be modified to include code similar to this:

spritesheet_manager& spr_mgr = spritesheet_manager::get();
std::string& filename = val_.filename_;

if(spr_mgr.image_within_spritesheet(filename) {
  val_.filename_ = spr_mgr.get_spritesheet_for(filename);
  val_.modifications_.push_front(spr_mgr.get_crop_for(filename));
}

The spritesheet_manager class would read the config file from data/hardwired/spritesheets.cfg. This file would be the interface between the spritesheet tool and the spritesheet manager. After reading the config file (in the same way it is done in load_font_config) it would create a mapping between filenames and sprite structures. The sprite struct would be private withing the manager and would store all the information needed to create a crop_modification.

The get_crop_for method would look like this

modification* get_crop_for(const std::string& filename) {
  map<std::string, sprite>::iterator it = sprites.find(filename);

  if(it == sprites.end()) {
    // this sould never happen, throw error
  }

  sprite& spr = it->second;

  return new crop_modification(spr.x, spr.y, spr.width, spr.height);
}

As you can see the modification functor makes the code cleaner (no stringstreams have to be used).

Stage 2 :: GUI

Abstract

The GUI would allow the artist to change the arrangement of sprites using drag and drop. Every command would by default show the GUI for the artist to make modifications to the proposed arrangement. The tool would no longer have to be used through the command line.

Most of the GUI features would benefit a lot from suggestions from the artists. The main goal of the GUI is to make the whole process as simple and intuitive as possible.

To implement the GUI PyGame or some similar library would be used.

Substages

These are the key features the GUI should provide:

• Loading and displaying the spritesheet
• Modifying and saving
• Adding and removing images from spritesheets
• Packing and unpacking

I also have some ideas that could be implemented if there is enought time:

• Tabs that would allow having many spritesheets open at the same time
• Some tools for modification (like selecting and moving multiple spritesheets)

Sketches

Drag and drop. The user would modify the arrangement of sprites by just dragging them around.

Packing / unpacking. The user would select the spritesheets he wants to pack/unpack and apply the changes.

Stage 3 :: Reasonable suggestions

To make the artists' lives easier a packing algorithm would be implemented to generate reasonable suggestions of the arrangements of sprites. The algorithm would optimize many apsects of the arrangement like the total area of the spritesheet, arranging the sprites of a single animation in one row, etc.

Since the optimal packing of rectangles of various sizes within a smallest possible rectangle is an NP-hard problem, I would have to use some stochastic optimization algorithm to do that. I think genetic algorithms would do better for this problem than simulated annealing because they simultaneously search through a broader space than SA.

In most cases however the images have the same size. I would implement a deterministic algoirithm for that case that would find the optimal solution.

General notes

Most of the code would be unit tested. Especially the spritesheet packing and unpacking.

Use cases

Creating a spritesheet

1. The user starts up the tool
2. The GUI is displayed
3. The user clicks the Create spritesheet button
4. A file selection dialog is displayed
5. The user selects the sprites he or she wants to merge and clicks Ok
6. The GUI displays the suggested sprite arrangement.
7. The user modifies the arrangement by dragging the sprites into the desired positions and clicks Apply
8. A spritesheet file is created. A spritesheet entry is added to the spritesheet configuration file. The image files are removed.
9. The user closes the tool

Modifying a spritesheet

1. The user starts up the tool
2. The GUI is displayed
3. The user clicks Load spritesheet
4. A spritesheet selection dialog is dispalyed
5. The user selects the spritesheet he or she wants to modify
6. The GUI displays the spritesheet
7. The user does any of these actions any number of times
   1. Modifying the spritesheet by dragging sprites around
   2. Clicking Add sprites
      1. An image selection dialog is displayed
      2. The user selects the images he or she wants to add and clicks Ok
      3. The images are added to the spritesheet and arranged using the suggestion algorithm(the alogirthm would only arrange the newly added sprites).
   3. Clicking Remove sprites
      1. An image selection dialog is displayed
      2. The user selects the images he or she wants to remove and clicks Ok
      3. The images are removed from the spritesheet leaving gaps in the spritesheet (the user can now click Rearrange to get rid of the gaps)
   4. Clicking Back
      1. The last action is cancelled
   5. Clicking Rearrange
      1. The algorithm rearranges the sprites to optimize its quality function
8. The user clicks Save spritesheet
9. The images removed from the spritesheet are recreated; The spritesheet gets saved; the config file updated; images added to the spritesheet are removed.
10. The user closes the tool

Packing/unpacking spritesheets

1. The user starts up the tool
2. The GUI is displayed
3. The user selects the pack/unpack tab
4. The packing/unpacking view is displayed
5. The user selects the spritesheets he or she wants to pack/unpack and clicks the Pack/Unpack button
6. Selected spritesheets get packed/unpacked. (If any images have changed size while being unpacked, the user would have to confirm/modify the new arrangement (This would only work if there would be no more than one spritesheet with this problem or the spritesheet tabs would be implemented))
7. The user closes the tool

IRC

automagic

SoC Application

SoC Application

Questionnaire

1) Basics

1.1) Write a small introduction to yourself.

My name is Karol Kozub. I am interested in programming, mathematics and AI.

1.2) State your preferred email address.

karol <dot> kozub <at> gmail <dot> com

1.3) If you have chosen a nick for IRC and Wesnoth forums, what is it?

automagic

1.4) Why do you want to participate in summer of code?

I want to participate in an interesting project and gain experience.

1.5) What are you studying, subject, level and school?

I am a 4th year undergraduate student at the Polish-Japanese Institute of IT.

1.6) What country are you from, at what time are you most likely to be able to join IRC?

I am from Poland. Im most likely to join IRC in the evenings (around 8 PM GMT+1)

1.7) Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when.

At the end of June I will defend my bachelor's thesis.

2) Experience

2.1) What programs/software have you worked on before?

I have written many programs in C/C++ for programming competitions, built some game playing bots in various languages, written some AI programs and some games in various languages and developed some PHP/MySQL services.

2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own)

I have worked on some school projects in a group of 2-4 people.

2.3) Have you participated to the Google Summer of Code before? As a mentor or a student? In what project? Were you successful? If not, why?

No.

2.4) Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.

No.

2.5) Gaming experience - Are you a gamer?

I enjoy playing games, but I recently don't have time to play. I really like writing AIs for games.

2.5.1) What type of gamer are you?

Casual.

2.5.2) What type of games?

I like strategy games like starcraft and RPGs (especially MMO).

2.5.3) What type of opponents do you prefer?

Skilled and polite.

2.5.4) Are you more interested in story or gameplay?

Gameplay.

2.5.5) Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.

I have played for a few hours.

2.6) If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for GSoC. If you have gained commit access to our S­­V­­N (during the evaluation period or earlier) please state so.

I haven't.

3) Communication skills

3.1) Though most of our developers are not native English speakers, English is the project's working language. Describe your fluency level in written English.

I think my English is pretty good. I would rank myself at the CAE level.

3.2) What spoken languages are you fluent in?

English and Polish.

3.3) Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.

I think I am, but It's hard to say.

3.4) Do you give constructive advice?

I hope so.

3.5) Do you receive advice well?

Yes.

3.6) Are you good at sorting useful criticisms from useless ones?

I think I can distinguish these two at least in most cases.

3.7) How autonomous are you when developing ? Would you rather discuss intensively changes and not start coding until you know what you want to do or would you rather code a proof of concept to "see how it turn out", taking the risk of having it thrown away if it doesn't match what the project want

If I have an idea that seems to have some potential then I usually write the code, see how it works and then discard it if it's useless.

4) Project

4.1) Did you select a project from our list? If that is the case, what project did you select? What do you want to especially concentrate on?

I have selected the spritesheets idea. I would like to focus on making the spritesheet management tool easy to use and convenient for the artists.

4.2) If you have invented your own project, please describe the project and the scope.

I have not.

4.3) Why did you choose this project?

I like game development and I find your game interesting.

4.4) Include an estimated timeline for your work on the project. Don't forget to mention special things like "I booked holidays between A and B" and "I got an exam at ABC and won't be doing much then".

See timeline.

4.5) Include as much technical detail about your implementation as you can

See implementation details.

4.6) What do you expect to gain from this project?

Experience and pleasure.

4.7) What would make you stay in the Wesnoth community after the conclusion of SOC?

An opportunity to work on some aspect of the game that would benefit from my knowledge about AI and machine learning.

5) Practical considerations

5.1) Are you familiar with any of the following tools or languages?

• Sub­­version (used for all commits)

I used sub­­version a couple of times.

• C++ (language used for all the normal source code)

I am really good at this language.

• STL, Boost, Sdl (C++ libraries used by Wesnoth)

I know STL pretty well and have used some Boost libraries (ASIO, SmartPtr, Regex)

• Python (optional, mainly used for tools)

I have written some scripts in python.

• build environments (eg cmake/scons)

I know how to write makefiles and rakefiles. I have edited some ant build files once or twice.

• WML (the wesnoth specific scenario language)

I don't know WML.

• Lua (used in combination with WML to create scenarios)

I don't know Lua.

5.2) Which tools do you normally use for development? Why do you use them?

I usually use git for version control, rake as a build tool and emacs for editing text. I have used make but switched to rake because I find ruby more convenient and succinct than bash. I occasionally use gdb.

5.3) What programming languages are you fluent in?

I'm fluent in C, C++, Java, Ruby and Javascript. I have written some scripts in bash, python and scheme and I knew pascal ~10 years ago.

5.4) Would you mind talking with your mentor on telephone / internet phone? We would like to have a backup way for communications for the case that somehow emails and IRC do fail. If you are willing to do so, please do list a phone number (including international code) so that we are able to contact you. You should probably *only* add this number in the application for you submit to google since the info in the wiki is available in public. We will *not* make any use of your number unless some case of "there is no way to contact you" does arise!

I have no objections to talking through skype.

A simple prototype

I have created a simple prototype of the tool. It doesn't have much functionality, but it prooves that python is a good language to use for the task.

The tool reads the config file and displays a very simple GUI. When the GUI is clicked the spritesheet gets packed or unpacked. The config file's structure is the same as I intend to use in the project.

A pair of screenshots representing the whole functionality of the script.

Directory structure packed:

 $ tree
 .
 |-- config
 |   `-- spritesheets.cfg
 |-- images
 |   `-- leader-attack-spritesheet.png
 `-- prototype.py

Directory structure unpacked:

 $ tree
 .
 |-- config
 |   `-- spritesheets.cfg
 |-- images
 |   |-- leader-attack-1.png
 |   |-- leader-attack-2.png
 |   |-- leader-attack-3.png
 |   |-- leader-attack-4.png
 |   `-- leader-attack-5.png
 `-- prototype.py

The spritesheets.cfg file:

[spritesheet]
  name=images/leader-attack-spritesheet.png
  is_packed=false
  [image]
    name=images/leader-attack-1.png
    x=1
    y=1
    width=72
    height=72
  [/image]
  [image]
    name=images/leader-attack-2.png
    x=73
    y=1
    width=72
    height=72
  [/image]
  [image]
    name=images/leader-attack-3.png
    x=145
    y=1
    width=72
    height=72
  [/image]
  [image]
    name=images/leader-attack-4.png
    x=217
    y=1
    width=72
    height=72
  [/image]
  [image]
    name=images/leader-attack-5.png
    x=289
    y=1
    width=72
    height=72
  [/image]
[/spritesheet]

For displaying the GUI and loading/manipulating/saving png images the PyGame library was used. The complete source code can be viewed here: tool-prototype.py. The code isn't too clean - it was intended to work, not to be used in the future (I also don't have that much spare time at the moment to polish prototypes unfortunately).

Patches

• patch #2633 refactoring image modification parsing
• commit #49235 - unit tests for the image modification parsing

Refactoring modificaiton parsing

I have finally arrived at a seemingly working solution. It hasn't been tested yet - I have only played the game build with this change and haven't noticed any differences. I will write some unit tests to make sure it works when I get more time.

Abstract

While reading through image.cpp to prepare my proposal I have noticed the ugly almost 400 line long loop in the image::locator::load_image_sub_file method. In the process of analysing it I have devised a way of refactoring it into smaller pieces. This patch is an implementation of that idea.

Essentially the image::function hierarchy is repalced with the image::modification hierarchy and the image::modification::decode(const std::string&) static method is capable of reading the image::modification objects from the modification string.

Modification class

The modification class is almost the same as the function class it replaces. It only adds a priority virtual method for determining modification priority. Here it is:

class modification
{
public:
	static modification_queue decode(const std::string&);

	virtual ~modification() {}

	virtual surface operator()(const surface& src) const = 0;
	virtual int priority() const { return 0; }
};

Decoding

This is the main function:

modification_queue modification::decode(const std::string& encoded_mods)
{
	modification_queue mods;
	
	foreach(const std::string& encoded_mod, 
		utils::parenthetical_split(encoded_mods, '~')) {
		modification* mod = decode_modification(encoded_mod);
		
		if(mod) {
			mods.push(mod);
		}
	}

	return mods;
}

It splits the modificaitons by tildes and decodes them using the decode_modification function. Here is that function:

modification* decode_modification(const std::string& encoded_mod)
{
	std::vector<std::string> split = utils::parenthetical_split(encoded_mod);
	
	// Important!
	// Modifications not seperated by tildes are not supported
	// ~TC(...)~TC(...) OK
	// ~TC(...)TC(...)  NOT OK
	if(split.size() != 2) {
		ERR_DP << "error parsing image modifications: " 
		       << encoded_mod << "\n";
		return NULL;
	}
	
	std::string mod_type = split[0];
	std::string args = split[1];
	
	if(mod_parsers.find(mod_type) == mod_parsers.end()) {
		ERR_DP << "unknown image function in path: " 
		       << mod_type << '\n';
		return NULL;
	}
	
	return (*mod_parsers[mod_type])(args);
}	

Since the modifications are supposed to be already seperated only modifications seperated by tildes are supported (otherwise the split will have more than 2 elements and an error will be returned). Then the mod_parsers map is checked to see if the modification type was registered. If everything goes well the modification parser is applied to arguments to create a new instance of a modification.

Registering parsers

Modificaiton parsers are registered using the REGISTER_MOD_PARSER macro.

#define REGISTER_MOD_PARSER(type, args_var)     	               \
	modification* parse_##type##_mod(const std::string&);          \
	struct parse_##type##_mod_registration                         \
	{                                                              \
	        parse_##type##_mod_registration()                      \
	        {                                                      \
			mod_parsers[#type] = &parse_##type##_mod;      \
                }                                                      \
        } parse_##type##_mod_registration_aux;                         \
        modification* parse_##type##_mod(const std::string& args_var)

It seems complicated but it isn't. It delcares the parser function, defines a struct and creates an instance of that struct to register the function and then generates the first line of the function definition.

For example:

REGISTER_MOD_PARSER(BL, args)
{
	const int depth = std::max<int>(0, lexical_cast_default<int>(args));

	return new bl_modification(depth);
}

Would be evaluated to (I modified whitespace for readability):

modification* parse_BL_mod(const std::string&);

 
struct parse_BL_mod_registration
{
        parse_BL_mod_registration()
        {
		mod_parsers["BL"] = &parse_BL_mod;
        }
} parse_BL_mod_registration_aux;


modification* parse_BL_mod(const std::string& args)
{
	const int depth = std::max<int>(0, lexical_cast_default<int>(args));

	return new bl_modification(depth);
}

The structure is necessary to evaluate the mod_parsers["BL"] = &parse_BL_mod; line at global scope (i.e. without being within any function). Everything is embedded in an anonymous namespace.

The modificaiton queue

You may ask why is there a modificaiton queue and some weird mod_ptr_wrapper_. The queue is necessary to make the RC modifications be executed first. Here is its definition:

typedef std::priority_queue<mod_ptr_wrapper_> modification_queue;

The wrapper is necessary for the queue to serve its purpose. The queue was intended to contain modificaiton pointers. The problem is that the priority queue bases its decisions on the operator<, which cannot be redefined for pointers. That's why I have created a wrapper for the pointer, which has the correct operator<, and in all other cases should behave like a modification* - It has a conversion operator and an implicit constructor.

class mod_ptr_wrapper_
{
public:
	mod_ptr_wrapper_(modification* mod)
		:mod_(mod)
	{}

	operator modification*() const
	{
		return mod_;
	}

	bool operator<(const mod_ptr_wrapper_& mpw) const
	{
		return mod_->priority() < mpw.mod_->priority();
	}

private:
	modification* mod_;
};

Results

This patch at the moment only changes the big loop in locator's' file loading method. The whole method had around 400 lines of code. Now it can be easily read on one screen.

surface locator::load_image_sub_file() const
{
	surface surf = get_image(val_.filename_, UNSCALED);
	if(surf == NULL)
		return NULL;

	if(val_.loc_.valid()) {
		SDL_Rect srcrect = create_rect(
				((tile_size*3) / 4) * val_.loc_.x
				, tile_size * val_.loc_.y + (tile_size / 2) * (val_.loc_.x % 2)
				, tile_size
				, tile_size);

		if(val_.center_x_ >= 0 && val_.center_y_>= 0){
			srcrect.x += surf->w/2 - val_.center_x_;
			srcrect.y += surf->h/2 - val_.center_y_;
		}

		surface cut(cut_surface(surf, srcrect));
		surf = mask_surface(cut, get_hexmask());
	}

	modification_queue mods = modification::decode(val_.modifications_);

	for(; !mods.empty(); mods.pop()) {
		modification* mod = mods.top();

		surf = (*mod)(surf);
		delete mod;
	}

	return surf;
}