PATHFINDING SANS CASES A*( COMPARAISON DE TEMPS )

Signaler
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
-
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/32058-pathfinding-sans-cases-a-comparaison-de-temps

Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
Pardon de répondre aussi tardivement je travaillais loin de chez moi donc je n'ai pas vu le message :)
Il s'agit d'une version optimisé pour les jeux : elle donne un des chemins les plus court en un minimum de temps à savoir qu'avec toutes les version de A* sur le net il devient difficile de trouver le vrai A* le mieux est donc de l'adapter...
Pour résumé c'est donc une version simple , optimisé et perso :)
Messages postés
1536
Date d'inscription
samedi 21 décembre 2002
Statut
Membre
Dernière intervention
24 mai 2009
2
Par contre, une petite question : je trouve ton algo assez 'vide' en comparaison avec les tuts que j'ai pu lire sur le net. Est ce une version 'simple' ou au contraire 'optimisée' de A* ?
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
Merci mais en fait désolé, j'ai compris mon erreur depuis un moment : il ne faut en aucun cas delete à ce moment là puisque sinon après lors de la reconstruction du chemin ça pointera vers rien :/

On doit donc stocker dans une liste en plus les adresses de tous les noeuds créer afin de ne pas oublier d'en supprimer !
Messages postés
1536
Date d'inscription
samedi 21 décembre 2002
Statut
Membre
Dernière intervention
24 mai 2009
2
Je pense savoir pourquoi lors du delete actual;, ton prog plante : j'ai recodé ton algo, et chez moi aussi ca plante. Lorsque tu delete actual, neighbour->parent = actual; pointe vers une zone 'vide', désallouée, donc pouf ca plante :(
Je ne suis pas sur que cela soit ca, mais chez moi aussi, en l'enlevant, tout baigne :)
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
Oui il s'agit d'une méthode de procéder qui a ses avantages et inconvénients ( si il s'agit d'une unités ennemi qui ne bougera pas il aurait mieux valu faire le tour .
Ces méthodes d'optimisation sont propres au jeu et peuvent être cumulé par dizaine .
D'ailleurs dans un jeu il y a au moins 2 pathfinding qui dépendent de l'échelle !
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

Tiens, question: en pratique, si lors du parcours le mobile rencontre un obstacle dynamique (un PNJ, un OVNI ...), que fait-il? Il recalcule son chemin en tenant compte de lui? On en avait déjà causé "là bas" ^^ mais je pense que tu peux faire comme ça, et alors dans ton calcul de chemin tu ne considères comme obstacle que les objets dynamiques qui se trouvent à moins de x unités de toi. Ça te permet de ne pas faire de détour à cause d'une unité qui pourrait avoir bougé d'ici ton arrivée. En cas de collision avec cette unité, il suffit de recalculer le chemin: comme elle est tout près, elle sera prise en compte.
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
Afin de gagner en efficacité : on peut tenir à jour une table contenant la liste des voisins pour chaque point ( cette liste serait classé suivant les abscisses pour un accès rapide par dichotomie ) et il suffirait ensuite de revérifier tous les points accessibles au point qui est modifié et si la modification date de plus de x milliseconde ( on peut refaire un calcul avec le tableau datant de 100 ms dans certains jeu sans probleme )
Donc ici non le graphe n'est pas précalculé le temps tient compte de ca :)
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

Intéressant, j'ai causé de ce système pendant pas mal de cours de sciences avec Xurei (mon pote, si tu te souviens MoDDiB ;)).

Je me demande quand même si ça va pas poser de problème quand tu modifies le terrain... tu précalcules le graphe ou pas?
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7
C'est bon j'ai compris, c'est parce que je ne faisais pas le clic droit à la fin :)
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
Le calcul du centre ( barycentre ici ) ne permet que de déterminer les points de passages par les polygones a une distance x
En fait si tu connais bien : il s'agit de la recherche du plus court chemin :)
L'algo de recherche du plus court chemin est mis ici et le reste ce sont surtout des fonctions propres aux polygones qui représentent les obstacles !

Désolé je n'est pas été assez précis sur le fonctionnement propre du programme :
En gros :
- lors de la création du polygone ( obstable ) on dresse une liste des sommets
du polygone ( il s'agira des points de passages ) et des segments composant le sommet avec équation de droite
- Puis lors de la recherche du plus court chemin les points voisins sont ceux qui sont accessibles directement par ligne droite sans entrer en collisions avec une droite d'un polygone !

Cette méthode semble largement plus rapide que du case par case ( sans obstacle pour un terrain de 700*500 on a 0.01ms contre 45ms ) et surtout plus réaliste .
Je n'ai pas trouvé de tutoriaux concernant cette méthode ( enfin je n'ai pas énormément cherché ) mais j'avais vu un tutorial la dessus il y a 2-3ans il s'intulait : pathfinding pour jeux 3D

Dis moi encore si il y a des points d'ombres je me rends compte que j'ai bien expliqué chaque fonction mais pas la globalité :/
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7
Ca calcule quoi en fait? Le point tel que la moyenne des distances aux autres points est minimale, une sorte de barycentre? (j'y connais rien au pathfinding, je connaissais même pas le mot)
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
J'ai juste oublié de dire que si le polygone est concave ca ne fonctionnera pas très bien ( voire pas du tout :p )
Mais bon tout polygone concave peut se décomposer en polygones non concaves :)