Ce site est optimisé pour être consulté depuis un navigateur moderne dans lequel JavaScript est activé.

Question Algorithme A*

Neewd

Bonjour,

Je commence à réfléchir au pathfinder alors que je n'ai même pas réussi à lire les maps etc mais j'me suis intéressé au A* quand même.

J'ai donc lu les tutoriels du forum de Lolo et Redbust.

Et une question me trotte dans la tête, comment peut on calculer la distance comme on le dit dans A* sans tenir compte des obstacles.

Dans le tutoriel de RedBust on a comme obstacle 3 cases au milieu. Que se passerait-il si les obstacles étaient sur toute la largeur en laissant un bloc d'espace (peu importe où).

Je n'arrive pas bien à comprendre, si quelqu'un pouvait m'aider à comprendre ce point obscur, ce serait cool :D :mrgreen:

Kyu

L'algo trouvera cet espace en longeant le long des obstacles.

Neewd

C'est ce que je me suis dis aussi, il va longer à forcer de tomber sur des cases en obstacles.

Mais dans le cas de l'exemple de Redbust il va partir vers le bas, tomber sur l'obstacle, et longer jusqu'en haut pour trouver la sortie ?

Sparkdaemon

D'après mes souvenirs, le A* fait une recherche en rond autour du point de départ et élargis la recherche à chaque itération jusqu'à ce que les deux points soient réunis. Dans tous les cas, le calcul est relativement rapide, le nombre de cases par map étant limité.

Mais, si un chemin est trouvable, ce chemin sera trouvé dans tous les cas. (Sauf si la route est bouchée.)

Moonlight-Angel

Sparkdaemon (cctwa <3) : C'est l'algorithme de Dijkstra ça.

Neewd : Grosso modo (pour faire court), l'algo Dijkstra (comme l'a dit mon VDD) va créer un genre de "cercle" autour de la case de départ, s'élargissant dans toutes les directions en même temps. L'algo A* va privilégier la direction qui s'approche du point d'arrivée. Conséquence directe, le premier va prendre plus de temps, le second va en prendre moins. Conséquence indirecte, le premier va forcément trouver le chemin le plus court, le second pas toujours.

Plutôt que de faire un gros pavé, j'te propose d'aller voir http://qiao.github.io/PathFinding.js/visual/ et comprendre toi-même comment fonctionne A* et Dijkstra. Déjà parce que c'est vachement fun avec cette méthode-là et aussi parce que tu peux voir en temps réel comment réagit l'algo et comment il s'y prend pour trouver le chemin et je suis sûr que ça répondra à toutes les questions que tu te poses (y compris celle que tu poses ici).

PS : Lorsque tu utilises l'A*, essaye de jouer avec l'option "weight" lorsque tu as plusieurs chemins qui mènent à une solution. Il suffit d'ajouter 1 à weight pour qu'il trouve le chemin plus rapidement, mais du coup il y aura encore plus de chances qu'il ne trouve pas le plus court.

Neewd

Merci à tous, et surtout merci à Moonlight, ton site en JS est vraiment top, je comprend bien mieux les choses qu'il réalise pour arriver au plus court chemin.

Moonlight-Angel

Btw, quand je disais que l'A* ne trouvait pas forcément le plus simple, voici un exemple.

Cliquez pour révéler Cliquez pour masquer

[Image Introuvable] Loading Image

Cliquez pour révéler Cliquez pour masquer

[Image Introuvable] Loading Image

Dans le premier cas (A*), il va se precipiter dans la direction de la destination, se heurter au mur, le longer dans les deux sens. Il va arriver à l'ouverture en-haut et voir qu'il a le champ libre vers la destination. Du coup, il cherche même pas à comprendre, il met les gaz et trace jusqu'à la destination.

Dans le second cas (Dijkstra), il va partir dans toutes les directions. Il va aussi arriver à l'ouverture en-haut en premier, mais plutôt que de tracer en YOLO jusqu'à la destination, il va garder son calme et continuer à balayer tout autour de lui. Résultat des courses, en passant par le bas, le chemin est plus court (37.46) qu'en passant vers le haut (38.49).

Forcément, dans le cas du pathfinding Dofus, on s'en fout un peu de trouver le chemin le plus court, nous tout ce qu'on veut c'est arriver à la destination sain et sauf :D.

Neewd

Ouais, j'ai regarder les différents algorithmes, je ne savais d'ailleurs pas qu'il y en avait tant.

Et j'avais lu dans mes recherches que le choix entre Djikstra et A* dépendait de la situation, mais dans notre cas cela n'a pas tellement d'importance.

En fait, j'aurais voulu après avoir re-réussi la connexion et à bouger, pouvoir gérer la distance d'aggression des mobs, donc je voulais voir lequel était le plus propice à ça :)

Moonlight-Angel

You're doing it wrong.

Dans tous les cas, j'te rappelle qu'un bot doit simuler le comportement du client (valable pour MITM et socket). Le but c'est pas de changer complètement les algos parce qu'il y en a un meilleur ou pas. Le but c'est de conserver les algos du client. Tu peux les optimiser bien sûr, mais si tu commences à planter des algos à ta sauce, tu risques de récolter le ban (ou au moins les ennuis avec le serveur).

À toi de voir.

Neewd

Donc mettre les cellules autour du groupe de monstres comme non marchable ou comme obstacle pour simuler une non agression c'est risqué ?

Moonlight-Angel

Ça j'en sais rien, j'ai jamais essayé.

Neewd

D'accord, quand j'en viendrais à ça je te tiendrais au courant pour voir si ça fonctionne.

En tout cas merci pour tes réponses et ce super tuto sur gith :)

ToOnS

non c'est pas risqué comme les cellules restes du coté client le serveur en saura jamais rien par contre il va pas falloir bouger comme d'hab , imagine un mur de cellules non marchables ajouté , normalement comme ce mur existe pas alors le perso devrait se deplacer en une seule fois , si il y'a un mur fictif alors le perso devra s'arreter pour le contourner et pas le contourner en une seule fois (car forcement le chemin sera pas le meme qu si y'a pas de mur) sinon le serveur peut se demander pourquoi le chemin est pas normal en une seule traite , si tu t'arretes entre 2 alors le serveur se dira "oh yeah , lui il evite les mobs , tout est normal"

donc se deplacer avec plusieurs petits "pathfinding" qui se stopent au(x) mur(s) fictif(s) et pas en un seul gros qui serait pas logique pour le serveur

Labo

En effet, un peu comme dit ToOnS, pour éviter les mobs, tu peux faire quelque chose de plus intelligent et en même temps efficace : tu fais ton pathfinding A* en rajoutant des obstacles, et après tu l'envoies au serveur en découpant ton chemin en morceaux qui vont tout droit.

Ainsi, tu n'envoies pas trop de messages, tu respectes le pathfinding A*, et t'es sûr d'éviter les mobs.

Neewd

Ah je comprend un peu mieux avec ton explication Labo et c'est vrai que j'avais pas trop penser a couper le chemin final en plusieurs fois !

Je vais essayer ca quand j'y serais !

Apokah

(Petit intrus) Merci pour vos réponses ça m'a bien éclairit plusieurs choses ^^

Toujours pas capable de faire le pathfinding, mais ça va arriver !

RedBust

Coucou,

Dans mon tuto il était question d'un espace discret dont on connaît les limites, donc la question d'un obstacle traversant toute la largeur ne se pose pas.

L'algo avancerait alors jusqu'à la limite puis s'arrêterait là : il n'y a pas de solution réelle donnée par le processus (dans mon tuto, ça revient au choix "pas de solution" dans le résumé de la fin).

Je suis pas sûr d'avoir bien compris la question par contre :3

kelvin59

Coucou, ça m'a beaucoup aidé à comprendre le fonctionnement, maintenant il reste plus qu'à mettre en application, se qui risque d'être assez dur ^^

BlueDream

Tu peux aussi jeter un coup d’œil aux source que j'ai partagé si cela peut t'aider:

https://github.com/BlueDream4/Pathfinder-2.0