[Résolu] Distance sur une carte

[popayan]

Bonjour à tous.

Une petite question d'algo:

j'ai une carte faite d'hexagone et je souhaiterais calculer la distance entre une position et une autre sur cette carte. Pour une carte de carré, rien de plus simple (algo distance de levenstein) par contre je coince pour des hexagones.

En appliquant la distance de levenstein, j'obtiens un décalage sur certaine case du fait que l'hexagone a 6 cotés!

Pour avoir un apercu du problème: carte hexagone

Si vous avez une idée?
merci d'avance

[php_addict]

salut

--> http://lmgtfy.com/?q=calcul+distance+carte+hexagonale

j'ai trouvé ceci:
http://www.developpez.net/forums/d697951...rthonrome/
http://www.developpez.net/forums/d648414...hexagonal/

ca t'aides?

[popayan]

non ca ne m'aide pas... les formues de ces différents posts me donnent de meilleur résultat mais j'ai toujours un décalage de 1 sur certaine case.
J'étudie ca: http://www-cs-students.stanford.edu/~ami...exLOS.html, peut être que trouverais ma réponse là...

Au passage, le "google est ton ami" comme réponse, c'est super utile...

[atra27]

Heu ta carte est basés sur un système orthogonal ou pas?

Si oui je te propose:

Code PHP :

<?php 

$dist=sqrt(($x1-$x2)^2+($y1-$y2)^2); 

[popayan]

Je vais tester ta formule.
Par contre, pour le moment c'est plus un test, j'ai bien un projet en tête mais c'est encore loin d'être bien clair, donc rien en base de données tout simplement parce que pour le moment il y en a pas ^^

[atra27]

C'était juste pour savoir la méthode de stockage...

Certains mettrons un id a chaque case, d'autre des coordonnées x et y

Pour mon jeu j'ai opté pour les id :p (avec des coordonnées en dur derrière) mais en même temps c'est pas non plus la même base que toi (enfin je pense)

[popayan]

J'ai trouvé! Il fallait que je passe mon système de coordonnées en un système pour la forme "hexagone".
Si quelqu'un veut les formules, elles sont dispo dans la source de la page que je donne dans mon premier post.

[atra27]

Bah si ça marche...

Pas le temps de regarder le code mais c'est simpa de le mettre a dispo

Je jetterai un coup d'oeil un de ces 4 si jamais... mais si sa marche, que demander de plus!

[Kihmé]

et l'algorythme de djisktra ou un nom dans le genre, il calcul la distance la plus courte entre deux points à partir d'une matrice où sont indiquer les points reliés entre eux...

[popayan]

Oui c'est facile de l'utilisé pour un repère où l'on a, pour une position donnée, 4 voisins. Beaucoup moins facile quand on passe à 6 voisins