Aide algo (re)calcul de région dynamique d'un plateau hexagonal

[trex]

Bonjour,

Je souhaiterais bien avoir vos avis / connaissance si vous avez déjà eu affaire à la gestion d'un plateau de jeux hexagonal.

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 voie 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

Un pseudo code bête et moche que j'ai pour l'instant en gros c'est :


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.

[TheMothMan]

Pas sûr de bien comprendre le problème, mais j'aurais fait comme ça :

Pour une case qui va changer de couleur, on regarde les 6 cases voisines.
S'il y a plus d'une de ces cases qui a l'ancienne couleur, et si une case ne touche aucune autre des cases voisines qui ont cette couleur, ça veut dire qu'il y a des chances pour qu'on coupe le groupe en plusieurs parties (2 ou 3).

Maintenant si on découpe, on peu détruire l'ancien groupe, et en partant des cases voisines qui ont la couleur du groupe précédent on peut utiliser simplement un algorithme de remplissage pour trouver les nouveaux groupes.

J'explique mal, mais j'espère que ça peut aider. :)

[trex]

Oui je comprend l'idée que tu énonces.
En gros moi je propose de faire plein de tests pour savoir si il faut recalculer les régions ou non et faire uniquement ce recalcul au besoin.
Toi tu propose de faire moins de test, beaucoup plus simple et direct pour recalculer plus souvent in fine.

Intuitivement j'aurais pensé que ta solution serais plus efficace sur un petit plateau (puisque moins d'hexagones, au final le recalcul des régions ira assez vite), mais moins intéressant eu fur et à mesure que le plateau grandit (recalcule des régions sur un grand nombre de cases prend du temps).

Mais bon mes tests aussi sont dépendant de la taille du plateau (pas les tiens), à voir précisément si ils sont aussi couteux, plus, ou moins qu'un recalcul brute à chaque supposition de scinder une région.

[TheMothMan]

Oui, ça dépend aussi de la taille du plateau et quand c'est appelé, il faut tester.

Je pense que le mieux c'est de toujours faire simple, et revenir dessus plus tard s'il y a besoin d'optimiser.

[Bordeliec]

Couin-couin !

Je pense que ça dépend beaucoup de l'ordre de grandeur de la taille du plateau (10, 100, 1000, un million d'hexagones ?) et surtout de ce que tu veux en faire.

Les "hexagones "vide" non visible pour le joueur, mais présent logiquement", c'est pour le développeur ou ça joue dans le jeu ? Entre Un hexagone 6 voisin direct qu'on peut requérir et On peut accéder à la région courante d'un hexagone (une liste d'hexagones), lequel est fait en fonction de l'autre ?

Les fonctionnalités du jeu sont-elles bien définies ?

En fonction de ça, on pourrait, d'abord, choisir un format de données adapté et, ensuite, en déduire un algorithme.

[trex]

Couin-couin !

Je pense que ça dépend beaucoup de l'ordre de grandeur de la taille du plateau (10, 100, 1000, un million d'hexagones ?) et surtout de ce que tu veux en faire.

Les "hexagones "vide" non visible pour le joueur, mais présent logiquement", c'est pour le développeur ou ça joue dans le jeu ? Entre Un hexagone 6 voisin direct qu'on peut requérir et On peut accéder à la région courante d'un hexagone (une liste d'hexagones), lequel est fait en fonction de l'autre ?

Les fonctionnalités du jeu sont-elles bien définies ?

En fonction de ça, on pourrait, d'abord, choisir un format de données adapté et, ensuite, en déduire un algorithme.

Les hexagones vide c'est pour simplifier la représentation du plateau (un tableau à 2 dimensions d'hexagones). De plus cela permettrait au besoin de créer des zones vide au milieu du plateau si on veut.

Donc en mémoire le plateaux hexagonal est stocké sous forme de tableau à 2 dimensions, mais logiquement on peut se le représenter sous forme de graphe planaire non orienté dont chaque noeuds (hormis les bords) à 6 arrêtes (voisins).
Via la représentation sous forme de tableau on peut facilement requérir ces 6 voisins.

A distinguer d'une autre représentation logique, celle des régions, qui sont en faites les composantes connexe du graphe que représente le plateau hexagonal. En mémoire on utilise une liste d'hexagone.



Les fonctionnalités du jeu sont-elles bien définies ?

? Peut tu préciser ?

[Bordeliec]

? Peut tu préciser ?
Que fait le logiciel ? Tu ne l'as pas dit.

A mon avis, laisse tomber les histoires de composantes connexes.
Tu as un tableau à 2 dimensions dont chaque élément représente un hexagone, indexé par ses coordonnées dans un repère non orthogonal, je suppose. J'en déduis que le plateau a une taille définie. Sinon il faudra peut-être utiliser une autre structure de données. Chaque hexagone à une couleur (ou "sans couleur" pour un hexagone absent). Bon, ben, si j'ai bien compris, tout ce dont tu as besoin, étant donné un hexagone, c'est de trouver les coordonnées de tous les hexagones de sa région. (Pourquoi faire, d'ailleurs ?) tu pars de cet hexagone. Il a six voisins. Tu les testes chacun (récursion ou itération) pour savoir s'ils sont de cette même couleur. Si un nouvel hexagone est de cette même couleur, tu le rajoutes à ta liste et tu recommence avec les nouveaux voisins de cet hexagone, et ainsi de suite jusqu'à ce que tu ne trouves plus d'hexagone de cette couleur. Pour être exhaustif sans revenir en arrière, il suffit, à chaque fois que tu vas tester un nouvel hexagone, de mémoriser dans quelle direction tu pars : si tu vas examiner un hexagone vers le nord-est de l'hexagone courant, en cas de succès, les hexagones suivants seront à tester au nord-ouest, au nord-est et à l'est. À moins d'avoir un plateau de taille galactique, ça devrait tourner un un temps insignifiant.
Tu as écrit ds ton message originel : on peut accéder à la région courante d'un hexagone... Pas la peine d'aller plus loin...
Maintenant, peut-être que tu veux, en fait, pouvoir obtenir la liste de toutes les régions ? Dans ce cas, il faudra appliquer plusieurs fois ce qui précède, et réfléchir encore un peu pour éviter de recalculer plusieurs fois chaque région. Mais cette solution me paraît quand même la plus simple, donc la plus sûre. Si tu essaies de maintenir des listes de régions à jour, tu pourrais te casser la tête pour pas grand-chose et te retrouver avec des régions corrompues à la suite d'erreurs subtiles dans ton algorithme !

[Bordeliec]

Désolé, j'ai écrit une ânerie ci-dessus dans le parcours du pavage pour lister les hexagones d'un région donnée. Je ne vois pas comment faire autrement qu'en vérifiant, pour chaque nouvel hexagone, s'il n'a pas déjà été testé.

[trex]

Que fait le logiciel ? Tu ne l'as pas dit.

A mon avis, laisse tomber les histoires de composantes connexes.
Tu as un tableau à 2 dimensions dont chaque élément représente un hexagone, indexé par ses coordonnées dans un repère non orthogonal, je suppose. J'en déduis que le plateau a une taille définie. Sinon il faudra peut-être utiliser une autre structure de données. Chaque hexagone à une couleur (ou "sans couleur" pour un hexagone absent). Bon, ben, si j'ai bien compris, tout ce dont tu as besoin, étant donné un hexagone, c'est de trouver les coordonnées de tous les hexagones de sa région. (Pourquoi faire, d'ailleurs ?) tu pars de cet hexagone. Il a six voisins. Tu les testes chacun (récursion ou itération) pour savoir s'ils sont de cette même couleur. Si un nouvel hexagone est de cette même couleur, tu le rajoutes à ta liste et tu recommence avec les nouveaux voisins de cet hexagone, et ainsi de suite jusqu'à ce que tu ne trouves plus d'hexagone de cette couleur. Pour être exhaustif sans revenir en arrière, il suffit, à chaque fois que tu vas tester un nouvel hexagone, de mémoriser dans quelle direction tu pars : si tu vas examiner un hexagone vers le nord-est de l'hexagone courant, en cas de succès, les hexagones suivants seront à tester au nord-ouest, au nord-est et à l'est. À moins d'avoir un plateau de taille galactique, ça devrait tourner un un temps insignifiant.
Tu as écrit ds ton message originel : on peut accéder à la région courante d'un hexagone... Pas la peine d'aller plus loin...
Maintenant, peut-être que tu veux, en fait, pouvoir obtenir la liste de toutes les régions ? Dans ce cas, il faudra appliquer plusieurs fois ce qui précède, et réfléchir encore un peu pour éviter de recalculer plusieurs fois chaque région. Mais cette solution me paraît quand même la plus simple, donc la plus sûre. Si tu essaies de maintenir des listes de régions à jour, tu pourrais te casser la tête pour pas grand-chose et te retrouver avec des régions corrompues à la suite d'erreurs subtiles dans ton algorithme !


Oui ce que tu présente correspond à un parcours en largeur du 2eme (voir ce qui suit) graphe pour tester sa connexité.

D'ailleurs j'ai été un peu flou dans mon post précédent.

Alors il y a bien une représentation logique du plateau sous forme un graphe planaire non orienté ou chaque nœud représente un hexagone, chaque arrête reliant ces voisin (6 sauf sur les bords). Ce graphe est statique.
Représenté en mémoire sous forme de tableau statique à deux dimensions.

---- sans rapport au problème du thread, mais puisque tu pose la question -----
Pas besoin de connaitre les coordonnées d'un hexagone. un simple T[NBHEX_X][NBHEX_Y] avec X_NBMAX = x, Y_NBHEX= y, x*y représentant le nombre de case du plateau de jeu (incluant les hexagones vide). La taille d'un hexagone étant fixe (en pourcentage de la résolution de l'écran de jeu), une simple position (k,l) (toujours en pourcentage de la résolution de l'écran de jeu) de départ pour le premier hexagone T[0][0], nous permettra de déduire les position des autre hexagone pour leur affichage / gestion de mouse over etc...
----------------------------------------------------------------------------

Et aussi une autre représentation logique sous forme d'un sous graphe couvrant du graphe précédent, avec les même nœuds (toujours les hexagones du plateau) mais dont les arrêtes correspondent aux voisin direct qui partage la même couleur (jusqu'à 6 maximum, 0 minimum). Les composantes connexe de ce sous graphe couvrant correspondent aux régions du plateau de jeu. Ce graphe est dynamique (au niveau des arrêtes, i.e. changement de couleurs d'un hexagone induit la suppression/création d’arêtes)
Représenté en mémoire sous forme de (plusieurs) liste(s) d'hexagone. Une liste par région. Peut évoluer, notamment en fonction de la meilleur stratégie à adopter pour le calcul des composantes connexes.