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.