Algorithme A star pour tuiles carrés et hexagonales

[Maz]

Bonjour, voici enfin mes classes de pathfinding basé sur l'algorithme A star.
La classe de génération de carte: Map.class.php

• Cases carrés:
  • Mode classique: Aperçu - Astar.class.php
    
  • Mode jeu de dames: Aperçu - Astar.class.php
    
  • Mode omnidirectionnel: Aperçu - Astar.class.php
    
• Cases hexagonales:
  • Orientation verticale: Aperçu - Astar.class.php
    
  • Orientation horizontale: Aperçu - Astar.class.php
    

Un exemple basique d'utilisation(aucun rendu, juste l'exécution des class): exemple.php

Si vous avez des suggestions d'améliorations, je prends =)

[chaton2cam]

Chouette, ça correspond à peut près à ce que j'ai commencé à développer avant de partir en vacances

Je regarderai plus en détail ce soir chez moi. Penses-tu que ajouter des cases "difficilement franchissable" est faisable ? Ce type de case couterait par exemple le double d'une case classique.

Sur le même principe, si tu veux tu pourrais aussi gérer des dénivelés (escaliers et pentes), qui couterait plus cher lorsqu'on les monte, et moins cher lorsqu'on les descend.

Bien sûr, le but étant que l'IA choisisse le chemin le plus rentable

[Maz]

Je l'ai développé avec ce but de pouvoir ajouter des cases de ce type. Il suffis de rajouter les conditions if ou switch (s'il y a pas mal de type de case différentes: eau, herbe, terre, sable, ...) nécessaire dans la fonction "coutCase". Je ferais probablement une implémentation basique de ce type pour une case eau coûtant deux fois plus dans les jours qui viennent pour montrer le principe.

Edit: dans un soucis de simplicité je comptes séparé ces classes en deux distinctes: une class Map gérant uniquement la génération & les coordonnées, et une class Astar gérant uniquement le chemin. Ainsi je pourrais mettre en attribut de la class Astar les listes ouverte, fermé, cout et parent, et ainsi réduire les paramètre à passer à chaque fois en référence qui commences légèrement à me sortir des yeux. Ainsi il seras aussi plus aisé d'amélioré une seule des deux classes séparément (ajouter la gestion des pnj sur la class Map par exemple...)

[Hideaki]

Comme tu as bientôt fini, voici un axe de recherche.
Actuellement ton algo donne cela http://en.wikipedia.org/wiki/File:Astar_...mation.gif voici un exemple d'un autre algo dérivé de A* http://en.wikipedia.org/wiki/File:Weight..._eps_5.gif

Le but est maintenant la performance

[Maz]

Merci pour le filon, d'après ce que je vois, théoriquement, ce serais un Astar qui:
récupères un point A ayant le plus petit score F dans la liste ouverte, récupères les points B C D E ayant le score F le plus petit par rapport au point A(la distance euclidienne calculé par rapport au point A sur ces 4points et non par rapport au point final).

Ma vision est-elle exacte? ,)

Edit: J'ai beaucoup de mal pour le bug actuel du script pour les cases carré omnidirectionnel. En effet certains chemin reste irrésolu sans raison, comme celui-ci en pièce jointe n°1. En faisant des hightlight sur le rendu de la carte pour afficher les cases qui ont été analysé, on se rends bien compte que toutes les possibilité ne sont pas calculé(voir pièce jointe n°2), et la fonction sort sur le return FALSE; du if(count($this->open) == 0) (j'ai vérifié en remplaçant le return par un print_r de la liste ouverte suivi d'un exit pour ne pas généré d'erreur sur le SVG...).
Ne faites pas attention au point de départ de la pièce jointes n°2, ils sont faussé par l'hightlight des cases analysés. Les points de départ sont toujours: 0,0 et arrivée: 9,9.

Je me casse la tronche à chercher le truc qui bloques... Mais je ne vois pas le suspect...

Edit^2: On peut voir aussi dans la pièce jointe n°3 que même si le chemin est réellement irrésolvable, toutes les cases "atteignable" ne sont pas analysé, alors qu'elles le devraient.

Edit^3: Yes, j'ai résolu le bug =) je met actuellement les classes à jour avec notamment la séparation des class Map & Astar, avec un exemple de code pour les utiliser.

Edit^4: Update réalisé.

[Hideaki]

Oui cela doit être ça ,)
Après à toi de voir et étudier toutes les possibilités mais ce n'est pas bien difficile une fois le concept comprit.

[Maz]

Oui effectivement, après ce n'est qu'une modification de la fonction casesAdjacentes. Mais je crois que je vais m'y attarder très vite, car certaines résolution avec ce script basique me laisse vraiment perplexe sur la capacité de cet algorithme (voir pièce jointe, les cases en vert clair étant dû a un passage sous paint pour définir le chemin réellement le plus court).

[Hideaki]

Je ne pense pas que cela proviennent de l'algo mais de ton code exécute ton programme pas à pas, entre nous toi aussi tu ne trouves pas le chemin minimum :p

[Maz]

Je ne pense pas que cela proviennent de l'algo mais de ton code exécute ton programme pas à pas, entre nous toi aussi tu ne trouves pas le chemin minimum :p

Nah, c'est pas mon codeuh:cogne:.

Sans blaguer si on prends par exemple le premier exemple (qui est le plus stupide =) ).

On commences sur la case au dessus de la verte: il est "normal" que l'algo partes en diagonale vers le bas(X+1;Y+1), car sa distance euclidienne avec le point final est meilleur que le point vert. On continues:
Le point le plus rapide est directement celui du dessous (Y+1), là on est d'accord. On continues donc:
On ne peut pas aller en bas, donc ce ne seras pas Y+1, ni à droite, donc pas X+1, la diagonale X-1;Y+1 est interdite, il nous reste plus que X-1 (logique).
Ensuite il finis son chemin.

Non?

Edit: après avoir refait tout les calcul des coûts des cases environnante à la mains. Tu as raison -_-:
Il aurait du au passage sur 7;7 dont le coût en "esquivant" la solution est de: 196 se refixer sur 7;6 dont le coût est de 180... c'est énervant, au moins 4jours que je n'arrives pas à faire fonctionner cet algo pourtant "basique" -_-

[Hideaki]

Le soucis avec ta case verte c'est que l'on ne sait pas la couleur dessous, je pense que tu as un problème avec le parent ou quelques choses dans ce genre.