The damage map

> Programming

With the evaluation of the displacements and the management of the combinations of attack, the map of damage is essential in LeekWars. The main objective is to evaluate, according to the opponent, a level of danger of each square in order to be able to withdraw towards a cell of lesser danger at the end of the turn. The easiest way to do this is to create an associative table: HazardMap=[ cell1:hazard1 , cell2:hazard2 , ... ], possibly limited to your accessible cells.

For this purpose, several algorithms are possible.

The "naive" algorithm

This is usually the first idea that comes to mind when one wants to create a hazard assessment algorithm. The idea is described here :

/* -for each of my accessible cells -for each opponent -for each accessible cell of the opponent -for each weapon of the opponent -if he can shoot at my cell from his cell add a "hazard score" to my cell */

The choice of the score is a part of your algorithm: you can put "+1" on it, or calculate the potential damage inflicted, ... There are as many ways to refine this evaluation as there are players 😉

The big problem with this algorithm is that it is extremely gluttonous in operations! So you usually have to optimize it very quickly.

Areas for improvement

The first thing to do is to prevent your leek from crashing ... So, at some point in the code, you have to test getOperations() and get out of the loops if the number of operations is too close to the limit: you will only have a partial assessment of the danger, but your leek will still be able to move 😉

For the optimisation itself, one of the first principles that should guide your approach is to avoid repeating the same operations several times in loops: in this case, it is better to prepare things in arrays to be recalled later. So, for instance, in the innermost loop which calculates the "danger score", if you paste in a call to getStrength(Enemy), you will call this function several thousand times. The idea is then to calculate the enemy's strength once and store it in a variable before doing the inner loops. You will already start saving a few hundred thousand operations! So hunt down the elements of the "inner" loops that do not depend on the loop variable, but only on an "outer" loop: you can then trace these elements back to their loop.

If your algorithm is still computationally expensive, another way to optimise it is to degrade the resolution of this evaluation. You can, for instance, not test all the accessible cells (yours and/or the opponent's), but, for instance, only those which require an even number of movement points. It is then "sufficient" to fill in the holes obtained by interpolating the values on the neighbouring cells (average of the neighbours, maximum of the neighbours, maximum of the average between two lines, ...). This approach is less accurate, but, with the example of even PMs, consumes about 4x less than the first algorithm.

To continue optimising, you'll need to think about pre-calculating things, usually on the first turn, storing in large (or many) tables some things that you need to re-calculate and that never change, or even updating some values on each turn (in our example, the enemy leeks strength)

The "once and for all" algorithm

This algorithm pre-calculates a hazard map only once at the beginning of the fight. It is not very computationally costly, but it is much less precise, but it allows you to quickly have a list of the parts of the combat map that are globally dangerous. It consists in evaluating, at the beginning of the turn, for each cell of the combat map, all the cells that can be shot at with the weapons possessed by the enemy(s): a cell that can only be reached from 5 other cells will then have a much lower score than a cell that can be reached from 200 other cells! It may be wise to try to retreat to the "low risk" areas, and to make the enemy stay in the "high risk" areas.