SoC Ideas Whiteboard Backend Refactoring 2012

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 Idea

Description

Whiteboard: Refactor the backend

Page for the idea: SoC Ideas Whiteboard Backend Refactoring 2012

Improve the whiteboard's backend code by refactoring the data structure which holds the planned actions. Also refactor the verification and mapbuilding processes by combining them, and use this single new process to cache as much data as possible to avoid redundant lookups. You can also propose other simplifications.

Produce complete unit tests to cover all operations on the new planned action storage and the new combined mapbuilding/verification.

Document this new backend, explaining your design approach and including all diagrams necessary for the reader's understanding.

Finally, do exhaustive playtesting and bugfixing involving devs and community members to make sure the whiteboard is fully reliable.

There are 8 submitted student proposals for this idea

Andriy Andriychuk - "Total defence" strategy

The idea is to group own troops so they are in advantageous position and get less damage.
See Avrilfanomar for more information.


See Kripsi for more information.

Sanka Darshana - "Implement a 'total defense' strategy"

The AI will decide the best movements considering the resources available, enemy positions and their types, enemy distribution and etc... The generated movements will be decided on the values of the each troop. As an example, a shaman will be more important if there are more troops with low health, and Archers if there are troops with health. So the AI will determine which actions to take depending on a list of variables in the game environment
See SankaD for more information.

Geoffrey Hart - Maximizing Utility

A good offense is made by identifying an opponents vulnerabilities and exploiting them. As such, a good defense is made by reducing the number of weak spots. Since there is no perfect unit and all have their own imperfections, the idea is send them out in groups of units that compliment each others strengths and weaknesses. This will allow them to rearrange themselves in a way most suitable to handle nearby enemies. Since the number of predictive steps the AI can make is limited, it can become "surprised" rather easily. Therefore, it's a good choice to maximize utility and the ability to be flexible in order to handle these surprises. Then, within action-packed skirmishes, raw processing power can be brought to bear more effectively.
See SOC - Geoffrey Hart for more information.

Christopher Conway - Defensive AI

My goal is to develop an AI which is capable of “total defense” behavior, as opposed to the current aggressive AI. It would allow for the AI to function in scenarios like controlled retreats, unit escort, or holding a given area while minimizing unit loss.
See Soc2012 Borgrumm Defensive AI for more information.

Conor Nevin - Implementing a Total Defense AI

Implementing a defensive mode of the AI, so that it is able to heal units whilst holding ground against an advancing enemy.
See Soc2012 cnevin92 Total Defense AI for more information.

Nikolay Agafonov - Line Defence Strategy

The idea of this strategy is to stick together the troops and create the defencive line. All the units should be put on hexes where they would be on the defensive in most effective way. THere would be some kinds of AI's behaviour (full retreat, banking, passive attack etc.) depending on on game factors.
See SoC2012 LineDefenceStrategy for more information.

Ed Kim - Total Defense AI

Often, the best defense is a good offense. In Wesnoth, lacking either can get you slaughtered. It is particularly important that the AI learn not only to consider immediate gains and losses off a linear formula, but to take other considerations into account, especially some foresight into human reactions and macroscopic army flux. Similar to a chess engine, if the AI could learn to take "next move" heuristics into account as well as consider positional strategies such as defensive formations (line, square) by taking unit relationships into account, the AI would become a much more versatile and formidable foe.

See SoC2012 Yokipi Total Defense AI for more information.

Additional Information

Combining the mapbuilding and action verification

The whiteboard planning system can show you things like possible enemy moves "in the future", after you've moved your units to the planned positions. To achieve this, it builds an internal future state by taking the orders of the player and applying them to the game state in the correct order, a process we call "mapbuilding".

The issue here is that we also have a separate "verification" of said orders to make sure they are possible. This is used everytime the game state might have changed outside of the whiteboard's control, or whenever the player deletes one of his planned actions, and so on. For historical reasons this is separate from mapbuilding, which is a problem since we end up with a lot of duplicate code, and since they don't handle actions spread over multiple turns consistently.

Another issue is that we often do a full search of the planned actions for various purposes, which is not optimal.

The solution to both of those is to combine mapbuilding and verification in a single process, so that we basically validate actions every time we build the future state. We also want to take advantage that we're going over every planned action to cache some data, such as which hexes are planned moves destinations: this way we avoid going over the planned actions again when displaying the whiteboard's visual aids.

Lastly we also have a "highlighting" process which identifies which planned actions should receive a visual highlight depending on the mouse position. A lot if not all of the information processed there should be instead cached inside the combined mapbuilding/validator.

Refactoring the actions container

Right now the actions for each turn are held in a separate stl container, and we have an iterator front-end to make all of a player's actions accessible as one container. This makes for an overly complicated and wasteful backend. The objective here is to simplify it as much as possible and make it rock-solid.

Requirements

Good skills with the stl, and boost shared pointers, are recommended. As is basic experience in writing unit tests. Prior Wesnoth multiplayer experience is a plus, but not essential.

Since this project is very focused you're expected to have a pretty complete view of what you want to develop down to the most important class members, before GSoC starts. You're also expected to provide a realistic development calendar.

Note that all development must be finished by the GSoC midterm evaluation, after which all the time will be reserved for documenting, playtesting and bugfixing.

Whom to ask about this

gabba on irc. If I'm hard to reach you can also find my email in the game's source files (if you're gonna make the effort to find it, I can make the effort to read your mail ;) ).