Sujet Précédent Sujet Suivant

PATHFINDING SANS CASES A*( COMPARAISON DE TEMPS )

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 - 14 juin 2005 à 15:22
MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 - 30 août 2005 à 13:46

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

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 1
30 août 2005 à 13:46

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 :)

cs_AlexMAN Messages postés 1536 Date d'inscription samedi 21 décembre 2002 Statut Membre Dernière intervention 24 mai 2009 1
18 juil. 2005 à 21:06

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* ?

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 1
18 juil. 2005 à 20:44

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 !

cs_AlexMAN Messages postés 1536 Date d'inscription samedi 21 décembre 2002 Statut Membre Dernière intervention 24 mai 2009 1
18 juil. 2005 à 19:35

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 :)

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 1
15 juin 2005 à 11:00

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 !

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
15 juin 2005 à 09:17

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.

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 1
15 juin 2005 à 00:29

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 :)

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
14 juin 2005 à 20:27

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?

vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 14
14 juin 2005 à 17:28

C'est bon j'ai compris, c'est parce que je ne faisais pas le clic droit à la fin :)

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 1
14 juin 2005 à 16:39

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é :/

vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 14
14 juin 2005 à 16:07

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)

MoDDiB Messages postés 546 Date d'inscription mardi 26 novembre 2002 Statut Membre Dernière intervention 4 mai 2007 1
14 juin 2005 à 15:22

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 :)

Discussions similaires

comparaison date

imprimer une feuille excel directement de vb

comparer deux date dans une requete select simple

Comparer date('y-m-d') avec un champs DATETIME

Comparaison entre 2 date sur sql

Votre réponse

Discussions similaires