Colas Sébastien
Le but de ce projet est réaliser :
Le jeu de l'âne rouge est une sorte de jeu de taquin. Sur
un damier de 5 x 4 cases carrées sont placés 10 pièces
de tailles différentes. Le jeu consiste à utiliser les cases
vides pour déplacer les pièces et passer d'une configuration
à une autre.
Dans ce chapitre nous ne nous intéresserons pas à la recherche automatique de solutions. Nous nous próccuperons seulement de créer une interface permettant de jouer à ce jeu. Nous devrons donc pouvoir mémoriser et visualiser des configurations et aussi réaliser les mouvements souhaités par l'utilisateur. Pour cela nous devrons permettre à l'utilisateur de désigner une pièce puis de spécifier un mouvement. Lorsqu'une pièce aura été sélectionnéss, elle sera mise en évidence graphiquement par un changement de couleur. Enfin, nous fournirons plusieurs moyens à l'utilisateur pour indiquer le mouvement qu'il souhaite voir effectuer à une pièce sélectionnée. Le premier se fera en sélectionnant la pièce à déplacer par un premier clique puis à la déplacer à un nouvel endroit indiqué par un second clique. Enfin une autre méthode consistant à faire glisser la pièce vers sa nouvelle position par un mouvement de la souris. Nous nous sommes efforcés de rendre le fonctionnement du jeu sur écran aussi proche que possible du jeu matériel. En particulier, dans le jeu matériel, une pièce peut en pousser une autre et on peut donc bouger plusieurs pièces d'un seul mouvement.
Cette classe sert aussi à capturer les évènements liés aux boutons et d'effectuer le code correspondant. Les évènements sur les objets de type GameBoard sont gérés par eux-même.
Cette classe va en fait assurer une interface avec sa sous-classe CheckBoardControler. Cette classe contient deux constructeurs chacun instanciant la sous-classe CheckBoardControler à la différence que le constructeur ne prenant pas d'arguments gère les évènement dûs à la souris. L'autre constructeur quant à lui ne gère pas les évènemments liés à la souris, l'objet reste passif. La méthode la plus importante est la méthode processEvent. C'est elle qui va en fonction de l'action reçue executer des méthodes sur la sous-classe. c'est aussi elle qui récupère les coordonnées ou c'est déroulé l'évènement.
C'est cette classe qui va permettre de dplacer réellement les pièces. Voici un rapide descriptif de son fonctionnement.
Tout d'abord on attent qu'une pièce soit sélectionnée par un clique la méthode mouseClicked est alors exécutée. Une fois que l'on a cliqué sur une pièce on garde en mémoire la pièce ainsi sélectionnée et on la fait changer de couleur, c'est ce que fait la méthode setCurrentPiece().
Ensuite on attend le deuxième clique qui va appeler de nouveau la méthode mouseClicked. Tout d'abord on fait des tests pour savoir le résultat du déplacement est valide. On teste par exemple si un déplacement se fait en diagonale, si c'est le cas alors on ignore la commande. On teste aussi si on a cliqué sur la pièce déjà sélectionnée, dans ce cas on déselectionne la piece (unsetCurrentPiece). Si tous ces tests on réussi alors on effectue le déplacement (goNorth, goSouth, goWest, goEst). Il faut noter ici que le test sur le déplacement de la pièce ou sur un groupe de pièces a été effectué lorsque l'on a cliqué.
La méthode mousePressed s'occupe de sélectionner une pièce si celle-ci est valide. Ensuite on regarde les déplacements possibles: canGoNorth, canGoSouth, canGoWest, canGoEst. Ces fonctions seront décrites plus loin, mais il faut savoir que ces méthodes disent si on peut déplacer une pièce et si oui elles remplissent un structure contenant les pièces à déplacer.
La méthode mouseDragged s'occupe d'effectuer le déplacement du groupe de pièces à déplacer. Il faut noter que l'on autorise seulement les mouvements que l'on peut effecuer. De plus lorsque l'on arrive dans une position stable on effectue le déplacement (goNorth, goSouth, goWest, goEst) et on recalcule les possibilités de déplacement de la pièce à sa nouvelle position.
La méthode mouseReleased est chargée de déselectionner la pièce sélectionnée ainsi que de repositionner les pièces à des positions stables.
public boolean canGoWest(int piece)
{
int y,west;
boolean tmp=true; // 0
if (pieces[piece].getX()==0) return(false); // 1
for (y=pieces[piece].getY(); // 2
y<pieces[piece].getY()+pieces[piece].getHeight();
y++)
{
west=checkboard[pieces[piece].getX()-1][y]; // 3
if (west!=-1) // 4
{
tmp=tmp&&canGoWest(west); // 5
if (!tmp) break; // 6
}
}
addGroup(groupWest,piece); // 7
return(tmp); // 8
}
Voilà un exemple d'une méthode testant le déplacement. Regardons le plus précisément:
Le jeu de l'Ane Rouge est suffisament simple pour qu'il soit possible d'explorer totalement son graphe. Partant d'un configuration initiale, on calculera, toute les configurations qu'on peut atteindre en un coup, puis toutes le configurations qu'on peut atteindre en deux coups etc. Il faut bien entendu mémoriser l'ensemblre des configurations déjà rencontrées pour éviter les boucles. En théorie des graphes, ce type de parcours s'appelle un parcours de largeur.
Etant données un configuration initiale et une configuration finale, deux situations différentes peuvent se produire. Si les deux configurations appartiennent à une même composante connexedu jeu, alors on finit par atteindre la configuration finale en partant de la configuration initiale et on connaît le nombre minimal de mouvements pour passer de l'une à l'autre. Si les deux configurations appartiennent à des composantes connexes différentes, alors on explore toute la composante connexe de la configuration initiale sans rencontrer la configuration finale. On sait alors que cette variante n'a pas de solution.
L'assistance à l'utilisateur peut donc intervenir à deux niveaux. Lors d'une nouvelle variante, on pourra indiquer à l'utilisateur si cette variante a une solution ou non et quelle est la longueur de la solution la plus courte. Au cours du jeu, on pourra indiquer au joueur à quelle distance il se trouve de la solution la plus proche.
Tout d'abord regardons la classe Resolve cette classe dérive de la classe Runnable ce qui lui permet de s'exécuté en tant qu'activité (thread). Cette classe doit donc implémenter les méthodes suivantes:
Regardons maintenant Les fonctions d'initialisation ainsi que les types de données.
Tout d'abord le constructeur: Resolve(Button res,Button stp). Cette méthode prend en arguments deux boutons se seront les boutons de démmarage et d'arret de l'activité. Ils servent à interdire de lancer une activité si une activité est déjà demmarée en désactivant ou activant ces boutons. Cette méthode initialise toutes les variables dont nous allons nous servir plus tard.
Ensuite viennent deux méthodes d'initialisations: setCurrentConfig(byte [ ][ ])
setCurrentGoal(byte [ ][ ]), ainsi qu'une méthode de copie de configurqtion:
byte [ ][ ]copyConfig(byte [ ][ ].
Pour mieux comprendre ces fonctions voici la structure sur laquelle ces
fonctions travaillent:
| x y | 0 | 1 | 2 | 3 |
| 0 | 0 | 4 | 4 | 1 |
| 1 | 2 | 4 | 4 | 3 |
| 2 | -1 | 5 | 5 | -1 |
| 3 | 6 | 7 | 8 | 9 |
| 3 | 6 | 7 | 8 | 9 |
Les deux premmières fonction set initialise les variables d'objet aux
configurations initiales et finales. La méthode copy réalise une
copie de la configuration passée en paramètre.
Ensuite comme nous l'avons vu précédemment les pièces sont classées sauf
les barres horizontales et verticale il nous faut donc une méthode permettant
de dire si une barre est horizontale ou verticale. C'est ce que fait la méthode
boolean isHor(byte [ ][ ]tab,char x,cahr y). On lui passe en arguments
la configuration ainsi que la position de la piece (x,y).
Un autre méthode essentielle à notre algorithme est la méthode
boolean [ ][ ]canMove(char x,char y). Cette méthode prend comme
arguments une configuration ainsi que la position d'une pièce (x,y), on suppose
que les coordoonées (x,y) sont situées sur le coin en haut à gauche de la
pièce dont on veux savoir dans quelle direction on peut la déplacer. Cette
méthode fait de simples tests sur le tableau pour savoir dans quelles directions
on peut déplacer la pièce. Cette méthode retourne un tableau de booléens.
Le premier élément du tableau dit si on peut déplacer la pièce en haut (north),
le second en bas (south), le troisième à gauche (west), le quatrième à
droite (est).
Une fois ces tests effectués il faut pouvoir effectuer le déplacement, c'est ce que font les méthodes goNorth(char x,char y), goSouth(char x,char y), goWest(char x,char y), goEst(char x,char y). Nous ne décrivons pas ici ces fonctions mais il faut tout de même savoir que l'on commence par faire une copie de la configuration passée en paramètre, ensuite on regarde le type de pièce pour effectué son dplacement. Finalement les fonctions retourne une nouvelle configuration où le déplacement a été effectué. Pour simplifier le code qui va suivre il faut noter que la fonction byte [ ][ ]goDir(byte dir,char x,char y) prenant en paramètres la position d'une pièce ainsi qu'un indicateur de direction, assure la liaison avec les méthodes prcédentes.
Nous voici maintenant dans une partie de l'algorithme avec la fonction ci-dessous. Cette fonction calcul toutes les configurations:
private boolean calculNewConfig(int depth, int parent)
{ boolean []go;
boolean check[]=new boolean[10];
byte tmp[][];
for (char cmpt=0;cmpt<10;cmpt++) check[cmpt]=false; // 1
for (char y=0;y<5;y++) // 2
for (char x=0;x<4;x++) // 2
{
if (currentConfig[x][y]!=-1) // 3
{
if (!check[currentConfig[x][y]]) // 4
{
check[currentConfig[x][y]]=true; // 5
go=canMove(x,y); // 6
for (byte i=0;i<4;i++) // 7
{
if (go[i]) // 8
{
tmp=goDir(i,x,y); // 9
if (!listExplore.alreadyExplored(tmp)) // 10
{
moveTree.add(tmp,depth+1,i,parent); // 11
if (listExplore.add(tmp)) return(true); // 12
}
}
}
}
}
}
return(false);
}
Voici la méthode qui va ráliser le calcul complet:
public void go()
{ int next=0; // 1
boolean goalReach=false; // 2
listExplore.setGoal(currentGoal); // 3
listExplore.add(currentConfig); // 4
moveTree.add(currentConfig,0,(byte)-1,-1); // 5
while ((next=moveTree.nextUnexplored(next))!=-1) // 6
{
currentConfig=moveTree.getConfig(next); // 7
if (goalReach=calculNewConfig(moveTree.getDepth(next)
,moveTree.getNumber(next))) break; // 8
moveTree.setExplored(next); // 9
}
}
Nous avons volontairement allégé le code pour une meilleur compréhension.
On peut ajouter que c'est cette fonction qui réalise le parcours de l'arbre en largeur en appelant les fonctions décrites précédemment. C'est elle qui sera appelée par la fonction run, c'est donc elle qui sera exécuté en tant qu'activité.
Cette classe ne contient que 2 méthodes:
Le constructeur se contente d'initialiser les variables de l'objet nouvellement
créé. Pour initialiser la configuation finale nous avons une fonction
setGoal(byte [ ][ ]conf). Nous avons aussi une fonction de hâchage
private int hashCode(byte [ ][ ]config) qui nous permet de hâcher la
liste des configurations déjà explorées et donc de dire plus vite si un
élément appartient à notre liste ou pas.
La strucuture gardée par la liste d'element n'est pas la même que précédemment en effet précédemment nous faisions la distinction entre les pièces alors que maintenant la seule chose qui distingue 2 pièces c'est leur forme. Voilà un exemple de conversion (c'est ce qu'effectue la fonction byte [ ][ ]convertConfig (byte [ ][ ]config)):
|
Les méthodes suivantes add et alreadyExplored servent quant à elles à ajouter une nouvelle configuration dans la liste des configurations (en se servant de la table de hâchage) et a dire si oui ou on une configuration a déjà été explorée toujours en se servant de la table de hâchage.
La classe MoveTree sert principalement à garder une trace du parcours de l'arbre des déplacements. C'est grâce à lui que l'on peut calculer le nombre de déplacements séparant deux configurations. On pourrait aussi s'en servir pour suggerer un déplacement ou encore donner une solution complète.
Le constructeur se contente d'initialiser la liste à vide. Laméthode add ajoute une nouvelle configuration dans la liste des éléments. La fonction int nextUnexplored(int num) retourne l'indice de la première configuration inexplorée, elle commence sa recherche à partir de l'indice passé en paramètre.Nous avons une fonction permettant de connaître la taille de la liste des configurations. Une méthode permet de dire que l'on a déjà étudier une configuration, c'est la méthode setExplored(int num) qui prend comme argument l'indice de laconfiguration à marquer comme explorée. Le reste de méthodes servent quant à elles a récupérer des information sur une configuration dont on connaît l'indice.
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.