Créer son algoritmhe de PathFinding

Le problème exposé dans ce sujet a été résolu.

Salut,

Il manque toujours une mise en contexte du problème. Là, on arrive sur le tutoriel, et tu parles directement de l’algorithme A* et de nœuds. En lisant les trois premiers paragraphes, j’ai presque l’impression qu’il me faut déjà connaître l’algorithme A* au moins un peu. À mon avis ce qu’il faudrait c’est :

  1. Présentation du problème : on veut un algorithme pour se rendre d’un endroit à un autre.
  2. Notre carte est représentée par un tableau à deux dimensions. Chaque case que l’on appellera « nœud » a une position (x, y) et est associée à une valeur ou un caractère qui représente ce que cette case est en réalité (elle peut être du sol, un mur qu’on ne peut pas traverser ou encore un autre obstacle. On associe encore à chaque case un coût (c’est le temps que l’on met pour traverser cette case).
  3. On veut se rendre d’une case du tableau (le nœud de départ) à une autre (le nœud d’arrivée). Il nous faut donc un algorithme qui trouve un chemin. Ce chemin devra être si possible le meilleur (le plus rapide à parcourir) ou en tout cas devra s’en rapprocher. Notre algorithme doit donc prendre en compte les coûts de chaque case et les cases « infranchissables » pour nous donner un bon chemin, tout ça en un temps de calcul raisonnable.

Peut-être que je me trompe et que d’autres trouveront ton début très bien. En tout cas, je suis content de voir que tu es résolu à tout expliquer le mieux possible. :)

+1 -0

Merci infiniment pour ton message. :)

Tu as entièrement raison. Je n'explique pas réellement à quoi sert un tel algorithme. Je vais donc modifier le début du cours (mais je pense mettre ça dans l’introduction du cours).

En tout cas, ton message m'aide énormément, car tu me dit ce qui ne va pas et comment réglé le problème ! :) Donc merci encore !

Peut-être que je me trompe et que d’autres trouveront ton début très bien.

Karnaj

Non, tu ne te trompe pas. Même si certain trouverons le début très bien, ça n'a pas été ton cas. Et si ce ne l'a pas été, c'est que ce ne sera pas le cas pour tout le monde. Il faut donc que je le modifie.

En tout cas, je suis content de voir que tu es résolu à tout expliquer le mieux possible. :)

Karnaj

En effet, j'aurais aimé trouvé un cours qui explique tout en détail lorsque je voulais apprendre un algorithme de recherche de chemin. Malheureusement, je n'en ai jamais trouvé (mais cela ne veut pas dire que ça n'existe pas ;) ). C'est pourquoi j'aimerais en faire un, afin d'aider le plus de débutants possible, et de ne pas les perdre en cours de route. :)

+0 -0

Bonjour les agrumes !

J'ai mit à jour le tutoriel. J'ai fait quelques ajouts dans la partie théorique (à moins que j'avais déjà publié la bêta :p ), j'ai ajouté l'introduction du cours et la partie "Pratique en Java - Préparation du terrain - Création des variables et des fonctions" ! :)

Merci d'avance pour vos commentaires.

+0 -0

Bonjour,

Ta partie de mise en contexte (intro général) mériterait une partie à part entière. Si ton public est celui qui n'a jamais fait jamais de recherche de chemin, il faut descendre d'un petit cran encore, et présenter les objectifs. Je dirai les choses ainsi.

  • on veux trouver un chemin d'un point à un autre ;
  • avec deux contraintes contradictoires
    • l'algorithme doit être rapide,
    • il doit trouver un chemin court, si possible le plus court.
  • la ligne droite est courte et rapide à calculer, mais ne tient pas compte des obstacles ;
  • on va proposer un algorithme qui trouve rapidement un chemin court.

Et là, tu peut enchainer sur la présentation de ton algorithme.

Une fois réalisé, cherche ses limites : il est lent. Tu peux alors dire les limitations standards de ces algorithmes là. À savoir, plus ou moins lent, parfois un chemin court plutôt que le plus court (mais on gagne en vitesse d’exécution en contrepartie), très mauvais dans les labyrinthes ou les long détours, très très mauvais s'il n'existe pas de chemin entre les points demandés à cause des obstacles.

Je te conseille de lire cette interview d'un type qui a réécrit le pathfinder d'un jeu de stratégie libre. Parmi les trucs subtils, ils n'utilisent pas le même algorithme pour les chemins longs et courts. De la même manière, pour les chemins longs, les jeux pré-calculent souvent un chemin : l'objet mouvant rejoint un nœud maitre qui va du bon côté, les chemins entre nœuds maitres sont pré-calculés, puis il part du dernier nœuds maitre jusqu'à sa position finale. Quand c'est bien fait, c'est transparent et efficace.

À partir de là, tu peux t'amuser à aller plus loin. Que ce passe-t-il si tu demandes à ton algorithme de faire bouger 100 bidules d'un point à un autre d'une carte avec obstacle avec un déplacement à vol d'oiseau d'une centaine de cases ? Rajoute une zone inaccessible, et tu vas bien voir les limites de ton algorithme. :P Enchaine sur un A*, qui n'est rien d'autre que ton algorithme avec une pondération lors du choix du prochain nœud à explorer.

Le site redblobgame a un excellent tuto là dessus (qui a été réécrit depuis que je l'ai lu, mais il toujours l'air bien).

Voilà. ^^

+0 -0
Ce sujet est verrouillé.