Terrain de jeu non rectangulaire

Bonjour,

Tout d’abord, je m’exuse pour ce titre qui n’est probablement pas très clair. Je cherche à savoir comment organiser un terrain de jeu non rectangulaire, hexagonal en l’occurence. Le but c’est bien sûr de faire quelque chose d’efficace, et si possible simple.

Pour illustrer ce que je souhaite faire, je vais prendre une grille rectangulaire classique en example. Ensuite la question est la même à chaque fois: comment transpose-t-on cela à un terrain hexagonal ?

Problème n°1: les coordonnées

Tout le monde sait que sur une grille rectangulaire, on peut désigner une case de manière unique à l’aide de deux coordonnées. A une case correspond exactement une seule coordonnée (x;y), et à une coordonnée (x;y) correspond exactement une seule case. Mathématiquement parlant, c’est une bijection.

Pour un terrain hexagonal, vu qu’on passe de 2 à 3 axes, on pourrait se dire naïvement qu’on n’a qu’à ajouter une troisième coordonnée.

Malheureusement on s’aperçoit très vite, même sans grand raisonnement compliqué, que (-1;1;0) désigne la même case que (0;0;1). Je laisse les pros s’amuser à prouver ce que j’avance, et qu’on ne peut pas construire un système linéairement indépendant avec trois coordonnées dans ce cas s’ils en ont envie, mais ce n’est pas le but premier de ce sujet.

Ce qui m’intéresse de savoir est, y a-t-il une solution en utilisant deux coordonnées ? Ou trois avec un moyen tordu pour éviter les ambiguïtés ? OU mieux vaut carrément numéroter les cases linéairement (équivalent à de la 1D) ? Les pros pourront s’amuser à prouver qu’il existe, ou qu’il n’existe pas d’isomorphisme avec une grille rectangulaire… de nouveau je ne cherche pas de preuve, seulement une solution à utiliser de manière pratique si elle existe. Je suis informaticien, pas mathématicien.

Problème 2: le nombre de cases

Pour une grille rectangulaire, si je décide qu’elle fait 6 cases de côté, alors c’est facile: il y a 6x6=36 cases. De manière générale, tout simplement x².

Pour un terrain hexagonal, j’arrive à la formule suivante par récurrences: l’exagone de 1 case de côté fait exactement 1 case, et pour construire l’exagone de côté n, on ajoute 6(n-1) cases à l’hexagone de côté n-1. Ce qui donne:

• 1 => 1
• 2 => 6(2-1)+1 = 6+1 = 7
• 3 => 12+7 = 19
• 4 => 18+19 = 37
• 5 => 24+37 = 61
• 6 => 91 (mince il n’est plus premier ! C’était trop beau)
• …

J’ai la flemme de compter pour voir si c’est correct. Ca ferait un problème de moins, mais attendez la suite !

Problème 3: Tableau 1D

Vous ne trouvez pas que les tableaux multidimensionels, c’est lourd à gérer, source d’erreurs idiotes et pas spécialement pratique, peu importe le langage de programmation ? C’est pour ça que j’aimerais bien représenter mon terrain dans un tableau 1D, c’est beaucoup plus simple.

D’où d’abord la nécessité de connaître le nombre de cases (problème précédent). Maintenant il faut ressortir le problème n°1, celui des coordonnées. Si on est resté sur deux coordonnées, on fait comment pour passer des coordonnées à l’index dans le tableau et vice-versa ?

Pour une grille rectangulaire c’est très simple: pour l la taille du côté, i l’index et (x;y) les coordonnées, on a:

• i = ly +x
• x = i%l; y = i/l

Évidemment il faudrait que la solution soit générale, c-à-d fonctionnant pour n’importe quelle valeur de l>0.

Problème 4: navigation

Mettons que sur une grille rectangulaire de taille 10x10, je me trouve sur la case à l’index 25. Par convention on va nommer les deux axes nord-sud et est-ouest, et on va dire que la case à l’index 0 (coordonnées (0;0)) est en haut à gauche. Sans même parler de conversion index=>coordonnées et vice-versa, on a:

• La case immédiatement à l’est est la case à l’index 25+1 = 26
• La case immédiatement à l’ouest est la case 25-1 = 24
• La case immédiatement au nord est la case 25-10 = 15
• Et finalement celle juste au sud est la 25+10 = 35

Et en bonus:

• JE sais que la case 29 est sur le bord droit car 29%10==10-1

• JE sais que la case 40 est sur le bord gauche car 40%10==0

• Je sais que la case 7 est sur le bord u haut car 7/10==0

• Je sais que 96 est sur le bord du bas car 96/10==10-1

Et maintenant pour mon terrain hexagonal ça donne quoi ? Vu que la réponse à ce problème découle du système de coordonnées choisi, je ne peux pas vraiment avoir d’idée… mais il faut que ça soit assez simple. Le but au final c’est quand même d’avoir un terrain où les pions se déplacent d’une case à l’autre sur les 3 axes.

Problème n°5: et si on recommençait ?

Eh oui, si on recommençait ? Parce que c’est aussi intéressant de se poser les mêmes questions pour un terrain fait de cases en forme de triangles équilatéraux par exemple; ou autre chose encore (qui est assez fou pour faire un jeu à plateau pentagonal, heptagonal ou décagonal si c’était possible ? pour les octogones je crois que ce n’est pas possible)

Conclusion

Merci pour vos réponses!

Par un mélange de flemme et de fatigue, je vais te rediriger vers cet excellent article, et t’encourager à nous dire ce qui te pose encore problème après sa lecture.

Salut !

Alors je ne suis pas un spécialiste du sujet, mais ça m’a intéressé donc j’ai fait une rapide recherche wiki / google et je suis tombé sur cet excellent article. Je l’air survolé en vitesse donc je vais laisser les gens avec plus d’expérience et de connaissances te répondre en détail mais ça à l’air de répondre à pas mal de tes questions déjà (système de coordonnées, voisins, déplacements, etc.).

Intuitivement j’aurais proposé un système de coordonnées par offset ou axial (donc un tableau 2D). Ici mais surtout ici tu pourras trouver des exemples de code utilisant les 3 systèmes de coordonnées: offset, axial (appelé hexagonal ici) et ’cubique’.

J’espère que ça peut déjà t’avancer un peu dans tes recherches. Bon courage !

[EDIT]: Bon bah grillé de 51 secondes (je t’aime, j’en boirai…), joli

Je dirais que tu as en gros deux possibilités :

• soit tu considères les diagonales comme tes lignes, mais c’est un peu galère car tu vas avoir des lignes de 2, 4, 6, 8, etc. cases
• soit tu considères la première ligne comme celle des hexagones les plus hauts et à la même hauteur, puis la deuxième ligne ceux qui sont à la même hauteur et à la hauteur la plus haute après la première, etc. Là encore tu as des lignes de longueur variable, mais que +- 1 case (11 et 12 dans mon exemple)

Donc tu peux tout à fait te ramener à un système à 2 coordonnées assez intuitif à manipuler, tu n’as plus qu’à te coder des petites fonctions qui vont bien pour convertir en index de tableau et vice-versa, vérifier que des coordonnées sont valides, obtenir les coordonnées des cases voisines, etc. selon tes besoins.

Pour ce qui est de la possibilité de faire ça avec telle ou telle forme, en maths ça s’appelle le pavage et y’a des théories assez poussées là dessus.

Du coup, on utilise un voisinage un peu spécile (Moore moins 2 coins, ce qui nous donne bien 8-2 = 6 voisins, comme un hexagone).

Voir : https://geometricolor.wordpress.com/2013/01/11/hexagonal-cellular-automata/

Pour compléter les réponses, particulièrement sur le « Problème n°5 », je propose un autre article de Red Blob Games : Amit’s Thoughts on Grids.

Au passage perso je connaissais pas red blob games, ça a l’air bien cool du coup

Bonjour,

Merci beaucoup ! JE n’ai pas encore tout lu et encore moins tout digéré du superbe article que vous avez posté, mais le système de coordonnées cubique me plaît particulièrement.

En choisissant (0;0;0) comme case centrale, ça réponds facilement à une partie du problème n°4: savoir si on se trouve dans un coin ou dans un bord. Car pour un hexagone de côté n, on se trouve dans un bord si une des coordonnées abs(x), abs(y) ou abs(z) == n, et dans un coin si deux des coordonnées respectent la condition.

Avec les coordonnées cubiques et axiales, on se rend compte que ces deux représentations sont identiques:

1
2
3
4
5
6
7

  _____
 /O-O-O\
/O-O-O-O\
O-O-O-O-O
\O-O-O-O/
 \O-O-O/
  -----

et:

1
2
3
4
5
6
7
8

  ABCDE
  ___
1|OOO\
2|OOOO\
3\OOOOO|
4 \OOOO|
5  \OOO|
    ---+

(J’espère que le forum prend bien les espaces insécables, et que je ne me suis pas trop foiré dans mon dessin en aSCII-art)

Là Oû je reste sceptique, c’est:

• Pour le stockage dans un tableau 1D
• Pour afficher les coordonnées à l’utilisateur

Pour l’affichage des coordonnées à l’utilisateur, passer en cordonnées axiales en supprimant tout bonnement z, est-ce suffisament intuitif ? ET ensuite en indiquant la coordonnée x sous forme de lettre au lieu d’un chiffre ?

Par exemple, la case centrale d’un hexagone de taille 3 serait alors C3, et on aurait les coins A1, C1, E3, E5, C5 et A3 (c’est ce que j’ai représenté dans mon second dessin) Ce qui risque d’être déroutant à expliquer au joueur est que les cases D1, E1, E2, A4, A5 et B5 n’existent pas. J’ai l’impression que c’est pourtant bien ce que font les joueurs d’abalone…

Pour le stockage dans un tableau 1D, une solution triviale s’éclaire aussi avec mon second dessin. En restant sur l’hexagone de taille 3 de l’exemple, pour ne pas faire compliqué, pourquoi ne pas faire un tableau de 25 cases, quitte à avoir 6 positions inutilisées ? L’avantage c’est que la conversion coordonnées axiales => index est immédiate, comme dans une grille rectangulaire, et après tout on n’est plus en 1980 où chaque octet compte.

Malgré tout, ça fait quand même 25% de place perdue, ou 50% si on fait un plateau en losange comme dans le jeu hex (je ne cherche pas une grille en losange mais c’est quand même important à noter).

J’ai pas bien tilté … Un lozange, c’est 0% de place perdu. Ça se stock très bien dans un tableau 2D et donc très bien dans un tableau 1D aussi.

cf mon précédent post.