Discussion :

[eltrex]

Bonjour,

Je souhaiterais bien avoir vos avis / connaissance si vous avez déjà eu affaire à la gestion d'un plateau de jeux hexagonal.
Ou bien plus généralement de la gestion d'un ensemble de nœuds d'un graphes que l'on peut connecter / déconnecter afin d'en définir dynamiquement les composantes connexes (je pense notamment à la gestion d'un réseau).

Voilà déjà mes bases :
- Un plateau de jeu hexagonal de X*Y hexagone (avec éventuellement des hexagones "vide" non visible pour le joueur, mais présent logiquement).
- Un hexagone 6 voisin direct qu'on peut requérir
- Chaque hexagone peut avoir une couleur propre à un instant T
- Tout hexagone de même couleur et contigüe sont assemblé dans un sous ensemble logique nommé région.
- On peut dynamiquement changer la couleurs de X hexagones à un instant T et former ainsi de nouvelles régions / en détruire / scindé d'autres.
- On peut accéder à la région courante d'un hexagone (une liste d'hexagones)

Pas la peine d'aller plus loin pour le moment sur les règles, seules celle-ci sont importante au problème.

Ici un petit exemple en image ou l'on voit 2 situations (A et B ) possible dont le réassignement dynamique de la couleur des 3 même hexagones change les régions résultant sur le plateau :



La différence se situe sur la séparation ou non de la région bleu (2) en 2 sous région bleu (2) et (8).

Une idée de pseudo code bête et moche que j'ai pour l'instant en gros c'est :

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
 
Pour chaque hexagone Hex_i dont on change la couleur
  Récupérer son ancienne région courante OldRegHex_i
  Retirer Hex_i de OldRegHex_i
  Pour tout les voisins direct VoiHexi_j de Hex_i
    Si la région de VoiHexi_j et la même que OldRegHex_i // (autrement dit le voisin direct courant de hex_i était dans la même région que Hex_i)
      Ajouter VoiHexi_j dans une liste temporaire Lvoisins_Hex_i_old des voisins de Hex_i appartenant à son ancienne région courante
    Sinon
      Ajouter VoiHexi_j dans une liste temporaire Lvoisins_Hex_i des voisins de Hex_i n'appartenant pas à son ancienne région courante    
    Fin si
  Fin pour
 
  // on teste si l'ancienne region de Hex_i c'est scindé avec son retrait de cette dernière (noeud séparateur) et on créer la (les) nouvelle(s) region(s) au besoin
  Pour chaque hexagone Hex_Voi_k de la liste Lvoisins_Hex_i_old
    Pour chaque hexagone restant Hex_Voi_l de la liste Lvoisins_Hex_i_old
      Si il n'y a pas un chemin élémentaire entre Hex_Voi_k et Hex_Voi_l parmi le sous graphe formé des hexagones de OldRegHex_i // les deux hexagones sont désormais séparés
        Parcourir les voisins récursif Hex_Liee_k de Hex_Voi_k et Hex_Liee_l de Hex_Voi_l et appartenant à OldRegHex_i et les stocker dans les listes temporaires respective des nouvelles composante connexe Lcc_k et Lcc_l
          Si Hex_Liee_k appartient à Lvoisins_Hex_i_old
            Retirer Hex_Liee_k de Lvoisins_Hex_i_old
          Si Hex_Liee_l appartient à Lvoisins_Hex_i_old
            Retirer Hex_Liee_l de Lvoisins_Hex_i_old        
        Fin parcours 
// on regarde lequel des deux hexagone séparer de l'autre fait partie de la plus grande nouvelle composante connexe (region in fine) créée
        Si |Lcc_k| > |Lcc_l|
          Retirer les hexagones de Lcc_l de OldRegHex_i
          Créer une nouvelle region NewRegHex_l équivalente à Lcc_l
        Sinon
          Retirer les hexagones de Lcc_k de OldRegHex_i
          Créer une nouvelle region NewRegHex_k équivalente à Lcc_k
          Hex_Voi_k = Hex_Voi_l
          Break // On arrête les test de connectivité pour Hex_Voi_k dans la liste restante Lvoisins_Hex_i_old, Hex_Voi_k atant sortie de OldRegHex_i, on passe directement a Hex_Voi_l
        Fin si
      Fin si
    Fin pour
  Fin pour
 
  // regarder si Hex_i peut s'integrer dans une région existante en consultant les voisins de Lvoisins_Hex_i dont la couleur de resion serai la même que sa nouvelle couler
  Pour chaque hexagone Hexi_n de Lvoisins_Hex_i
    Si la couleur de Hexi_n est égale à la nouvelle couleur de Hex_i
      Ajouter Hex_i à la région de Hexi_n
      Break
    Fin si
  Fin pour
 
  // sinon Hex_i forme une nouvelle region
  Si la region de Hex_i est NULL // precedentes étape infructueuse
    Créer une nouvelle region avec/pour Hex_i
  Fin si
Fin pour

Voilà c'est vraiment bête et moche.

Donc ce qui m’ennuie le plus c'est pour tester si le nouvel hexagone dynamiquement réassigné deviens séparateur pour sa composante connexe.
Là bêtement je fait beaucoup trop de parcourt de graphe.
J'ai l'impression que ce n'est pas la bonne solution et qu'il doit y avoir beaucoup plus simple et efficace pour faire ce test.

Alors si vous avec de l'expérience / connaissances dessus et vous souhaiteriez m'aider / m'indiquer des piste / etc. afin de pouvoir résoudre ce problème n'hésitez pas.

Merci.

[pseudocode]

Hum... Ca ne serait pas plus simple de recalculer la connexité des cases assignés aux régions 2 et 6 ?

[eltrex]

Hum... Ca ne serait pas plus simple de recalculer la connexité des cases assignés aux régions 2 et 6 ?

Quelque chose comme ceci ? :

pseudo 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
 
// fonction qui teste si il y a risque de scinder une région si on change la couleur d'un hexagone a partir de ces 6 voisins direct
PossibleSplit(Hexagon Hex)
  group_Hex = Hex.GetGroup() // la region de Hex
  // les 6 voisins direct d'un hexagone, visualisés dans une liste circulaire
  Pour chaque voisin Hex_i de Hex 
    Si Hex_i.GetGroup() == group_Hex
      // si il y a un hexagone d'une autre région entre deux hexagone de la même region que celle de Hex, alors il y a risque de coupure
      Si [((suivant(Hex_i).GetGroup() <> group_Hex) & (suivant(suivant(Hex_i)).GetGroup() == group_Hex)) || ((précédant(Hex_i).GetGroup() <> group_Hex) & (précédant(précédant(Hex_i)).GetGroup() == group_Hex))]
        return true
      Fin si
    Fin si
  Fin pour
  return false
Fin PossibleSplit()     
 
ListOldGroups // liste sans doublon des anciennes régions des hexagones dont va dynamiquement changer la couleur / région et qui présentent un risque de découpage
 
Pour chaque case Hex_i de la nouvelle région
  Si la nouvelle couleur de Hex_i est différente de son ancienne couleur
    Si PossibleSplit(Hex_i) // si on risque de scinder son ancienne region
      ListOldGroups.add(Hex_i.GetGroup()) // ajout sans doublon
      Hex_i.GetGroup().removeHex(Hex_i)
    Fin si
  Fin si
Fin pour
 
// on calcule la/les nouvelle région(s)/composante(s) connexe(s) des régions de ListOldGroups
Pour chaque région Log_j dans ListOldGroups
  // on calcul la composante connexe du premier hexagone de la région Log_j
  List NewSubGroup = CalculComposanteConnexe(Log_j.GetHex(0))
  Tant que |NewSubGroup| < |Log_j| // tant que le nombre d'hexagone de la composante connexe calculé est inférieur à celle de "départ"
    Pour chaque hexagone Hex_k dans NewSubGroup
      Log_j.removeHex(Hex_k)
    Fin pour
    // et on recalcul les autres possible composante connexe sur le reste de Log_j
    NewSubGroup = CalculComposanteConnexe(Log_j.GetHex(0))
  Fin tant que
Fin pour

Donc en gros on fait beaucoup moins de test en profondeur sur la séparation, et on recalcul plus souvent les régions.

Ça reste plus simple à comprendre, mais j'ai peur que sur un gros plateau de jeux les recalculs de régions prennent au final plus de temps que les calcul plus complexe initiaux sur les tests (exhaustifs) de séparation.

Et deuxième point il me reste a voir la fonction CalculComposanteConnexe() de calcule de composante connexes a partir d'un hexagone.
Je me demande quel algorithme serais le plus adapté à la structure particulière que représente un plateau hexagonal (graphe planaire non orienté avec des noeuds ayant toujours 6 arrêtes (voisin) )

Merci d'avance.

[pseudocode]

Ça reste plus simple à comprendre, mais j'ai peur que sur un gros plateau de jeux les recalculs de régions prennent au final plus de temps que les calcul plus complexe initiaux sur les tests (exhaustifs) de séparation.

Il y a des algos de labélisation en o(N), N étant le nombre de cases a labéliser. C'est donc assez rapide.

Des exemples ont été postés dans la rubrique "contribuez". L'algo "union-find" notamment a besoin de faire seulement deux passes sur les cases.

[MABROUKI]

bonjour eltrex

Pour trouver toutes les composantes connexes de ton graphe ...Cela est un vieux probleme pour lequel la solution consiste à executer une descente DFS ou BFS sur un noeud initial -s- quelconque du graph...
Une GraphTemp "temporaire" contenant tous les noeuds et arcs du graphe
Chaque descente trouve une composante connexe CP issue de -s-..
Les noeuds trouves doivent etre marques (memorises) dans des listes separees (une par composante) et supprimes dans GraphTemp comme etant traites...

Une boucle
TantQue GraphTemp non vide
pick noeudSuivant
performDFS (GraphTemp,noeudSuivant )

L'algo PerformDFS doit etre amenage :
-pour memoriser les noeuds de chaque composante connexe trouve et la composante evidement...

La recursivite etant une "seconde" nature des graphes c'est tout compte fait l'algo precedent que tu dois executer pour tester si un noeud(bleu) -m- disconnecte ta composante connexe courante ..car .....car.....
Ne l'oublie pas une composante connexe d'un graphe est par defintion un sous-graphe d'un graphe autrement dit un graph ...!!!!

Si l'algo precedent renvoi 2 composantes connexes le noeud -m- est disconnectant et en bonus les cp ce qui est recherche...sinon vide...

sur ce lien wiki "finding connected component"
http://www.google.fr/url?q=http://en...QGXdhuZfuAmY-Q

Consulter les paragraphes :
- The number of connected components
- Algorithms

It is straightforward to compute the connected components of a graph in linear time (in terms of the numbers of the vertices and edges of the graph) using either breadth-first search or depth-first search

et le renvoi sur DFS

http://en.wikipedia.org/wiki/Breadth-first_search

............

[eltrex]

bonjour eltrex

Pour trouver toutes les composantes connexes de ton graphe ...Cela est un vieux probleme pour lequel la solution consiste à executer une descente DFS ou BFS sur un noeud initial -s- quelconque du graph...
Une GraphTemp "temporaire" contenant tous les noeuds et arcs du graphe
Chaque descente trouve une composante connexe CP issue de -s-..
Les noeuds trouves doivent etre marques (memorises) dans des listes separees (une par composante) et supprimes dans GraphTemp comme etant traites...

Une boucle
TantQue GraphTemp non vide
pick noeudSuivant
performDFS (GraphTemp,noeudSuivant )

L'algo PerformDFS doit etre amenage :
-pour memoriser les noeuds de chaque composante connexe trouve et la composante evidement...

La recursivite etant une "seconde" nature des graphes c'est tout compte fait l'algo precedent que tu dois executer pour tester si un noeud(bleu) -m- disconnecte ta composante connexe courante ..car .....car.....
Ne l'oublie pas une composante connexe d'un graphe est par defintion un sous-graphe d'un graphe autrement dit un graph ...!!!!

Si l'algo precedent renvoi 2 composantes connexes le noeud -m- est disconnectant et en bonus les cp ce qui est recherche...sinon vide...

sur ce lien wiki "finding connected component"
http://www.google.fr/url?q=http://en...QGXdhuZfuAmY-Q

Consulter les paragraphes :
- The number of connected components
- Algorithms


et le renvoi sur DFS

http://en.wikipedia.org/wiki/Breadth-first_search

............

Oui je comprend, par contre justement je me posais la question de savoir si il ne valait mieux pas faire mon petit test (une sorte d'heuristique en fait) PossibleSplit().
Il est assez rapide et non dépendant de la taille du plateau de jeu puisque on regarde juste sur les 6 cases voisines si il y a un trou entre 2 de ces hexagones voisins de la même région que l'hexagone central dont veut changer la couleur, avant de faire la calcul de des composante connexes (et là effectivement si retour de composante connexe > 1 alors il y a séparation avec les nouvelle composante connexe résultante).

Aussi ok pour les parcours en profondeur ou largeur, pour calculer les composantes connexe, mais je demandait justement si en prenant en compte la nature hexagonale du graphe, un algorithme spécialement optimisé pour ce genre de graphe planaire non orienté, régulier (sauf sur les bords du plateau), aurait été plus efficace pour calculer les composantes connexes.

Des exemples ont été postés dans la rubrique "contribuez". L'algo "union-find" notamment a besoin de faire seulement deux passes sur les cases.

Il faudrait que je relise pour être sur, mais il me semblait que ce genre d'algo fonctionnait en parallèle de la construction du graphe. La mon graphe est dynamique (on change les régions, donc les arrêtes représentant 2 hexagones voisin direct de même couleur) au fur et à mesure de l'avancé du jeu.

[pseudocode]

Il faudrait que je relise pour être sur, mais il me semblait que ce genre d'algo fonctionnait en parallèle de la construction du graphe. La mon graphe est dynamique (on change les régions, donc les arrêtes représentant 2 hexagones voisin direct de même couleur) au fur et à mesure de l'avancé du jeu.

En gros, l'algo Union-Find consiste a maintenir des pointeurs vers la cellule précédente/suivante de la région. Une cellule qui n'a pas de prédécesseur est la racine d'une région.

C'est donc tout a fait compatible avec la représentation en graphe de ton plateau. Il suffit d'avoir un ordre de parcours des cellules.