La map de dégâts

> Programmation

Avec l'évaluation des déplacements et la gestion des combinaisons d'attaque, la map de dégâts est un grand indispensable dans LeekWars. L'objectif principal est de pouvoir évaluer, en fonction de l'adversaire, un niveau de dangerosité de chaque case afin de pouvoir se replier vers une case de moindre danger en fin de tour. Le plus simple est de créer un tableau associatif : dangerMap=[ cell1:danger1 , cell2:danger2 , ... ], éventuellement limité à vos cases accessibles. À cette fin, plusieurs algorithmes sont possibles

L'algorithme "naif"

C'est généralement la première idée qui vient à l'esprit lorsqu'on veut créer un algorithme d'évaluation du danger. L'idée est la suivante :

/* -pour chacune de mes cellules accessibles -pour chaque adversaire -pour chaque cellule accessibles de l'adversaire -pour chaque arme de l'adversaire -s'il peut tirer sur ma cellule depuis sa cellule ajouter un "score de danger" à ma cellule */

Le choix du score fait partie intégrante de votre algorithme : on peut y mettre "+1", ou calculer les dégats potentiellements infligés, ... Il y a autant de façon de raffiner cette évaluation que de joueurs 😉

Le gros problème de cet algorithme, c'est qu'il est extrêmement glouton en opérations! Il faut donc généralement très rapidement l'optimiser.

Pistes d'optimisations

La première chose à faire, c'est empêcher votre poireau de "planter" ... Il faut donc, à un endroit du code, faire un test sur getOperations() et sortir des boucles si le nombre d'opérations s'approche trop de la limite : vous n'aurez qu'une évaluation partielle du danger, mais votre poireau sera encore en mesure de bouger un minimum 😉

Pour l'optimisation proprement dite, un des premiers principes qui doit guider votre démarche, c'est avant tout d'éviter de refaire plusieurs fois, dans les boucles, les mêmes opérations : il vaut mieux dans ce cas préparer des choses dans des tableaux à rappeler ensuite. Ainsi, par exemple, dans la boucle la plus interne qui calcule le "score de danger", si vous y collez un appel à getStrength(enemy), vous allez rappeller cette fonction plusieurs milliers de fois. L'idée est alors de calculer une seule fois la force de l'ennemi et de la stocker dans une variable avant de faire les boucles internes. Vous commencerez déjà par gagner quelques centaines de milliers d'opérations! Faites donc la chasse aux éléments des boucles "internes" qui ne dépendent pas de la variable de la boucle, mais uniquement d'une boucle "externe" : vous pouvez alors remonter ces éléments jusqu'à leur boucle.

Si votre algorithme reste couteux, une autre piste d'optimisation, assez esthétique, est de dégrader la résolution de cette évaluation. Vous pouvez, par exemple, ne pas tester toutes les cases accessibles (les votres et/ou celles de l'adversaire), mais, par exemple, seulement celles qui demandent un nombre de points de mouvement pair. Il "suffit" ensuite de combler les trous obtenus par interpolation des valeurs sur les cases voisines (moyenne des voisins, maximum des voisins, maximum de la moyenne entre deux lignes, ...). Cette approche est moins précise, mais, avec l'exemple des MP pairs, consomme environ 4x moins que le premier algorithme.

Pour poursuivre les optimisations, il va vous falloir réfléchir à pré-calculer des choses, généralement au premier tour, à stocker dans de gros (ou de nombreux) tableaux certaines choses que vous devez re-calculer et qui ne changent jamais, voire mettre à jour certaines valeurs à chaque tour (dans notre exemple, la force des poireaux ennemis).

L'algorithme "une fois pour toute"

Cet algorithme pré-calcule une map de danger une seule fois en début de combat. Peu couteuse, elle est beaucoup moins précise mais permet d'avoir rapidement la liste des zones de la map de combat qui sont globalement dangeureuse. Elle consiste à évaluer, en début de tour, pour chaque cellule de la map de combat, toutes les cellules qui permettent de tirer dessus avec les armes que possède le/les ennemis : une case qui n'est atteignable que depuis 5 autres cases aura alors un score beaucoup plus faible qu'une case atteignable par 200 autres cases! Il sera peut être judicieux d'essayer de se replier dans les zones de "faible danger", et d'amener l'ennemi à rester dans les zones de "fort danger".