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
Je vous recommande fortement d’avoir au moins lu les exercices suivants : DEMINEUR, 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.
var T:int = 32;
var C:int = stage.stageWidth/T;
var i:int;
var stock:Array = [];
var voisins:Array = [];
var valeurs:Array = [];
// interface
var panneaux:Panneaux = new Panneaux();
panneaux.addEventListener(MouseEvent.CLICK, init);
panneaux.buttonMode = true;
addChild(panneaux);
function init(e:MouseEvent):void{
stock = [];
voisins = [];
valeurs = [];
while(numChildren>0) removeChildAt(0);
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.id = i;
t.width = t.height = T;
addChild(t);
t.mouseEnabled = false;
stock.push(t);
voisins.push([]);
valeurs.push(int(Math.random()*4+1));
t.gotoAndStop(valeurs[i]);
}
stage.addEventListener(MouseEvent.MOUSE_DOWN, jouer);
stage.addEventListener(MouseEvent.MOUSE_UP, checkTile);
}
function jouer(e:MouseEvent):void{
decouvre(int(mouseX/T)+int(mouseY/T)*C);
}
// découvrir les cases de même couleur
function decouvre(n:int):void{
trouveVoisin(n,stock[n].x/T,stock[n].y/T,C-1,valeurs[n]);
if(voisins[n].length){
for each(var h in voisins[n]){
if (h.currentFrame!=5) {
h.gotoAndStop(5);
decouvre(h.id);
valeurs[h.id] = 5;
}
}
voisins[n] = [];
valeurs[n] = 5;
stock[n].gotoAndStop(5);
}
}
// trouver les cases vides voisines
function trouveVoisin(i:int,X:int,Y:int,L:int,F:int):void{
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:MouseEvent) {
var x:int = C;
while(x--) checkColonne(x);
checkLigne();
for each(var j in stock) j.gotoAndStop(valeurs[j.id]);
verifieJeu();
}
function checkColonne(c:int):void{
var y:int = 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++;
}
}
function checkLigne():void{
var x:int = C;
while(x--) checkDecalage(x);
}
function checkDecalage(c:int):void{
var t:int = valeurs.length-C+c
if(valeurs[t] !=5 && valeurs[t-1] == 5 && t-1>valeurs.length-C-1){
var y:int = 0;
while(y<C) {
i = c+y*C;
valeurs[i-1] = valeurs[i];
valeurs[i] = 5;
y++;
}
checkLigne()
}
}
function verifieJeu():void{
var test:Boolean = true;
for (var n in stock){
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(2);
}
// fin de partie
function finPartie(G:int):void{
addChild(panneaux);
panneaux.gotoAndStop(G);
stage.removeEventListener(MouseEvent.CLICK, jouer);
stage.removeEventListener(MouseEvent.MOUSE_UP, checkTile);
}
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
chaque frame représente une couleur
la dernière frame est vide
Avant de nous jeter sur le code je dois préciser qu’il existe des méthodes pour accélérer les calculs, notamment avec l’utilisation du binaire et de ses opérateurs, cependant je pense qu’il est encore un peu tôt pour vous en parler et orienter l’exercice dans cette voie rendrait le code assez indigeste. Si vous souhaitez aller plus loin essayez de faire la même chose avec des performances accrues, stockez vos infos dans des entier non signés de 32 bits par exemple, gérez les couleurs avec une séquence de bits simples et usez des opérateurs binaires, ce sera une très bonne base si vous voulez aller plus loin. Sachez enfin que ce genre d’optimisations intervient généralement à la fin du développement car elles rendent le code moins malléable, plus rigide et surtout beaucoup plus indigeste, avant d’en arriver là assurez-vous que votre raisonnement tient la route et que votre programme fonctionne, puis essayez de l’optimiser au maximum.
Allez c’est parti pour l’étude pas à pas :
var T:int = 32;
var C:int = stage.stageWidth/T;
var i:int;
var stock:Array = [];
var voisins:Array = [];
var valeurs:Array = [];
// interface
var panneaux:Panneaux = new Panneaux();
panneaux.addEventListener(MouseEvent.CLICK, init);
panneaux.buttonMode = true;
addChild(panneaux);
Du gros classique si vous avez fait les exercices précédents, je commence par déclarer toutes mes variables globales et tableaux, puis je pose l’interface, notons simplement :
T = largeur des tuiles
C = nombre de colonnes
i = pointeur qui sert dans diverses boucles
stock = stockage des pièces
voisins = stockage des pièces voisines
valeurs = stockage des couleurs
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.
function init(e:MouseEvent):void{
stock = [];
voisins = [];
valeurs = [];
while(numChildren>0) removeChildAt(0);
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.id = i;
t.width = t.height = T;
addChild(t);
t.mouseEnabled = false;
stock.push(t);
voisins.push([]);
valeurs.push(int(Math.random()*4+1));
t.gotoAndStop(valeurs[i]);
}
stage.addEventListener(MouseEvent.MOUSE_DOWN, jouer);
stage.addEventListener(MouseEvent.MOUSE_UP, checkTile);
}
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), et supprimer tout ce qui se trouve sur la scène.
Ensuite je crée les tuiles, sur le même principe qu’on l’a fait avec le Démineur, vous allez voir que beaucoup de choses se ressemblent entre les deux jeux c’est pourquoi je vous demande de l’avoir lu dans les pré-resquis. La différence ici est que je tire une valeur aléatoire de 1 à 4 ce qui me permet d’afficher la bonne couleur pour chaque tuile.
Notez la particularité des écouteurs, j’en ai un qui écoute la pression du bouton de la souris et qui indique ce que le joueur joue, et un qui écoute le relâchement du bouton de la souris pour vérifier les tuiles et tout mettre en ordre dans la grille.
function jouer(e:MouseEvent):void{
decouvre(int(mouseX/T)+int(mouseY/T)*C);
}
Lorsque le joueur cliques sur une tuile on va lancer une fonction qui vérifie le résultat par rapport à la tuile sur laquelle il a cliqué, pour cela je me sert simplement de la position de la souris dans la grille.
// découvrir les cases de même couleur
function decouvre(n:int):void{
trouveVoisin(n,stock[n].x/T,stock[n].y/T,C-1,valeurs[n]);
if(voisins[n].length){
for each(var h in voisins[n]){
if (h.currentFrame!=5) {
h.gotoAndStop(5);
decouvre(h.id);
valeurs[h.id] = 5;
}
}
voisins[n] = [];
valeurs[n] = 5;
stock[n].gotoAndStop(5);
}
}
// trouver les cases voisines
function trouveVoisin(i:int,X:int,Y:int,L:int,F:int):void{
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 Démineur, 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 Démineur, 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:MouseEvent) {
var x:int = C;
while(x--) checkColonne(x);
checkLigne();
for each(var j in stock) j.gotoAndStop(valeurs[j.id]);
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, je 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.
function checkColonne(c:int):void{
var y:int = 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 cherches 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.
function checkLigne():void{
var x:int = 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.
function checkDecalage(c:int):void{
var t:int = valeurs.length-C+c
if(valeurs[t] !=5 && valeurs[t-1] == 5 && t-1>valeurs.length-C-1){
var y:int = 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.
function verifieJeu():void{
var test:Boolean = true;
for (var n in stock){
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(2);
}
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(G:int):void{
addChild(panneaux);
panneaux.gotoAndStop(G);
stage.removeEventListener(MouseEvent.CLICK, jouer);
stage.removeEventListener(MouseEvent.MOUSE_UP, checkTile);
}
Classique, on affiche le panneau de fin de partie et on retire les écouteurs.
Conclusion
Dans le Démineur nous avons commencé à aborder la récursivité, ici on l’emploie énormément, faites attention car la plupart des langages de programmation préfèrent l’incrémentiel à la récursivité, question d’optimisation, cependant cela nous permet de gérer la répétition des mêmes actions très souvent sans avoir à se soucier d’incrémenter des pointeurs dans tous les sens. La récursivité est à utiliser avec parcimonie, et uniquement si vous êtes sûr que cela n’impactera pas sur les performances de votre programme, ce qui vous impose de mettre des brides, la récursivité ce n’est pas magique et il faut faire très attention lorsqu’on l’utilise, mais si vous arrivez à maîtriser le processus cela peut vous épargner de longues séances de prise de tête ;-)
