Recherche de chemin ou "Path Finding"

Bonsoir à toutes et à tous !

J'aimerais écrire un cours sur un algorithme de recherche de chemin (ou "Path Finding" en anglais) que j'ai écrit en m'inspirent fortement de l'algorithme A*.

J'avais déjà rédigé une première version présentant mon algorithme. Cependant, celui-ci n’était pas parfait et était plutôt lent (pas super pour faire un jeu). C'est pourquoi je l'ai très grandement amélioré, et d'après mes nombreux tests, il peut parfaitement convenir pour un jeu (ou tout autre projet) utilisant ce genre d'algorithme.

Je souhaite donc repartir de zéro, et réécrire le cours avec cette nouvelle version.

J'ai donc fait un premier plan, que voici :

• I. Théorie
• • 1. Ce qui compose l'algorithme
• • 2. Fonctionnement de l'algorithme
• II. Pratique en Java
• • 1. Préparation du terrain
• • • a. Création des variables
• • • b. Création des fonctions
• • 2. Création de l'algorithme
• • • a. L'algorithme pas à pas
• • 3. Utilisation de l'algorithme
• • • a. Récupérer chaque nœuds
• • • b. Vers le nœud suivant

Dans la partie I. Théorie, j'expliquerais de quoi est composé mon algorithme, et comment il fonctionne. J'y mettrais plusieurs schémas afin que les lecteurs puissent comprendre cette théorie (que l'on n'aime pas toujours ) le plus simplement possible.

C'est aussi ici qu'il y aura du pseudo-code, afin de pouvoir mieux comprendre la partie II.

Dans la partie II. Pratique en Java, nous allons d'abord créer les variables et fonctions qui nous simplifierons grandement la tâche. J'expliquerais à quoi sert chacune de ces variables/fonctions.

C'est dans cette partie qu'il y aura les premières lignes de code (en Java, puisque c'est le seul langage que je maîtrise).

Une fois ces "outils" créés, on passera directement à la création de l'algorithme (2. Création de l'algorithme), toujours avec des schéma pour ne pas perdre les lecteurs en cours de route.

Enfin, le chapitre 3. Utilisation de l'algorithme expliquera comment utiliser au mieux cet algorithme.

J'aimerais savoir ce que vous pensez de ce plan. Je sais que c'est pas facile à répondre à cette question, puisque vous n'avez rien de concret. Cependant, d'après ce que je vous ai décrit, pensez-vous qu'il faut ajouter une ou plusieurs parties ?

Merci !

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.

Ça ne paraît pas être un très bon départ : écrire un bon tutoriel (donc un tutoriel validé), c'est long et ça demande de (très) bien maîtriser le sujet, parce que c'est ce que tes lecteurs supposeront en lisant ce que tu as écrit. Ce n'est pas comme un article de blog, où tu peux raconter ce que tu as fait et décrire ta démarche, même s'il reste des approximations et des choses un peu fausses. Tu risquerais de perdre beaucoup de temps pour un résultat décevant (avoir un tutoriel refusé en boucle, c'est décevant)

Je sais que cela peut paraître bizarre de dire "Je ne connais pas bien le sujet, mais je fait un tuto dessus !".

En fait, ce n'est pas comme ça qu'il faut le voir.

J'ai pendant longtemps et sans succès cherché à comprendre et à apprendre l'algorithme A Star. Puis, il n'y à pas si longtemps que ça, j'ai trouvé "mon propre algorithme" de recherche de chemin (en fait, c'est un algo basé sur A* mais de façon plus simple à comprendre et à écrire).

Du coup, je souhaiterais le partager à un plus grand nombre de personnes possible. Ce n'est pas rare de voir un débutant abandonner la recherche de chemin car il trouve ça trop compliqué. Mon cours sera là pour le remotiver, et lui montrer que finalement, ce n'est pas si compliqué que cela.

Reviens sur le tuto d'ici demain, j'ai déjà commencer la partie théorique, et tu me diras ce que tu en pense.

Ah oui, je voulais dire aussi que je préfère faire un tuto plutôt que de poster mon algo sur les forums et dire "Voilà un algo de recherche de chemin !".

Le tutoriel, contrairement au message sur le forum, sera rangé et pourra être visible par le plus grand nombre de personne (donc les débutants ont plus de chance de tomber dessus).

Je sais que tu reste dubitatif quand à ce cours, mais laisse moi jusqu’à demain ! Tu verra que finalement, je connais mieux mon sujet que je ne le pense !

Edit : Bon, j'ai réouvert la bêta du cours, afin que tu puisse voir comment sera le début :

Voir le cours

Je sais que cela peut paraître bizarre de dire "Je ne connais pas bien le sujet, mais je fait un tuto dessus !".

En fait, ce n'est pas comme ça qu'il faut le voir.

Mais c'est pourtant ce que tu veux faire.

J'ai pendant longtemps et sans succès cherché à comprendre et à apprendre l'algorithme A Star. Puis, il n'y à pas si longtemps que ça, j'ai trouvé "mon propre algorithme" de recherche de chemin (en fait, c'est un algo basé sur A* mais de façon plus simple à comprendre et à écrire).

Du coup, je souhaiterais le partager à un plus grand nombre de personnes possible.

Très bien, mais c'est le rôle d'un article de blog ça, pas d'un tutoriel.

Ce n'est pas rare de voir un débutant abandonner la recherche de chemin car il trouve ça trop compliqué. Mon cours sera là pour le remotiver, et lui montrer que finalement, ce n'est pas si compliqué que cela.

Mais est-ce que tu penses qu'un débutant qui n'a pas réussi à comprendre un tutoriel écrit par quelqu'un qui connaît le sujet a de meilleures chances d'y arriver en lisant les explications de quelqu'un qui ne le connaît pas ?

Ah oui, je voulais dire aussi que je préfère faire un tuto plutôt que de poster mon algo sur les forums et dire "Voilà un algo de recherche de chemin !".

Le tutoriel, contrairement au message sur le forum, sera rangé et pourra être visible par le plus grand nombre de personne (donc les débutants ont plus de chance de tomber dessus).

Oui d'accord, mais le tutoriel, contrairement au message sur le forum, est modéré a priori, et il n'est rangé et visible que s'il est de qualité.

On refuse rien à priori.

Ta démarche est un peu surprenante, mais j'attends de voir ton code et ton algo avant de savoir s'il acceptable ou pas.

Il n'est pas impossible que tu ais retrouvé par toi même un algorithme classique sans t'en rendre compte.

Pour l'instant tu as écrit trop peu pour que je puisse m'avancer, mais tu as de jolies illustrations et un soucis d'expliquer, ce qui est une chose que j'encourage vivement.

Si tu pouvais nous fournir le pseudo code de ton algo on serait peut-être plus aptes à te dire ce qu'il vaut.

Je vais peut être dire une betise mais ton algo semble être une recherche exhaustive avec une programmation dynamique, non ?

Tu recherche tous les chemins (recherches exhaustives) mais en cours de construction tu ne conserve que les chemins équivalents de coût minimum (la partie programmation dynamique). C'est fondamentalement différent de A* qui lui ne recherche pas forcément LE meilleur mais UN meilleur mais en économisant beaucoup de calculs.

Et par un meilleur tu veux dire potentiellement non optimal (on pourrait comprendre un chemin optimal parmi l'ensemble des chemins optimaux).

Oui, j'aurais du mettre "un des meilleurs".

Bonjour à tous.

J'ai mit à jour le tutoriel. J'explique maintenant comment remonter les Nœuds qui forme le chemin. J'ai bien sûr mit des exemples et un schéma afin de mieux comprendre.

Mais est-ce que tu penses qu'un débutant qui n'a pas réussi à comprendre un tutoriel écrit par quelqu'un qui connaît le sujet a de meilleures chances d'y arriver en lisant les explications de quelqu'un qui ne le connaît pas ?

On peux le voir de plusieurs façons.

Etant donné que je ne connais pas forcément aussi bien mon sujet qu'un "pro", je pourrais donner des explications que tout le monde pourra comprendre, alors que cette personne qui connais bien son sujet se dira parfois "Inutile d'expliquer cela, c'est simple à comprendre". Alors que non, pas forcément.

Le fait de ne pas connaitre très bien mon sujet me permettra de donner des explications de façon claire et surtout facile à comprendre.

C'est comme ça que je vois les choses.

Après, j'entend bien ce que tu essaye de me dire. Et je ne l'ignore pas. Simplement, j'aimerais essayer avant de baisser les bras et de partir sans avoir rien fait.

Et puis, écrire ce tutoriel m'apprendra beaucoup de chose. Je n'aurais donc pas perdu mon temps.

Le fait de ne pas connaitre très bien mon sujet me permettra de donner des explications de façon claire et surtout facile à comprendre.

C'est en effet quelque chose que l'on observe souvent.

Si tu pouvais nous fournir le pseudo code de ton algo on serait peut-être plus aptes à te dire ce qu'il vaut.

Autant pour moi, je n'avais que brièvement survolé ton tuto et je n'avais pas vu que c'était déjà abordé.

L'algorithme que tu décris est un BFS, car tu considères que toutes tes arêtes sont de poids unitaire (c'est à dire que la distance entre deux cases contigües vaut au plus 1). C'est très bien d'avoir su le retrouver par soi même !
J'en parle ici.

Quelques suggestions : ta liste fermée n'est pas nécessaire, puisque tu n'accèdes plus à un noeud une fois qu'il a été mis dedans. Même pour retrouver le chemin !
Tu donnes toi même une propriété :

Il faut savoir qu'un nœud parent a toujours un coût égal au coût du nœud enfant moins un.

En marquant chaque case par sa distance à la case de départ, quand tu auras trouvé l'arrivée, il suffira de parcourir en sens inverse le graphe en choisissant toujours un voisin à une distance $n-1$ (tu es sûr qu'il existe au moins un tel voisin).
Ta liste ouverte s'implémente avec une file FIFO.

Si tu pondères ton graphe, il te suffit de remplacer la file FIFO par une file à priorité et tu obtiens un dijkstra.
Si tu prends un dijkstra et que tu rajoutes un coût heuristique au poids de tes arêtes, tu obtiens A*.

Tout ça pour dire que tu fais du bon travail, mais puisque c'est redondant avec des algorithmes qui existent déjà je t'invite à prendre en considération ces remarques.

Merci pour ton message.

J'ai mit à jour le tuto. Il contient maintenant un pseudo-code de mon algorithme, et tu comprendra à quoi sert ma liste fermée.

Par contre, je n'ai pas très bien compris la fin de ton message.

Alors oui, je me doute que mon algo ce n'est pas "un algo tout nouveau que personne n'a inventé jusqu'à présent". Il a existé, à mon avis, bien avant ma naissance.

Cependant, si je veux faire un tuto dessus, c'est parce que je connais très bien mon code, et je pourrais donc l'expliquer plus facilement qu'un code déjà existant.