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 manager 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 management. (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 management system would have to be implemented in C++. It would be responsible for loading single images from spritesheets using the configuration files.

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.

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 haven't. Sorry.

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 sprite sheets idea. I think I could use some stochastic optimization algorithm to efficiently pack the images.

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.

SoC2011 Automagic

Contents