{{SoC2010Student}}

=Description=
I want add sprite sheet support to Wesnoth. The general idea is to assemble multiple small images into few bigger.

=IRC=
Shuger

=Questionnaire=
http://wiki.wesnoth.org/User:Shuger

=Implementation=
==Sprite Formats==
In my idea of implementation there are three possible sprite formats:
* separate files
* normal sprite sheet
* optimized sprite sheet
===separate files===
Current way of managing sprites, each image in a separate file.

wml remains the same.

===normal sprite sheet===
Multiple sprites on one big image. This is a way for artists to work if they prefer sprite sheets over separate images. The artist can place sprites in a sheet in any way he/she wants.

example wml:
[frame]
x_position = 32
y_position = 32
x_size = 32
y_size = 32
image="units/elves-wood/archer+female-spritesheet.png"
[/frame]

x_position and y_position - position of the sprite in the sheet, in pixels from top left corner(because of the way SDL coordinate system works). 
x_size and y_size - optimized sprite size.

===optimzed sprite sheet===
This format is not for manual editing. It is created from separete files or normal sprite sheet automatically. To generate it special packing algorithms will be used to optimize it's size. This will be the format normally used. Generation should occur at build time uing a custom tool added to build process. It will be possible too run tool manually if someon desires.

Algorithm:
1. Parse wml file created by artist and collect all information about needed sprites for certain unit.
2. Load all needed images, parts normal sprite sheet specified by wml file.
3. Optimze all sprites by cutting unneeded part of sprites.
4. Use a rectangle packing algorithm to pack them into as small space as possible.
5. Bake optimized sprites onto new optimized sprite sheet using information from step 4. Write it to a new file.
6. Update wml file with changing all references to optimized version and adding each sprite offset and size information.

example wml frame definition:
[frame]
x_position = 32
y_position = 32
x_size = 24
y_size = 24
x_offset = 6
y_offset = 6
image="units/elves-wood/archer+female-spritesheet.png"
[/frame]
notes:

x_position and y_position - position of the sprite in the sheet, in pixels from top left corner(because of the way SDL coordinate system works).

x_size and y_size - optimized sprite size.

x_offset and y_offset - If image was optimized by cutting transparent border it needs to be offset during blitting.

Comment on step 3:
Many sprites have image (say 72x72 pixels) where only a part is actually a sprite and the rest is wide transparent border. This doesn't considerably impact image size on disk, because of png compression but is taking significant amount of uneeded memory when loaded into SDL surface (which doesn't use compression). The point of this step is to crop the image by finding a minimal rectangle to fit entire sprite in and then store the size and offset of this rectangle in comparison to original image in order to blit image properly.

==Memory==
First gain for the memory will come from cropping sprites as described earlier. Second will come from using a cache. There is no need to store every spritesheet in uncompressed format as it will requie a lot of memory even if not needed. On the other hand disk operations are very slow so reading spriteshhets during game should be avoided. The solution to this is to hold currently unused sprites in compressed format. SDL_image allows it. Instead of directly loading into a surface images can be loaded without parsing into memory. It will take only as much memory as file on hard drive. Also compressing one big image gives better results then many small ones.

First step is to load image from hard drive using SDL_RWFromFile function. Then once cached sprite sheet will be needed it will unpacked using IMG_Load_RW (this is from SDL_image library). Once not needed anymore, uncompressed surface will be deleted from memory.

This may require some changes to Wesnoth cache code. Also while it may seem that uncompressing raw data is performance loss, it's actually not that slow compared to reading from disk which takes most of the time neded to load image completely.

==Performance==
Croping sprites will increase blitting speed beacause there will be less data for SL to process in blitting functions.

==Workfolw==
1. Artist makes sprite bay making separate images or normal sprite sheet.

2. He can test those normally. The game will support both formats.

3. Special tool will be run at build time to process al images and sprite sheets

2010-04-08T11:22:56Z

Shuger: /* Why do you want to participate in summer of code? */

==Basics==

====Write a small introduction to yourself.====
I'm computer science student living in Poland. I'm interested generally in game davelopment but i usually focus on graphics.

====Email, IRC, Forums====
* Email - shugerpl@gmail.com
* IRC - shuger
* Forums - shuger

====Why do you want to participate in summer of code?====
I' want to improve my skills and i always wanted to get involved into some open-source community. GSoC is a great occasion becaouse it allows me to work on it full time.

====What are you studying, subject, level and school?====
I'm currently studying Computer Science, year 4, specialty: internet technologies and algorithms. At Gdansk University of Technology; Faculty of Electronics, Telecommunications and Informatics

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

I'm from Poland.

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

==Experience==

====What programs/software have you worked on before?====
Nothing publicly released, mostly some little projects of my own, games mostly. Also a whole lot of projects for university classes.

====Have you developed software in a team environment before? ====
Yes, most of my university projects are team projects. Team sizes ranged from two to four.

====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 i didn't.

====Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.====
I'm not.

====Gaming experience - Are you a gamer?====
Sure.

====What type of gamer are you?====
I like to play games but not so much as u used too. While I still play i now spend more times working on my own game projects ratter then play others.

====What type of games?====
RPGs, strategies, platformers, sometimes some FPS. I play lot of indie games.

====What type of opponents do you prefer?====
No strong preference here but i favor real people over AI if i know them personally.

====Are you more interested in story or gameplay?====
I thnik both are important. But in my opinion story can put a game in a whole aother dimension so maybe a bit more in story.

====Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.====
I played singleplayer since i enjoyed storylines. I Tried multi too but didn't liked it as much.

====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.====

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

My English is pretty fluent, i don't have any problem understanding it in speech or text but i sometimes make mistakes when speaking/writing.

====What spoken languages are you fluent in?====
Polish, english.

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

====Do you give constructive advice?====

====Do you receive advice well?====

====Are you good at sorting useful criticisms from useless ones?====

====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====

==Project==

====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 chose spritesheet implementation, i would like to focus on reducing memory requiements and increasing performace.
====If you have invented your own project, please describe the project and the scope.====

====Why did you choose this project?====
Because it fits my area of interest. I am working on my own 2d game which -same as Wesnoth - uses SDL library for graphics. I have been investigating performance issues and this project would allow me to spend a lot of time doing things that greatly interests me. A privilege i don't have, when there are university projects deadlines to meet.

====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".====

====Include as much technical detail about your implementation as you can====

TODO: insert link here

====What do you expect to gain from this project?====
Experience and satisfaction.

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

==Practical considerations==

====Are you familiar with any of the following tools or languages?====
* Subversion (used for all commits) - I used it and i know the basics
* C++ (language used for all the normal source code) - 4+ years of experience, my langueage of choice for most of things
* STL, Boost, Sdl (C++ libraries used by Wesnoth):
** STL - i use it all the time
** Boost - never used it
** SDL - i have a lot experience with it, i first used SDL when i started learining C++, been using it ever since. projects i did with it involved mostly event handling and video (both vanilla SDL blitting and using it for creating context and window handling for OpenGL)
* Python (optional, mainly used for tools) - i know all the basics needed to write simple windows application and i'm actively learning it now
* build environments (eg cmake/autotools/scons) - not much experience here but i know how to create and edit basic makefile
* WML (the wesnoth specific scenario language) - not familiar, catching up right now
* Lua (used in combination with WML to create scenarios) - i know the basics

====Which tools do you normally use for development? Why do you use them?====
* Windows: Visual Studio 2010 - because great code completion, debugging and profiling
* Linux: Codeblocks or vim + g++ + make -

====What programming languages are you fluent in?====
* C\C++ - very fluent, i use them all the time
* C# and Java - a bit less but still.
* Python - not as good as C++ but actively learning (i like the speed of development)

====Would you mind talking with your mentor on telephone / internet phone?====
I don't mind at all.

GSoC Sprite Sheets Shuger

2010-04-08T11:20:48Z

Shuger: /* Description */

{{SoC2010Student}}

=Description=
I want add sprite sheet support to Wesnoth. The general idea is to assemble multiple small images a few bigger.

=IRC=
Shuger

=Questionnaire=
http://wiki.wesnoth.org/User:Shuger

=Implementation=
==Sprite Formats==
In my idea of implementation there are three possible sprite formats:
* separate files
* normal sprite sheet
* optimized sprite sheet
===separate files===
Current way of amanging sprites, each image in a sepatare file.

wml remains the same.
===normal sprite sheet===
Multiple sprites on one big image. This is a way for artists to work if they prefer sprite sheets over separate images. The artist can place sprites in a sheet in any way he/she wants.

example wml:
[frame]
x_position = 32
y_position = 32
x_size = 32
y_size = 32
image="units/elves-wood/archer+female-spritesheet.png"
[/frame]

x_position and y_position - position of the sprite in the sheet, in pixels from top left corner(because of the way SDL coordinate system works). 
x_size and y_size - optimized sprite size.

===optimzed sprite sheet===
This format is not for manual editing. It is created from separete files or normal sprite sheet automatically. To generate it special packing algorithms will be used to optimize it's size. This will be the format normally used. Generation should occur at build time uing a custom tool added to build process. It will be possible too run tool manually if someon desires.

Algorithm:
1. Parse wml file created by artist and collect all information about needed sprites for certain unit.
2. Load all needed images, parts normal sprite sheet specified by wml file.
3. Optimze all sprites by cutting unneeded part of sprites.
4. Use a rectangle packing algorithm to pack them into as small space as possible.
5. Bake optimized sprites onto new optimized sprite sheet using information from step 4. Write it to a new file.
6. Update wml file with changing all references to optimized version and adding each sprite offset and size information.

example wml frame definition:
[frame]
x_position = 32
y_position = 32
x_size = 24
y_size = 24
x_offset = 6
y_offset = 6
image="units/elves-wood/archer+female-spritesheet.png"
[/frame]
notes:

x_position and y_position - position of the sprite in the sheet, in pixels from top left corner(because of the way SDL coordinate system works).

x_size and y_size - optimized sprite size.

x_offset and y_offset - If image was optimized by cutting transparent border it needs to be offset during blitting.

Comment on step 3:
Many sprites have image (say 72x72 pixels) where only a part is actually a sprite and the rest is wide transparent border. This doesn't considerably impact image size on disk, because of png compression but is taking significant amount of uneeded memory when loaded into SDL surface (which doesn't use compression). The point of this step is to crop the image by finding a minimal rectangle to fit entire sprite in and then store the size and offset of this rectangle in comparison to original image in order to blit image properly.

==Workfolw==
1. Artist makes sprite bay making separate images or normal sprite sheet.

2. He can test those normally. The game will support both formats.

3. Special tool will be run at build time to process al images and sprite sheets