Discussion :

[flateur18]

Bonjour chères amis,

Je me retourne vers ce forum en dernier recours, car après maintes recherches je n'ai pas trouvé de réponse adéquate.
Ma question : je suis entrain de réaliser un projet JAVA, c'est en gros un plateau qui contient des cases remplies aléatoirement, et ce que je veux faire c'est, à chaque fois que je selectionne une case, un arrayliste (tab) doit contenir les cordonnées de toutes les cases voisines et voisines des voisines sans doublons.
C'est ce que j'essaie de faire, mais ma méthode récursive engendre une erreur qui bloque l'execution de mon programme.

Je voudrais qu'on m'aide sur le raisonnement.

Voici les parties interessantes de mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
//////////////////* donne les coordonnées des voisins de la même couleur */////////////
    public void chercheVoisinsCouleur (Case C){
 
    	for(int i=C.getLigne()-1; i<=C.getLigne()+1; i++){
    		for(int j=C.getColonne()-1; j<=C.getColonne()+1; j++){
 
    			if (i<plateau.length && j<plateau.length){
    				if(i<0) i++;
					if(j<0) j++;
 
    				if((i+j) %2 == 1){     // test si impaire (pour ne pas inclure les diagonales)
    					if(tab.contains(plateau[i][j])==false){	// saute les cases qu'on a deja testé
    						if (plateau[i][j].equals(C)){		
    								tab.add(plateau[i][j]);
    								cmpt++;
    						}	
    					}	
    				}
    			}
 
 
 
    		}
 
    	 }
 
 
 
	}
 
 
    //////////////////////* Methode pour retirer les billes si >=3 */////////////////////
    public Case[][] retireBillesCouleur (Case C){
 
    	tab = new ArrayList <Case>();
    	tab.add(C); cmpt++;
 
    	chercheVoisinsCouleur(C);
 
 
    	if (cmpt>2){
    		for(int i=0; i<cmpt; i++){
    			plateau[tab.get(i).getLigne()][tab.get(i).getColonne()].setEtat(false);
    		}			
    	}
    	return plateau;
    }

ce code marche pour toute les voisines directes (sans compter les diagonales),
je sait que je dois utiliser une methode recursive (appeler chercheVoisinsCouleur dans chercheVoisinsCouleur) pour avoir les coordonnées des voisins des voisins mais je n'arrive pas à faire le bon raisonnement.

Merci d'avance pour votre aide!

[hwoarang]

Euh, tu pars d'un tableau représentant ton damier et tu cherches les 25 cases autour de l'une d'elles. Je ne vois vraiment pas ou est le probleme de recursivité...

[eatherquake]

Salut,

a mon avis, si c'est juste les voisins, et les voisins des voisins, pas besoin de faire du récursif. Quel est la définition d'un voisin? les cases en diagonales comptent également? le plateau est carré? (on peut représenter les cases avec une abscisse et une ordonnée?)

[eatherquake]

D'accord avec Hwoarang, sauf que moi je trouve 24 cases adjacentes, et ceci dans le meilleur des cas (il faut tenir compte je pense des cas limites genre la case sélectionné est sur un bord du plateau ou dans un coin...)

Suivant la représentation que tu fais de ton plateau, les calculs peuvent être très simples (cf la technique "mailbox" dans le cas ou on veut représenter un échiquier et faciliter la recherche des coups possibles dans le jeu d'échecs : http://chessprogramming.wikispaces.com/Mailbox mais tu n'as peut être pas besoin d'aller jusque là^^)

[flateur18]

Merci pour vos réponses,

mon constructeur Case a comme attributs : ligne, colonne et état.
c'est un jeu de boulles de couleurs, sur un plateau dont le joueur définit la taille.
quand j'appel la méthode retireBillesCouleurs (Case C) qui elle même appelle chercheVoisinsCouleur, je souhaiterai que les coordonnées de tous les voisins contiguës de cette case soit répértoriés dans mon arraylist tab, comme ca je les retire au prochain tour.

contiguës : pour ne pas inclure les diagonoles (c'est pour ca que j'utilise le %2)

[eatherquake]

A ce moment là, c'est au max 12 cases que tu dois remonter, si tu ne dois pas compter les diagonales. Et bien sur, pas de récursif, il faut accéder directement aux cases en question, en testant à chaque fois qu'elles sont bien dans le plateau. Par exemple, si ton plateau est de taille 5(largeur)*5(longueur) et est modéliser par un tableau de taille 25, avec la première case du tableau qui représente la case en bas à gauche du plateau, et après on se déplace de gauche à droite et de bas en haut, alors pour accéder au voisin du voisin dans la direction nord de la case 13, tu as juste à aller chercher dans ton tableau en ajoutant 2* la largeur de ton tableau (ici 5) ce qui donne 13+2*5 = 23. la case 23 est donc le voisin du voisin de la case sélectionné dans la direction nord. Après, tu fais pareil pour les 11 autres cases. (il faudra faire des calculs modulo 5 pour vérifier que les cases ne sortent pas du plateau)

C'est pas compliqué, il suffit de faire un dessin :

X X A X X
X A A A X
A A Z A A
X A A A X
X X A X X

case Z : la case sélectionné (indice 13, le X en bas à gauche représentant la première case du tableau soit indice 1)
case A : les cases voisines et voisines de voisines
case X : le reste du plateau

Je t'ai fait le boulot pour la case A (indice 23) de la première ligne
Bon courage

[flateur18]

Merci eatherquake, mais je ne crois pas que ce soit exactement ce que je veux faire, voici le resultat quand je lance le programme dont le code est cité ci haut (chaque entier représente une couleur ici 4 choix possibles)

Bonjour et bienvenue dans le jeu 'Bubbles' !!!
Veuillez rentrer la taille du plateau de jeu (entier) : 5

+-----+
|31321|
|30111|
|12300|
|23131|
|10200|
+-----+

Pour quelle case souhaitez vous connaitre le nombre de voisins de la même couleur ?
Entrez la ligne : 2
Entrez la colonne : 4

La case selectionee est de couleur 1 et ils sont 3 voisins de la même couleur.

deuxième tour :

+-----+
|31321|
|30 ... |
|12300|
|23131|
|10200|
+-----+

...

le problème que j'ai ici c'est que le programme doit aussi m'enlever le '1' de coordonnée 1,5. il devrai dans ce cas me trouver 4 et non 3 voisins.

Je stock les coordonnées de chaque case identique à celle de départ dans un arraylist, puis j'enlève au tour d'après ces cases là. je souhaite donc depuis ma méthode, pouvoir stocker dans ce meme arrayliste les cordonnées des voisins qui y sont déjà

ce que j'ai oublier aussi de dire c'est qu'il doit detecter toutes les cases même les plus lointaines à condition qu'elle soient liées avec la case de départ
je ne sait pas si je suis très claire, dsl c'est dur pour moi d'expliquer

[eatherquake]

c'est juste qu'on ne modélise pas de la même façon
Adopte une approche systématique (cf. mon schéma), tu as 12 cases à vérifier, donc vérifie les une par une, et vérifie également les couleurs et les bords du plateau pour savoir si tu dois garder cette case ou pas. Si la case est "éligible", tu l'ajoutes à ta liste et tu passes à l'étude de la case suivante.

ça sera beaucoup plus rapide qu'une approche récursive ou alors une approche ou tu dois t'occuper des doublons potentiels.

edit: euh, et au passage, ton 1 de coordonnée (1,5) est en diagonale par rapport à ton 1 de coordonnée (2,4), donc d'après ce que tu m'as dit, il ne faut pas le sélectionner... ou alors j'ai rien compris

[flateur18]

aiie c'est plus dure que ce que je croyais !!!

la méthode systématique et très compliquée et longue à mettre en place, vu l'infinité de ligne et de colonnes que je peux avoir, et vu que je dois aussi détecter les voisin des voisins des voisins ...

y'a-t-il une méthode plus simplifiée?

un bout de code serait le bienvenue

merci

[flateur18]

edit: euh, et au passage, ton 1 de coordonnée (1,5) est en diagonale par rapport à ton 1 de coordonnée (2,4), donc d'après ce que tu m'as dit, il ne faut pas le sélectionner... ou alors j'ai rien compris

il fau le selectionner car c'est le voisin du voisin !!!

c pour ca que c aussi compliqué

[eatherquake]

ok.
Sélectionner les voisins et les voisins des voisins, c'est pas compliqué, il n'y a que 12 cas. Si tu dois sélectionner à l'infini les voisins des voisins, dis le dés le départ... c'est le cas?

En utilisant ton modèle de donnée, si ta case sélectionné est de coordonnée (X,Y), alors les 12 cases que tu dois sélectionner sont
(X+1,Y)
(X+2,Y)
(X-1,Y)
(X-2,Y)
(X,Y+1)
(X,Y+2)
(X,Y-1)
(X,Y-2)
(X+1,Y+1)
(X+1,Y-1)
(X-1,Y+1)
(X-1,Y+1)

une fois que tu as ces cases, il n'y a plus qu'a regarder si la couleur est ok et si la case n'est pas en dehors de tableau (un test du genre x+1 < largeur ou x-1>0 etc...)

[flateur18]

aiie c'est plus dure que ce que je croyais !!!

la méthode systématique et très compliquée et longue à mettre en place, vu l'infinité de ligne et de colonnes que je peux avoir, et vu que je dois aussi détecter les voisin des voisins des voisins ...

C'est bien le voisins des voisins à l'infini
c'est pour cela que dès le départ j'ai choisi de mettre toutes les cordonnées dans un ArrayList

dsl si on c'est mal compris

[billynirvana]

Je ne comprends pas pourquoi tu stockes la ligne et la colonne dans la classe Case puisque c'est ton plateau contient cette information.

J'espère avoir compris ton problème. Et je confirme la solution récursive.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.ArrayList;
import java.util.List;
 
public class Test {
 
	public static void main(String[] args) {
		new Test();
	}
 
	/////////////////////////////////////////////////////////////////////////////////
 
	private Case[][] plateau = null;
 
	public Test() {
		plateau = new Case[5][5];
 
		plateau[0][0] = new Case(0, 0, 3);
		plateau[0][1] = new Case(0, 1, 1);
		plateau[0][2] = new Case(0, 2, 3);
		plateau[0][3] = new Case(0, 3, 2);
		plateau[0][4] = new Case(0, 4, 1);
 
		plateau[1][0] = new Case(1, 0, 3);
		plateau[1][1] = new Case(1, 1, 0);
		plateau[1][2] = new Case(1, 2, 1);
		plateau[1][3] = new Case(1, 3, 1);
		plateau[1][4] = new Case(1, 4, 1);
 
		plateau[2][0] = new Case(2, 0, 1);
		plateau[2][1] = new Case(2, 1, 2);
		plateau[2][2] = new Case(2, 2, 3);
		plateau[2][3] = new Case(2, 3, 0);
		plateau[2][4] = new Case(2, 4, 0);
 
		plateau[3][0] = new Case(3, 0, 2);
		plateau[3][1] = new Case(3, 1, 3);
		plateau[3][2] = new Case(3, 2, 1);
		plateau[3][3] = new Case(3, 3, 3);
		plateau[3][4] = new Case(3, 4, 1);
 
		plateau[4][0] = new Case(3, 0, 1);
		plateau[4][1] = new Case(3, 1, 0);
		plateau[4][2] = new Case(3, 2, 2);
		plateau[4][3] = new Case(3, 3, 0);
		plateau[4][4] = new Case(3, 4, 0);
 
		List<Case> billesRetirees = retireBilles(1, 3);
		System.out.println(billesRetirees);
	}
 
	public List<Case> retireBilles(int ligne, int colonne) {
		return retireBilles(ligne, colonne, plateau[ligne][colonne].couleur, 0, new ArrayList<Case>());
	}
 
	public List<Case> retireBilles(int ligne, int colonne, int couleur, int profondeur, List<Case> dejaVisites) {
		if (profondeur == 3) {
			return dejaVisites;
		}
 
		if (ligne < 0 || colonne < 0 || ligne >= plateau.length || colonne >= plateau[0].length) {
			return dejaVisites;
		}
 
		if (plateau[ligne][colonne].couleur == couleur && dejaVisites.contains(plateau[ligne][colonne]) == false) {
			dejaVisites.add(plateau[ligne][colonne]);
 
			dejaVisites = retireBilles(ligne - 1, colonne, couleur, profondeur + 1, dejaVisites);
			dejaVisites = retireBilles(ligne, colonne - 1, couleur, profondeur + 1, dejaVisites);
			dejaVisites = retireBilles(ligne + 1, colonne, couleur, profondeur + 1, dejaVisites);
			dejaVisites = retireBilles(ligne, colonne + 1, couleur, profondeur + 1, dejaVisites);
		}
 
		return dejaVisites;
	}
}
 
class Case {
	public int ligne = 0;
	public int colonne = 0;
	public int couleur = 0;
 
	public Case(int ligne, int colonne, int couleur) {
		this.ligne = ligne;
		this.colonne = colonne;
		this.couleur = couleur;
	}
 
	public String toString() {
		return "[" + ligne + "," + colonne + "," + couleur + "]";
	}
}

Edit: Le code est perfectible, je propose cela à toi d'améliorer et d'adapter à tes besoins!

[flateur18]

Merci billyNirvana,
effectivement, ca se raproche beaucoup plus de ce que je veut faire,
je vais tester de suite et vous tiens au courant

[flateur18]

Bonne nouvelle !!

j'ai enfin réussi à franchir cette étape !!! ouff...

je rappel que ça s'agissait de trouver les voisins des voisins des voisins ... égales dans un tableau à 2 dimensions.

voici l'idée pour ceux qui sont intéressés, elle se raproche beaucoup de celle de billyNirvana :

On déclare un tableau, un vecteur, une liste ou une ArrayList, peu importe, de type Case. On controle d'abord les cases directement liées à celle que l'on souhaite tester. Si elle sont égales on stock leurs attribues dans un ArrayList.
Puis, on fait une boucle qui fait cette même opération pour les objets stockés dans l'ArrayList, un par un sans inclure les doublons.
Comme ça, notre ArrayList contiendra toutes les coordonnées des cases identiques des voisines, voisines des voisines ... de ma case de départ.

Génial non

Merci encore