Algo (re)calcul de région dynamique d'un plateau hexagonal (Graphes)
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 :
http://i.imgur.com/Vhy57ZL.gif
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:
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.
