Discussion :

[titpuce]

Bonjour,
Je vous soumet un petit problème (j'ai une partie de la solution, mais je pense qu'il y a beaucoup moins couteux et plus élégant).
J'ai un assemblage rectangulaire dans lequel je vais mettre des mailles. l'ensemble de ces mailles va former un hexagone, dans lequel j'aimerai pouvoir gérer des symétries.

en dessin cela donne : chaque - représente une case vide.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
°° 1234567
01 ---f---
02 --f-f--
03 -f-f-f-
04 f-f-f-f
05 -f-f-f-
06 f-f-f-f
07 -f-f-f-
08 f-f-f-f
09 -f-f-f-
10 f-f-f-f
11 -f-f-f-
12 --f-f--
13 ---f---

La structure est réalisée avec des cases rectangulaires, ce qui lui donne un aspect moin "aplati" que sur mon dessin, mais bref, passons.
Dans cette structure, il y a des cases équivalentes.
Si je découpe l'hexagone formé en six, je vais avoir six cadrans symétriques. Par conséquent, il y a des cases équivalentes : si l'on s'aide des coordonnées de ligne/colonne de chaque case (chaque lettre dans mon schéma), cela donne : la case (13;4) est équivalente par symétrie médiane à la case (1;4).
Si je prend un secteur de cet hexagone de 60° et que, pour la pointe de ce secteur (case (13;4)), je cherche toutes les cases équivalentes, je vais trouver : (1;10), (1;4) (4;1) (7;4) (7;10).

La question du jour : trouver un algorithme simple qui me donne, connaissant la composition d'un secteur de 60° la composition de tout l'hexagone obtenue après rotation de ce secteur.
Dans l'exemple que j'ai donné toutes les cases sont identiques, mais dans la réalité ce n'est pas toujours le cas.
Faire la même chose pour tous les types de symétries possibles dans un hexagone, et toutes les rotations.

[titpuce]

je fais remonter, ça n'a pas l'air d'inspirer grand monde...
J'ai vu qu'il y avait des codes pour gérer les structures hexagonales, mais en s'aidant du voisin. A priori je ne peux pas les utiliser dans ce cas là, sauf si qq'un me prouve le contraire, ce qui m'arrangerait bien

[Nemerle]

je fais remonter, ça n'a pas l'air d'inspirer grand monde...

faudrait que tu expliques mieux en particulier "Si je prend un secteur de cet hexagone de 60° et que, pour la pointe de ce secteur (case (13;4)), je cherche toutes les cases équivalentes, je vais trouver : (1;10), (1;4) (4;1) (7;4) (7;10)."

En particulier, je dirais la même chose qu'à Charly: cherche "système radiciel" --> il existe une "base" (u,v) qui te permet de placer tes hexagones et de travailler simplement avec tes rotations.

Ensuite, il te suffit de passer de ta base (u,v) à ta base standard (x,y).

[Nemerle]

Considère la base (i,j) suivante:



- le centre est un centre d'un hexagone choisi par toi
- i est le vecteur qui relie ce centre au centre de l'hexagone voisin "de droite"
- j est le vecteur qui relie ce centre au centre de l'hexagone voisin "en haut à droite" (l'angle (i,j) est donc de 60 degrés)

Dans cette base, tous les centres des hexagones s'écrivent ai+bj ou i,j sont des entiers relatifs. Par exemple, en partant du centre

....j-i.....j
-i......0.....i
....-j....i-j

Travailler avec des rotations est alors plus simple dans cette base (=réseau radiciel associé à notre hexagone)

[titpuce]

merci Nemerle
Zai toujours pas compris ce qu'était un système radiciel, mais je suppose que c'est un autre référentiel de base... Google n'est pas très causant dessus....

Si je comprends bien ton explication, je dois dans mon algo travailler d'abord en ne considérant que les hexagones.
Mais si j'ai trois couronnes d'hexagones autour de ma cellule centrale, comment calculer les coordonnées selon ton système ?
Si je veux les coordonnées des trois cellules situées sous la cellule centrale je calcule :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
0
i-j
i-2j
2i-3j

Est-ce exact ?

[Nemerle]

Mais si j'ai trois couronnes d'hexagones autour de ma cellule centrale, comment calculer les coordonnées selon ton système

[titpuce]

ça, ca vaut au moins deux
m'ci lemerle

[Nemerle]

...et ai+bj c'est l'élément [a,j] de ton tableau, pour clore avec ce double post

[borisd]

...et ai+bj c'est l'élément [a,j] de ton tableau, pour clore avec ce double post

Ce serait pas [a,b] ?
Merci pour ma déniaiserie en tous cas

[j.p.mignot]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Ce serait pas [a,b]

Dans ce domaine je ne pourrais aussi que recommander de lire les chapitres d'introduction à la cristallographie.

[Nemerle]

Ce serait pas [a,b] ?
Merci pour ma déniaiserie en tous cas

si, tu as raison, j'avais des mouffles: ai+bj donne [a,b], puisque (i,j) est notre base de vecteurs !

Effectivement, une intro à la cristalo peut être utile; la base ce celle-ci réside dans les réseaux radiciels ("root systems", puisqu'en français Google n'est pas prolixe). Donc, un article sur Wiki:

http://en.wikipedia.org/wiki/Root_system

les diagrammes de Dynkin n'étant pas utiles ici, mais cela donne un exemple d'invariants rigolo

[Zarr.be]

moi aussi je travaille sur le développement de jeux avec des Hexagones, et votre discussion m'intéresse beaucoup
je crois que j'ai compris le calcul d'hexagone à Hexagone mais comment transformer une coordonnée d'hexagone en coordonner d'un tableau carré
x=5
y=6
i=x
j=y

si après ma fonction je détermine que les besoins de l'hexagone situé en i+4 et de j+2 comment je fais pour le retrouver dans mon tableau carré?
ce serait gentil de me donner le calcul sous format programmation car je n'y connais rien en algèbre ...

[Zarr.be]

attendez... je crois que ça fait Tilt
mais pour un affichage à l'écran de 20 Hexagones sur 20 j'aurais besoin d'un tableau en 30 sur 30 ce qui me fait 500 cases qui occuperaient de la place en mémoire inutilement
imaginez maintenant, une tres grande carte (pour un jeu de strategie online massivement Multi-joueurs ) de 5000 sur 5000, donc, j'aurais besoin d'un tableau de 7500 * 7500 ce qui nous fait tout de meme 31.250.000 cellules inutilement réservé
auriez-vous une astuce pour éviter cela?

[Nemerle]

et bien non: la base "canonique" (i,j) évidente indiqué plus haut et le minimum necessaire pour encoder les positions sous forme de paires d'entiers.

C'est logique: si tu prends un hexa + les 6 autours, cela te fais 7 hexagones, mais que tu stockes dans une table 3*3....... passkeuh 2*2 ca fait que 4 et 3*2 ca fait que 6

Maintenant si ta question etait technique, et si tu veux éviter les tableaux, utilise des objets différents -- des vector par exemple --

[titpuce]

Zarr : pourquoi as-tu besoin de repasser en base classique ?
Si c'est pour un calcul de positionnement de tes hexagones, tu peux aussi garder en mémoire les coordonnées chaque hexagone par rapport au centre de ta grille, mais calculé avec la base vectorielle indiquée plus haut.
Pour mon problème, je gère deux affichages : l'affichage de la grille hexagonale, où je passe d'un hexagone à un autre par un pas de 1, et un affichage d'un maillage rectangulaire, dans lequel j'indique les positions de mes hexagones (chais pas si c'est très clair comme ça....).
Pour l'hexagonale, je part d'une base vectorielle (merci nemerle), puis je fais un changement de repère pour retrouver les coordonnées de l'hexagone dans mon maillage rectangulaire.
dans le repère rectangulaire, le vecteur i correspond à un déplacement de (nx; my). Le vecteur j à un déplacemnt (ox; py)
Donc si dans le repère radiciel mon hexagone a pour coordonnées (3i+4j), la coordonnée dans le repère orthonormé sera :
( (x0+3*nx + 4*ox); (y0+3*my+4*py) )

[titpuce]

Sinon pour revenir à mon problème j'ai fini par faire un truc tout bete :
dans un tableau j'enregistre mon élément de base (1/6 de l'hexagone par ex), puis je copie dans le tableau principale la composition de l'hexagone entier, à l'aide de deux boucles for imbriquées pour générer les coordonnées x,y. Si il y a symétrie ou rotation, je génère la valeur nécessaire en parcourant le premier tableau dans un sens ou dans l'autre....
C'est bete, c'est lourd, mais ça marche....