[Réglé]Distance entre 2 hexagones

[Loetheri]

J'ai un peu réfléchi et cela ne me semble pas super compliqué à comprendre. Maintenant, il faut encore le programmer.

Tout d'abord, je me suis basé sur cette disposition de case :


Soit le tuple [x,y] le point d'arrivée et le tuple [u,v] le point de départ (Cela ressemble à une démonstration mathématique mais c'est pour la clarté).
Si tu voyages uniquement horizontalement, c'est simple ^^ cela veut déjà dire que y = v
Tu prends ton tuple [x,y] auquel tu soustrais ton tuple [u,v]. Cela te donne un nouveau tuple [x-u, 0]. Tu considères la valeur x-u. Tu la divises par 2 en prenant toujours le nombre entier supérieur. Cela te donne le nombre de déplacement à effectuer pour aller de [u,v] à [x,y].

Si tu voyages uniquement verticalement, c'est tout aussi simple. Cela veut dire que x = u.
Tu refais la même chose soit la soustraction de [u,v] à [x,y]. Cela te donne [0,y-v]. Tu ne considères que la valeur y-v. Tu multiplies par 2.

Là, c'était les deux cas simples ^^
J'avoue que la partie suivante ne sera peut-être pas claire. Mais n'hésitez pas à poser des questions
Tu regardes si x et u sont paires ou impaires.

• Si x et u sont tous les deux paires ou impaires, tu fais (y-v)*2. C'est le nombre de cases que tu effectues en diagonales (bas gauche, bas droite, haut gauche ou haut droite, peu importe).
  Maintenant, pour toutes les deux cases que tu effectues en diagonales (soit y-v), tu vas bouger de 2,1 (ou de -2,1 ou 2,-1 ou encore -2,-1 en fonction de la direction ^^).
  
  
• Si x et u ne sont pas tous les deux paires ou impaires, tu fais (y-v)*2 + 1. C'est le nombre de cases que tu effectues en diagonales.
  Maintenant, pour toutes les deux cases que tu effectues en diagonales (soit y-v), tu vas bouger de 2,1 (ou de -2,1 ou 2,-1 ou encore -2,-1 en fonction de la direction ^^).
  Mais n'oublie pas que tu as effectué encore une case en plus en diagonale. Ce qui veut dire que tu as augmenté/diminué encore de 1 unité sur la première coordonnée.
  Attention, car il faut savoir si tu as sauté d'une ligne complète ou non
  Exemple si tu es en 2,0 et que tu descendes, tu seras en en 3,0. Mais si tu montais, tu aurais été en 1,-1
  

Pour savoir combien de cases, il te reste à faire, c'est simple. Tu calcules la nouvelle coordonnée (en fonction du nombre de déplacements en diagonale que tu as effectué) que l'on va appeller par le tuple [a,b].
Là, c'est la même méthode que pour l'horizontale. Donc tu effectues (x-a)/2. Le nombre obtenu est le nombre de déplacements horizontaux.

J'espère avoir été suffisament clair et que tu as compris.
Bien entendu, c'est la distance en terme de cases à parcourir.
Tu peux naturellement inverser donc d'abord effecuter les déplacements horizontaux puis diagonaux.

L'image a été produite à l'aide du simulateur trouvé sur LaLex. Vous y trouverez aussi des articules sur le pathfinding (donc la traduction d'un article).

[denisc]

Je vais donc prendre les choses en main et vous dévoiler le secret du déplacement sur un terrain hexagonale...

Laissez moi le temps de préparer les petits schémas...


1. Prenons le terrain suivant : un hexagone de 6 cases de côté



2. Commençons par numéroter les cellules de cet hexagone, ligne par ligne.
Les coordonnées seront les suivantes : x,y
Elles commencent à 0.



3. Plaçons 3 points, A, B et C
Ces points ont pour objectif de nous permettre de tester le système de déplacement sur divers modèles : A vers B, A vers C, B vers C...



4. Maintenant, place aux modélisations et aux mathématiques.

A. Déplacement de A vers B
Ce déplacement a deux solutions :



Bien, commençons donc par une petite observation...
* Lorsque je me déplace sur l'axe horizontal, les valeurs de x changent toujours, de 1 en 1, et les valeurs de y sont constantes. Le deplacement sur cet axe est donc constant et uniquement basé sur l'axe des x.

Nous allons noter dX (delta X), la valeur absolue de la différence entre les valeurs de x de nos deux points : dX = ABS(xA - xB) = ABS(1 - 4) = 3

* Lorsque je me déplace sur l'axe vertical, les valeurs de y changent toujours, de 1 en 1, mais les valeurs de x changent aussi, 1 fois sur 2!

Nous allons noter dY (delta Y), la valeur absolue de la différence entre les valeurs y de nos deux points : dY = ABS(yA - yB) = ABS(0 - 2) = 2
Nous allons noter dD (delta Décalage), le nombre de décalage sur l'axe des x qui n'intervient que dY/2 fois : dD=dY/2 = 2/2 = 1

Notre nombre de cases (D=Distance ) entre A et B s'écrit donc : D = dX + dY - dD = dX + dY - dY/2 = dX + dY/2 = 3 + 2/2 = 4 cases.

Vérification : Entre B et C :
D = dX + dY/2 = 1 + 3/2 = 2,5 cases...
Comme on ne peut pas se déplacer d'une demie case, il faut arrondir à la valeur supérieure (car si on arrondi à l'inférieure, on n'aura pas parcouru les 2,5 cases nécessaires au déplacement!!!)
Donc entre B et C, D = 3 cases.

Vérifions avec d'autres distances :
Entre A et C :
D = dX + dY = 2 + 5/2 = 4,5 => D = 5 cases

Entre [0,5] et [5,1] :
D= 5 + 4/2 = 7 cases

CQFD

[Loetheri]

Quand je vois la dernière image, je me dis que ma façon de faire coutera une case de plus.
Cela dit, ma méthode a été pondue en 30 minutes.

Mais j'ai quand même hâte de voir ce que tu vas nous pondre :p

[Scha]

Hello,
Merci à tous les 2 de vous attaquer à ce problème.

Ce que je pense avoir compris de la méthode de Loetheri est qu'il décompose le mouvement en 2 : 1 diagonal, et 1 orthogonal, et ça semble être une bonne idée.
Mais je n'ai pas bien compris la manière. Quand je prend des exemples je ne retombe pas sur mes pattes, il doit me manquer des élements.

ex:
entre 4,0 et 6,2 : x et u paires. (y-v)*2 = 4. Comment savoir que le mouvement est terminé (car 4 est le bon résultat) ?

Tu dis que pour toutes les 2 cases parcourues en diagonales, on bouge de 2,1 ou -2,1 ou... etc. Comment le déterminer ? Faut-il faire un test pour chaque case du parcours ? Si oui, le code est effectivement réalisable, mais je vais rencontrer un pb de performance, car il ne s'agit pas d'un mouvement, à faire occasionnelement, mais d'une distance, à analyser (ex: parmi les 150 cases "bistrot", quelle sont les plus proches de Lulu, Gégé et Bebert ?).

Une simple formule n'est-elle pas envisageable, d'après vous ?

[naholyr]

J'ai une implémentation du A* sur plateau hexagonal dans un coin, je vais tacher de te retrouver ça.

[Loetheri]

Ma façon de faire fonctionne relativement bien mais n'est pas totalement juste. Il manque certains détails.

Pour savoir où tu te trouves, n'hésites pas à passer par des tuples (ou array) temporaires ;-) Cela t'aidera bien.

Comment déterminer le sens ? En fonction de l'endroit d'où tu viens et où tu vas ;-) C'est la même chose pour une carte avec des carrés. Une fois que tu sais dans quel sens tu dois aller, tu effectues les "mouvements" dans ce sens.

[denisc]

Voilà, j'ai terminé la démonstration.
Bon codage à présent

[Zamentur]

Tu dis que pour toutes les 2 cases parcourues en diagonales, on bouge de 2,1 ou -2,1 ou... etc. Comment le déterminer ? Faut-il faire un test pour chaque case du parcours ? Si oui, le code est effectivement réalisable, mais je vais rencontrer un pb de performance, car il ne s'agit pas d'un mouvement, à faire occasionnelement, mais d'une distance, à analyser (ex: parmi les 150 cases "bistrot", quelle sont les plus proches de Lulu, Gégé et Bebert ?).

Une simple formule n'est-elle pas envisageable, d'après vous ?

Dans ce cas je pense qu'on se trompe de codage de l'hexagrillage...

Si c'est juste çà que tu veux faire moi je te propose de representer tes Hexagone par leur centre
Tu t'aperçoit alors que ces centres sont à equidistance de leur voisin (je te propose de choisir une distance d=1 pour simplifier les calculs, ce qui peut etre plus facile pour te permetre de dessiner justement cette carte hexagonale

Ainsi si mon premier Hexagone est au point (a;b)
Les coordonnée de ses voisin sont donné par (a+cos(alpha),b+sin(alpha))
Et alpha est definie ainsi:
hexagone à droite alpha=0
en haut à droite alpha=60°
en haut à gauche alpha=120°
à gauche alpha=180°
à gauche en bas alpha=240°
à droite en bas alpha=300°

Ainsi tu peux creer ta map simplement, une fois cette map creer de cette façon tu peux utiliser la formule toute bete:

D=sqrt(pow(x2-x1,2)+pow(y2-y1))

Pour determiner la distance.
Tu peux ainsi l'utiliser directement dans une requete sql

A noter que la distance ici c'est la distance entre les 2 isocentres des 2 hexagones. Et cette methode est impropre aux problemes des obstacles qui est beaucoup plus complexe.

Voilà si tu veux plus de precision dis-le!

[Scha]

Et bien nous voilà donc avec 2 belles solutions.
Pour l'heure, je vais utiliser celle de Denis, car en plus d'être élégante, je l'ai mise en oeuvre en 30 secondes sans rien modifier de ma map, et c'est parfaitement en place. Celle de Loetheri, parfaitement logique, peut probablement être utile dans un autre contexte.

[MAJ]
Après quelques tests plus poussés, je crois qu'il y a quelques anomalies dans la formule. Ex: les cases adjacentes 3,3 et 4,2 donnent : 2. Hum ça ne doit pas être bien grave. voyons...

[Zamentur]

D'ailleurs avec la disposition que j'ai presentée tu peux aussi obtenir le chemin complet le plus court avec la methode de la droite dont j'avais parler...
Mais c'est un peu plus complexe

Déjà il faut commencer par delimiter l'hexagone qui je le rappelle est positionner par rapport à son centre... Edit: apres calcul on peut simplifier par un cercle, donc vous pouvez aller directement au passage en gras suivant
Donc on a dis que la distance d entre 2 centre etait de 1

Du coup on peut en deduire qu'un coté d'hexagone c'est
C=cos(30°)*0.5=0.43301270
De meme une diagonale
Di=C+tan(30°)=1.01036297

De çà on peut deduire les droite qui delimite l'hexagone:
Dd y=Xg+0.5
Dhd y=-(Di/2)t+(Xg-Yg+Di/2)
Dhg y=(Di/2)t+(Xg-Yg+Di/2)
Dg y=Xg-0.5
Dbd y=(Di/2)t+(Xg-Yg-Di/2)
Dbg y=-(Di/2)t+(Xg-Yg-Di/2)

et x=t t etant le parametre

Avec Xg et Yg les coordonnée du centre de l'hexagone
Bon j'espere que je me suis pas trompé dans le calcul. Bon bref là tu as ton hexagone delimitée

Il te suffit maintenant comme je disais de tracer la droite entre tes 2 points et de prendre tout les hexagones ou elle passe.
Mais le mieux de tout c'est que tu peux te permetre de simplifier les hexagones (enfin j'en suir à 99% selon les calcul que j'ai fait) par un simple cercle de rayon 0.5 et de centre G

Donc
Nous sommes sur l'hexagone A de coordonnée (a,b)
On desire se rendre sur l'hexagone B de coordonnée (c,d)
La droite peut s'ecrire ainsi:
x=(c-a)t'
y=(d-b)t' avec t' de 0 à 1 (pour que ce soit un segment et non une droite on pourrait meme affiner en ne prennat que les cases du chemin)

Donc du coup la case fait partie du chemin si:
sqrt(pow(Xg-(c-a)t,2)+pow(Yg-(d-b)t,2))=0.5 et t>0 et t<1

Alors le probleme me dira tu c'est que t est variable entre 0 et 1 et que c'est difficile à concevoir en mysql
Là je te repond tout à fait!
la seul solution que je vois c'est d'utilisé une table de t dans la bdd, qui sont tous tres raproché de 0.001 en 0.001 par exemple et l'utilisé pour simuler ce t variable (avec un Group by x,y pour pas avoir 5000 fois la meme case)
Mais il y a surement une autre solution.

En tout cas ce que je te presente là te sort tout de meme les hexagone dans l'ordre du chemin (si il y a un order by t).
A noter qu'il peut y avoir des doublons qui peuvent etre suprimer en utilisant Group by t (le probleme c'est que je l'utilise déjà)

Enfin bref je sais pas si tu as compris mais en tout cas çà me semble la methode la plus efficaces pour ton probleme