Difference between revisions of "SoC2011 Automagic"

From The Battle for Wesnoth Wiki
m
Line 115: Line 115:
  
 
The first step toward integrating the spritesheet system into the current image loading code would be restructuring the image modification handling.
 
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:
+
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:
 
<pre>
 
<pre>
 
namespace image {
 
namespace image {
Line 127: Line 127:
 
</pre>
 
</pre>
  
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.
+
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'':
 
This change would make some parts of the code simpler and more readable. For example this part from ''display.cpp'':
 
<pre>
 
<pre>
Line 153: Line 153:
 
The code would be fairly simple. There would be a spritesheet manager singleton class, which would load a WML spritesheet configuration file.
 
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 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:
+
The ''parse_arguments'' method would be modified to include code similar to this:
 
<pre>
 
<pre>
 
spritesheet_manager& spr_mgr = spritesheet_manager::get();
 
spritesheet_manager& spr_mgr = spritesheet_manager::get();

Revision as of 10:42, 7 April 2011


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 image loader 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 May 23 - June 21 Implementing the sprite packing tool's core and the image loader. (Around the end of June I will have one exam and will have to defend my bachelor's thesis)
Stage 2 June 22 - July 21 Implementing a GUI for the tool.
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 Writing 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.

Use cases

The tool would support the following actions:

  • 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=0
     y=0
     width=72
     height=72
   [/image]
   [image]
     (...)
   [/image]
 [/spritesheet]


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


Spritesheet manager

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.

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&);
    void operator ()(surface&) = 0;
  };
}

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 much simpler

mod.push_back(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);
}

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.is_within_spritesheet(filename) {
  val_.filename_ = spr_mgr.get_spritesheet_for(filename);
  val_.modifications_.push_back(spr_mgr.get_crop_for(filename));
}

The spritesheet manager would have a map of sprite structures read from the spritesheet configuration file. For example 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()) {
    // throw error
  }

  sprite& spr = it->second;

  return 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

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.

spritesheet-manager-drag-and-drop.png
Drag and drop
spritesheet-manager-pack-and-unpack.png
Packing / unpacking

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

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.

IRC

automagic

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 SVN (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?

  • Subversion (used for all commits)
I used subversion 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.