Le jeu « SameGame »
1 Description d'une version simple du jeu
Le tableau de jeu a la forme d'un rectangle de 10 lignes
et 15 colonnes où figurent des pièces variées (disques
de couleur ou bien comme dans cet énoncé pièces géométriques),
avec 3 types possibles. Ces pièces sont tirées au hasard
au début du jeu. Voici un exemple de tableau de jeu au début
d'une partie :
Il s'agit pour le joueur d'enlever le plus possible de pièces sur
le rectangle de jeu, sachant que pour retirer une pièce il faut
que cette pièce fasse partie d'une sélection. Une
sélection comprend nécessairement au minimum deux pièces
du même type disposées côte à côte verticalement
ou horizontalement. La sélection s'effectue en cliquant sur une
pièce et le programme détermine lui-même quel est l'ensemble
des pièces qui forment une chaîne ininterrompue de sélections
élémentaires à partir de la pièce désignée
par le joueur. Par exemple sur le jeu ci-dessus, si l'on clique sur la
pièce qui se trouve dans la huitième ligne à partir
du bas et la quatrième colonne à partir de la gauche, alors
la sélection effectuée correspond à la zone entourée
sur la vue suivante :
Cette sélection va disparaître selon la première règle
suivante : les pièces qui se trouvaient au dessus des pièces
de la sélection descendent pour prendre leur place. Pour la sélection
de notre exemple, cela donne :
Si la suppression de la sélection produit une colonne vide, comme
pour la sélection ci-dessous :
alors cette colonne vide disparaît et les colonnes suivantes sont
décalées d'un cran sur la gauche, comme le montre la figure
ci-dessous pour la deuxième sélection de notre exemple.
Le jeu est terminé quand il n'est plus possible de retirer aucune
pièce du tableau de jeu comme dans le cas ci-dessous.
2 Description de l'implantation
2.1 Représentation interne du jeu
Tableau débordant
On représente le tableau de jeu par un tableau débordant,
c'est-à-dire que si le jeu comprend L lignes et C
colonnes, on crée un tableau de taille (L+2)×(C+2),
dont les indices de lignes peuvent varier de 0 à L+1 et les
indices de colonnes de 0 à
C+1.
Ceci a pour effet que, lors de la détection de la zone sélectionnée,
pour tout indice de ligne l (resp. de colonne c) compris
entre 1 et L (resp. C), les lignes l-1 et l+1
(resp. les colonnes
c-1 et c+1) du tableau existent.
On ne représente graphiquement que les lignes (resp. colonnes)
d'indice compris entre 1 et L (resp. C).
Pièces
Chaque case du tableau a un type qui est celui de la pièce
s'il y en a une ou bien celui du fond s'il n'y en a pas. Par exemple, les
bords du tableau (ces lignes et colonnes d'indice 0, L+1 et C+1)
sont du type du fond. Ceci nous sert lors de la détection de la
zone sélectionnée.
Par ailleurs, lors de cette détection, on a besoin de pouvoir
marquer les cases selon que l'on sait déjà que la pièce
appartient ou n'appartient pas à la zone déjà sélectionnée.
2.2 L'algorithme central : la détection de la zone sélectionnée
et sa suppression
La sélection
n'est valide que si la zone comporte au moins deux pièces
Le marquage
Dans un premier temps, pour détecter la zone sélectionnée
dans le tableau t à la ligne l et la colonne c,
on va passer d'une situation initiale où aucune case n'est marquée
à une situation finale où toutes les cases de la sélection
sont marquées. Pour cela on procède récursivement
dans les quatre directions à partir de la case de départ
en s'arrêtant aux bords et en ne marquant que les cases qui
ne le sont pas déjà.
La suppression
Lorsque le tableau est entièrement marqué
de cette façon , on va tout d'abord supprimer dans chaque colonne
les pièces marquées, puis supprimer les colonnes vides et
enfin mettre à jour la représentation graphique du tableau
de jeu.
2.3 Le hasard
Le hasard dans le choix de la couleur des pièces
lorsque l'on produit le tableau de jeu sera obtenu en utilisant la fonction
Random.int.