Les cellules accessibles

Les cellules accessibles

> Programmation

Cet algorithme a pour but de trouver les cellules que peut atteindre un poireau en partant d'une cellule et d'un nombre de PM donnés.

Cela se traduit par une fonction prenant en paramètre une cellule et un nombre, et qui retournera un tableau de cellules.

Si on vous parle des fonctions "getAccessibleCells" ou "getReachableCells", ou tout autre nom ressemblant, vous saurez désormais de quoi il s'agit.

Utilisation

A partir du moment où vous souhaiterez prévoir vos déplacements, cette fonction sera indispensable.

Connaître les cellules où vous pouvez aller permet par exemple de choisir la cellule ou vous subirez le moins de dégâts potentiels, ou voir où vous pourriez vous déplacer pour infliger des dégâts à votre adversaire.

Cet algorithme est notamment utilisé dans l'algorithme du Cache-cache (Le cache-cache).

Premières méthodes

Principe

En soi, il est assez simple de mettre en place un moyen d'obtenir les cellules accessibles. La méthode la plus simple est de tester la distance avec chaque cellule de la map en utilisant getPathLength.

Mais cette fonction a un coût en opérations élevé. Alors l'utiliser sur chaque cellule de la map... Votre consommation d'opérations grimperait en flèche.

Une solution un peu plus maligne serait de commencer par trouver les cellules à portée de PM, puis de vérifier qu'elles sont atteignables via getPathLength.

Si ces deux solutions sont réalisables, elles ont un coût en opération devenant rapidement élevé.

Si vous êtes débutant et que la solution que nous allons aborder dans la suite vous semble encore un peu compliquée, n'hésitez pas à vous contenter de ces solutions au début. Au début du jeu, vous n'aurez pas forcément beaucoup de calculs à faire, et à bas niveau, vous n'aurez pas une grande quantité de PM. Ainsi, vous pouvez vous permettre d'utiliser ces solutions.

Le problème

Obtenir vos cellules accessibles par ces méthodes se fera sans souci.

Mais un premier problème se pose lorsque votre nombre de PM augmente. Plus il grimpera, plus il y aura de cases à tester, évidemment. Dans le pire des cas, si vous parcourez toute la map à grand coups de getPathLength, vous devriez vous en sortir avec une facture d'environ 4 millions d'opérations, "seulement".

Autant dire que cela réduit de beaucoup les opérations disponibles pour d'autres algorithmes comme les Combos, ou la Map de dégâts.

Et ce n'est pas tout ! Il y a un autre problème : Vous n'êtes pas tout seul dans un combat. Vous aurez très certainement besoin d'obtenir les cellules accessibles de vos adversaires pour pouvoir vous protéger de leurs attaques. Et si les différents poireaux commencent à invoquer des bulbes, cela fait encore plus de cellules à calculer.

Bref, si vous commencez à vouloir calculer les cellules accessibles de tout ce p'tit monde avec ces méthodes, cela vous coûtera bien plus qu'un bras.

Ainsi, on utilise une autre méthode, bien plus efficace : Aller de voisin en voisin !

Méthode des voisins

Pré-requis

En premier lieu, qu'est-ce qu'un "voisin" ? Les voisins d'une cellule, ce sont simplement les cellules adjacentes à celle-ci. Et on parle évidemment des cellules qui ont un côté commun, les cellules qui sont directement à côté, et non celles en diagonale.

Ainsi, les cellules qui se trouvent dans les coins de la map ont un unique voisin. Les cellules se trouvant sur les bords en ont deux. Et toutes les autres en ont quatre.

La première chose que vous devrez savoir faire est donc de récupérer les voisins d'une cellule. En utilisant les fonctions getCellX, getCellY et getCellFromXY, vous pourrez facilement déterminer ces fameux voisins.

Une fois que vous arrivez à récupérer les voisins d'une cellule, vous devez déterminer si cette cellule est "franchissable". En clair, si la cellule est un obstacle ou qu'un poireau s'y trouve, votre poireau ne pourra pas se déplacer sur celle-ci.

Pour savoir cela, vous aurez besoin des fonctions isObstacle, isEmptyCell, isEntity ou getCellContent.

Principe

Le principe est en fait assez simple. Même s'il n'est pas forcément évident à mettre en place pour un débutant en programmation.

Votre poireau se trouve donc sur une cellule, et il dispose d'un certain nombre de PM pour se déplacer. La cellule sur laquelle il se trouve actuellement se trouve à une distance de 0 PM; jusque là, tout va bien...

Si votre poireau possède 1 PM, où peut-il se déplacer ? Et bien, sur les voisins libres de sa cellule de départ.

Et s'il possède 2 PM ? Il peut donc se déplacer pour 1 PM sur les voisins libres de sa cellule de départ. Mais aussi, pour 2 PM, sur les voisins libres des voisins libres de la cellule de départ.

Et ainsi de suite...

En vert, la cellule de départ. En rouge, les cellules qui sont explorées.

En allant ainsi, de voisin en voisin, on obtient toutes les cellules où l'on peut se déplacer, et en bonus, on a aussi le nombre de PM nécessaire pour chacune.

Mais quand faut-il s'arrêter ? Quand on a plus de PM, évidemment. Et pour savoir cela, il suffit de compter à l'envers.

Si par exemple, un poireau a 3 PM, alors en restant sur place, il lui restera 3 PM. En bougeant d'une cellule, il lui restera 2 PM, etc...

En vert, la cellule de départ. En rouge, les cellules qui sont explorées.

Et hop ! En s'arrêtant à zéro, on obtient uniquement les cellules accessibles avec nos PM.

Enfin, pour gérer les obstacles, il n'y a qu'une chose à faire, si ce n'est pas encore fait. Pour gérer les obstacles, il suffit simplement d'ignorer les cellules qui sont des obstacles, ou qui sont occupées par un poireau. Et évidemment, les bords de map.

Vous devriez obtenir un algorithme agissant comme ceci :

En vert, la cellule de départ. En rouge, les cellules qui sont explorées.

Si vous obtenez ce genre de résultat, alors bravo, vous avez réussi à mettre en place un superbe algorithme de cellules accessibles !

Explosion d'opérations

Attention, cette méthode n'est pas forcément moins chère que celle utilisant getPathLength. Si vous la gérez mal, elle risque de vous coûter bien plus cher.

En effet, lorsque vous explorez la map en allant de voisins en voisins, vous devez être attentif à ne pas revenir en arrière. Vous devez étendre la zone de vos cellules accessibles sans les parcourir à nouveau en sens inverse.

Si vous n'avez pas prévu le coup et que vous parcourez à nouveau des cellules comme sur l'image, le coût en opérations risque d'exploser lorsque vos PM augmenteront.

En rouge, les cellules parcourues. En orange, les cellules qui sont analysées à chaque itération.

A gauche, ce qui devrait se passer. A droite, ce qui peut se passer si vous "revenez en arrière".

Améliorations diverses

Voici quelques améliorations, permettant soit de diminuer le nombre d'opérations de l'algorithme, soit d'obtenir des résultats plus pratiques a utiliser.

Utilisation d'une table (ou tableau associatif)

Pré-requis

Pour pouvoir utiliser cette astuce, il est nécessaire de connaître le fonctionnement des tables et de savoir s'en servir.

Principe

Plutôt que de stocker de manière classique les cases accessibles, ou celles en cours de test, dans un tableau de manière classique, il est possible de les utiliser comme clefs dans une table : ainsi, vérifier si une cellule est accessible, ou a déjà été testée se fait sans utiliser la fonction inArray, mais en faisant simplement :

if(mapContainsKey(table, cellule)) { //la cellule a déjà été testée } else { //la cellule n'a pas encore été testée }

Particularité

Etant donné que les cellules sont les clefs du tableau, il est possible de stocker une information pour chaque cellule, comme par exemple le nombre de PM nécessaires pour se rendre sur cette cellule.

Utilisation d'un cache

Pré-requis

Connaître l'existence des variables globales, savoir mettre des tableaux dans des tableaux, et éventuellement connaître la fonction getTurn.

Principe

Pour une case donnée, les cases voisines n'étant pas des obstacles (si l'on excepte les poireaux) varient généralement peu en combat. Ainsi, il n'est pas nécessaire de les recalculer a chaque appel de la fonction, il suffit de les stocker au tour 1 dans une variable globale, sous la forme d'un gigantesque tableau stockant, pour chaque cellule, un petit tableau contenant tous les voisins non-obstacles. Ainsi, il suffit, pour une cellule donnée, de parcourir ce petit tableau, et de vérifier que chacune de ces cases n'est pas occupée par un poireau. Il est également possible, en début de chaque tour, de modifier la variable globale, pour retirer les voisins occupés par des poireaux (et remettre ceux qui étaient occupés par un poireau au tour précédent).

Utilisation du binaire

Pré-requis

Cette méthode repose sur une représentation de la carte utilisant les propriétés du binaire, et des opérateurs bit à bit : un nombre entier est constitué de 64 bits, et une partie de ces bits permettent de stocker une information concernant une cellule donnée.

Principe

La carte est décomposée en 35 lignes, et on associe a chaque ligne un entier. le bit de rang i de cet entier permet alors de stocker une information sur la i-ième cellule de cette ligne.

!Access binaires

les cases colorées en bleu foncé sont celles de la première ligne, celle en jaune vif appartiennent a la 8ème ligne, et la case rouge est la 3ème case de la 19ème ligne

Il faut ensuite créer deux tableaux respectant ce principe :

Il faut ensuite initialiser l'algorithme en mettant a 1 le bit correspondant a la case de départ, dans le second tableau.

Ensuite, il suffit d'utiliser quelques opérateurs bit à bit afin de pouvoir connaître toutes les cellules adjacentes à celles qui sont déjà accessibles :

//obs correspond ici au premier tableau, indiquant si une cellule est vide ou non //acc correspond ici au second tableau, indiquant si une cellule est accessible ou non

//cas 1, N est pair : acc[N] |= (acc[N-1] | acc[N+1] | (acc[N-1] >> 1) | (acc[N+1] >> 1)) & obs[N] //cas 2, N est impair : acc[N] |= (acc[N-1] | acc[N+1] | (acc[N-1] Note : depuis que les entiers sont représentés sur 64 bits au lieu de 32, il est possible d'utiliser d'autres représentations de la carte que celle-ci. À vous de choisir laquelle vous convient le mieux !

Particularités

Cette méthode utilise les opérateurs bit à bit, qui ont la particularité de coûter seulement une opération chacun. Ainsi, elle est beaucoup moins coûteuse en opérations que les autres. Néanmoins, elle n'est pas parfaite : par exemple, il est plus difficile de savoir combien de mp sont requis pour se déplacer sur une cellule donnée.

Benchmark

N'hésitez pas à vous rendre sur ce sujet du forum Leek Wars.

Vous pourrez confronter les résultats de votre algorithme avec les autres joueurs.

Vous y trouverez aussi de nombreuses pistes pour optimiser le coût en opérations de votre code.