JeuWeb - Crée ton jeu par navigateur
Algorithme A star pour tuiles carrés et hexagonales - Version imprimable

+- 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 : Algorithme A star pour tuiles carrés et hexagonales (/showthread.php?tid=5656)

Pages : 1 2

Algorithme A star pour tuiles carrés et hexagonales - Maz - 22-08-2011

Bonjour, voici enfin mes classes de pathfinding basé sur l'algorithme A star.
La classe de génération de carte: Map.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 =)

RE: Algorithme A star pour tuiles carrés et hexagonales - chaton2cam - 22-08-2011

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

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

RE: Algorithme A star pour tuiles carrés et hexagonales - Maz - 22-08-2011

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...)

RE: Algorithme A star pour tuiles carrés et hexagonales - Hideaki - 23-08-2011

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

Le but est maintenant la performance Wink

RE: Algorithme A star pour tuiles carrés et hexagonales - Maz - 23-08-2011

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é.

RE: Algorithme A star pour tuiles carrés et hexagonales - Hideaki - 23-08-2011

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.

RE: Algorithme A star pour tuiles carrés et hexagonales - Maz - 23-08-2011

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).

RE: Algorithme A star pour tuiles carrés et hexagonales - Hideaki - 23-08-2011

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

RE: Algorithme A star pour tuiles carrés et hexagonales - Maz - 23-08-2011

(23-08-2011, 11:11 PM)Hideaki a écrit : 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" -_-

RE: Algorithme A star pour tuiles carrés et hexagonales - Hideaki - 23-08-2011

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.