Jeu morpion / algo recherche du gagnant
Bonjour,
Je travaille sur un TD morpion pour ma formation et je bloque un peu sur la méthode qui permet de trouver un gagnant.
La version du morpion sur laquelle on travaille est évolutive avec une grille n*n et il faut aligner 5 pions pour gagner.
Pour le moment, j’ai une première méthode rechercherAlignement() qui recherche un alignement de pions du joueur courant.
La méthode rechercherAlignement() est appelée par une méthode coupGagnant() qui recherche après chaque coup, un alignement de pions du joueur courant dans toutes les directions (8 directions) à partir de la position du dernier pion joué.
Cet algo ne me détecte pas toutes les combinaisons gagnantes*:
exemple 1*: dernier position jouée (3,3) → gagnant non détecté
[ X ] [ O ] [ X ] [ O ] [ O ] [ O ]
[ O ] [ X ] [ X ] [ O ] [ X ] [ O ]
[ O ] [ O ] [ X ] [ X ] [ O ] [ O ]
[ O ] [ O ] [ O ] [ X ] [ X ] [ O ]
[ O ] [ O ] [ X ] [ O ] [ X ] [ X ]
[ O ] [ O ] [ O ] [ O ] [ O ] [ O ]
exemple 2*: dernier position jouée (4,4) → gagnant détecté
[ X ] [ O ] [ X ] [ O ] [ O ] [ O ]
[ O ] [ X ] [ X ] [ O ] [ X ] [ O ]
[ O ] [ O ] [ X ] [ X ] [ O ] [ O ]
[ O ] [ O ] [ O ] [ X ] [ X ] [ O ]
[ O ] [ O ] [ X ] [ O ] [ X ] [ X ]
[ O ] [ O ] [ O ] [ O ] [ O ] [ O ]
Je ne vois pas trop comment faire sans multiplier les tests tout autours de la dernière position jouée.
d’avance merci de votre aide.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
boolean coupGagnant(int x, int y) {
//case courante = dernier pion joué
int ligne = x;
int colonne = y;
//boucle sur les tableaux de déplacements pour faire une recherche
//dans toutes les directions de la dernière case jouée
for (int i=0; i<8; i++) {
//case de départ --> dernier coup joué
//on stocke le nombre de pions alignés dans chaque direction
alignement[i] = rechercherAlignement(ligne, colonne, DEP_COL[i], DEP_LIG[i]);
//println("Nombre de pions alignés direction "+i+": "+alignement[i]);
//Vérification des conditions pour gagner
if (alignement[i]>=5) {
println("Joueur "+joueurCourant+" gagnant");
//textSize(24);
//textAlign(CENTER, CENTER);
//text("Joueur "+joueurCourant+" gagnant", 400, 50);
return true;
}
}
return false;
}
int rechercherAlignement(int x, int y, int depX, int depY) {
int ligne = x;
int colonne = y;
int nombreAlignes = 0;
//On récupère la liste des cases composant l'alignement pour
//éventuellement le ré-afficher
//ArrayList<Integer> listeCases = new ArrayList<>();
//5 == au nombre de pion qui doivent être alignés pour gagner
for (int i=0; i<5; i++) {
//si la case correspond à un pion du joueur courant
//on incrémente le compteur
//on teste que l'on est dans la grille
if (ligne>=0 && ligne<nbCases && colonne>=0 && colonne<nbCases) {
if (tableau[ligne][colonne]==joueurCourant) {
nombreAlignes++;
//sinon, on réinitialise le compteur
} else {
nombreAlignes=0;
}
//deplacement depuis la position du dernier pion joué
//utiliser le tableau des déplacements en X et Y
colonne+=depX;
ligne+=depY;
}
}
ligne = 0;
colonne = 0;
return nombreAlignes;
} |
Procède brique par brique
Je te donne une réponse d'un dimanche soir à minuit mais je pense que cela devrait t'aider à résoudre ton problème.
Partons du postulat suivant:
_ La grille est évolutive mais pas restrictive, c'est à dire que si elle contient 30 colonnes avec des cases vides, on toujours les remplir --> on est donc obligé de tout parcourir pour vérifier un gagnant (quoi que en se creusant un peu la soupière...)
_ On à simplement 2 axes, ce qui nous donne un nombre de suites à vérifier égale à "nbAxe X (( (nbCol + nbLi ) / nbAxe ) + nbAxe)" soit par exemple dans une grille 5x10 donne 17 vérifications.
Champs des recherches(colonnes/lignes)
DiagoA = 0/0 à colMax/liMax
DiagoB = colMax/0 à 0/liMax
uColonne = colOffset/0 à colOffset/liMax
uLigne = 0/liOffset à colMax/liOffset
Donc en code, on aurait quelque chose comme ça:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
String symbolePlayer = "x"; (setter à chaque tour de jeu...)
// -- Exemple pour la première diago
public final int CONS_UNDEFINED = 0;
public final int CONS_WINNER= 1;
public final int CONS_LOOSER = 2;
public int STATE_ACTUAL = CONS_UNDEFINED;
int incrConsecutif= 0;
int offset = 0;
int maxOffset = Math.min(colMax, liMax);
public void workDiagonalA(){
while(offset <= maxOffset && STATE_ACTUAL == CONS_UNDEFINED){
verifyConsecutifEquals(monTableau[offset,offset]);
}
}
public void verifyConsecutifEqual(String symbol){
if(symbol).equals(symbolePlayer){
increConsecutif++;
offset++;
if(increConsecutif == 5){
STATE_ACTUAL== CONS_WINNER;
}else if(offset-maxOffset <5){
STATE_ACTUAL== CONS_LOOSER;
}else{
verifyConsecutifEqual(String symbol); // Récursif
}
}else{
offset++;
increConsecutif =0; // RESET
if(offset-maxOffset <5){
STATE_ACTUAL == CONS_LOOSER; // Plus assez de possibilité pour gagner
}
} |
Voilà pour la diagonale, même principe pour les colonnes et lignes mise à part qu'il faut itérer sur leur nombres dans une boucle et bouger l'offset que sur colonne ou ligne. (A contrario de la diagonale).
De plus, si ton tableau commence à avoir énormément de ligne et colonne (qui à dit SGBD ?), tu peux itérer plus rapidement en utilisant tes processeurs avec des recursiveAction dans un forkJoinPool(Runtime.availableProcessor()).
Ceci dit, il faut au moins dépasser les 100 000 voir plus pour avoir une différence qui vaut le coup, en dessous tu va gagner des millisecondes donc aucun intérêt. :P
En esperant t'avoir aider, même si le code parait brouillon l'idée générale devrait être assez obvious.
