Difference between revisions of "SoC2011 Automagic"

From The Battle for Wesnoth Wiki
Line 32: Line 32:
  
 
=Implementation details=
 
=Implementation details=
===Stage 1===
+
===Stage 1 :: Sprite packing tool===
 
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.
 
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.
  
 
If it turns out that the rectangles have in many cases the same size of at least one of the dimensions  
 
If it turns out that the rectangles have in many cases the same size of at least one of the dimensions  
 
an optimal solution could be acheived using convex optimization algorithms.
 
an optimal solution could be acheived using convex optimization algorithms.
===Stage 2===
+
===Stage 2 :: Image management modification===
===Stage 3===
+
===Stage 3 :: Build process integration===
  
 
=IRC=
 
=IRC=

Revision as of 23:25, 31 March 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 - Sprite Sheets

I would like to implement a tool that would pack images that belong together into spritesheets and also create files describing these spritesheets (i.e. a mapping between an image name and coordinates of the image on the spritesheet). This tool would be embedded in the build process. On the other end there would be an ImageManager/ImageFactory class that would read these files and supply images based on their name.

Timeline

Stage 0 April 25 - May 22 I get to know the codebase, read the documentation, discuss project details with my mentor.
Stage 1 May 23 - June 30 I implement the sprite packing tool. (Around the end of June I will have one exam and will have to defend my bachelor's thesis)
Stage 2 July 1 - July 14 I modify the image management system to use the generated spritesheets.
Stage 3 July 15 - August 7 I integrate my solution with the build process. (I will probably be on holidays between Aug 1 - 7)
Buffer time August 8 - August 22 I write documentation.

Implementation details

Stage 1 :: Sprite packing tool

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.

If it turns out that the rectangles have in many cases the same size of at least one of the dimensions an optimal solution could be acheived using convex optimization algorithms.

Stage 2 :: Image management modification

Stage 3 :: Build process integration

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 basic scripts in python. It is IMO very similar to Ruby (only the syntax is different).
  • 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.

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.