Problème PathFinding

[chaton2cam]

Bonjour!

J'étudie actuellement la faisabilité d'un jeu web en PHP, de type Tactical RPG.
Je planche actuellement sur l'IA des ennemis.

Comme je l'ai dit dans ma présentation, c'est ma première expérience, et tout avis ou coup de pouce est bon à prendre.

Le calcul du chemin à parcourir se fait grâce via le "Pathfinding" disponible sur le wiki. Mais il ne marche pas tout à fait pour le moment.

La fonction de calcul retourne un tableau de l'ensemble des coordonnées à parcourir
exemple: si l'ennemi est en (0,0) et cible (6,0), le tableau du chemin sera par exemple ((0,0),(1,0),(2,0),(3,0),etc...).

Test 1 : pas d'obstacle
L'itinéraire est bien calculé

Test 2 : obstacle en (2,0)
L'itinéraire est modifié, et fait bien un détour

Test 3 : obstacle en (2,0) et (2,1)
Bug. Bien qu'il existe un chemin alternatif en faisait un plus gros détour, la fonction ne renvoi aucune solution.

Pour info, le cout pour passer sur un obstacle est de 9999.
Et j'ai rentré coutMax=9000 pour avoir suffisamment de points pour arriver à la cible en évitant les obstacles, via la fonction : chemin($tableau, 0, 0, 6, 0, 9000)

Quelqu'un a-t-il une idée de où peut venir le problème ? Une faille est-elle connue dans cette fonction ?

[php_addict]

j'ai voulu faire du pathfinding en php mais c'est pas du tout adapté, sauf pour de petits graphes, à mon humble avis il faut du langage compilé genre c++ ou java, sinon c'est beauuuuuucoup trop lent

[chaton2cam]

J'ai quand même créer mon pathfinding en PHP.

A priori, il fonctionne pas mal. Le bot évite les obstacles, et privilégie le chemin le moins couteux (il évite les "forets").

Pour le moment, chaque tour se déroule de la manière suivante :
- Détermination des coordonnées du bot.
- Calcul de l'itinéraire du bot vers l'ennemi.
- Si l'ennemi est trop loin, le bot va cibler la case du parcours calculé la plus proche de l'ennemi, et s'y rendre.

Je n'ai pas de problème de vitesse de calcul (mes cartes ne sont pas immenses).