Etude préliminaire
Tout d’abord le DEMINEUR c’est quoi ? (merci Wikipedia)
Le démineur est un jeu de réflexion dont le but est de localiser des mines cachées dans un champ virtuel avec pour seule indication le nombre de mines dans les zones adjacentes. Le champ de mine est représenté par une grille, qui peut avoir différentes formes : deux ou trois dimensions, pavage rectangulaire ou non, etc.
Chaque case de la grille peut soit cacher une mine, soit être vide. Le but du jeu est de découvrir toutes les cases libres sans faire exploser les mines, c’est-à-dire sans cliquer sur les cases qui les dissimulent.
Lorsque le joueur clique sur une case libre et que toutes les cases adjacentes le sont également, une case vide est affichée. Si en revanche au moins l’une des cases avoisinantes contient une mine, un chiffre apparaît, indiquant le nombre de cases adjacentes contenant une mine. En comparant les différentes informations récoltées, le joueur peut ainsi progresser dans le déminage du terrain. S’il se trompe et clique sur une mine, il a perdu.
Nous avons là l’essentiel utile pour nous attaquer à l’exercice, je vous encourage cependant à lire la définition complète sur Wikipedia car les algorithmes de placement des bombes et pour trouver les valeurs des cases y sont proposés.
Les pré-requis
Je vous recommande fortement d’avoir au moins lu les exercices suivants : PONG, SNAKE, TAQUIN
Les exercices sont courts mais de nombreuses astuces y sont proposées, je ne les expliquerai pas à chaque nouvel exercice.
Pour ce programme vous devez connaître :
Variables et types : http://help.adobe.com/fr_FR/FlashPl...
Fonctions et paramètres : http://help.adobe.com/fr_FR/FlashPl...
Manipulation de tableaux : http://help.adobe.com/fr_FR/FlashPl...
Ecouteurs d’événements : http://help.adobe.com/fr_FR/FlashPl...
Si vous souhaitez plus de précisions sur ces points, je vous encourage à parcourir le Wiki de Mediabox où vous trouverez de nombreux tutoriaux détaillés.
Le code
Voyons d’abord tout le code d’un coup.
// variables
var W:int = stage.stageWidth;
var T:int = 32;
var C:int = W/T;
var N:int;
var F:int;
var i:int;
// tableaux de stockage
var tuiles:Array;
var voisins:Array;
// interface
var panneaux:Panneaux = new Panneaux();
panneaux.addEventListener(MouseEvent.MOUSE_DOWN, init);
panneaux.buttonMode = true;
addChild(panneaux);
// initialisation du jeu
function init(e:MouseEvent):void{
tuiles = [];
voisins = [];
N = 10;
F = C*C-N;
while(numChildren>0) removeChildAt(0);
// placer les tuiles
for (i=0;i<C*C;i++){
var t:Tiles = new Tiles();
t.x = int(i%C)*T;
t.y = int(i/C)*T;
t.width = t.height = T;
t.id = i;
t.val = 0;
addChild(t);
tuiles.push(t);
voisins.push([]);
t.mouseEnabled= false;
}
// placer les bombes
while(N) {
var n:int = Math.random()*tuiles.length;
var p:Object = tuiles[n];
if(p.val!=9) p.val=9, N--, trouveValeurs(n,p.x/T,p.y/T,C-1);
}
for each(var j in tuiles) if(j.val) j.chiffre.text = j.val;
stage.addEventListener(MouseEvent.CLICK, action);
}
// trouver les valeurs des cases
function trouveValeurs(i:int,X:int,Y:int,L:int):void{
if(Y<L && tuiles[i+C].val != 9) tuiles[i+C].val++;
if(Y>0 && tuiles[i-C].val != 9) tuiles[i-C].val++;
if(X<L && tuiles[i+1].val != 9) tuiles[i+1].val++;
if(X>0 && tuiles[i-1].val != 9) tuiles[i-1].val++;
if(X<L && Y>0 && tuiles[i-C+1].val != 9) tuiles[i-C+1].val++;
if(X>0 && Y>0 && tuiles[i-C-1].val != 9) tuiles[i-C-1].val++;
if(X<L && Y<L && tuiles[i+C+1].val != 9) tuiles[i+C+1].val++;
if(X>0 && Y<L && tuiles[i+C-1].val != 9) tuiles[i+C-1].val++;
}
// cliquer sur une case
function action(e:Event):void{
i = int(mouseX/T)+int(mouseY/T)*C;
if(tuiles[i].currentFrame==1) tuiles[i].gotoAndStop(2), F--;
if(tuiles[i].val==9) tuiles[i].gotoAndStop(3), finPartie(2);
if(!tuiles[i].val) decouvre(i);
if(F==0) finPartie(3);
}
// découvrir les cases vides
function decouvre(n:int):void{
trouveVoisin(n,tuiles[n].x/T,tuiles[n].y/T,C-1);
for each(var h in voisins[n]){
if (h.currentFrame==1) {
if(!F--) finPartie(3);
h.gotoAndStop(2);
decouvre(h.id);
}
}
}
// trouver les cases vides voisines
function trouveVoisin(i:int,X:int,Y:int,L:int):void{
if(X>0 && !tuiles[i-1].val) voisins[i].push(tuiles[i-1]);
if(X<L && !tuiles[i+1].val) voisins[i].push(tuiles[i+1]);
if(Y>0 && !tuiles[i-C].val) voisins[i].push(tuiles[i-C]);
if(Y<L && !tuiles[i+C].val) voisins[i].push(tuiles[i+C]);
}
// fin de partie
function finPartie(G:int):void{
addChild(panneaux);
panneaux.gotoAndStop(G);
stage.removeEventListener(MouseEvent.CLICK, action);
}
Etude du programme
Comme d’habitude j’utilise la bibliothèque de Flash pour gérer les graphismes, ce qui me permet d’alléger le code et de ne conserver que ce qui est utile pour l’exercice, si vous n’utilisez pas Flash voici les modifications à faire dans le programme :
Panneaux :
* un clip qui regroupe tous les panneaux d’interface
* un panneau différent par frame
Tiles :
* un clip qui regroupe toutes les tuiles
* une tuile sur chaque frame
* la tuile 1 représente le cache des pièces
* la tuile 2 représente la pièce vide
* la tuile 3 représente une bombe
* sur un second calque se trouve le champ texte affichant la valeur de la case
Jetons un oeil au code, si vous avez lu les pré-requis on va pouvoir aller assez vite :
// variables
var W:int = stage.stageWidth;
var T:int = 32;
var C:int = W/T;
var N:int;
var F:int;
var i:int;
// tableaux de stockage
var tuiles:Array;
var voisins:Array;
// interface
var panneaux:Panneaux = new Panneaux();
panneaux.addEventListener(MouseEvent.MOUSE_DOWN, init);
panneaux.buttonMode = true;
addChild(panneaux);
Ok tout ça ne vous est pas inconnu, c’est toujours le même principe, je commence par déclarer toutes mes variables globales, tableaux et je pose l’interface, notons simplement :
W = largeur du jeu
T = largeur des tuiles
C = nombre de colonnes
N = nombre de bombes
F = nombre de pièces à découvrir pour finir le jeu
i = pointeur qui sert dans diverses boucles
tuiles = stockage des pièces
voisins = stockage des pièces voisines
Le jeu étant carré je n’ai pas besoin de la hauteur ni du nombre de lignes, il y a autant de lignes que de colonnes, pensez à ajouter la hauteur si vous changez la forme de la grille.
Vous remarquerez que je trouve le nombre de colonnes (et donc de lignes) à l’aide de la taille du jeu divisée par la taille des pièces, du coup vous pouvez adapter le nombre de cases de la grille en modifiant simplement la taille des pièces, faites cependant attention à ce que la taille d’une pièce soit toujours une fraction de la taille du jeu.
// initialisation du jeu
function init(e:MouseEvent):void{
tuiles = [];
voisins = [];
N = 10;
F = C*C-N;
while(numChildren>0) removeChildAt(0);
// placer les tuiles
for (i=0;i<C*C;i++){
var t:Tiles = new Tiles();
t.x = int(i%C)*T;
t.y = int(i/C)*T;
t.width = t.height = T;
t.id = i;
t.val = 0;
addChild(t);
tuiles.push(t);
voisins.push([]);
t.mouseEnabled= false;
}
// placer les bombes
while(N) {
var n:int = Math.random()*tuiles.length;
var p:Object = tuiles[n];
if(p.val!=9) p.val=9, N--, trouveValeurs(n,p.x/T,p.y/T,C-1);
}
for each(var j in tuiles) if(j.val) j.chiffre.text = j.val;
stage.addEventListener(MouseEvent.CLICK, action);
}
La toute première chose à faire est d’initialiser le jeu, je commence par vider les tableaux (pour le cas où on recommencerai une partie), donner une valeur à mes variables globales, le nombre de bombes et le nombre de pièces à jouer, et à ce propos justement :
F = C*C-N;
Autant de lignes que de colonnes, donc le nombre total de pièces est égal au nombre de colonnes au carré, je retire le nombre de bombes et je trouve le nombre de pièces à découvrir pour gagner la partie.
while(numChildren>0) removeChildAt(0);
Je vide la liste d’affichage avant de replacer de nouvelles pièces.
// placer les tuiles
for (i=0;i<C*C;i++){
var t:Tiles = new Tiles();
t.x = int(i%C)*T;
t.y = int(i/C)*T;
t.width = t.height = T;
t.id = i;
t.val = 0;
addChild(t);
tuiles.push(t);
voisins.push([]);
t.mouseEnabled= false;
}
On a vu dans la Taquin la méthode pour passer d’une liste à une grille 2D, on ne va donc pas revenir dessus, notez que j’indique à chaque pièce la taille qu’elle doit avoir dans la grille, cela me permet d’adapter la grille quel que soit le nombre de pièces.
t.id = i;
t.val = 0;
J’aurai besoin par la suite de retrouver l’index de mes pièces dans le tableau de stockage des tuiles, cependant pour m’éviter de parcourir le tableau à chaque fois je vais simplement passer l’index en paramètre de la tuile (id).
De même, chaque tuile à une valeur déterminée par la proximité ou non des bombes, pour éviter d’aller stocker ça ailleurs je vais également passer cette valeur en paramètre de la tuile, pour le départ toutes les pièces ont une valeur de 0.
tuiles.push(t);
voisins.push([]);
A chaque tuile créée je la pousse dans le stock, et je crée également un nouveau tableau à son index dans le stock des voisins, et là je sent bien que je vous perds, petite explication :
Je ne vais pas entrer dans les détails tout de suite, sachez simplement que chaque pièce à potentiellement (c’est important) besoin de déterminer quelles sont ses voisines, par exemple :
0 0 0
0 X 0
0 0 0
La pièces "X" à 8 voisines. Pour chaque pièce je vais donc créer un petit tableau de stockage où je glisserai les pièces voisines lorsque j’ai besoin d’effectuer un test, c’est pourquoi j’ai un nouveau tableau par index des pièces dans le stock des voisines.
// placer les bombes
while(N) {
var n:int = Math.random()*tuiles.length;
var p:Object = tuiles[n];
if(p.val!=9) p.val=9, N--, trouveValeurs(n,p.x/T,p.y/T,C-1);
}
Je viens de créer toutes les pièces de la grille, à présent je veux placer les bombes, pour cela c’est très simple, je fais une boucle sur le nombre de bombes à placer, je tire une pièce aléatoirement dans le stock et je regarde sa valeur. Si c’est déjà une bombe je recommence le tirage, sinon je stipule à la pièce que c’est une bombe (elle prend la valeur 9 puisque les valeurs possibles des pièces vont de 1 à 8), je décrémente le pointeur de la boucle (le nombre de bombes à placer) et je fais une recherche des valeurs des pièces voisines :
trouveValeurs(n,p.x/T,p.y/T,C-1);
C’est avec cet appel de fonction que je vais déterminer la valeur de chaque pièce voisine d’une bombe, on va terminer la fonction "init()" avant de vous expliquer comment ça marche.
for each(var j in tuiles) if(j.val) j.chiffre.text = j.val;
Une fois toutes les pièces posées et toutes les valeurs trouvées, je parcours le stock et pour chaque pièce, si elle n’a pas une valeur nulle (0), j’affiche sa valeur dans le champ texte de la pièce. Je n’affiche pas les valeurs nulles uniquement par choix esthétique, cela n’a aucune incidence sur le programme.
Revenons à présent au placement des bombes et à la recherche des valeurs des cases voisines.
// trouver les valeurs des cases
function trouveValeurs(i:int,X:int,Y:int,L:int):void{
if(Y<L && tuiles[i+C].val != 9) tuiles[i+C].val++;
if(Y>0 && tuiles[i-C].val != 9) tuiles[i-C].val++;
if(X<L && tuiles[i+1].val != 9) tuiles[i+1].val++;
if(X>0 && tuiles[i-1].val != 9) tuiles[i-1].val++;
if(X<L && Y>0 && tuiles[i-C+1].val != 9) tuiles[i-C+1].val++;
if(X>0 && Y>0 && tuiles[i-C-1].val != 9) tuiles[i-C-1].val++;
if(X<L && Y<L && tuiles[i+C+1].val != 9) tuiles[i+C+1].val++;
if(X>0 && Y<L && tuiles[i+C-1].val != 9) tuiles[i+C-1].val++;
}
Comme expliqué sur la page Wikipedia du Démineur, il y a deux algorithmes possibles pour trouver la valeur des cases, soit parcourir tout le stock et vérifier case par case l’ensemble des ses voisines et déterminer combien il y a de bombes dans le voisinage, ce qui peut s’avérer lent si on a un grand nombre de cases, soit incrémenter la valeur des cases adjacentes lorsqu’on pose une bombe, ce qui est beaucoup plus optimisé car on aura jamais autant de bombes que de pièces dans la grille, question de jouabilité ;-)
Lorsque je pose une bombe je vais donc chercher les pièces voisines et incrémenter leurs valeurs, les valeurs étant propres à chaque pièce, si je pose une bombe juste à côté de la première la valeur des pièces mitoyennes s’incrémente, voilà où réside toute l’astuce pour la recherche des valeurs.
Nous avons vu plus haut qu’une pièce (bombe ou pas) comporte en général 8 voisines, pour les trouver il suffit donc de partir de la bombe concernée (B dans le schéma) et de regarder les pièces voisines dans la grille, mais rappelez-vous que nous travaillons avec une liste (le stock) où il n’y a pas de différenciation entre les lignes et les colonnes, voici comment je retrouve mes petits :
Placement de B et de ses voisines :
0 0 0
0 B 0
0 0 0
Trouver la pièce de gauche : B-1 (index précédent dans le stock)
Trouver la pièce de droite : B+1 (index suivant dans le stock)
Trouver la pièce du haut : B-C (index de la bombe moins nombre de colonnes)
Trouver la pièce du bas : B+C (index de la bombe plus nombre de colonnes)
Voyons si vous avez compris, voici les diagonales :
Trouver la pièce haut gauche : B-C-1
Trouver la pièce haut droite : B-C+1
Trouver la pièce bas gauche : B+C-1
Trouver la pièce bas droite : B+C+1
Je suis persuadé qu’il existe une solution plus courte à base d’opérateurs binaires et de boucles, mais à ce stade je préfère décomposer pour ce que soit bien clair pour tout le monde, libre à vous de faire vos expériences à ce niveau ;-)
Ok on sait comment trouver une pièce, maintenant que faire si la pièce sur laquelle on tombe est une bombe ? Et bien on ne la prend tout simplement pas en compte, d’où le " !=9" qui stipule que si la valeur de la pièce est un 9 on ne fait rien.
Reste la première partie de chaque condition pour chaque pièce qui peut vous paraître obscure, elle utilise la position de la bombe dans la grille (X et Y), elle est imposée par le fait que je travaille avec une liste (le stock) et via les index de cette liste et non une grille 2D. Lorsqu’une bombe est placée en bordure de la grille il ne faut pas pouvoir tester les cases qui sont normalement en dehors de la grille, mais comme nous travaillons avec des index nous n’avons pas ce type de limite, il faut l’ajouter.
Prenons un exemple, si j’ai une bombe placée sur la dernière case à droite d’une ligne de la grille. Je ne dois pas pouvoir tester la case suivante puisqu’elle n’est pas sensée exister, pourtant l’index suivant existe bien dans le stock, il s’agit de la première case de la ligne suivante. Je vais donc regarder la colonne (X) où se trouve la bombe, et vérifier que ce n’est pas la dernière colonne de la grille (X
Ce qui vaut pour les colonnes vaut aussi pour les lignes, c’est pourquoi on utilise deux tests, X et Y selon la case traitée.
// cliquer sur une case
function action(e:Event):void{
i = int(mouseX/T)+int(mouseY/T)*C;
if(tuiles[i].currentFrame==1) tuiles[i].gotoAndStop(2), F--;
if(tuiles[i].val==9) tuiles[i].gotoAndStop(3), finPartie(2);
if(!tuiles[i].val) decouvre(i);
if(F==0) finPartie(3);
}
Lorsque le joueur clique, je récupère la position de la souris que je transforme en position relative dans la grille (colonne et ligne). Si la case correspondante n’est pas vide (et n’est pas une bombe), je vide graphiquement la case (on passe à la frame 2 de la tuile) et je décrémente le nombre de pièces à découvrir pour gagner la partie.
Si la pièce est une bombe, j’affiche la bombe et j’appelle la fonction de fin de partie puisque le joueur à perdu.
Si la valeur de la pièce est nulle (0), je découvre la pièce et je vérifie ses voisines (on va y revenir tout de suite).
Et enfin, si il ne reste plus de pièces à découvrir, le joueur gagne la partie.
// découvrir les cases vides
function decouvre(n:int):void{
trouveVoisin(n,tuiles[n].x/T,tuiles[n].y/T,C-1);
for each(var h in voisins[n]){
if (h.currentFrame==1) {
if(!F--) finPartie(3);
h.gotoAndStop(2);
decouvre(h.id);
}
}
}
Bienvenue dans la récursivité ;-)
Cette fonction est appelée quand le joueur clique sur une pièce dont la valeur est nulle (pas de bombe à proximité), dans le jeu original toutes les pièces contiguës ayant une valeur nulle se révèlent d’un coup. Je vais m’efforcer de reproduire ce comportement et pour cela je vais utiliser la récursivité, c’est à dire la répétition de la même fonction au sein d’elle même. Pas de panique on va étudier le bout de code :
trouveVoisin(n,tuiles[n].x/T,tuiles[n].y/T,C-1);
On commence par trouver les cases voisines de la case ayant une valeur nulle, on va faire un petit aparté pour étudier la fonction appelée ici :
// trouver les cases vides voisines
function trouveVoisin(i:int,X:int,Y:int,L:int):void{
if(X>0 && !tuiles[i-1].val) voisins[i].push(tuiles[i-1]);
if(X<L && !tuiles[i+1].val) voisins[i].push(tuiles[i+1]);
if(Y>0 && !tuiles[i-C].val) voisins[i].push(tuiles[i-C]);
if(Y<L && !tuiles[i+C].val) voisins[i].push(tuiles[i+C]);
}
On a étudié le principe plus haut, on ne va donc pas revenir dessus, on cherche les cases voisines mais cette fois on ne prend pas en compte les diagonales, puisque nous cherchons les cases directement à proximité, et la valeur de la case à prendre en compte n’est plus 9 (les bombes) mais 0 (les cases vides) autrement dit ayant une valeur nulle.
Revenons à notre fonction récursive :
for each(var h in voisins[n]){
if (h.currentFrame==1) {
if(!F--) finPartie(3);
h.gotoAndStop(2);
decouvre(h.id);
}
}
Je fais une boucle sur toutes les cases voisines trouvées pour la pièce en cours de test. Si la pièce voisine concernée à ce moment dans la boucle n’est pas encore découverte, je décrémente le nombre de pièce restant à découvrir et je vérifie dans le même temps si le joueur à gagné. Puis je passe la pièce en frame 2 (elle est donc à présent découverte) et je relance ma fonction pour cette nouvelle pièce découverte, ce qui n’empêche pas la fonction de passer aussi à la pièce suivante dans la boucle des voisines.
Pour faire clair, pour chaque nouvelle pièce découverte ayant une valeur nulle, je vérifie ses voisines et relance les mêmes opérations, ainsi je vais pouvoir découvrir toutes les pièces ayant une valeur nulle et contiguës à la pièce découverte au moment où le joueur à cliqué sur une pièce ayant une valeur nulle. La fonction s’arrêtera lorsqu’il n’y a plus de pièces répondant aux critères demandés.
Ce type de manipulation récursive est très importante dans les jeux vidéo mais demande de bien maîtriser le processus si vous ne voulez pas vous retrouver avec des boucles infinies et des dépassements mémoire, étudiez bien votre code avant de vous lancer dans la récursivité.
// fin de partie
function finPartie(G:int):void{
addChild(panneaux);
panneaux.gotoAndStop(G);
stage.removeEventListener(MouseEvent.CLICK, action);
}
Appelée à deux conditions, si le joueur gagne ou si il perd, cette fonction bloque le clic de la souris, et affiche le bon panneau d’interface, un nouveau clic sur le panneau relance l’initialisation du jeu que nous avons étudié en début d’exercice, la boucle est bouclée comme on dit ;-)
Conclusion
Ce qu’il est important de voir avec ce petit exercice c’est l’utilisation de la récursivité qui vous sera utile dans de nombreux jeux, mais également la détection des cases voisines qui vous sera également très utile. Notez cependant qu’il existe des méthodes plus optimisées pour chercher les voisines d’une case dans une grille, mais nous n’en sommes pas encore là et je préfères détailler le processus et vous réserver la version optimisée pour un autre exercice.
Les sources sont disponibles à la fin de l’exercice.
