A* Pathfinding avec Compass

[msteve]

Bonjour à tous,

J'était en train de développer un petit jeu quand j'ai été confronté à la problématique du pathfinding. Du coup je vous fait part de mon expérience pour ce genre de problèmes avec une petite lib que j'ai créée. Dedans j'ai implémenté une fonction qui utilise l'algo AStar.

https://github.com/smagras/Compass

Et j'essayerais de mettre à jour un tuto sur cette page, pour ceux qui voudraient plus  de précisions quand à l'utilisation de la bibliothèque:
http://idevlog.atspace.eu/magrasSteve/a-pathfinding-avec-compass/

Voila comment l'utiliser (On a une carte 2d, un point de départ et d'arrivé):

// Load map from file
Compass::PCore::Matrix<int> mapi = getMapFromFile("mapInput.txt");

// Config parameters for the algorithm
Compass::PPathfinding::AStar  astar;
astar.smoothPath(true); //To have smoot path
astar.init(&mapi);

// Find the path from pend to pstart
Compass::PCore::Point pend(2,2);
Compass::PCore::Point pstart(8,8);
std::list<Compass::PCore::Point> res = astar.run(pend,pstart);

// Save result in file
savePathInFile("outFile.txt",mapi,res);

Voila, j'espère que ça en aidera certain =)
(Je garantit rien quand aux performances car je n'ai pas fait beaucoup de testes pour l'instant )

[Cmdu76]

Très intéressant !

Je pense m'en servir si ça ne dérange pas

Au départ j'ai eu juste peur parce j'ai cru qu'il fallait employer ton système de map (que je n'ai pas regardé plus que ça hein, c'est juste que le mien m'est plus familier) mais en fait c'est juste une fonction perso donc c'est super

Ensuite une petite question : Pourquoi commences-tu par donner pend (qui je crois serait donc la fin) ?

(Encore une autre question en fait... : Pourquoi utiliser une classe Point au lieu de se servir de sf::Vector2i ?)

Sinon je le redis très beau travail

[msteve]

Merci pour ton enthousiasme, je suis heureux que mon travail puisse être utile.

Oui, j'aurais dû préciser le fait que "getMapFromFile" n'est pas une fonction propre à la bibliothèque. En fait,  il s'agit simplement de remplir la matrice "mapi" avec des entiers. Je voulais que ce soit le plus générique possible.

Pour le pend, tu as raison, c'est moi qui ai fait une petite erreur. Cela dépend du sens du chemin que tu veux obtenir (dans mon cas, j'étais en train de tester plusieurs cas de figure et j'ai oublié de remettre les paramètres dans l’ordre).

En ce qui concerne "sf::Vector2i", j'ai préféré utiliser une classe plus générique (Compass::PCore::Point)  pour ne pas limiter la bibliothèque à la SFML.

Merci encore pour ce commentaire.

[MyPix]

ça à l'air pas mal, mais quand on a une map déja faite, sans tiles, comment on fait pour utiliser ta lib ? (je veux dire, la map n'est pas dans un fichier et on a besoin d'un résultat en temps réel)

[msteve]

Je l'ai expliqué dans le tutoriel http://idevlog.atspace.eu/magrasSteve/a-pathfinding-avec-compass/

Regarde sous le titre: La matrice représentant votre terrain

[MyPix]

Ouais mais si justement on utilise pas de Matrice mais directement un Sprite qui représente les obstacles ? On fait comment (je veux dire on n'as pas de tiles, et on veut aller de (50;50) à (400;300)px par exemple )

[msteve]

En fait il y a deux manières de voir le déplacement d'un personnage.

- Soit celui-ci est dans un terrain (une map...) et donc tu vas chercher a trouver le meilleur chemin en fonction du terrain (pour ne pas arriver dans un cul de sac par exemple). Dans ce cas tu pourra utiliser un algorithme de pathfiding (comme le astar).#Compass

- Soit il n'y as pas de terrain et la seul chose que tu veux, c'est éviter les obstacles "un peu bêtement" pour arriver à destination. Dans ce cas tu vas en ligne droite et tu utilise un algorithme d’évitement comme le Steering Behaviors (http://gamedevelopment.tutsplus.com/tutorials/understanding-steering-behaviors-collision-avoidance--gamedev-7777).

nb: Même dans le cas du pathfinding tu auras sans doute besoin du Steering pour éviter les obstacles mobiles comme les autre personnages.

nb2: Un jour, si j'ai le temps, j'aimerais bien ajouter cet algorithme à ma bibliothèque, mais pour l'instant je n'ai pas trop le temps.

J'espère avoir répondu à ta question.

[MyPix]

Ouais, ce que je peux essayer de faire à la limite c'est un Algorithme OpenGL qui va prendre la texture de la map et qui va mettre 1 ou 0 (ou tes objets de Compass wall) pour obtenir une matrice (certes tres grande (genre 1/4 de la résolution (Si Full Hd, matrice de 480*270) selon si le pixel est transparent ou coloré
Mais je ne sais pas comment faire ça et si ça aura un impact important sur les perf (du à la taille du tableau ou au calcul)

[msteve]

480*270 ça me semble correcte, cependant je n'ai pas ue le temps de m'attarder a faire des testes, du coups je n'exclus pas un problème de perf.