Créer son algoritmhe de PathFinding

L’auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Malheureusement, ce tutoriel qui était en bêta a été supprimé par son auteur.

Tout le monde se secoue ! :D

J'ai commencé (il y a 16 heures) la rédaction d'un tutoriel au doux nom de « Créer son algoritmhe de PathFinding » et j'ai dans l'objectif de proposer en validation un texte aux petits oignons. Je fais donc appel à votre bonté sans limite pour dénicher le moindre pépin, que ce soit à propos du fond ou de la forme. Vous pourrez consulter la bêta à votre guise à l'adresse suivante :

Merci !

Bonjour ! :) (Oui, je vais laisser le texte par défaut, je l'aime bien :p ).

Après avoir cherché pendant un très long moment à apprendre l'algorithme A* afin de faire de la recherche de chemin, je n'ai jamais réussi. Je trouvais cet algorithme très compliqué.

J'ai donc décidé d'écrire le mien, en m'inspirent fortement de l'algorithme A*.

Je me suis donc dit que je devais écrire un petit cours, afin d'aider les autres personnes à apprendre à coder ce genre de chose.

Cependant, je ne suis vraiment pas doué en écriture, et c'est pourquoi mon tutoriel n'est (du moins je pense) pas agréable à lire.

J'ai donc mit ce cours en bêta, afin d'avoir des avis et des idées d'améliorations.

Attention, je n'ai pas encore corrigé les (énormes) fautes d'orthographe. Je m'en occupe dès maintenant ! :p

Merci !

Édité par FougereBle

Ku Wenja warhata? U miha Wenja warha!

+0 -0
Auteur du sujet

J'ai corrigé un très grand nombre de fautes d’orthographe et j'ai reformulé quelques phrases.

Alors bien sûr, tout n'est pas parfait et certaines parties sont un peu "lourde", mais je ne sais pas trop comment faire mieux. :p

  • Que pensez-vous du tutoriel en l'état actuel (je veux dire par là : Le comprenez-vous ?) ?
  • Qu'est-ce qui reste flou ?
  • Quels sont les points à améliorés ?

Vos réponses me seront très utiles, car écrire ce cours me tiens vraiment à coeur, et j'aimerais aider les "débutants" (ne voyez ici rien de péjoratif) en leurs écrivant un tutoriel qui soit le plus accessible possible ! :)

Édité par FougereBle

Ku Wenja warhata? U miha Wenja warha!

+0 -0

Déjà algorithme !!

Ensuite, comme tu présente un algorithme, je pense qu'il est nécessaire de présenter un peu de pseudo-code. (Ou au moins une présentation "texte" au début du tuto du fonctionnement).

Ensuite, pourquoi présenter "un algorithme que tu as fait" ? :p Au final c'est l'ago A* à quelques différences d'implémentation près.

C'est juste une suggestion, mais pourquoi ne pas faire un tutoriel un peu plus général sur le PathFinding (Dijkstra, Floyd-Warshall, parcours en profondeur/largeur dans un graphe …)

Après, ceci est aussi une suggestion, peut être ajouter une preuve de l'algorithme ? (Surtout que comme tu dis que tu l'as refais à ta sauce, on n'a aucune preuve que ton implémentation marche :D ).

Idem pour la complexité.

Sinon, c'est assez bien expliqué :) (Je n'ai pas du tout fais attention aux fautes d'orthographes éventuelles). Peut-être rajouter des schémas ? (C'est peut être compliqué).

+1 -0
Auteur du sujet

Déjà algorithme !!

Ah bon ? Nan je rigole, c'est une faute de frappe. ;)

Ensuite, comme tu présente un algorithme, je pense qu'il est nécessaire de présenter un peu de pseudo-code. (Ou au moins une présentation "texte" au début du tuto du fonctionnement).

Tu as entièrement raison. Je vais m'en occuper ! :)

Ensuite, pourquoi présenter "un algorithme que tu as fait" ? :p Au final c'est l'ago A* à quelques différences d'implémentation près.

Pourquoi j'ai dit : "Un algorithme que j'ai fait" ? Et bien parce que j'ai cherché à apprendre l'algorithme A* sans succès. Je ne connais donc pas comment il se "code". Je connais juste comment il recherche un chemin.

Je ne pouvais donc pas dire "Je vais vous apprendre l'algo A Star" puisque je n'ai jamais su le refaire. J'ai donc inventé mon propre code (et non mon propre algorithme comme je le dit par erreur) en reprenant le même fonctionnement que l'algo A Star. Du coup, oui, mon algo est celui de l'A* (à deux trois poils près :p ), mais je ne sais pas à quel point.

Si je présente cet algo est pas celui A*, c'est pour trois raisons :

  • La première, c'est que je n'ai su refaire ce dernier.
  • La seconde, c'est que si j'ai su faire celui-ci, c'est qu'il est vraiment simple à comprendre.
  • La troisième, c'est que comme c'est moi qui l'ai écrit, je connais parfaitement bien mon code et je peux donc l'expliquer sans problèmes.

C'est juste une suggestion, mais pourquoi ne pas faire un tutoriel un peu plus général sur le PathFinding (Dijkstra, Floyd-Warshall, parcours en profondeur/largeur dans un graphe …)

A vrai dire, si je n'ai jamais su refaire l'algo A*, c'est qu'il y à une raison. Je ne connais pas bien ce domaine. Je voulais simplement faire un petit cours sur un algo simple à comprendre et surtout efficace !

Cependant, j'y ai tout de même pensé, c'est pourquoi je vais apprendre le plus possible sur ce domaine pour pouvoir ensuite le réexpliqué dans ce cours. Cependant, j'ai peur de :

  • Mal expliqué car je ne maîtrise pas parfaitement le sujet
  • Donner une mauvaise explication

Alors pourquoi faire un cours si je ne connais pas mon domaine ?

Et bien tout simplement parce que, comme je l'ai dit, j'apprend au "débutants" un algo extrêmement simple. Et cet algo, je le maîtrise ! ;)

C'est donc pour aider ceux qui sont dans même cas que j'était il y à quelque temps. Cependant, je vais vraiment me pencher sur le sujet afin de fournir tout ce dont le tutoriel à besoin !

Après, ceci est aussi une suggestion, peut être ajouter une preuve de l'algorithme ? (Surtout que comme tu dis que tu l'as refais à ta sauce, on n'a aucune preuve que ton implémentation marche :D ).

Comment faire ? En donnant un exécutable démo utilisant cet algo ?

A vrai dire, lorsque j'ai commencé à écrire cet algo et que je l'ai eu terminé (du moins, je pensais), il fonctionnait à merveille. Le chemin le plus court été trouvé.

Cependant, il mettait plus de 6 secondes à trouver un chemin sur une carte de 20x20 sans obstacles. Je l'ai donc amélioré, et il trouve maintenant un chemin instanément.

Mais je vais faire un petit test et vous dire combien de temps il met à trouver un chemin. ;) (Je vous dit ça dans mon prochain message !)

Idem pour la complexité.

Je n'ai pas compris. ^^

Sinon, c'est assez bien expliqué :)

Merci ! :) L'explication, c'est ce que je craignais le plus !

Avec mes maigres capacité à expliquer, j'avais très peur que mon tuto soit confus. ;)

  • A-tu réussi à comprendre la totalité des explications ?
  • Y-a-t'il eu des passages un peu plus difficile à comprendre ?

Pour les schéma, j'y ai pensé. Je sais déjà ou je vais les ajouter, et comment les faire. ;)

En tout cas, merci infiniment pour ta réponse, cela m'aide énormément !

Edit : Voici les performances de l'algo :

La recherche à été effectuée en 128 millisecondes sur une carte d'une taille de 40 sur 40.
Longeur du chemin : 48

Édité par FougereBle

Ku Wenja warhata? U miha Wenja warha!

+0 -0

Salut,

Le plus gros problème en l’état est qu’il n’y a pas d’explications du fonctionnement de l’algorithme. On arrive, on voit que tu parles de Node (d’ailleurs ce serait mieux d’utiliser le mot « nœud ») et que tu pars directement sur la réalisation de l’algorithme alors qu’on n’a aucune information à son sujet.

En gros, tu expliques seulement comment tu as codé l’algorithme et non comment il fonctionne. Or il faut faire les deux, surtout si on considère que le tutoriel est destiné aux débutants. En effet, si un débutant arrive sur ton tutoriel en l’état, il se dira peut-être « Oulah, c’est pas fait pour moi ». Alors qu’avec un extrait sur le fonctionnement de l’algorithme que tu vas présenter et sur son contexte, il se sent mieux accompagné et sait dans quoi il s’embarque avant même de toucher au code. Cet extrait plus quelques schémas, ce serait parfait. :) Donc il faudrait un peu changer le plan.

Concernant le code, je regrette juste qu’il soit en Java avec création de classe et tout. Et si tu décides d’écrire l’extrait d’explication, il faudrait y mettre du pseudo-code. Selon moi, la classe Jeu est inutile, il faudrait juste faire la fonction rechercheChemin et les fonctions qu’elle utilise. Le contexte autour rajoute des explications un peu hors de propos.

Voilà. :)

Édité par Karnaj

Assez des salamis, je passe au jambon — Je fais un carnage si ce car nage car je nage, moi, Karnaj ! — Le comble pour un professeur de mathématique ? Mourir dans l’exercice de ses fonctions.

+0 -0
Auteur du sujet

Bon mauvaise nouvelle… :(

J'ai testé mon algo en conditions réelles… je suis passé de 61FPS à 15…

Cependant, je suis en train d'apprendre l'algo A et maintenant que j'ai créé ce code (qui malheureusement ne peut être appelé à chaque tour de boucle), je trouve l'algo A plus simple ! :)

Du coup, je vais enlever ce tuto pour le moment, et je le remplacerais sûrement par celui de l'A* ! :)

Désolé encore pour le dérangement (c'est ma faute, j'avais cas mieux tester :p ).

Ku Wenja warhata? U miha Wenja warha!

+0 -0
Auteur du sujet

Oyez oyez les agrumes !

Je rouvre le tutoriels pour pouvoir poster de nouveau ici. :)

Après tout ce temps, et alors que j'essayer d'apprendre toujours et encore sans y arriver l'algorithme A*, j'ai décider d'améliorer le mien !

Cette-fois ci, je l'ai testé sur une map de 40x40, avec plein de murs et j'ai mit le Node de départ et le Node d'arrivé aux extrémités, résultats :

Temps = 57ms

Le nombre de FPS, qu'en à luir, reste à 61, alors que j’appel la fonction rechercherChemin à chaque update.

Du coup, je vais finalement pouvoir faire (enfin du coup… refaire :p) le tutoriel.

Je prend tout de même note de vos commentaires pour la V2 ! :o)

Edit : Karnaj je prend note de tes remarques. C'est vrai qu'il n'y à aucune théorie, ce qui est vraiment un gros point noir.

Je vais dans un premier temps établir un plan. Car là, j'avais écrit le cours sans en faire (bah oui, j'ai jamais écrit de cours ou de rédacs, donc je ne sais pas comment on fait).

Édité par FougereBle

Ku Wenja warhata? U miha Wenja warha!

+0 -0

Je vais dans un premier temps établir un plan. Car là, j'avais écrit le cours sans en faire (bah oui, j'ai jamais écrit de cours ou de rédacs, donc je ne sais pas comment on fait).

Tu peux toujours contacter un staff (ou ouvrir un sujet) pour demander. Nous ne sommes pas là que pour valider du contenu, mais pour conseiller aussi. ;)

Auteur du sujet

Merci ! :)

Ca fait vraiment plaisir de voir que l'on est pas tout seul. C'est vrai que j'aurais grandement besoin d'aide pour écrire ce cours.

Cependant, je sais biens que je ne peux pas arrivé et dire "Bon, je vous file mon code, rédigez moi un bon tuto !". :D

Il faut que je fasse un effort de mon côté. ;)

Je vais donc établir un premier plan, que je vous donnerais une fois que j'y aurais bien réfléchi. Si ce plan vous semble correct, alors je commencerais la rédaction du tutoriel.

Cependant, je voudrais savoir si je dois continuer à poser ici, ou ouvrir un nouveau sujet ? (Dans ce cas, je le poste où ?)

Merci encore ! :)

Ku Wenja warhata? U miha Wenja warha!

+0 -0
Auteur du sujet

Oyez oyez les agrumes !

Je vous annonce avec plaisir la ré-ouverture de la bêta du contenu « [Java] Recherche de chemin ou "Path Finding" » ! Je vous souhaite une agréable lecture à l'adresse suivante :

Merci pour votre participation.

Ku Wenja warhata? U miha Wenja warha!

+0 -0
Ce sujet est verrouillé.