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 - Sprite Sheets

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

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.

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. Image loading would consist of these steps:

1. if (the image hasn't been loaded yet) {
2.   if (the image isn't stored in a spritesheet) {
3.     load the image from file
4.   } else {
5.     if (the spritesheet isn't loaded) {
6.       load the spritesheet
7.     }
8.     cut the image out using the cut_surface function
9.   }
A. }
B. return the image

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

Stage 2 :: GUI

The GUI would allow the artist to change the arrangement of sprites. Every command would by default show the GUI for the artist to make modifications to the proposed arrangement. The GUI would support drag-and-drop.

The GUI would allow changing the arrangement using drag and drop

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

Stage 3 :: Optimal 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 will 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 patche