Exercice 09 - DEMINEUR

Exercice 09 - DEMINEUR
Etude préliminaire
Les pré-requis
La structure
L'habillage
Les images
Le code Javascript
Etude du programme
Conclusion
Les sources

Bonjour,

Maintenant qu'on sait utiliser la récursivité (voir exercice précédent), si on mettait ça en application avec un jeu que tout le monde connait ?

Avant de commencer, voici à quoi tout ceci va ressembler.

*pour des raisons de sécurité il n'est pas possible de vous présenter le jeu au sein d'une page du wiki, reportez-vous à la source située en bas de cette page pour voir comment ça marche.

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

Pour ce programme vous devez connaître :

Création d'une page HTML : http://forums.mediabox.fr/wiki/tutoriaux/html_et_css/html/les-rudiments-html
Variables et fonctions en Javascript : http://forums.mediabox.fr/wiki/tutoriaux/javascript/language/notions_base
Ecouteurs d'événements en Javascript : https://developer.mozilla.org/fr/docs/Web/API/EventTarget/addEventListener
Manipulation de tableaux en Javascript : http://www.commentcamarche.net/contents/587-javascript-les-tableaux
Exercice PONG en Javascript : http://forums.mediabox.fr/wiki/tutoriaux/javascript/divers/exercice_pong
Exercice TAQUIN en Javascript : http://forums.mediabox.fr/wiki/tutoriaux/javascript/divers/exercice_taquin
Exercice MEMORY en Javascript : http://forums.mediabox.fr/wiki/tutoriaux/javascript/divers/exercice_memory
Exercice CASCADE en Javascript : http://forums.mediabox.fr/wiki/tutoriaux/javascript/divers/exercice_cascade

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.

La structure

Le support principal est une page HTML classique utilisant une simple balise canvas et intégrant une feuille de style et le script du jeu.

<!DOCTYPE html>
<html>
    <head>
        <title>DEMINEUR</title>
	<link rel="stylesheet" type="text/css" href="css/styles.css" />
	<script type="text/javascript" src="js/jeu.js"></script>
	<!--[if lt IE 9]><script type="text/javascript" src="excanvas.compiled.js"></script><![endif]-->
    </head>
    <body>
         <canvas id="canvas">Votre navigateur ne supporte pas HTML5.</canvas>
    </body>
</html>

L'habillage

J'ajoute une bordure à la balise canvas :

canvas {
    border: 1px solid black;
}

Les images

Je prépare tous mes assets, c'est à dire toutes les images prédécoupées qui vont servir à mon jeu.

Je range le tout dans le dossier “assets”.

Le code Javascript

// variables
var canvas, ctx, posX, posY, T, C, N,F,i,images,tuiles,voisins;
 
// quand la page est chargée
window.onload = function() {
    canvas = document.getElementById('canvas');
    ctx = canvas.getContext('2d');
	canvas.width = 480;
	canvas.height = 480;
	posX = canvas.offsetLeft;
	posY = canvas.offsetTop;
	T = 32;
	C = 480/T;
	loadImages(3);
}
 
// chargement des images
function loadImages(nbImg){
	images = [];
	for(i=1; i<nbImg+1; i++){
		var b = new Image();
		b.src = "assets/tuile"+i+".jpg";
		b.onload = function() {
			images.push(this);
			if(--nbImg==0) init();
		};
	}
}
 
// initialisation du jeu
function init() {
 
	tuiles = [];
	voisins = [];
	N = 20;
	F = C*C-N;
 
	// placer les tuiles
	for (i=0;i<C*C;i++){
		var t = {};
		t.x = parseInt(i%C)*T;
		t.y = parseInt(i/C)*T;
		t.width = t.height = T;
		t.id = i;
		t.frame = 1;
		t.val = 0;
		tuiles.push(t);
		voisins.push([]);
	}
 
	// placer les bombes
	while(N) {
		var n = parseInt(Math.random()*tuiles.length);
		var p = tuiles[n];
		if(p.val!=9) {
			p.val=9; 
			N--;
			trouveValeurs(n,p.x/T,p.y/T,C-1);
		}
	}
 
	render();
	canvas.addEventListener("click", action, false);
}
 
// cliquer sur une case
function action(e){
	i = parseInt((e.clientX-posX)/T)+parseInt((e.clientY-posY)/T)*C;
	if(tuiles[i].frame==1) tuiles[i].frame=2, F--;
	if(tuiles[i].val==9) {
		tuiles[i].frame=3;
		finPartie();
		return;
	}
	if(!tuiles[i].val) decouvre(i); 
	if(F==0) finPartie(3);
	render();
}
 
// trouver les valeurs des cases
function trouveValeurs(i,X,Y,L){
	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++;
}
 
// découvrir les cases vides
function decouvre(n){
	trouveVoisin(n,tuiles[n].x/T,tuiles[n].y/T,C-1);
	for (var h = 0; h<voisins[n].length; h++){
		if (voisins[n][h].frame==1) {
			if(!F--) finPartie();
			voisins[n][h].frame = 2;
			decouvre(voisins[n][h].id);
		}
	}
}
 
// trouver les cases vides voisines
function trouveVoisin(i,X,Y,L){
	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(){
	render();
	alert("Fin de partie, cliquez pour rejouer.");
	init();
}
 
// Dessine le jeu
function render() {	
	for(var i=0; i<tuiles.length; i++){
		ctx.drawImage(images[tuiles[i].frame-1], tuiles[i].x, tuiles[i].y);
		if(tuiles[i].val && tuiles[i].frame==2) afficheValeur(tuiles[i]);
	}	
}
 
// Affiche la valeur de la pièce
function afficheValeur(p) {		
	ctx.fillStyle = "white";
	ctx.font = "16px Arial";
	ctx.textAlign = "center";
	ctx.fillText(p.val, p.x+p.width/2, p.y+p.height/2+4);
}

Etude du programme

Nous sommes au neuvième exercie basé sur la même structure, on va donc aller très vite.

// variables
var canvas, ctx, posX, posY, T, C, N,F,i,images,tuiles,voisins;
 
// quand la page est chargée
window.onload = function() {
    canvas = document.getElementById('canvas');
    ctx = canvas.getContext('2d');
	canvas.width = 480;
	canvas.height = 480;
	posX = canvas.offsetLeft;
	posY = canvas.offsetTop;
	T = 32;
	C = 480/T;
	loadImages(3);
}
 
// chargement des images
function loadImages(nbImg){
	images = [];
	for(i=1; i<nbImg+1; i++){
		var b = new Image();
		b.src = "assets/tuile"+i+".jpg";
		b.onload = function() {
			images.push(this);
			if(--nbImg==0) init();
		};
	}
}

Les variables globales, la préparation du jeu, le chargement des images.

// initialisation du jeu
function init() {
 
	tuiles = [];
	voisins = [];
	N = 20;
	F = C*C-N;
 
	// placer les tuiles
	for (i=0;i<C*C;i++){
		var t = {};
		t.x = parseInt(i%C)*T;
		t.y = parseInt(i/C)*T;
		t.width = t.height = T;
		t.id = i;
		t.frame = 1;
		t.val = 0;
		tuiles.push(t);
		voisins.push([]);
	}
 
	// placer les bombes
	while(N) {
		var n = parseInt(Math.random()*tuiles.length);
		var p = tuiles[n];
		if(p.val!=9) {
			p.val=9; 
			N--;
			trouveValeurs(n,p.x/T,p.y/T,C-1);
		}
	}
 
	render();
	canvas.addEventListener("click", action, false);
}

L'initialisation du jeu, on commence par vider les tableaux.
“N” correspond au nombre de bombes à placer, et “F” au nombre de tuiles libres du jeu.
On place ensuite toutes les tuiles du jeu, si vous avez fait l'exercice “Cascade” c'est la même chose a ceci près qu'on stocke la valeur de la tuile en tant que paramètre de la tuile et non dans un tableau secondaire.

On place ensuite les bombes, là aussi c'est très simple, il suffit de tirer une case au hasard, de vérifier qu'elle est libre, et de modifier sa valeur pour en faire une bombe. Mais attention, a ce stade on va également déterminer les valeurs des cases voisines autour de la bombe, nous étudierons cette fonction un peu plus bas.

On affiche le rendu et on ajoute l'écouteur au clic de la souris, comme pour tous les jeux de ce type.

// cliquer sur une case
function action(e){
	i = parseInt((e.clientX-posX)/T)+parseInt((e.clientY-posY)/T)*C;
	if(tuiles[i].frame==1) tuiles[i].frame=2, F--;
	if(tuiles[i].val==9) {
		tuiles[i].frame=3;
		finPartie();
		return;
	}
	if(!tuiles[i].val) decouvre(i); 
	if(F==0) finPartie(3);
	render();
}

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 plsu bas).

Et enfin, si il ne reste plus de pièces à découvrir, le joueur gagne la partie.

Revenons sur la fonction qui permet de trouver les valeurs des cases situées autour des bombes.

// trouver les valeurs des cases
function trouveValeurs(i,X,Y,L){
	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.

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<C-1), attention C correspond au nombre de colonnes, pas à la position de la dernière colonne qui est C-1 et c'est la position que je cherche, je dois donc retirer une colonne puisque la position de ma première colonne commence à 0 ;-)

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.

// découvrir les cases vides
function decouvre(n){
	trouveVoisin(n,tuiles[n].x/T,tuiles[n].y/T,C-1);
	for (var h = 0; h<voisins[n].length; h++){
		if (voisins[n][h].frame==1) {
			if(!F--) finPartie();
			voisins[n][h].frame = 2;
			decouvre(voisins[n][h].id);
		}
	}
}

Cette fonction récursive 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,X,Y,L){
	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 (var h = 0; h<voisins[n].length; h++){
	if (voisins[n][h].frame==1) {
		if(!F--) finPartie();
		voisins[n][h].frame = 2;
		decouvre(voisins[n][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 a récursivité.

// fin de partie
function finPartie(){
	render();
	alert("Fin de partie, cliquez pour rejouer.");
	init();
}
 
// Dessine le jeu
function render() {	
	for(var i=0; i<tuiles.length; i++){
		ctx.drawImage(images[tuiles[i].frame-1], tuiles[i].x, tuiles[i].y);
		if(tuiles[i].val && tuiles[i].frame==2) afficheValeur(tuiles[i]);
	}	
}

On termine par les classiques fonctions de fin de partie et de rendu graphique, cette fois cependant nous allons utiliser une petite fonction séparée pour afficher les valeurs des cases.

// Affiche la valeur de la pièce
function afficheValeur(p) {		
	ctx.fillStyle = "white";
	ctx.font = "16px Arial";
	ctx.textAlign = "center";
	ctx.fillText(p.val, p.x+p.width/2, p.y+p.height/2+4);
}

Rien de bien compliqué, nous avons déjà vu l'affichage du texte dans le PENDU, c'est la même chose ici, on place juste le texte au centre de la case.

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.

Les sources

demineur.rar

Forums Développement Multimédia