+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : [Réglé]Distance entre 2 hexagones (/showthread.php?tid=1312)
[Réglé]Distance entre 2 hexagones - Scha - 20-06-2007
Hello,
Je débute, alors j'espère que vous ne m'en voudrez pas de demander de l'aide sans en avoir apporté pour l'instant. :-\
Je cherche à déterminer le nombre de cases minimum qu'il existe entre 2 hexagones sur une carte (le chemin le plus court). J'ai vu sur internet que beaucoup de personnes se posaient cette question, mais je n'ai pas trouvé de réponse...
Ma carte fait 60/60, les cases sont numérotée de 0 à 3599.
les lignes impaires sont décalées vers la droite :
0----1----2----3 ...
--60---61---62---63 ...
...
J'ai déja pas mal cherché, et j'arrive à ce code:
($rz=distance (en nb de cases) entre les cases $d et $p)
<?
$rx=($d%60-$p%60); // difference dx-px
$ry=abs((round(($d-$p)/60))); // difference dy-py
if ($ry%2==1)
{$rx=($rx-0.5);} // jusque là, les calculs semblent bons.
$rz=round(sqrt($rx*$rx+$ry*$ry));
?>
Si la distance est inférieure à 5, ça marche, mais au-delà, ça se décale dans les 4 diagonales, puis le décalage se propage en étoile... Bref, ça n'est pas satisfaisant, et je séche complétement. La formule du triangle-rectangle n'est sans doute pas adaptée à cette situation !?
Qui pourrait m'aider, s'il vous plaît ?
RE: Distance entre 2 hexagones - denisc - 20-06-2007
C'est un simple problème de mathématiques, niveau 3°
Commence par faire un dessin de ta carte, place des points de départ et d'arrivée selon plusieurs modèles que tu pourrais rencontrer, et compte les à la main...
Comment fais-tu pour les compter??? Bin voilà, c'est pareil pour ton prg. Le tout réside dans un savant mélange des coordonnées x/(y+.5)
J'adooooooooooooooore les maths!
Bien évidemment ce système de comptage ne prendra pas en compte les cases infranchissables (rivières, creuvasses,...)!!!
RE: Distance entre 2 hexagones - Scha - 20-06-2007
Puisque le problème semble trop simple pour que tu le résolves, alors peut-être me diras-tu comment prendre en compte les crevasses ? ;-)
RE: Distance entre 2 hexagones - Zamentur - 20-06-2007
Ne suffit t'il pas de tracer une droite(le chemin le plus court) et de prendre tout les hexagone touché par cette droite? (en partant du principe que la carte est modeliser par des X/Y et non des id d'hexagone)
Apres pour ce qui est de ta crevasse c'est plus complexe, car si le but est de trouver le chemin le plus court c'est pas de la tarte!
En fait je me pose la meme question mais sur des coordonnée reelle (et donc plus d'"hexagrillage"), jusqu'ici la seul solution que je voyais c'était un algorythme qui essaye de contourner les obstacles et recupere les extremums, puis trace des droite entre ces derniers
Evidement çà ne garanties pas à 100% que c'est le chemin le plus court! Car si tu veux le chemin le plus court il faut contourner les obstacle des 2 cotés...
Je sais pas si je suis tres clair là?
A noter qu'il doit certainement exister un super algorythme(voire une formule de math?) mieux que çà...
RE: Distance entre 2 hexagones - Loetheri - 20-06-2007
Déjà, numérote tes cases en x et y.
Sinon pour ta question principale ^^ Il existe le pathfinding ou A* qui permet de découvrir le chemin le plus court entre deux cases mais s'applique également dans le cas de "tir".
Je ne saurais t'aider beaucoup plus car je n'ai que trouvé à ce jour des textes plus vagues et théorique. Mais ce n'est pas quelque chose de simple, parait-il.
RE: Distance entre 2 hexagones - Zamentur - 20-06-2007
Pourrait tu nous donner les liens de ces textes plus vague et theorique?
RE: Distance entre 2 hexagones - Loetheri - 20-06-2007
Tu les auras rapidement en faisant une recherche.
J'ai fait mes recherches il y a plus de 6 mois ^^ Donc je ne sais pas te donner de liens.
Cependant, la question me turlupine aussi donc je ferais des recherches ;-)
RE: Distance entre 2 hexagones - Zamentur - 20-06-2007
http://brassens.upmf-grenoble.fr/IMSS/mamass/graphecomp/dijkstra.htm
Et il ya une source code qui semble correspondre tout à fait à ton probleme et qui utilise cette algorythme:
http://www.vbfrance.com/codes/CALCUL-OPTIMISE-CHEMIN-PLUS-COURT-ENTRE-POINTS-GRILLE_37343.aspx
Donc je suppose que la solution est là...
A noter que j'ai pas prix le temps de lire, et que cette algorythme concerne le cas d'une matrice donc pas adapter au cas reel que j'ai presentée (en tout cas pas sous cette forme). Celà dit avec une legere adaptation çà doit fonctionner pour un Hexagrillage
RE: Distance entre 2 hexagones - Loetheri - 20-06-2007
Attention, car il existe plusieurs manières de faire du path-finding. Celle qui est la meilleure en terme de rapport qualité/"puissance investi" est le A*. Les autres algorithmes sont également bons mais ont peut-être d'autres contraintes.
Dans le code source que tu donnes, il y a au moins 13 fichiers à convertir du Visual Basic vers PHP, ce qui n'est pas idéal.
Sinon il existe un moyen mais je ne sais si cela est réalisable rapidement. Je l'expliquerai demain.
RE: Distance entre 2 hexagones - Scha - 20-06-2007
En réalité, je ne cherche pas à gérer les obstacles, c'était une blague pour Denis ;-)
Le premier stade est de trouver la distance sans obstacles, au moins jusqu'à 60 cases. Si vous êtes plus à l'aise avec des coordonnées, considérez x=n%60 et y=n/60, pour les 2 cases en question.
Merci de votre intérêt.