NotSoEasyCoding

From The Battle for Wesnoth Wiki
Revision as of 21:30, 16 April 2014 by Iceiceice (talk | contribs)

Foreword

This page shows projects which are considered a good idea by the developers but which have nobody working on them so far. If you think you've got the required skill for a task go on, implement it and you've got a high chance that it'll be accepted. The remaining barrier will only be that it's done well. :-)

If you are such a person, you should feel free to edit this page.

If you're not, you should post a feature request and discuss your idea on the forum or IRC. A coder with better knowledge of the code might give you the green light to add your feature here.

Anybody should feel free to add "clues" to any tasks, that is entry points, traps to avoid, person to contact to discuss and so on.

If you plan to work on a feature, write your name at the bottom of the feature, with the date. Note that if you are too long at working on a feature I'll "free" it back (that is if you're not working on it. If you have problems implementing it, just tell us....)


Game Engine

add a mode to improve OOS detection in MP

We really need an optional 'pedantic mode' for MP which detects OOSes immediately, by comparing all game state information after each action and printing any mismatches. This mode will be optional because of the extra overhead it adds, and it would be very useful for debugging.

Fix a longstanding bug concerning failure to initialize a side in networked mp

https://gna.org/bugs/index.php?21397

The problem itself is quite simple -- when the server tells a client that their turn has begun, the client immediately broadcasts [init_side] to all the other players via the server, performing the initial upkeep, healing, and movement point reset actions. However, if this player disconnects / blocks the action by opening a dialog during the prior turn and never closing it, [init_side] is never broadcast. And if the game is then saved by one of the other clients, nothing in the current mechanism detects that this has been overlooked when the game is reloaded. The consequence is that in the reloaded game, that side's turn is *never* initialized -- they get no gold, their units don't heal, and they don't get full move points at the start of the turn.

Propose a mechanism to fix this -- perhaps games which have been loaded should be scanned to see if the current turn failed to initialize. Perhaps a flag in game_state could be used and saved. Perhaps a completely different approach. Check that your mechanism works whether the save is loaded from [snapshot] or [replay_start] and [replay].

This bug has existed since at least Wesnoth 1.8

Make a "play single move" button in the replay viewer

This is an often requested feature. The idea is to have a third button which plays until a move or attack command appears, then stops again.

https://gna.org/bugs/?9354

MP Related

Automatically resolve add-on dependencies

In 1.11 add-ons may declare dependencies. A related easy coding task is to allow the user to force breaking dependencies.

A related goal which would be greatly beneficial would be that wesnoth can automatically resolve the dependencies by fetching the add-ons from the download server, when in the MP-lobby the user tries to join a game with a dependency they don't meet. A dialog would ideally be provided as well, or perhaps a preference.

https://gna.org/bugs/?21705

Even older: https://gna.org/bugs/?9683

Gold graph

Make a graph feature, presumably in a dialog, that helps depict the history of the game. For example it could display army value, army + bank value, number of villages tagged, luck swings... the purpose would be to assist spectators of a live game / spectators of a replay to understand the history of the game. It would be particularly helpful with AI development, by helping AI developers to identify key points where one of the AI is making a big mistake.

A possible nice feature for this purpose would be to allow the user to click on the graph at key points which would trigger the "back to turn" mechanism to jump back in the replay, or automatically play the replay forwards from the beginning to that point... etc.

Related email on dev-talk: https://mail.gna.org/public/wesnoth-dev/2014-02/msg00089.html

Automatically link up to wesnothd server on a local network

The feature request was to use ZeroConf technology, if available, to publish info of a running wesnothd instance to other machines on a local network. Then when they are searching to connect to an unofficial server, they won't have to learn the IP address.

The extra code should be guarded with preprocessor flags so that ZeroConf does not become a build dependency of wesnoth.

https://gna.org/bugs/?13703

Improvements to AI

Move and targeting phase

AI needs to move units which are not within range of the enemy. This is generally a sequence of moves (some interesting things like 'ambush!' or 'WML event' might happen as a result of those moves, which should interrupt this phase). The problem is that simply doing those moves 1-by-1 is very slow, for two reasons:

  1. movement maps are invalidated after each move, and are recalculated from the start. yet, if we are doing just a sequence of moves, we can just 'remove moved unit from moves' after each move and avoid expensive recalculation of the movement map.
    • Note that WML could mess with the game state at any time, so at the very least, movement will need to be recalculated after a WML event blocks undo (that is, indicates that it changed game state). --Brilliand 01:30, 28 May 2012 (UTC)
  2. most tasks need devoting more than one unit to execute (i.e., it's meaningless to go for the enemy position with just 1 unit). So, making individual decisions just does some repeating calculations, which is slow.

A practical demonstration of these concerns are LoW 2 (dwarf ai is slow due to large avoid aspect) and NR:Showdown (orc AIs there are slow because of huge number of units)


we need a fast and effective 'move and targeting stage' - both ideas and implementations are wanted. Here's Sirp's idea (more in 2009-aug-15 irclog):

--

Eval-based AI

The AI system would be based around an 'eval' function -- a formula which is given a position, and returns a number saying how attractive that position is.

There would also be a 'candidate_moves' function -- a formula which is given a unit and returns a list of 'candidate moves' -- i.e. moves for that unit that the AI should consider making.

The aim of the system is to come up with the combination of candidate moves that gives the best possible evaluation. By doing this, the AI will work in a team, since the 'eval' function can give bonuses for units being close together, protecting each other, etc.

There are likely to be, of course, a very large combination of possible moves, and not every one can possibly be evaluated. Instead, we take a monte carlo approach.

If an AI has N units that it can move, that is an N-dimension matrix of possible moves. We would choose some cells in this matrix at random and then evaluate them. Then, of these cells evaluated we would choose cells that evaluated well, and discard those that did not evaluate well. Then, we would begin with those cells that evaluated well, and choose a scattering of 'close by' cells -- i.e. cells where we only vary some of the dimensions, at random. We would continue to evaluate cells at random, starting with those cells that evaluated well, and evaluating cells nearby. After several iterations, we would hope to arrive at a cell that evaluates very well, and we would use this as our set of moves.

Of course, this system will be made more complex by the uncertainty of attacks. There are a number of ways to handle attacks, probably the easiest being to consider attacks as types of moves, and then if a move combination involving an attack is chosen, perform the attack and then re-run the entire AI algorithm before moving again. (Something similar to what the current AI does).

This is effectively an AI framework, not an AI in itself. How well it performs will correlate strongly with how good an eval() function one can write, and is also based on the notion that generally certain combinations of moves are 'similar' to other combinations.

--

Village grabbing

Improve AI village grabbing algorithm to assign villages that are farther than one turn from current unit location. Idea how to do would be value villages so that it can filter out villages that belongs to enemies/allies sides. Those villages are stored in memory and used in 2nd pass that determines how AI should dispatch units to get villages if it should at all in this turn. This should be close to optimal solution with currently available units but performance limits should be taken into account. Good solution would be that village grabbing value could be calculated with attack ratings and if some village has high value it would make unit go for that village instead

This should help AI in begin of scenario. Currently AI might not grab all of villages that belong to its area which results quite large incoming loses. In later game enemy might have large number of units in one part of map so village grabbing should be avoided in that are. Single unit would be easy pray for enemy so moving there would result just to loses.

Data Structures

Config Writer

The speed of saving Wesnoth games is dominated by the time to marshall all the config structures. This involves deep copying them many times as each subsystem returns its config bundle; far better would be to have a "config_writer" class which is handed to each subsystem which iterates through its structures and does the writing (to file or network) directly to the config_writer instance.

Stop by #wesnoth-dev on freenode irc if you want to help with this, or post in the Coder's Corner.

Config memory optimisation

Right now, most of the memory used by wesnoth when using low_memory configuration flag is used by the config object trees. It would be possible to drop unused "branches" of that trees by using boost smart pointers in the config structure

come and discuss that change on #wesnoth-dev. Sirp is the one that knows the most about that...

Improvements to Unit Map

As described here: [1] (cjhopman has submitted a patch on that already)

See Also

Frequently Proposed Good Ideas

Check the B.W.H. list in the Ideas Forum. Be aware that some entries there are old and have already been implemented, so you will need to investigate that before beginning work.