User:Tschmitz

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_Whiteboard_2011

Description

Tommy Schmitz - Whiteboard Improvements

The Wesnoth whiteboard system is the mechanism by which players can plan their strategies in-game. The whiteboard is currently unfinished and requires both debugging and additional features. The proposed project will address these, with the focus on allowing allied players to view each others' plans over the network.

IRC

tschmitz

Submitted Patch

• Fixed some whiteboard bugs

Introduction

This is a continuation of gabba's 2010 whiteboard project! To see some of his ideas for the future of the project, see his "Future" page.

After compiling a list of several sub-tasks, I can now describe my project as a plan to turn the whiteboard into a powerful "what-if scenario" engine and planning system. I plan to add network support to enable players to plan with their allies on the network, and after that, I plan to make it possible to consider possible actions by enemies and suggest possible actions to allies. As a kind of perk that is worth mentioning here, I hope to upgrade the damage calculations dialog to be able to take into account multiple attacks against the same target (either against an enemy target or against one of your own units).

The details section below covers the following sub-tasks

• "Suppose dead" planning
• Change behavior of invalid actions
• Network support
• Multi-turn moves
• (optional) Suggesting planned actions to allies
• (optional) "What-if" enemy actions
• (optional) Cumulative combat probability calculations
• (optional) Interface updates

Details

"Suppose dead" planning

Motivation

"What if that enemy unit wasn't there? Could I reach the enemy leader?"

Proposed Solution

Right-click the unit and select "Suppose dead" from the context menu. The unit will be marked in some way to indicate that you have done this. After doing so, you will be able to plan actions as if that unit wasn't there; this way, you can rely on the pathfinding algorithm to accurately determine the resulting possible moves. Additionally, you will be able to plan subsequent actions in advance, as long as the unit really does die when you think it will (which is a fairly reasonable assumption for attacks with a 99% chance to kill, for example). When you're done playing make-believe, right click the enemy unit and select "Undo suppose dead" to bring things back to reality.

Implementation Details

The option must be added to the context menu when right clicking on enemy units. When the "Suppose dead" command is selected, a "suppose_dead"-type subclass of wb::action (which temporarily removes the unit from the map) will be added to the planned actions queue. Using the existing framework of the whiteboard, this will be a fairly simple way to provide this functionality.

Open Questions

• What happens if I try to execute the "Suppose dead" planned action (using the 'Y' button)?

I think nothing will happen; if it was during an Execute-All command, the execution will stop, because if you're trying to execute a suppose_dead action in this way, that means the unit didn't die the way you expected it to.

Change behavior of invalid actions

Motivation

One of the best features of the whiteboard will be the ability to start taking your turn during other people's turns, but your plans will be affected by the actions of the player who's taking his or her turn. If this player is your ally, then even their whiteboard plans will be visible to you and will affect (and possibly invalidate) your plans, even if the ally later decides to erase the planned actions that invalidated your planned actions. Currently, invalid actions are immediately discarded when they are discovered. Do you want to have to input your moves again?

Proposed Solution

Instead of immediately discarding invalid actions, they will be preserved, but displayed with a different arrow style to indicate that they are invalid. If the action later becomes valid again, it will simply become valid again. If/when you wish to discard the invalid action, you may do so via the context menu.

Implementation Details

Disable the immediately-discarding-invalid-actions behavior. Add the context menu option to remove invalid actions. Change the arrow style of invalid actions.

Usually actions become invalid because someone else got in your unit's way. However, sometimes actions become invalid because the unit for which the action was planned has either moved or died. In this case, the planned action will be discarded anyway, because it is either impossible or much less likely for the action to become valid again.

Open Questions

• Should there be a way to erase all invalid actions?
• Should there be a preferences setting to immediately discard invalid actions (just like the old way) instead of preserving them?

Network support

Motivation

This was the original purpose of the whiteboard! See gabba's page for some motivation.

Proposed Solution

Teams of allies will essentially share a whiteboard, as far as they'll be able to tell (though the implementation underneath will tell a slightly different story, since their action_queues will be separate). They'll only be able to plan actions for their own units, though.

Since the actions of earlier players in the turn sequence will be applied earlier than those of players that are later in the turn sequence, it will appear as though the plans of the player currently taking his or her turn will have precedence over those of the other allies (their actions will be invalidated if in conflict with those of the current player).

Implementation Details

The future_unit_map is currently constructed by applying the actions from the current side's action_queue only. Instead, it must also apply the action_queues of every ally afterward, in the order that their turns will be taken. This data will need to be serialized and unserialized. Finally, the whiteboard data will piggyback on the turn_info that gets sent through the network. Additional sending/receiving code will be necessary to send data across the network on every modification, not just non-undoable actions.

For more information, see gabba's original ideas on this part of the project.

Open Questions

• Should the data be serialized into config form or raw-data form?

I'm thinking config will be more convenient.

• Should the entire list of actions be sent, or just small updates?

As far as I can tell, the latter method is used by the existing turn_info framework; presumably it will be fairly straightforward to send data in small updates, even though sending the entire list would be slightly easier. I will need to ask around to determine whether there are important measures I will need to take to avoid desynchronization in this case.

Multi-turn moves

Motivation

Well, Wesnoth supports multi-turn moves without the whiteboard, so the whiteboard should, too!

Proposed Solution

Clicking beyond the movement range of the unit will queue up the necessary movement actions for the subsequent turns. The ones that must occur on subsequent turns will be indicated with a different arrow style. When the next turn begins, the subsequent moves will already be present in the actions queue as planned actions and may be invoked via the usual Execute command for planned actions.

Implementation Details

A new action_queue will be created for every future turn on which a move action must be planned to accomodate the multi-turn move. If a move takes 4 turns to complete, for example, the first will be planned in the queue for the current turn, and 3 additional queues will be created (to represent the planned actions for "next turn," "turn after next," and "three turns from now") and the subsequent wb::move objects inserted into them. When the player ends his or her turn, the current turn queue and the next turn queue will require a simple merge, depending on whether or not the player decided to execute the current turn's portion of the multi-turn move.

I might reconsider this implementation. Instead of splitting a multi-turn move into completely distinct wb::move objects, it might be more flexible to redefine wb::move objects such that they are allowed to denote paths that are too long to complete in a single turn. The display of such moves would be altered to indicate where the unit's stops would occur and wb::move::execute() would be altered to just move as far as possible along the path this turn.

I will need to research the existing pathfinding code to locate the intermediate stopping-points and implement the interface. Since the game already knows how to find a multi-turn path from one spot to another, I will leverage that. Finally, new arrow styles will be required to distinguish current-turn arrows from subsequent-turn arrows.

Finally, since the current waypoints ('W' key) and multi-turn move (affectionately called "gotos") systems will become obsolete after implementing this part of the project, those two features will most likely be disabled at that point. As it stands at the moment, there is a conflict (game crashing) between the waypoints system and the whiteboard system anyway.

Open Questions

• Which implementation should I use?

(optional) Suggesting planned actions to allies

Motivation

"Don't move there, dude; move here instead ..."

Proposed Solution

Players may plan moves for their allies' units, but those plans will not be written directly into their ally's action_queue; instead, the ally will see a specially styled arrow indicating the suggested action and may right click the action to either accept (immediately add to the action queue) or reject (erase) the suggestion.

Implementation Details

Every side will need a separate action_queue for suggestions from every other player. For example, if 4 players are allied, each of the 4 of them will have 3 extra action_queues: one for suggestions from each of the other 3 players. Whenever player 1 is providing suggestions for player 2, there will conceptually be an extra future_unit_map that is calculated by first applying all of player 1's planned actions and then by applying player 2's suggested actions. Player 2's suggestions for player 1 will be checked for validity against this (conceptual) alternate future_unit_map.

Suggestions will, of course, need to be serialized and unserialized and sent and received through the network.

It will also be necessary to provide an interface for making suggestions. Presumably players could just make moves for their allies' units to make suggestions, or perhaps there could be a "suggestions mode" to enable making suggestions. In either case, I will have to research the interface for selecting moves so that I can get move data when the player attempts to move an ally's unit.

New arrow styles will again be necessary for this part of the project, as well as context menu options: "Accept suggestion" and "Reject suggestion".

Open Questions

• Should there be a "suggestions mode" that the player must activate in order to make suggestions, or should players just be able to make suggestions by moving their allies' units?
• In the latter case of the above question, how would it be possible to suggest a suppose_dead action to another player?
• Can player 1 see suggestions from player 2 to player 3, even if player 2 hasn't accepted the suggestions yet?

I think it would probably be useful to be able to see these. It will just get messy with the multi-colored arrows.

• Will there be any issues with concurrent modification?

I have realized that providing the Accept/Reject functionality causes a concurrent modification issue to arise: both the suggesting player and the player receiving the suggestions are capable of making modifications to the action_queue of suggested actions. I haven't yet determined a solution to this problem.

(optional) "What-if" enemy actions

Motivation

"An enemy unit can reach my healer! Will the healer survive if attacked by that enemy? I wish I could see the damage calculations for that potential attack ..."

Proposed Solution

"Planned" actions can be made for enemy units in the same way as suggesting actions to allies, though no notifications will be sent to the enemy player, of course. This will allow players to consider what-if scenarios involving enemy actions as well.

Implementation Details

The framework for suggesting actions to allies will be very applicable to this feature as well. In fact, this feature may be developed simultaneously with the above.

Open Questions

• Can my allies see my what-if scenarios?

It would make sense to (occasionally) ask allies "What if the enemy moves here?" but it raises another issue: What happens when two allies simultaneously want to view different what-if scenarios for the same enemy unit? This one will require some thought.

(optional) Cumulative combat probability calculations

Motivation

"Three enemy units can reach my healer! Will the healer survive if attacked by all three enemies (gee, they must be pretty weak if that's in question)? I wish I could see the cumulative probability of dying across all three attacks ..."

Proposed Solution

When planning more than one attack against a single target, the combat dialog will display the probability analysis of all of the attacks considered together.

Implementation Details

Gabba told me that Crab_ told him that cumulative calculations have already been implemented, though not in a visible dialog. So this part of the project will involve asking about that algorithm, and then editing the Damage Calculations dialog accordingly.

Open Questions

• Should allies' planned attacks against that same target be considered in the calculation?

I think the calculations should involve all attacks that will have occurred up to this point in the action_queue. So if it's your turn and your ally will be attacking later, then your calculations don't include that ally's power. If you're doing some planning during someone else's turn, then that person's attack plans come earlier than your attack plans, so your plans should include that person's damage in the calculations. What if it's your turn and you want to include your ally's power in the calculations? Make an attack suggestion for that ally and check the dialog that appears; it should include your units in the calculation.

(optional) Interface updates

Motivation

"Which units haven't I moved yet?" and "Where are all my planned units at this point?"

Proposed Solution

I haven't decided yet, but I was thinking that, when not in planning mode, the whiteboard information should be hidden and the view should revert to normal. When in planning mode, future unit positions should be full-color and all previous (and possibly future) positions should be grayed or something. This would make it easy to switch between viewing only old unit locations and viewing only new (planned) unit locations.

Implementation Details

Depends on what we decide to do, but this one is going to involve research on the way units are displayed to the screen.

Open Questions

• Couldn't we make it look a different way instead?

I'm open to suggestions.

Map of the Implementation

Each side will have its very own action_queue, that is, a list of planned actions. What's more, for every pair of allies, there will be two action_queue objects for suggestions (one for player 1's suggestions to player 2, one for player 2's suggestions to player 1).

When Player 1 makes a planned action, it goes into the main Player 1 action_queue, is sent to all allies through the network, and is placed into their local Player 1 action_queues. When Player 1 suggests an action to Player 2, it goes into the action_queue for "suggestions from Player 1 to Player 2," is sent to all allies through the network, and is placed into their local action_queues for "suggestions from Player 1 to Player 2." When Player 2 wants to see a what-if scenario for units controlled by (Enemy) Player 3, the action is placed into Player 1's local action_queue for (Enemy) Player 3, is sent to all allies through the network, and is placed into their local action_queues for (Enemy) Player 3 (this causes an issue with simultaneous modification, so this may change; perhaps there will be a separate action_queue for "What-if scenarios by Player 1 about Player 3" so that the only one modifying that list is Player 1).

Progress

protocol for whiteboard config "packets"

 [whiteboard]
   command=insert
   index=4
   [action]
     ...
   [/action]
 [/whiteboard]

or

 [whiteboard]
   command=remove
   index=4
 [/whiteboard]

etc.

17 June 2011

• Add "config to_config() const" to each subclass of wb::action
• Add "static action_ptr from_config(config)" to wb::action itself

18 June 2011

• Add "static void send_to_allies(config)" somewhere (maybe wb::manager)
  • This function calls network::send_data()
  • Is there a function that does this already? Ask.
• Add "void execute_network_command(net_command)" to wb::side_actions
  • Add "typedef config net_command" to wb::side_actions
  • This function calls wb::action::from_config()
• Add calls to side_actions::execute_network_command() inside turn_info::process_network_data()
• Add call to <something>::send_to_allies() and to to_config() inside side_actions mutator functions

Timeline

Soon (Right now)

1. Allow "suppose dead" planning
   • Back-end: Define a new wb::action subclass called suppose_dead
   • Interface: Add context menu option to create/delete a suppose_dead action

Official Kick-off (May 23, week 0/13)

1. Change behavior of invalid actions
   • Back-end: Make invalid actions not expire immediately
   • Interface: Add new arrow styles
   • Interface: Add context menu option to erase invalid action

School's out! (June 9, week 2.5/13)

1. Add network support
   • Back-end: Change the calculation of future_unit_map to include allies' actions (in proper turn order)
   • Back-end: Serialize side_actions class
     • Choose between config or raw data for network representation
   • Back-end: Implement network send and receive
     • Choose whether to send the entire structure or just "diffs"

Personal checkpoint

• Make sure the above is all done.

Mid-term Evaluation (July 15, week 7.5/13)

1. Allow multi-turn move actions to be planned
   • Back-end: Add action_queues for future turns
   • Back-end: Modify find_last_action_of() to look in the future action_queues first and progressively go backward
   • Interface: Allow these actions to be created via the normal method: clicking on a hex that's too far away to reach in one turn
   • Interface: Provide visual distinction between current-turn planned moves and future-turn planned moves.
2. (optional) Allow players to suggest actions to their allies
   • Back-end: Add action_queues for lists of suggestions from allies
   • Back-end: Add code to serialize, send/receive suggestion objects
   • Interface: Allow players to make suggestions
     • Possibly a menu option to switch to suggestion mode for a particular ally
       • The moves you make for their units will be sent as suggestions to that player
     • Perhaps no special mode -- the moves you make for your allies' units will just be sent as suggestions
   • Interface: Allow players to see suggestions
     • New arrow styles
   • Interface: Allow players to accept/reject suggestions
     • Context menu
3. (optional) Allow players to make "what-if scenarios" by predicting possible enemy moves
   • Extend the framework for suggestions-to-allies to possible-actions-by-enemies
4. (optional) Implement multiple-attack combat probability analysis
   • Ask Crab_ about the cumulative calculations algorithm
   • Back-end: Implement the calculation
   • Interface: Modify the dialog accordingly
5. (optional) Change what planned actions look like
   • Possibly make future units no longer gray
   • Discuss possible changes, draw mockups

Personal checkpoint (August 8, week 11/13)

• Is there enough time to finish at this point? Consider switching to testing and bugfixing at this point.

Suggested Termination (August 15, week 12/13)

• Test
• Fix what went wrong

My Old Brainstorm

Main goal

• Planned actions will be visible to allied players

Some other goals

• Planned action data will be made available to AI scripts
• Actions can be suggested to other players via "suggested actions"

Other brainstorming

• Planned action object (be it move, move+attack, recruit, or recall)
  • Additional data: On what turn will this action take place? Allows planning a delayed task
  • Additional data: attacks will include information about whether the player wishes to assume the defender will die or not, and also whether the attacker will die or not
• Suggested action object
  • A planned action object that uses an allied player's unit as the actor
  • Will be displayed to that player
• Make the whiteboard available to WML (if we're going to write a whiteboard tutorial scenario, this will be essential ...)
• Write a whiteboard tutorial scenario
• Some interface changes
  • Enable planning multi-turn moves
  • Attack actions ...
    • Perhaps a context menu option to set/unset the "assumed dead" status of units
    • Combat probability analysis dialog will incorporate previous planned attacks against that unit into the "equation"
  • Filtering display of certain planned actions
  • "Foresight view" for allowing one to view the future state of the battlefield
    • Presumably there will be a visual cue (such as graying the battlefield or something) that indicates that the current view is a future turn and not the current turn
    • New UI functions to accomodate this view:
      • "View next turn" button
      • "View previous turn" button (cannot go earlier than current turn)
      • Possibly "View current turn" button
  • "Itinerary view" (text list) of planned actions, listed in order and categorized by turn number.
    • Possibly simplifies the task of reordering actions
  • Making moves during other players' turns
    • Modify the behavior of the screen automatically centering on the moves that are happening.

Questionnaire

1) Basics

1.1) Write a small introduction to yourself. My name is Tommy Schmitz. My legal name is, of course, Thomas, but everyone has always called me Tommy and I have never found any reason to change that, so I'm known as Tommy. I have been a code-tinkerer all my life, but this will be my first time working with other programmers.

1.2) State your preferred email address. tschmitz.wesnoth@gmail.com

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

1.4) Why do you want to participate in summer of code? I really want to finally get some experience working on a group project. I was drawn to the Battle for Wesnoth project because it was one of the few that I recognized from the list of participating organizations. I played Wesnoth around two years ago and was surprised to see the name again!

1.5) What are you studying, subject, level and school? I am working toward a bachelor's degree in computer science and mathematics.

1.6) What country are you from, at what time are you most likely to be able to join IRC? I'm from the United States. My local time is currently UTC - 7. During the week, I should be on IRC with roughly the following schedule (times given in UTC):

• Mon, Wed, Fri: During 16:30-17:40 and from 00:00 until 07:00 ish.
• Tuesday: From 17:00 ish until 14:15 and from 01:00 until 06:00 ish.
• Thursday: From 17:00 ish until 13:15 and from 01:00 until 06:00 ish.

These are the times when I'm not in class and when I'm not sleeping, roughly speaking. On weekends, I might be sleeping during 07:00-17:00 (UTC) roughly speaking. I haven't established a consistent time, unfortunately.

1.7) Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when. I will be in school until June 9, so my time will be somewhat limited until this day. Aside from that, my intent for the summer is to take on this project exclusively; I have planned no vacations.

2) Experience

2.1) What programs/software have you worked on before? Aside from command line programs for school, I have mainly worked on small independent projects of my own with the hopes of refining and expanding my game-development tool kit. My most polished project was a Tetris clone implemented as a Java applet.

2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own) No, but this is something I very much look forward to doing!

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, I didn't hear about the Summer of Code until recently. This is my first time applying!

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, this will be my first experience.

2.5) Gaming experience - Are you a gamer? Yes.

2.5.1) What type of gamer are you? These days, I only play games when I have spare time, but when I do, I go all out.

2.5.2) What type of games? Platformers are my favorite. I like turn-based strategy games a lot too, though, because it both requires and allows thinking deeply to succeed.

2.5.3) What type of opponents do you prefer? Computer opponents. I prefer to cooperate with my friends rather than compete with them.

2.5.4) Are you more interested in story or gameplay? I very much enjoy both.

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

We do not plan to favor Wesnoth players as such, but some particular projects require a good feeling for the game which is hard to get without having played intensively. I played for a few months and I liked single player, multiplayer, and also making custom content. I tended to prefer playing multiplayer games with my friends.

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. None just yet, and I do not yet have commit access.

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. My fluency will be sufficient to communicate with the other collaborators on this project. As a programmer and mathematician, I have excellent attention to detail, which includes the details of English communication (such as grammar).

3.2) What spoken languages are you fluent in? English.

3.3) Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough. In the past, I have played multiplayer games fairly extensively and should fit right in.

3.4) Do you give constructive advice? I do my best to evaluate others' work with the courtesy that I like to have from others.

3.5) Do you receive advice well? Again, I do my best; when receiving advice, I try to focus on the content of the criticism and keep my ego out of the picture.

3.6) Are you good at sorting useful criticisms from useless ones? Once more, I do the best I can -- if someone offers me critique that lacks specificity, I'll ask for clarification. If it's clearly hostile, I'll simply ignore it.

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 lean toward having discussions to clarify details as much as possible, but if I can't gain an audience, I'll focus on the parts I'm most comfortable with until I can get my questions answered.

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 picked the whiteboard project mainly because it has no other takers yet, but I think it is a good fit for me because I enjoy collaborative multiplayer games and careful planning and the whiteboard is designed for exactly those purposes. I'm also interested in getting some experience in network programming, and the whiteboard project will have elements of that.

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? For the reasons above, I think that it is a good fit for me and that I will learn a lot doing it.

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 the top of this page.

4.5) Include as much technical detail about your implementation as you can Again, see the top of this page.

4.6) What do you expect to gain from this project? This should be a good opportunity for me not only to learn technical skills, but also to experience the dynamic of creating a software project collaboratively.

4.7) What would make you stay in the Wesnoth community after the conclusion of SOC? It's going to be a lot of fun!

5) Practical considerations

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

Subversion (used for all commits)

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

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

Python (optional, mainly used for tools)

build environments (eg cmake/scons)

WML (the wesnoth specific scenario language)

Lua (used in combination with WML to create scenarios)

I haven't used SVN much, but I have been introduced to it before and it seems relatively straightforward.

I am quite familiar with C++ and the STL from my programming classes and a few personal projects.

I used WML for a while two years ago, so I'm sure I'll be able to pick it up again fairly quickly.

Unfortunately, I can't say I have had any experience with Boost, Sdl, Python, cmake/scons, or Lua.

5.2) Which tools do you normally use for development? Why do you use them? For my programming classes, we have mainly used the university Unix system to write command line utilities in various languages (C, C++, Java, and Perl in my case). We used "gcc" to compile C++ code, "make" to write build scripts, and RCS for version control. When writing computational tools, I often use the university system since it is nicely set up for me already. More recently, I began to write Java applets, using Sun's compiler and appletviewer and Windows batch files for build scripts, to make graphical applications, mainly because applets are easy to deploy on the web. I usually use Notepad or Pico as text editors, but I have also used Visual C++ for projects from time to time.

5.3) What programming languages are you fluent in? My best are C++, Java, and Matlab. I have also tinkered with HTML, Javascript, PHP, and Perl.

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 certainly would not mind!

SoC Application

tschmitz SoC Application