Forums Développement Multimédia

Les formations Mediabox
Les formations Mediabox

Exercice 08 - CASCADE

Compatible JavaScript. Cliquer pour en savoir plus sur les compatibilités.Par Monsieur Spi, le 26 octobre 2015

Bonjour,

Et si on essayait de voir comment est fait le jeu “Cascade” ?

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 CASCADE c'est quoi ? (d'habitude je dis merci Wikipedia, mais là on va faire sans)

Cascade est un jeu de réflexion dont le but est de détruire des séries de blocs alignés de la même couleur. Lorsqu'un bloc est détruit l'ensemble des blocs situés au dessus descend pour combler le vide. Lorsqu'une colonne entière est détruite l'ensemble des colonnes suivantes se déplace pour combler le vide. La partie est terminée lorsqu'il ne reste plus de blocs à détruire ou si plus aucun bloc n'a de bloc voisin permettant de créer une série destructible.

C'est assez maigre comme définition mais cela suffit pour nous attaquer à l'exercice, ce type de jeu étant une variante récente du très célèbre Tetris, aucune définition n'existe sur Wikipedia, il est cependant intéressant à étudier car il pose des problèmes de récursivité et d'optimisation.

Les pré-requis

Pour ce programme vous devez connaître :

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>CASCADE</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, W, H, posX, posY, T, C, L, i, images, stock, voisins, valeurs, images;
 
// préparation du jeu
window.onload = function() {
    canvas = 		document.getElementById('canvas');
    ctx = 			canvas.getContext('2d');
	W = 			480;
	H = 			480;
	canvas.width = 	W;
	canvas.height = H;
	posX = 			canvas.offsetLeft;
	posY = 			canvas.offsetTop;
	T = 			32;
	C = 			W/T;
	loadImages(5);
}
 
// chargement des images
function loadImages(nbImg){	
	images = [];
	for(i=1; i<nbImg+1; i++){
		var b = new Image();
		b.src = "assets/tuile"+i+".png";
		b.onload = function() {
			images.push(this);
			if(--nbImg==0) init();
		};
	}
}
 
// initialisation du jeu
function init() {
	stock = 	[];
	voisins = 	[];
	valeurs = 	[];	
	for (i=0;i<C*C;i++){
		voisins.push([]);
		valeurs.push(parseInt(Math.random()*4+1));
		stock.push({x : parseInt(i%C)*T, y : parseInt(i/C)*T, id : i, width : T, height : T, frame : valeurs[i]});
	}
	render();
	canvas.addEventListener("mousedown", jouer, false);
	canvas.addEventListener("mouseup", checkTile, false);
}
 
// cliquer sur une case
function jouer(e){
	decouvre(parseInt((e.clientX-posX)/T)+parseInt((e.clientY-posY)/T)*C);
}
 
// découvrir les cases de même couleur
function decouvre(n){
	trouveVoisin(n,stock[n].x/T,stock[n].y/T,C-1,valeurs[n]);
	if(voisins[n].length){
		var v = voisins[n];
		for (var h=0; h<v.length; h++){
			if (v[h].frame!=5) {
				v[h].frame=5;
				decouvre(v[h].id);
				valeurs[v[h].id] = 5;
			}
		}
		voisins[n] = [];
		valeurs[n] = 5;
		stock[n].frame = 5;
		render();
	}
}
 
// trouver les cases vides voisines
function trouveVoisin(i,X,Y,L,F){
	if(X>0 && valeurs[i-1]==F) voisins[i].push(stock[i-1]);
	if(X<L && valeurs[i+1]==F) voisins[i].push(stock[i+1]);
	if(Y>0 && valeurs[i-C]==F) voisins[i].push(stock[i-C]);
	if(Y<L && valeurs[i+C]==F) voisins[i].push(stock[i+C]);
} 
 
// vérifier les tuiles
function checkTile(e) {
	var x = C; 
	while(x--) checkColonne(x);
	checkLigne();
	for (var j=0; j<stock.length;j++) stock[j].frame = valeurs[stock[j].id];
	render();
	verifieJeu();
} 
 
// vérifie une colonne
function checkColonne(c){
	var y = 0;
	while(y<C) {
		i = c+y*C;
		if (valeurs[i+C] && valeurs[i] != 5 && valeurs[i+C] == 5) {
			valeurs[i+C]= valeurs[i];
			valeurs[i] = 5;
			checkColonne(c);
		}
		y++;
	}
}
 
// vérifie une ligne
function checkLigne(){
	var x = C; 
	while(x--) checkDecalage(x);
}
 
function checkDecalage(c){
	var t = valeurs.length-C+c
	if(valeurs[t] !=5 && valeurs[t-1] == 5 && t-1>valeurs.length-C-1){
		var y = 0;
		while(y<C) {
			i = c+y*C;
			valeurs[i-1] = valeurs[i];
			valeurs[i] = 5;
			y++;
		}
		checkLigne()
	}
}
 
// vérifie si il reste des combinaisons jouables	
function verifieJeu(){
	var test = true;
	for (var n=0; n<stock.length; n++){
		if(valeurs[n]!=5){
			trouveVoisin(n,stock[n].x/T,stock[n].y/T,C-1,valeurs[n]);
			if(voisins[n].length) test=false;
			voisins[n] = [];
		}
	}
	if (test) finPartie();
}
 
// fin de partie
function finPartie(){
	alert("Fin de partie, cliquez pour rejouer.");
	init();
}
 
// Dessine le jeu
function render() {	
	for(var i=0; i<stock.length; i++){
		ctx.drawImage(images[stock[i].frame-1], stock[i].x, stock[i].y);
	}
}

Etude du programme

CASCADE est un très bon exercice pour introduire les notions de récursivité en programmation.

Une fonction récursive est une fonction qui s'appelle elle-même sous certaines conditions.
La récursivité a de nombreux avantages dans beaucoup de jeux, mais doit être utilisée avec précautions.
Pour sa plus grande partie, le programme est structuré de la même manière que les précédents exercices.
C'est pourquoi je vais aller très vite sur ces parties pour passer un peu plus de temps sur la récursivité.

// variables
var canvas, ctx, W, H, posX, posY, T, C, L, i, images, stock, voisins, valeurs, images;
 
// préparation du jeu
window.onload = function() {
	canvas = 		document.getElementById('canvas');
	ctx = 			canvas.getContext('2d');
	W = 			480;
	H = 			480;
	canvas.width = 	W;
	canvas.height = H;
	posX = 			canvas.offsetLeft;
	posY = 			canvas.offsetTop;
	T = 			32;
	C = 			W/T;
	loadImages(5);
}
 
// chargement des images
function loadImages(nbImg){	
	images = [];
	for(i=1; i<nbImg+1; i++){
		var b = new Image();
		b.src = "assets/tuile"+i+".png";
		b.onload = function() {
			images.push(this);
			if(--nbImg==0) init();
		};
	}
}

Les variables globales, la préparation du jeu, le chargement des images, c'est la même chose depuis le début des exercices pour ces trois blocs de code.

// initialisation du jeu
function init() {
	stock = 	[];
	voisins = 	[];
	valeurs = 	[];	
	for (i=0;i<C*C;i++){
		voisins.push([]);
		valeurs.push(parseInt(Math.random()*4+1));
		stock.push({x : parseInt(i%C)*T, y : parseInt(i/C)*T, id : i, width : T, height : T, frame : valeurs[i]});
	}
	render();
	canvas.addEventListener("mousedown", jouer, false);
	canvas.addEventListener("mouseup", checkTile, false);
}

L'initialisation du jeu, on commence par vider les tableaux.
On crée une boucle sur toutes les cases du jeu et on rempli les tableaux.

stock = stockage des pièces
voisins = stockage des pièces voisines
valeurs = stockage des couleurs

Pour chaque case on stocke un tableau vide dans le tableau des voisins, chaque case aura donc un certain nombre de voisines.
Pour chaque case on stocke une couleur aléatoire alant de 1 à 4 dans le tableau des valeurs.
Pour chaque case on stocke la tuile correspondante dans le stock.

On affiche le rendu et pour une fois on va utiliser deux écouteurs, l'un lorsque la souris est enfoncée et un quand la souris est relevée.

// cliquer sur une case
function jouer(e){
	decouvre(parseInt((e.clientX-posX)/T)+parseInt((e.clientY-posY)/T)*C);
}

Quand on clique sur une case on demande au programme de rechercher les cases de la même couleur qui sont contigües à la case choisie.

// découvrir les cases de même couleur
function decouvre(n){
	trouveVoisin(n,stock[n].x/T,stock[n].y/T,C-1,valeurs[n]);
	if(voisins[n].length){
		var v = voisins[n];
		for (var h=0; h<v.length; h++){
			if (v[h].frame!=5) {
				v[h].frame=5;
				decouvre(v[h].id);
				valeurs[v[h].id] = 5;
			}
		}
		voisins[n] = [];
		valeurs[n] = 5;
		stock[n].frame = 5;
		render();
	}
}
 
// trouver les cases vides voisines
function trouveVoisin(i,X,Y,L,F){
	if(X>0 && valeurs[i-1]==F) voisins[i].push(stock[i-1]);
	if(X<L && valeurs[i+1]==F) voisins[i].push(stock[i+1]);
	if(Y>0 && valeurs[i-C]==F) voisins[i].push(stock[i-C]);
	if(Y<L && valeurs[i+C]==F) voisins[i].push(stock[i+C]);
}

Vous avez étudié le TAQUIN, vous savez donc comment je procède pour trouver les pièces voisines à la pièce de référence, ayant la même couleur.

Une fois les voisines de la pièce trouvées je vérifie que le tableau des voisins n'est pas vide, sinon il ne se passe rien, le joueur ne peut pas supprimer un bloc isolé. Pour chaque pièce voisine ayant la même couleur, la pièce est supprimée (passe en frame 5) et on recherche à nouveau ses voisines. Attention, afin de ne pas perturber le test des couleurs pour la recherche des voisines je ne change la couleur de la pièce qu'après avoir trouvé les pièces voisines. C'est notre première boucle récursive.

Une fois toutes les voisines de toutes les pièces trouvées je nettoie le tableau des voisins de chaque pièce car je vais être amené à m'en servir de nouveau, je dois donc le vider, et je pense à détruire la pièce originale (la passer en frame 5 et changer sa valeur).

Jusque là rien de bien compliqué, c'est presque la même chose que le TAQUIN, le joueur viens de jouer, on a modifié toutes les tuiles qui le devaient, le joueur relâche le bouton de la souris et on va donc maintenant devoir nettoyer la grille, c'est à dire d'abord faire descendre toutes les tuiles pour boucher les trous, puis décaler toutes les colonnes pour combler les colonnes vides, cela se passe en deux temps.

// vérifier les tuiles
function checkTile(e) {
	var x = C; 
	while(x--) checkColonne(x);
	checkLigne();
	for (var j=0; j<stock.length;j++) stock[j].frame = valeurs[stock[j].id];
	render();
	verifieJeu();
}

Je connaît le nombre de colonnes de ma grille ( C ) , je vais donc vérifier chaque colonne en partant de la dernière, une fois que toutes les colonnes auront été vérifiées je m'attaquerai au décalage, puis une fois toutes les vérifications faites, le met à jour l'affichage en modifiant toutes les tuiles selon le nouvel ordre du tableau de valeurs et je vérifie si le joueur à terminé la partie. Notez que tous les calculs sont effectués sur le tableau de valeurs et non sur les tuiles qui ne servent qu'à l'affichage.

Voyons déjà la fonction “checkColonne”.

// vérifie une colonne
function checkColonne(c){
	var y = 0;
	while(y<C) {
		i = c+y*C;
		if (valeurs[i+C] && valeurs[i] != 5 && valeurs[i+C] == 5) {
			valeurs[i+C]= valeurs[i];
			valeurs[i] = 5;
			checkColonne(c);
		}
		y++;
	}
}

Pour chaque colonne je vais vérifier chaque ligne en partant de la première.

i = c+y*C;

Je cherche d'abord la case concernée.

if (valeurs[i+C] && valeurs[i] != 5 && valeurs[i+C] == 5) {
	valeurs[i+C]= valeurs[i];
	valeurs[i] = 5;
	checkColonne(c);
}

Si la case située en dessous de la case concernée n'est pas en dehors du tableau de valeurs, que la case concernée n'est pas vide, et que la case qui est dessous est vide, alors la tuile du dessous prend la valeur de la tuile concernée et cette dernière se vide. Puis je recommence immédiatement le test à partir de la tuile que je viens de modifier, c'est notre seconde boucle récursive.

A quoi ça sert de revérifier toute la colonne à partir de la tuile modifée à chaque tuile modifiée ?

Imaginez que la tuile que vous modifiez se trouve vers le bas de la colonne, si vous ne faites qu'inverser les deux tuiles (la concernée et celle du dessous) vous n'aurez qu'une tuile qui semble descendre et le test s'arrêtera là. Dès que vous modifiez une tuile vous devez donc revérifier toute la colonne à partir de la tuile modifiée afin de faire descendre toutes les pièces qui sont au dessus, la boucle s'arrête lorsqu'il n'y a plus de tuile à modifier dans la colonne.

Toutes les lignes de chaque colonne ont été vérifiées et toutes les tuiles modifiées en conséquence, nous allons maintenant devoir vérifier si il n'existe pas de colonne vide, auquel cas nous allons devoir décaler toutes les colonnes pour boucher les trous, exactement comme nous l'avons fait pour faire descendre les tuiles.

// vérifie une ligne
function checkLigne(){
	var x = C; 
	while(x--) checkDecalage(x);
}

La procédure est sensiblement la même que pour faire descendre les lignes, sauf que cette fois on doit bouger des colonnes entières et il se peut que nous ayons plusieurs colonnes vides successives, c'est pourquoi ce calcul est effectué dans une fonction à part que je peut rappeler quand je le souhaite. Je part de la colonne la plus à droite, la dernière de la grille et je vérifies toutes les colonnes jusqu'à la première.

// vérifie si on dois décaler une colonne
function checkDecalage(c){
	var t = valeurs.length-C+c
	if(valeurs[t] !=5 && valeurs[t-1] == 5 && t-1>valeurs.length-C-1){
		var y = 0;
		while(y<C) {
			i = c+y*C;
			valeurs[i-1] = valeurs[i];
			valeurs[i] = 5;
			y++;
		}
		checkLigne()
	}
}

Bien on attaque le plus difficile, pour chaque colonne je ne vais vérifier que la dernière tuile tout en bas de la colonne, puisque juste avant j'ai fait descendre toutes les tuiles dans les colonnes si la dernière est vide c'est qu'il n'y a plus de tuile dans la colonne, c'est donc celle là que je dois vérifier.

Si la tuile concernée n'est pas vide mais que la tuile précédente est vide et que la tuile précédente ne se trouve pas en dehors de la ligne que je suis en train de vérifier (la dernière tout en bas), alors je dois déplacer la colonne. Rappelez-vous que nous travaillons avec des listes, la grille ne sert qu'à l'affichage, j'ai donc des index qui se suivent dans un tableau sans distinction de lignes ou de colonnes, c'est pourquoi je suis obligé de vérifier que la tuile que je vais modifier ne se trouve pas dans la ligne précédente, sinon cela fausserai tout le calcul.

Pour faire court, c'est la même méthode que pour faire descendre les tuiles, chaque tuile de la colonne prend la valeur de la tuile de la colonne précédente sur la même ligne. Lorsque toutes les tuiles de la colonne ont été modifiées, je relance une vérification complète de la grille, c'est notre troisième boucle récursive. Elle existe pour les mêmes raisons que lorsque je fais descendre les tuiles, toutes les colonnes précédentes doivent être modifiées afin de conserver la cohérence et c'est pourquoi la boucle sur les colonnes à été isolée dans une fonction à part que je rappelle ici.

On a fait le plus dur, il reste à présent à vérifier que le joueur peut encore détruire des blocs ou si la partie est terminée.

// vérifie si il reste des combinaisons jouables	
function verifieJeu(){
	var test = true;
	for (var n=0; n<stock.length; n++){
		if(valeurs[n]!=5){
			trouveVoisin(n,stock[n].x/T,stock[n].y/T,C-1,valeurs[n]);
			if(voisins[n].length) test=false;
			voisins[n] = [];
		}
	}
	if (test) finPartie();
}

Cette partie est un peu lourde mais je n'ai pas encore trouvé plus simple, ça existe sûrement et je vous laisse le loisir de chercher. La fonction fait une boucle sur toutes les cases de la grille et vérifie pour chaque case non vide restante si elle a des voisines de même couleur, si c'est le cas la partie continue et on vide le tableau des voisins de la pièce testée (rappelez-vous qu'on en a besoin pour la destruction des pièces quand le joueur joue). Sinon la partie est terminée, logiquement on devrait compter les points et proposer au joueur d'améliorer son score, mais cela ne concerne pas vraiment le sujet de notre exercice.

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

On termine par les deux fonctions désormais classiques pour gérer la fin d'une partie et le rendu graphique du jeu, une fois de plus pas de changement dans ces deux blocs de code.

Conclusion

Ce jeu utilise a fond la récursivité, on la retrouve un peu partout y compris en dehors des jeux, par exemple elle est utilisée dans les algorithmes de “flood fill” ( https://fr.wikipedia.org/wiki/Algorithme_de_remplissage_par_diffusion ).

Les sources