Encerclement dans hexagone

Version imprimable

13/12/2006, 08h37
chris28200

Encerclement dans hexagone

Bonjour,

Je travaille sur un clone Open Source de 7colors. Le principe est identique sauf qu'il se jouerai sur un hexagone jusqu'à 6 joueurs et par Internet (mais je ne suis pas encore là).

Pour mon hexagone j'utilise le principe donné par Nemerle sur le forum (merci Nemerle !)

Lorsqu'un joueur choisi une couleur toutes les cellules de cette couleur adjacentes à son territoire sont annexées (là pas de problème) mais aussi toutes les cellules encerclèes dans le nouveau territoire et là je ne vois pas comment faire.

http://www.jalmus.net/Capture.png

Pas de problème pour les cases toutes seules (comme les roses) mais pour les groupes (comme celui en haut entouré par le territoire vert) je ne vois pas. Si quelqu'un a une idée, merci.
13/12/2006, 10h41
Fabllot

Je pense qu'il faut que tu appliques un algorithme de détection de contours...
C'est de l'analyse d'image, et c'est fort complexe... Accroches toi bien !

Tu pourras trouver de la doc concernant ce sujet par là ... http://dept-info.labri.fr/~lachaud/ETD/
13/12/2006, 10h53
FrancisSourd

Je te conseillerais plutôt de travailler avec le graphe sous-jacent: les noeuds sont les cases et les arêtes relient deux noeuds voisins. Lorsqu'un noeud est acquis par un joueur, on peut l'enlever du graphe. Si le fait d'enlever ce noeud crée des composantes connexes, les petites composantes connexes créées doivent correspondre aux régions entourées.
13/12/2006, 12h50
millie

Citation:

Envoyé par Fabllot

Je pense qu'il faut que tu appliques un algorithme de détection de contours...
C'est de l'analyse d'image, et c'est fort complexe... Accroches toi bien !

Tu pourras trouver de la doc concernant ce sujet par là ... http://dept-info.labri.fr/~lachaud/ETD/

Je ne vois pas pourquoi s'embeter avec ca :aie:

Ici, il est possible de savoir de maniere sure et deterministe (en utilisant par exemple des graphes) si une partie est entouree par une autre (desole je suis sur un qwerty), alors pourquoi faire intervenir des algorithmes de detection de contours en traitement d'images ? (d'autant plus qu'il en existe de tous les types, qui peuvent fonctionner que pour des cas particuliers, qui ne sont pas parfaits, et qui fonctionne en general sur un espace dont la discretisation spatiale ne correspond pas du tout a un decoupage en hexagone).
13/12/2006, 13h45
ToTo13

Bonjour,

en analyse d'image, cela revient à compter les composantes connexes...
Voilà comment faire :
- Pour une couleur qui t'interesse, tu répends une sorte de germe qui va marquer toute ta couleur. Ainsi tu saura combien de composante il y a pour chaque couleur.
- Ensuite, tu répètes cette opération mais pour le complémentaire (les parties non marquées). Si le nombre de composante du complémentaire est supérieure à un c'est qu'il y a un trou... C'est ce trou que tu veux boucher...

Si c'est pas clair, je peux de donner un exemple sur une image...
13/12/2006, 14h23
Sivrît

La connexité par une méthode comme le remplissage devrait faire l'affaire mais... sur l'image donnée les verts n'entourent pas une zone mais deux (il y en aura toujours plusieurs) : le petit groupement sur le bord et tout le reste qui est, à la taille près, dans la même situation.

Donc l'idée, je suppose, est d'identifier tous les groupements et de les assimiler tous sauf le plus gros.
13/12/2006, 17h22
Nemerle

Raffinement de FrancisSourd:

Déjà "étend" ton plateau en stockant les cases invisibles entourant ton plateau. Ces cases auront une 8ième couleur spéciale, valant toute les autres. Disons que cette couleur spéciale est "8"

a chaque hexa stocke la couleur de ses voisins (pour les hexas au bord de ton plateau donc , tu as stocké la valeur spéciale "8")

Pour une couleur donnée c, tu recherches sa frontière, soit l'ensemble des cases de couleur c n'ayant pas toutes ses couleurs de ses voisins à c ou à 8.

Alors toutes les cases à l'intérieur de cette frontière sont obligatoirement de couleur c !!

L'avantage est que même avec plusieurs composantes connexes cet algo fonctionne en une fois.

En somme:

- Soit p1(x1,y1),...,pn(xn,yn) les cases de couleur c n'ayant pas toutes ses couleurs de ses voisins à c ou à 8.
- Alors toutes les cases p(x,y) vérifiant
il existe i,j tel que xi=xj=x et yi<y<yj (en algo: le minimum des yi tel que xi=x est <y, et le maximum des yi tel que xi=x est >y)
il existe k,l tel que xk<x<xl et yk=y=yl (en algo: le minimum des xi tel que yi=y est <x, et le maximum des xi tel que yi=y est >x)
sont à passer en couleur c si elles ne le sont déjà pas!!
13/12/2006, 22h48
chris28200

Merci à tous pour toutes ces pistes.

Ta solution, Nemerle, me semble la plus intéressante et je vais essayer de la mettre en application dés que possible.
14/12/2006, 00h32
Sivrît

Citation:

Envoyé par Nemerle

- Soit p1(x1,y1),...,pn(xn,yn) les cases de couleur c n'ayant pas toutes ses couleurs de ses voisins à c ou à 8.
- Alors toutes les cases p(x,y) vérifiant
il existe i,j tel que xi=xj=x et yi<y<yj (en algo: le minimum des yi tel que xi=x est <y, et le maximum des yi tel que xi=x est >y)
il existe k,l tel que xk<x<xl et yk=y=yl (en algo: le minimum des xi tel que yi=y est <x, et le maximum des xi tel que yi=y est >x)
sont à passer en couleur c si elles ne le sont déjà pas!!

A mon avis ça ne sera pas si simple :?
Ce critère me semble supposer que le territoire du joueur soit convexe, ce qui n'est pas garanti. D'ou des faux positifs. Et comme les cases des poches sur les bords ne peuvent être ainsi encadrées il y aura des faux négatifs.

Ma méthode à moi que j'aime (note : je ne sors des formules comme ça qu'à minuit cinq):

On garde un tableau d'entiers qui double l'aire de jeu pour attribuer aux cases un numéro de zone.

Tant que l'on a des cases sans zone et n'étant pas possédées par le joueur:
--- On incrémente le compteur de zones.
--- On prend une de ces cases, on lui donne le numéro de zone courrant et on l'empile.
--- Tant que la pile est non vide:
------ On dépile.
------ Pour toutes les cases voisines n'ayant pas de zone et n'étant pas encore au joueur:
--------- On lui donne le numéro de zone courrant et on l'empile.
------ Fin pour
--- Fin tant que
--- On met le nombre de cases de la zone dans un tableau, une map ou autre.
Fin tant que

Toutes les zones sauf la plus grande (parcours brutal du tableau des numéros de zone) passent sous le contrôle du joueur.

J'ai supposé que l'on pouvait savoir si une case appartient au joueur, ce qui est différent d'être de sa couleur. Donc soit on a le "vert joueur" et le "vert non joueur" (et ainsi de suite), soit on commence par marquer le territoire du joueur comme étant la zone -1, ou 1 ,ou 0 en prenant -1 pour signifier qu'aucune zone n'a été attribuée, ou toute autre convention.

Si jamais on a deux (ou plus 8O) plus grandes zones c'est la poisse. Je suppose qu'elles rentent toutes le deux neutres...

ZUT!!!

J'ai oublié un bout d'explication!! Une fois la frontière p1(x1,y1),...,pn(xn,yn) identifée, il faut BIEN SUR checker si il y a des cycles ou pas (en particulier afin Sivrit de tenir compte de la non convexité).

Pour ce faire:

- tu pars de p1 et tu cherches un voisin V de p1 dans p2...pn
- tu continues à former ta chaine des voisins (étape 2: un voisin W de V, étape 3: un voisin X de W...) , mais à chaque étape tu check si ce voisin est AUSSI un voisin des précédents --> si oui, alors tu as une zone fermée et tu appliques l'algo du précédent post. Si non, tu regardes s'il te reste des pi non traités et tu recommences (dans le cas où la frontière a plusieurs composantes connexes).

Je résume:

- Tables x[] et y[] et z[] de longueur n représentant les pi(xi,yi) et les i
- Tables xx[] et yy[], initialisée à NULL
- un entier L initialisé à L=0
- Table booléenne b[] de longueur n, initialisée à TRUE
- un entier Nb initialisé par Nb=n
- 3 entiers muet i et j,k
- un entier imin=0
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 tant que NB<>0 si L=0{ j=0 i=imin tant que b[i]=false { i=i+1 imin=i+1 } xx[j]=x[i] yy[j]=y[i] zz[j]=i b[i]=false NB=NB-1 } sinon{ i=imin tant que |x[i]-xx[j]|>1 ou|y[i]-yy[j]|>1 ou i>n {i=i+1} \\trouve un voisin de xx[j] si i>n{ \\ pas de voisin...............on passe à une autre composante connexe L=0 j=0 } sinon{ j=j+1 xx[j]=x[i] yy[j]=y[i] zz[j]=i b[i]=false NB=NB-1 k=0 tant que k<j ou |xx[j]-xx[k]|>1 ou|yy[j]-yy[k]|>1{k=k+1} \\test si candidat xx[j] est voisin des autres xx[] si k<j{ APPEL FONCTION DE REMPLISSAGE pour les cases de k à j (cf post précédent) pour l de 0 à k-1{ b[l]=TRUE} \\on repasse les b[] des cases de 0 à k-1 à TRUE" NB=NB+k-j } } } }
[edit] j'avais oublié un -j à la derniere ligne...[\edit]

14/12/2006, 17h42
chris28200
J'aurais peut-être du vous donner dès le départ la structure que j'utilise.

Mieux vaut tard que jamais.

Pour les cellules :
Code:

1 2 3 4 5 6 7 public class cell { Color color; int centerx; int centery; int rayon; boolean empty; int owner; //player n or 0 for anyone
Pour l'hexagone :
Code:

1 2 public class board { cell[][] tab = new cell[80][80];
Pour créer mon hexagone je part du centre du tableau correspondant au centre de l'hexagone et j'utilise le système indiqué par Nermele :

http://www.imageshotel.org/images/Nemerle/hexa1.jpg

Au départ, avec deux joueurs, les cases à droite et à gauche (en noir dans l'exemple) sont marquées comme possédées respectivement par 1 et 2.

J'avais tout d'abord pensé utiliser les chemins. Par exemple, une case est encerclée par le joueur 1 si il n'existe aucun chemin reliant cette case à la case de départ du joueur 2 sans passer par une case 1. Mais j'ai peur que cela soit un peu lourd.

Les solutions par zone ou par frontière sont intéressantes mais j'avoue avoir du mal à les comprendre comme cela : je vais essayer de les implémenter et voir ce que cela donne.

Merci
14/12/2006, 17h51
Nemerle

dans mon code, il manque juste la fct de remplissage --> si tu as du mal, j'essayerai de t'écrire le code ;)
15/12/2006, 00h11
Sivrît

En fait je me demande si on ne complique pas tout... L'idée est de donner au joueur courrant toutes les zones où un autre joueur n'est pas présent (histoire de ne pas les phagocyter).

Donc en fait on pourrait faire un simple remplissage en s'arrêtant aux bords et aux cases du joueur courrant, et ce à partir des points de départ de tous les autres joueurs (ils sont connus et il suffit de tous les empiler au début). Les cases marquées nous donnent alors la ou les zones non controlée par le joueur auquel on peut donner tout le reste.

D'ailleurs ça doit être l'origine de la règle, on donne au joueur toutes les cases que les autres n'ont plus aucune chance d'atteindre.
15/12/2006, 11h42
Nemerle

ca marche aussi, mais je pense que cela ne sera pas plus simple...