SoC2012 Bloodycoin Particle Engine

This page is related to Summer of Code 2012

See the list of Summer of Code 2012 Ideas

This is a Summer of Code 2012 student page

Description

Justas Tomkus - Particle Engine

Implementing particle engine in a library-like fashion, using existing game's graphic functionality and SDL library. Final version of this engine would allow to use it anywhere on map with other drawing functions, given required init is done.

In addition to simple pixel drawing, I am ready to implement version where small alpha transparent images are blitted for particles. Color transitions for particles wouldn't be a problem either.

IRC

bloodycoin, S_arms, bloodyGP

SoC Application

Submitted to google

Questionnaire

1) Basics

1.1) Write a small introduction to yourself.

My name is Justas Tomkus, I am 21 years, Lithuanian. Studying Computer Science, specialising in programming, currently in sixth semester of Bachelor.

1.2) State your preferred email address.

justas.tomkus at google.com

1.3) If you have chosen a nick for IRC and Wesnoth forums, what is it?

bloodycoin

1.4) Why do you want to participate in summer of code?

Fame, money and google T-shirt :)

Personal development:

• Experience development in a big project, team
• Polish my coding skills and design

Also I am all for open source and I wanted to join for some time. Google summer of code is nice starting point. Moreover as I am approaching my graduation in university, I am required to take practise in some company to get real-life working experience, and GSoC lets me combine university requirement with contributing to open source.

1.5) What are you studying, subject, level and school?

I study in Kaunas University of Technology, Lithuania, 6th semester of Bachelor in Computer Science, specialising in programming.

Currently I am in Erasmus exchange programme, studying in Upper Austria University of Applied Sciences, Hagenberg. Here I am studying master courses mainly focused on game production and programming.

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

I am from Lithuania, currently living in Austria (due to Erasmus). Probability of reaching me on IRC could be described as Gaussian with peak being at 23:00 GMT and deviation of 3 hours, so it's from ~20:00 GMT to ~2:00 GMT. Thought I am lurking in IRC most of the time.

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

I have university lectures till July and I plan to take a week-long tour in mid July (going back home to Lithuania). Other than that, I will be committed to GSoC.

2) Experience

2.1) What programs/software have you worked on before?

• For my 2nd semester in university I have made spring simulator in C++ using SDL, unfortunately code didn't survive.
• For my 3rd semester in university I have made little 2D game (more of raytraycer) with python and OpenGL ([code])
• For my 5th semester in university I have made mock-up digital notebook using C++ and QT library ([code])
• For my 5th semester in university I have made prototype DB system for museum exponates using Python and Django framework
• I have participated in last 3 Global gamejam event and few local ones. In last 2 I have used Lua with Love2D framework ([code])
• For university assignment I was forced to use Java. (used with SWING library, building GUI, and with Threads)
• I took parallel computing course (assignments in c++ with OpenMP, MPI, java with native threads, CSP, google Go)
• Used Matlab for mathematical computations in university and Python for my own.
• Last year I made mock-up IMGUI in C using SDL ([code])

As for software, I mainly use Vim and terminal. Though I have used NetBeans and Eclipse. Have some experience with Photoshop and Illustrator, Blender for 3D modelling.

(sidenote: through these projects my code writing style is quite different, but that's because I am still searching for it)

2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own)

Yes, few projects I have developed were teamwork (mainly Gamejam ones). Have both worked with people in same workplace and remotely.

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?

Yes, last year I tried applying to ScummVM and Plan9, proposing to do IMGUI library. Unfortunately, I was not accepted in neither. I suspect, because I was late with my application, wasn't communicating much and/or neither project was pleased with IMGUI style libraries.

2.4) Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.

Not yet. Unless my games count, because they are open source.

2.5) Gaming experience - Are you a gamer?

Yes, I consider myself one.

2.5.1) What type of gamer are you?

Exploring one. I want to see the what are game possibilities and limits, what story does it offer.

2.5.2) What type of games?

In no particular order:

• Strategy and tycoons(e.g.: Pharaoh, Civilization series, Transport tycoon, Roller Coaster tycoon 1, Age of Empires)
• Adventure RPG (e.g.: Tales of Monkey Island, Spyro, Megaman Legends, Castlevania series, Final Fantasy series, Brief of Fire series, Bastion, Crono Trigger, Elder Scrolls series)
• rarely MMORPG (e.g.: Maple Story)
• Puzzle and logic games (e.g.: Cogs, Crazy machines 1&2, Braid, Monthy Python and Holy Grail)
• Dwarf Fortress, because in my view, it doesn't fit to any category.
• Most commercial indie games, though they are mainly adventure (e.g.: Aquaria, Cave Story, Gish, World of Goo)

2.5.3) What type of opponents do you prefer?

Depends on a game, but mainly challenging ones, be it Human player or AI.

2.5.4) Are you more interested in story or gameplay?

Story I would like to say, but story without good gameplay is not a game. Likewise while gameplay without story is possible, but boring or repetitive.

2.5.5) Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.

Not till yesterday. I haven't seem much, but I think I prefer single player campaigns.

We do not plan to favour Wesnoth players as such, but some particular projects require a good feeling for the game which is hard to get without having played intensively.

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 S­­V­­N (during the evaluation period or earlier) please state so.

[patch#3243] and [r53929] - fixes ghosted unit animation in whiteboard, when unit graphics are larger than hex; (bug [#19486])
8th of April gained s­­v­­n access.
[r53872] and [r53879] - resolves issue with bad refresh after scrolling and hex calculation under rectangle.
[r53928] - bugfix [#19614]

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 tend to miss some words, due to my slow typing, but I correct myself. Other than that, I would say fluent.

3.2) What spoken languages are you fluent in?

• Lithuanian
• English (haven't spoken to native speakers, so hard to say)

Not fluent, but I can understand fair part of Russian and Japanese.

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 would say yes. I tend to ignore trolling and flaming and honestly answer good questions if can answer them. From my player perspective, I used to play some MMORPG, so I can deal with it.

3.4) Do you give constructive advice?

Yes. I also like advising others in a way, that they find the answer themselves.

3.5) Do you receive advice well?

Most of the time, if it's argumented and not biased. Othervise I want a argumented discussion.

3.6) Are you good at sorting useful criticisms from useless ones?

As I mentioned before, I need argumented advice and argumented advice is not too far away from constructive criticism. Now of course this is not 100% of the time, I am human too and I might get upset/demotivated from constant disdain and flaming.

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

I try to mix both approaches. First I would figure out (myself or through discussion) changes needed to be done. Then start coding, show intermediate result, make adjustments and continue. If there is no good concept of what/how to do something, I would try creating something, then evaluate work (myself or preferably in discussion) and continue working or redesign bad parts.

I can work both autonomously and cooperative, but I prefer I would not do evaluations alone, because developers get attached to their code and see thing subjectively.

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 selected "implementing particle engine". I would like to make particle engine like a library, which you can use from whenever you want to.

If possible I would like to concentrate on making particles blit alpha images instead of pixels. Also I prefer to (additionally) implement it using OpenGL to use videocard computing power.

Of course I want to make this particle engine fast and reusable (at least on wesnoth scale).

4.2) If you have invented your own project, please describe the project and the scope.

4.3) Why did you choose this project?

I like games, making games, and playing them. I also like graphic related material and optimisations, algorithm analysis and physics. This project lets me do it all at the same time.

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

If possible I would like to use Scrum methodology and define tasks for week sprints, depending on current progress. I have university lectures till end of June, but it shouldn't be much of a problem. Preliminary plan:

March -> Mid-May

- familiarising with Wesnoth code structure and architecture used, refining engines functional requirements and technical details, forming API. Bugging (in a good way) my mentor if I get accepted. Making my own branch (in git, as I plan to use git-s­­v­­n) of Wesnoth and playing with current graphic code. (Play Wesnoth :), finish most university assignments). While I still have lectures, they don't take much time.

Start of Coding - > Mid June

- start making particle engine for single pixel particles and implementing it, document progress, testing in Wesnoth and debug. By the mid June I expect having most of engine done (with update function still lacking in some parts). effects would be predefined.

18-22 of May and 10-11 of June - exams.

Mid June -> Mid July

- finishing implementation (fully working update and all other functions), writing full documentation, testing.
- making effects dynamically creatable, writing a good set of predefined effects (like templates).

Week in ~Mid July - tour, going home

Mid July -> Mid August

- exposing particle engine to lua code, making effects creation fully dynamical (except for particle movement formulas)
- finishing where I failed at, extending engine to use images, documenting, testing, debug
- writing a good set of particle movement functions.

Mid August -> End of Coding

- hopefully nothing, but time reserved clearing up failures.

4.5) Include as much technical detail about your implementation as you can

Preliminary plan:
I will create a set of functions and/or classes that use existing drawing code, extend drawing code in any way I need. Form a library-like API for created classes, their methods and functions.

A short description:
At the start of game, Particle_engine singleton (part_engine_ from now on) would be created (much like display singleton), so later on it could be called. This step is init of engine, though no resource-heavy loading should taken during it. Unit (possibly terrain structures) would be extended to accommodate vector of pointers to ongoing effects associated with unit, so it could be canceled and/or interrupted. The part_engine_ would keep a list of pointers to active effects, so to say, the part_engine_ would be responsible for all effect creation, destruction and their changing handling.

Structure:
part_engine_ would have public methods:

 Class Part_engine {
 public:
   update(float time_slice);
   reset();
   add_effect(const unit_t& unit, string type, bool hover_only, int turns = 1);
   add_effect(const unit_t& unit,
              int particle_number,
              float spread,
              std::vector<int> color_array,
              string particle_formula,
              int frame_number,
              bool hover_only,
              int turns = 1);
   remove_effect(const effect& eff);
 private:
   std::map< unit_t, std::vector< effect_type > > effect_map_;
   std::map< string, void(*movement)(particle&, float) > particle_movement_map_;
   std::map< string, effect_type > effect_ype_map_;
   void construct_effect_type_map();
   void construct_movement_map();
 };

• update(float time_slice) <-- play all active animations, would be called in method like play_slice(), also allowing "on hover animations".
  
• reset() <-- reset all active effect, so, no effect is displayed.
  
• add_effect(const unit_t& unit, string type, bool hover_only, int turns = 1) <-- add effect to execution list and associates it with given unit (or terrain), where:
  

-unit is reference to unit, on which this effect is active
-type is a string, which maps to pre-defined structs of effect information (see below)
-hover_only tells if this effect should be displayed always, or only on mouse hover
-turns tells how many turns should this effect be visible (only if hover_only is set to false), after every turn it is decremented, and effect is removed from list once it reaches 0. passing -1 makes effect stay for all game or until the unit dies.

• add_effect(const unit_t& unit, int particle_number, float spread, std::vector<int> color_array, string particle_formula, int frame_number, bool hover_only, int turns = 1) <-- overloaded function, in which you can dynamically create your own effect, most likely to be used through lua code, to let users define their own effect. (see structure below for argument explanations)
  
• remove_effect(const effect& eff) <-- forcefully remove given effect from active list.
  
• construct_effect_type_map() <-- would simply create a map associating effect names with predefined effect configurations.
  
• construct_movement_map() <-- would create a map of particle movement name to the function, defining logic, how particle should move.
  
• effect_map_ <-- maps units' address to a vector of effects, unit currently have.
  
• effect_type_map_ <-- maps effect name to defined effect configuration.
  
• particle_movement_map_ <-- maps particle movement name to a function, defining movement logic.
  

The mentioned string "type" would map to similar structure:

 struct effect_type {
   int particle_numbe_r;
   float spread_;
   std::vector<int> color_array_;
   string particle_formula_;
   int frames_number_;
   std::vector<particle> particle_list_;
   bool active_
 };

where:

• particle_number_ is the number of particles to be released over frames_number
• spread_ is value in range 0..1 describing how concentrated or spread over hex should effect be
• color_array_ is a list of color values, how should particles change their color over one animation cycle
• particle_formula_ would be key to std::map<string, *function> OR std::map<string, string> (see below)
• frames_number_ - is the number of frames the animation should spawn over
• particle_list_ - null while unitialized, contains a list of particles to be drawn (with their positions and individual data); Also particle_list could be interchangable between effects to enable smooth transition from one type of effect to another (for example with change of animation type).
• active_ - indicates if effect is active and has to be drawn.

As far as I know such structure could be easily binded to lua code, exposing users to particle effects.
Currently I am assuming effect center to be center of hex cell, but I don't see problem modifying so it can by anywhere on hex.

For particle_formula I see two possibilities:
1. map of string - pointer to function. Such structure would be easy to implement, but would limit user to predefined particle movement functions.
2. map of string - string, where second string is expresion of how should the particles move. This would be a 'bit' more tricky, as string would need to be parsed, constructing correct expression and evaluating it every time, particle needs to be updated. (this could potentially be another GSoC project for a optimized and robust system). Another solution would be to pass string to lua code, for dynamic evaluation and getting result, but this would leave particle engine lua-code-dependant, which I do not seek.
Of course it is possible combining both implementations, though most likely only the first one will used in GSoC timespan.

Integration to current code:
First of I propose drawing particles on two layers - to give better impression of deph. One under unit, another on unit. Following current tdrawing_layers enumeration:

 ..
 ..
 LAYER_UNIT_BG,
 PARTICLES_BG,
 LAYER_UNIT_DEFAULT,
 ..
 ..
 LAYER_UNIT_MOVE_DEFAULT,
 PARTICLES_FG,
 LAYER_UNIT_FG,
 ..
 ..

Units and/or terrain would be responsible for invalidating own their particle effects. This can be achieved by going through effect list in each unit, in unit invalidation call. Invalidated hexes - added to common invalidated_ set in display class. Similary units that require redrawing - added to unit_list_.
Particle engine singleton could have additional list for special effects. Special effect invalidation would be handled by singleton itself as a separate case. This would be used for specific cases invoked directly from WML.
Particle drawing would be done to offscreen buffer by particle engine singleton in (most likely) display::draw. While particle position, color calculations would be performed in controller_base::play_slice (or playsingle_controller / playmp_controller ::play_human_turn).
Of course by giving player option to turn off particle rendering in config menu, we skip particle invalidations, calculations and drawing.

For WML integration I propose adding additional key-value fields to animations:

 [animation]
   ..
   ..
   [particles]
     effect=name
     lifetime=< int >
     direction=< progressive float >
     spread=< progressive float >
     source=< progressive float >
     colours="#ffbbaaff, #cc3344bb, #93f31299"
   [/particles]
   ..
   ..
 [/animation]

Mandatory values:

• effect - a string naming a predefined effect formula.
• individual particle lifetime in number of frames.

Optional values:

• direction - 0~2 float value in radians, defining which direction should new particles be going.
• spread - 0~2 float value in radians, defining spread variance around given direction.
• source - -1~1 float value describing where on hex should particle emission source should be.
• colours - a string of comma separated colour codes, describing how particle colour should change during it's lifetime.

Or directly from campaign:

 [campaign]
   ..
   ..
   [particles]
     effect=name
     lifetime=< int >
     location_x=< int >
     location_y=< int >
     direction=< progressive float >
     spread=< progressive float >
     source=< progressive float >
     colours="#ffbbaaff, #cc3344bb, #93f31299"
   [/particles]
   ..
   ..
 [/campaign]

Adding additional:

• location_x - hex x location for effect
• location_y - hex y location for effect

During animation change, like 'standing'->'moving', if both animations have different effects assigned, particle_list_ from current standing effect would be transffered to moving effects. That way different effect formula will be applied on same, already existing particles, allowing smoother transitions. A nice side effect of such transitions would be minimisation of memory allocation/deallocation for particles.

As for effect list, I am currently thinking of:

• Particles circling unit in force field-like manner - going from left side of unit to right side in front of unit, and going from right side to left side under unit. (Right-hand rule for magnetic field in wire with current flowing through it). Simpliest formula could be: x = cos(t/T + variance_x); y = 0.3*cos(t/T + variance_x), variance - for phase difference.
• Particles slowly rising upwards from bottom of hex.
• Particles expanding from source in all directions in wave-like way. (e.g.: x += vel_x*dt; vel_x += force_x*dt; y calculations - same way as x).
• Particles contracting from circle line inscribed in hex to the center of hex

Of course, list is open for suggestions.

4.6) What do you expect to gain from this project?

• More experience in graphics and working in project.
• Contacts with capable developers.
• Better understanding of c++ and game structure and/or design.
• Maybe increasing my AI knowledge too?
• Usefully spent summer.

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

Friendly community, something I can work on and enough free time.

5) Practical considerations

5.1) Are you familiar with any of the following tools or languages?

• Sub­­version (used for all commits)

S­­V­­N - Only checkouts.

version control system - Yes, I mainly use mercurial for my projects (and now git).

• C++ (language used for all the normal source code)

Yes, used in quite a few projects and university assignments, currently learning template metaprograming.

• STL, Boost, Sdl (C++ libraries used by Wesnoth)

Have used container part of STL (also iterators, sort and iostream though I prefer printf).

No experience with Boost, so far had no need to use it.

SDL - yes, used for few projects.

• Python (optional, mainly used for tools)

Yes, I use it whenever some small language independant tasks are needed. Also used to make a game.

• build environments (eg cmake/scons)

Scons - yes, have written very simple Sconstructs.

make - yes, used with qt for one project, no problem using already written makefiles :).

cmake, autotools - have compiled some projects/tools like SDL library and google Go language.

• WML (the wesnoth specific scenario language)

No, no experience

• Lua (used in combination with WML to create scenarios)

Yes, made about 3 games using Lua.

5.2) Which tools do you normally use for development? Why do you use them?

Vim and Terminal, gdb - because I don't have to use mouse and "if you can't make something in Vim, it just means you don't know it well enough". Also IDE usually use lots of memory and computing power, are slow with responses, have infinitely many check-boxes and GUI in general takes way too much space. Furthermore I don't that IDE is always trying to correct me, like I don't know what I am doing. Another feature of Vim, that not many editors have is to split (horizontally and vertically) window in how many times you want in whatever hierarchy you want. Not mentioning the fact, that Vim (or at least vi) is on most unix machines.

5.3) What programming languages are you fluent in?

Hard to say, but I suppose:

• Python (w/o integration to C)
• C
• Lua (w/o integration to C)

I know good chunk of Java, but I think it's nearly impossible to be fluent in Java without IDE. Also I am quite exposed to matlab, lisp (haven't used much, but I understand functional programing well), Factor, C++, google Go (I like how it is easy to multithread with Go, and ideas used in Go in general).

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!

No problem with that.