Jouer un coup¶

Le jeu Candy Crush Saga est certes composé de niveau tous différents les uns des autres, mais chacun des niveaux reposent sur un unique et même principe : permuter deux bonbons. Il faut respecter deux règles très simples pour que la permutation soit effective et qu'elle soit reconnue comme un coup :

1. Seul deux bonbons parfaitement côte à côte peuvent être permutés. Une permutation en diagonal est donc impossible.
2. La permutation des bonbons doit directement amener sur un alignement horizontal ou vertical d'au moins 3 bonbons identiques.

Lorsqu'une permutation amène à un alignement de plus de 3 bonbons, un nouveau bonbon spécial apparaît. Il en existe plusieurs, et chacun possède un bonus propre. Ces bonus sont déclenchés lorsque le bonbon spécial est détruit, et permette de détruire de nombreux bonbons. Que ce soit la destruction d'une ligne, d'une colonne, des bonbons voisins, ou bien tous les bonbons de la même couleur dans la grille, les bonus permettent de marquer de nombreux points. Chercher le meilleur coup c'est donc chercher la permutation qui détruira ou formera le plus de bonbon spéciaux possible. Pour cela il existe 3 formes différentes. Dans l'ordre d'importance :

Un alignement de quatre bonbons identiques forme un bonbon rayé.
Un double alignement de trois bonbons identiques forme un bonbon emballé
Un alignement de cinq bonbons identiques forme un bonbon chocolat

En tenant compte de ces règles, et en regroupant les différentes formes d'alignement à rechercher nous avons pu mettre en place un algorithme qui recherche et assigne directement un score à chaque coup.