Algo A* (AStar) en php

[mdcarter]

[wild-D]

- bon à la lecture, j'avoue que pour les coordonnées, l'usage de chaine de caractère que tu explodes/concatènes .. bof; je comprends pas pourquoi tu utilise pas directement des tableaux avec les 2 coord. :/

- premier test qui m'est venu à l'esprit, m'a valu déjà un plantage: si y a pas de chemin entre le départ et l'arrivée: ben on est dans la merde... donc éviter la boucle infinie ce serait bien

[keke]

Coucou,

J'avais à l'époque essayé celui là (qui se trouve dans le wiki de ce forum) :
http://wiki.jeuweb.org/tutoprog/pathfinding

Et ça avait aboutit... Peut-être as-tu travaillé pour des prunes (ou pour la joie d'avoir ré-inventé un algo ce qui peut-être un but en soit très important).
Si tu penses que ton algo est mieux, n'hésites pas à en indiquer la raison.
Si tu penses que ton algo est pire, n'hésites pas à voir si des points peuvent être amélioré sur l'algo actuellement présenté dans le Wiki.

Sache que de toutes les manières, un algo en PHP n'est pas la solution la plus optimisée qu'il soit car le PHP est bien plus lent que n'importe quelle implémentation en Assembleur ou en C/C++. C'est la raison pour laquelle on retrouve difficilement ce type d'algorithme dans ce langage.

PHP, c'est bien pour des choses basiques, pour le reste il y a la Vraie Programmation ^^ (et je pèse mes mots ^^)

Kéké
Ps : j'utilise l'algo sur mon jeu ^^, mais j'ai conscience de ses faiblesses.

[Ruz]

[Mode sais-pas-quoi ON]
Euh.. c'est quoi la fausse programmation?
[Mode sais-pas-quoi OFF]

[mdcarter]

Salut,
- La solution implémenté est loin d'être élégante j'en suis conscient, le but étant surtout de comprendre et d'implémenter cet algo, pas forcément intuitif dès de départ.
- Les cartes insolubles font également planter le script ce qui reste à régler

Je pense que mon script est mieux au niveau des commentaires, qui essayent de suivre l'algo ce qui permet d'apprendre et de l'intégrer plus facilement (j'ai toujours chercher à utiliser des scripts astar sur le net, rarement réussi du fait de l'austérité du code).
Par contre je sais bien que mon script est bien mauvais sur de nombreux points, trop verbeux, mal organisé et bugué

Voila voila, la prochaine étape serait de rendre plus propre le tout, et peut-être adapter ceci pour des cartes hexagonales.

[Ruz]

Si y en a qui veulent se pencher dessus en carte hexa, je suis pret à y contribuer ^^ (mais faut faire gaffe d'emblée aux différents types de cartes hexa possibles, suis pas sur que ce soit exactement la meme chose pour toutes...)

[mdcarter]

Je reviens vers vous, je teste actuellement la pathfinding sur une carte hexagonale, mais j'ai du mal à trouver les chemins les plus court.
Le problème en fait est de calcule les bon coûts G et H pour les cases, des idées ?

[wild-D]

pour le g ça doit être tout bête: je crois bien que ce sera toujours le même poids à ajouter 10 (y a pas de "diagonale" à 14).

par contre pour le h, ça risque d'être un peu plus chiant à calculer... (enfin je sais pas mais avec certain système de coord, ça me parait pas évident)

[mdcarter]

Pour le G on est d'accord, j'ai tout mis à 10 en effet.
Par contre j'ai beau essayer tout les système de calcul de H que je trouve, aucun ne correspond vraiment.
En fait j'ai l'impression qu'il faut ajouter une sorte de système de "correction" de chemin, car tout les chemins générés actuellement sont correct, mais ont toujours une ou deux cases de détour totalement inutile.

[wild-D]

tu utilise quel système de coordonnée hexa ?

c'est tordu parce que y a effectivement un truc; mais si tu prends un système de coordonnée pas ortho; mais aligné sur 60°; ça parait plus simple:
http://jmz.iki.fi/blog/programming/hexagonal_maps