Discussion :

[chris28200]

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.



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.

[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/

[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.

[millie]

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

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).

[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...

[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.

[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!!