Salut tout le monde,
La lib de pathfinding que je code commence à ressembler à quelque chose (enfin à devenir utilisable)
Pour l'instant il fait :
- Résolution de chemin par l'algo A* dans un graphe 2D (une matrice)
- Coûts de déplacement modifiables (si vous voulez que telle ou telle case soit de l'herbe, sable, bitume ou autre, l'algo en tiendra compte)

A venir (peut etre) :
- Résolution dans un univers 3D ? (je vois l'intéret que pour les simulateurs de vol/spatiaux)
- threads? Ca serait sympa même si pour l'instant je le trouve pas lent.

En gros à utiliser ca donne ça :

#include <yasp.h>
#include <iostream>

int main()
{
    // First, we create the graph
    yasp::CGraph *world;
    world = new yasp::CGraph(20);

    // Then, we make some squares unwalkable...
    for (int y = 1 ; y < 6 ; y++)
        world->getSquare(4,y)->setState(yasp::CSquare::ST_UNWALKABLE);

    for (int x = 1 ; x < 4 ; x++)
        world->getSquare(x,4)->setState(yasp::CSquare::ST_UNWALKABLE);

    // ... and we make some others slow
    for (int y = 3 ; y < 8 ; y++)
        world->getSquare(2,y)->setMoveCost(40);

    // We call the finder and give him the graph...
    yasp::CPathFinder aStarFinder(world);
    // And we solve it.
    yasp::CPath shortestPath = aStarFinder.find(world->getSquare(2,2),world->getSquare(8,8));

    std::cout << "Chemin choisi :" << std::endl;

    for(int i = 0 ; i < shortestPath.getSize() ; i++ )
        std::cout << "X = " << shortestPath.getSquareCoords(i).x << " et Y = " << shortestPath.getSquareCoords(i).y << std::endl;

    return 0;
}

Mais bon je sais pas si c'est utilisable partout. Comment vous voudriez que ça se présente pour l'utiliser dans votre projet? L'utilisation de matrice limite peut-être les possibilités?

plouf

izguit :

A venir (peut etre) :
- Résolution dans un univers 3D ? (je vois l'intéret que pour les simulateurs de vol/spatiaux)

hmm, t'est sur ? imagine un univers pas plat, avec des étages, ou des surplomb, ca pourrai etre sympa d'avoir enfin un pathfindig qui ne pense qu'a son étage mais bon pas forcé de passer par une matrice 3d, en tout cas je trouve quand meme l'idée sympa

izguit :

- threads? Ca serait sympa même si pour l'instant je le trouve pas lent.

de la logique floue ca pourrai etre super class, genre si on demande un résolution, le path find donne la derniere meilleure solution connue,

izguit :

Mais bon je sais pas si c'est utilisable partout. Comment vous voudriez que ça se présente pour l'utiliser dans votre projet? L'utilisation de matrice limite peut-être les possibilités?

je suis d'accord, un graphe matriciel ca pourrait etre pas mal aussi

bon courrage, ca a l'air cool

Dernière modification par Jerry Kan (16-07-2007 19:11:01)

Ca a l'air intéressant ca

Résolution dans un univers 3D ? (je vois l'intéret que pour les simulateurs de vol/spatiaux)

Je penses que ce serait très utile, et pas seulement pour les simulateurs de vol (imaginons un batiment à plusieurs étages dans un FPS, une matrice seule ne suffit sans doute pas).

L'utilisation de matrice limite peut-être les possibilités?

Certainement. A mon avis, le mieux serait d'avoir une classe abstraite, CGraphe, et plusieurs classes qui en dérivent : une représentation en matrice et une représentation en graphe (ou chaque noeud contient la liste des noeuds qui sont en relation avec lui). Après, l'utilisateur voit quelle est la représentation la plus adaptée (si il a juste un terrain, sans étages, comme dans la plupart des RTS par exemple, la représentation sous formes de matrices me parait plus adapté).
Enfin, c'est juste des suggestions, mais je penses que tu devrait implémenter de "vrais graphes".
Je te souhaites bon courage pour la suite, et je vais suivre ce thread avec attention

merci de vos réponses ça fait plaisir

Jerry :

hmm, t'est sur ? imagine un univers pas plat, avec des étages, ou des surplomb, ca pourrai etre sympa d'avoir enfin un pathfindig qui ne pense qu'a son étage  mais bon pas forcé de passer par une matrice 3d, en tout cas je trouve quand meme l'idée sympa

Bin le problème quand je parlais de pathfinding 3d c'est que les successeurs du node seraient tout ceux autour de celui-çi, donc il chercherait même en "volant", pas seulement au raz du sol (j'ai un peu de mal à l'expliquer )

Jerry :

de la logique floue ca pourrai etre super class, genre si on demande un résolution, le path find donne la derniere meilleure solution connue,

Pas encore regardé de ce côté là, je vois pas trop ce que tu veux dire par "la dernière meilleure solution connue"

Perceval :

Certainement. A mon avis, le mieux serait d'avoir une classe abstraite, CGraphe, et plusieurs classes qui en dérivent : une représentation en matrice et une représentation en graphe (ou chaque noeud contient la liste des noeuds qui sont en relation avec lui).

Ouais ça va peut se faire facilement. En revanche ça peut être le bordel à utiliser, faut déclarer tous les noeuds, avec tous leurs successeurs et les couts de déplacement de chacun. C'est un peu pour ça que je suis pas parti de ce côté-là (aussi parce que je dois l'utiliser avec un systeme de terrain tile-based)

Pour l'utilisation de thread je laisse tomber, autant faire tourner la fonction globale du pathfinder dans un thread si besoin.

faut déclarer tous les noeuds, avec tous leurs successeurs et les couts de déplacement de chacun

Dans ce cas là, je penses qu'il faudrait un outil pour éditer les noeuds du graphe, puis les sauver dans un fichier (si je me souviens bien, worldcraft, l'éditeur de Half life, faisait un truc comme ca : on plaçait des nodes un peu partout sur la carte, autour des poteaux, aux angles des couloirs, partout où les NPC étaient sensés pouvoir aller).

Pour l'utilisation de thread je laisse tomber, autant faire tourner la fonction globale du pathfinder dans un thread si besoin.

T'as raison Ca me paraît pas très utile, et çà risque de compliquer sérieusement le tout

je vais voir pour un plugin pour irrEdit, ça pourrait être intéressant, en plus de la matrice.

salut;

il est vrai que a avoir fait le systeme du graphe autant l'utiliser pour les algos comme une liste d'adjacence ainsi c'est a l'utilisateur de le transformer en structure 2d ou 3d de plus ca ne complique en rien la programmation des algo si mes souvenirs sont bons ( voir meme ca les facilites ... ).
Enfin puisque le systeme de graphe est fait ,coder les algos c'est plus tres dur alors pourquoi ne pas proposer autre chose que la A* car certain sont plus rapide sur certain type de graphe (complexite algorithmique fonction du nombre de sommets ou  nombre d'arretes ) ... c'est tres optionnel a vrai dire .

Bon moi je sais pas quoi dire, j'attends avec impatience de voir si ça sera intégrable dans mon jeux, ça me ferai gagner beaucoup de temps ^^.
Sinon tu prévois une démo quand même qu'on puisse tester rapido pour les fégnasses comme moi ?

Une lib de pathfinding, ça m'intéresse aussi pas mal.

Après un rapide parcours du thread, on dirait que ta résolution s'effectue uniquement dans un espace discret. Et on peut implémenter A* dans un milieu continu au moyen d'une petite bidouille élégante .... à réfléchir
Ta résolution se fait en un appel (qui est forcément long). Ne faudrait-il pas faire une résolution étape par étape, comme quand une unité est arrivée à un noeud et cherche quel sera le noeud suivant, quitte à implémenter les 2 ? Ca permet une résolution non omnisciente et donc plus réaliste (encore que, c'est discutable).
Une biblio de pathfinding fait appel à des contraintes de temps réel pour lesquelles il ne faut rien calculer qui pourrait se retrouver changé. Si une unité vient se placer sur le chemin, la solution ne sera plus bonne. Une utilisation de threads serait discutable, surtout si on ne calcule qu'un infime morceau du chemin à chaque appel.

Mais c'est une très bonne initiative, qui pourra être très intéressante si elle est suffisamment souple.

je m'attendais pas à autant de feedback

@ firnafin : Plus rapide que A* en pathfinding? t'as des liens? Perso jamais rencontré plus facile (quoique j'ai jamais regardé les réseaux neuronaux mais ca me parait un poil merdique à implémenter pour du pathfinding ) Mais ça m'intéresse.

@ Coco : Ouais une démo est prévue mais je trouve toujours des trucs à ajouter/modifier dans la lib et la démo de test est toujours aussi ..... pourrie

@ khayyam : Une résolution "noeud par noeud" comme tu le cite n'est pas vraiment possible avec A* (enfin si, mais on perd l'intéret de l'algo). Mais je vois ce que tu veux dire. Il faudrait plutot rechercher le chemin et mettre à jour le graphe à chaque "découverte" d'un obstacle, et réeffectuer la recherche. (Enfin c'est comme ça que je le verrais perso ; si vous avez d'autres idées...)

izguit :

[quote=Jerry]hmm, t'est sur ? imagine un univers pas plat, avec des étages, ou des surplomb, ca pourrai etre sympa d'avoir enfin un pathfindig qui ne pense qu'a son étage  mais bon pas forcé de passer par une matrice 3d, en tout cas je trouve quand meme l'idée sympa

Bin le problème quand je parlais de pathfinding 3d c'est que les successeurs du node seraient tout ceux autour de celui-çi, donc il chercherait même en "volant", pas seulement au raz du sol (j'ai un peu de mal à l'expliquer )[/quote]
t as raison, je vois ce que tu veux dire,

ca pourrai etre pas mal avec un graphe matriciel, yaurai alors juste a relier des endroits, et c'est encore plus souple que la 3d (imaginons des téléporteurs sur la map)

izguit :

[quote=Jerry]de la logique floue ca pourrai etre super class, genre si on demande un résolution, le path find donne la derniere meilleure solution connue,

Pas encore regardé de ce côté là, je vois pas trop ce que tu veux dire par "la dernière meilleure solution connue"[/quote]
en gros l'idée c'est de lancer un pathfind dans un thread, et quand le temps critique est attein (le perso DOIT se déplacer) on demande au thread,
ca fait longtemps que j'ai plus touché le a*, mais il va trouver plusieurs solutions et les évaluer non ? imginons que quand on l'interroge, il en ai trouvé, mais qu'il n'ai pas TOUT trouvé,  ca pourrai etre sympa d'avoir une solution approximative, ( par exemple la premiere solution qui se rapproche de la moitié de la distance)  ou une premiere solution sans etre sure que cette solution est optimale
( a noter que ces deux algos sont bien sur tres basique, il y a moyen de faire des choses tres complexe avec le flou)

Pour l'utilisation de thread je laisse tomber, autant faire tourner la fonction globale du pathfinder dans un thread si besoin.

ah ca ? je pense aussi que ce n'est pas la bonne approche pour le pathfind , un pool de thread n'est interressant que si les thread sont succeptible d'attendre des évènements bloquants (remarque avec un dual core peut etre)

Jerry Kan :

[quote=izguit][quote=Jerry]de la logique floue ca pourrai etre super class, genre si on demande un résolution, le path find donne la derniere meilleure solution connue,

Pas encore regardé de ce côté là, je vois pas trop ce que tu veux dire par "la dernière meilleure solution connue"[/quote]
en gros l'idée c'est de lancer un pathfind dans un thread, et quand le temps critique est attein (le perso DOIT se déplacer) on demande au thread,
ca fait longtemps que j'ai plus touché le a*, mais il va trouver plusieurs solutions et les évaluer non ? imginons que quand on l'interroge, il en ai trouvé, mais qu'il n'ai pas TOUT trouvé,  ca pourrai etre sympa d'avoir une solution approximative, ( par exemple la premiere solution qui se rapproche de la moitié de la distance)  ou une premiere solution sans etre sure que cette solution est optimale
( a noter que ces deux algos sont bien sur tres basique, il y a moyen de faire des choses tres complexe avec le flou)[/quote]
A* fait pas ça, il trouve une des solutions possibles, ca privilégie le temps de calcul. Il faudrait un autre algo type dijkstra pour trouver la meilleure, mais on perd tout l'intérêt de la rapidité. Et puis j'en ai lancé des graphes avec A* et j'ai jamais remarqué une solution vraiment meilleure que celle qu'il me proposait. (c'est surement arrivé mais c'était pas évident) Donc au bout du temps critique tu fait avancer ton perso dans la direction du noeud d'arrivée en attendant que le pathfinder renvoie la chemin, je crois que c'est comme ça dans les AoE, C&C & Co

Pour les threads...  vu la structure de l'algo ça sert vraiment pas à grand chose