PureBasic

C'est un brouillon mais ça peut servir

[EDIT] pour A* avec tri par tas voir page 2 [EDIT]
Pour ne pas être influencé, je n'ai pas regardé les autres algos sur le forum(Qui a déjà travaillé dessus? Comtois(c'est là que j'ai eu l'adresse du tuto, merci!), Lionel_OM, Thyphoon...?Ca m'interesse de connaître les problèmes rencontrés!). Quand le mien sera plus avancé, je regarderai ailleurs

(désolé pour tous les sprites PNG(16*16 et 64*64 noir et blanc, j'arrangerai ça dans les prochaines versions )
Les listes chaînées font tout le travail(Merci Fred

), c'est pour cela que la procédure "pathfinding" est relativement simple et courte!

je n'ai pas mis de conditions sur le passage à proximité des murs mais j'ai déjà une fonction toute prête au cas où!
le programme ne trace pas de chemin si la case arrivée est inaccessible!
un petit aperçu:

le départ

la souris:

l'arrivée:

la "tuile" mur:

le décor:

Voilà le point de départ(je ne détaille pas trop car l'article est très complet!)
L'utilisation de l'équation F = G + H
i et j sont des variables itératives comprises entre -1 et +1
G = Gparent + 10+Abs(i*j)*4 (méthode Huitbit!

)
H =(Abs(x-#x_arrivee)+Abs(y-#y_arrivee))*10 (méthode de Manhattan)
Chaque case à son ID=j*x_max+i
on retrouve les coordonnées avec x=ID%x_max et y=int(ID/x_max)
J'ai utilisé la fonction de tri des listes châinées
(quand on veut chercher un autre chemin(cad plusieurs points de départ pour une même arrivée, il vaut vider la liste_ouverte et nettoyer une partie du tableau map(x,y) à chaque fois qu'un chemin est trouvé)

Récapitulatif de la méthode A*
Maintenant que nous avons effectué la totalité de nos explications, faisons un petit récapitulatif étape par étape :
1. Ajouter le point de départ à la "liste ouverte"
2. Répéter les instructions suivantes :
a. Cherche la case ayant le coût F le plus faible dans la "liste ouverte". Elle devient la case en cours.
b. Passer la case en cours de la "liste ouverte" à la "liste fermée"
c. Pour les 8 case adjacentes à la case en cours
 Si on ne peut pas la traverser, on l'ignore.
 Si elle n'est pas dans la "liste ouverte", on l'y ajoute. La case en cours devient le parent de cette case. On calcule les coûts F, G et H de cette case.
 Si elle est déjà dans la "liste ouverte", on teste si le chemin passant par la case en cours est meilleur en comparant les coûts G. Un coût G inférieur signifie un meilleur chemin. Si c'est le cas, on change le parent de la case pour devenir la case en cours, en on recalcule les coûts F et G. Si vous conservez une "liste ouverte" triée par coût F, la liste doit être retriée à ce moment la.
d. On s'arrête quand
 La case de destination est ajoutée à la "liste fermée"
 Vous ne trouvez pas la case de destination et la "liste ouverte" est vide.
3. Enregistrez le chemin. En partant de la case de destination, remontez d'un case à son parent jusqu'à atteindre la case de départ. Vous avez votre chemin !

Code : Tout sélectionner

;essai algorithme A* 
;ECHAP ou click droit pour quitter 
;auteur Huitbit 
;utilisation de l'article "Pathfinding A* pour les débutants 
Enumeration 
  #spr_ecran 
  #spr_decor 
  #spr_mur 
  #spr_depart 
  #spr_arrivee 
  #spr_souris 
  #list_open 
  #list_closed 
  #list_mur 
  #list_chemin 
EndEnumeration 

Structure infos 
  mur.b 
  id.w 
  parent.w 
  f.w 
  g.w 
  h.w 
  list.b 
EndStructure 

Structure liste 
  id.w 
  f.w 
EndStructure 

#x_max=64 
#y_max=64 
#x_depart=8 
#y_depart=10 
#x_arrivee=54 
#y_arrivee=56 

Global Dim map.infos(#x_max-1,#y_max-1) 
Global NewList liste_ouverte.liste() 

;dessin de la carte******************************** 
Procedure.b initialisation() 
  CreateSprite(#spr_ecran,1280,1024) 
  ;traitement de l'image decor 
  StartDrawing(SpriteOutput(#spr_decor)) 
  For j=0 To 63 
    For i=0 To 63 
      If Red(Point(i,j))=0 
        map(i,j)\mur=1 
        map(i,j)\list=#list_mur 
      EndIf 
    Next i 
  Next j 
  StopDrawing() 
  ;grille 
  StartDrawing(SpriteOutput(#spr_ecran)) 
  For j=1 To 62 
    For i=1 To 62 
      Line(16,j*16,62*16,0,RGB(100,100,100)) 
      Line(16*i,16,0,62*16,RGB(100,100,100))      
    Next i 
  Next j 
  StopDrawing() 
  ;affichage des murs, départ et arrivée 
  UseBuffer(#spr_ecran) 
  For j=0 To 63 
    For i=0 To 63 
      If  map(i,j)\mur=1 
        DisplaySprite(#spr_mur,i*16,j*16) 
      EndIf 
    Next i 
  Next j 
  DisplaySprite(#spr_depart,#x_depart*16,#y_depart*16) 
  DisplaySprite(#spr_arrivee,#x_arrivee*16,#y_arrivee*16) 
  UseBuffer(-1) 
  ;ID des cases 
  For j=0 To 63 
    For i=0 To 63 
      map(i,j)\id=k    
      k+1      
    Next i 
  Next j 
EndProcedure 

;calcul deH************** 
Procedure.w manhattan(x.b,y.b) 
  resultat_manhattan.w=(Abs(x-#x_arrivee)+Abs(y-#y_arrivee))*10 
  ProcedureReturn resultat_manhattan 
EndProcedure 
;recherche du chemin******************************* 
Procedure .w pathfinding(x.b,y.b) 
  
  ;étape n°1 ajout de la case de départ à la liste ouverte 
  AddElement(liste_ouverte()) 
  liste_ouverte()\id=map(x,y)\id 
  liste_ouverte()\f=manhattan(x,y) 
  map(x,y)\list=#list_open 
  
  ;étape n°2 boucle de recherche 
  Repeat 
    
    ;étape n°2.a choix case en cours  
    x_temp.b=liste_ouverte()\id%#x_max 
    y_temp.b=Int(liste_ouverte()\id/#x_max) 
    
    ;étape n°2.b passage de la case en cours à la liste fermée 
    map(x_temp,y_temp)\list=#list_closed 
    DeleteElement(liste_ouverte()) 
    
    ;étape n°2.c  exploration des huit cases adjacentes 
    For i= -1 To 1 
      For j=-1 To 1 
        If map(x_temp+i,y_temp+j)\list=0 
          map(x_temp+i,y_temp+j)\parent=map(x_temp,y_temp)\id 
          map(x_temp+i,y_temp+j)\h=manhattan(x_temp+i,y_temp+j) 
          map(x_temp+i,y_temp+j)\g=map(x_temp,y_temp)\g+10+Abs(i*j)*4 
          map(x_temp+i,y_temp+j)\f=map(x_temp+i,y_temp+j)\h+map(x_temp+i,y_temp+j)\g 
          map(x_temp+i,y_temp+j)\list=#list_open 
          AddElement(liste_ouverte()) 
          liste_ouverte()\id=map(x_temp+i,y_temp+j)\id 
          liste_ouverte()\f=map(x_temp+i,y_temp+j)\f          
        ElseIf map(x_temp+i,y_temp+j)\list=#list_open 
          If map(x_temp+i,y_temp+j)\g > map(x_temp,y_temp)\g + 10+Abs(i*j)*4 
            map(x_temp+i,y_temp+j)\parent=map(x_temp,y_temp)\id 
            map(x_temp+i,y_temp+j)\h=manhattan(x_temp+i,y_temp+j) 
            map(x_temp+i,y_temp+j)\g=map(x_temp,y_temp)\g+10+Abs(i*j)*4 
            map(x_temp+i,y_temp+j)\f=map(x_temp+i,y_temp+j)\h+map(x_temp+i,y_temp+j)\g 
          EndIf  
        EndIf        
      Next j 
    Next i  

;tri de la liste ouverte
    SortStructuredList(liste_ouverte(),1,OffsetOf(liste\f),  #PB_Sort_Word) 
    
  Until     map(#x_arrivee,#y_arrivee)\list=#list_closed Or CountList(liste_ouverte())=0 
  
  ;3. enregistrement du chemin(cas où il y a un chemin) 
  x_parent.b=0 
  y_parent.b=0 
  If x_temp=#x_arrivee And y_temp=#y_arrivee 
    Repeat 
      map(x_temp,y_temp)\list=#list_chemin 
      x_parent=map(x_temp,y_temp)\parent%#x_max 
      y_parent=Int(map(x_temp,y_temp)\parent / #x_max) 
      x_temp=x_parent 
      y_temp=y_parent    
    Until  map(x_temp,y_temp)\parent=0  
  EndIf 
EndProcedure 

;programme principal*********************** 
InitSprite() 
InitKeyboard() 
InitMouse() 
OpenScreen(1280,1024,32,"algo_A*") 
UsePNGImageDecoder() 
LoadSprite(#spr_decor,"decor.png") 
LoadSprite(#spr_mur,"mur.png") 
LoadSprite(#spr_depart,"depart.png") 
LoadSprite(#spr_arrivee,"arrivee.png") 
LoadSprite(#spr_souris,"souris.png") 
initialisation() 
depart_chrono.f=ElapsedMilliseconds() 
pathfinding(#x_depart,#y_depart) 
duree_pathfinding.f=ElapsedMilliseconds() - depart_chrono 
Repeat 
  Delay(10) 
  x_souris.b=Int(MouseX()/16) 
  y_souris.b=Int(MouseY()/16) 
  DisplaySprite(#spr_ecran,0,0) 
  StartDrawing(ScreenOutput()) 
  DrawingMode(#PB_2DDrawing_Transparent) 
  FrontColor(RGB(255,255,255)) 
  DrawText(0,0,"F= "+Str( map(x_souris,y_souris)\f) +" >>>>>>>>>>>>>>>>>>>>>chemin trouvé en "+Str(duree_pathfinding)+" ms") 
  DrawText(0,16,"G= "+Str(map(x_souris,y_souris)\g)) 
  DrawText(0,32,"H= "+Str(map(x_souris,y_souris)\h)) 
  DrawText(0,48,"ID "+Str(map(x_souris,y_souris)\id)) 
  DrawText(0,64,"parent= "+Str(map(x_souris,y_souris)\parent)+" xp="+Str(map(x_souris,y_souris)\parent%#x_max)+" yp="+Str(Int(map(x_souris,y_souris)\parent / #x_max))) 
  Select map(x_souris,y_souris)\list 
    Case #list_closed 
      texte$="closed" 
    Case #list_open 
      texte$="open" 
    Case #list_mur 
      texte$="mur" 
    Case 0 
      texte$="##" 
  EndSelect 
  DrawText(0,80,"list= "+texte$) 
  For j=0 To #y_max-1 
    For i=0 To #x_max-1 
      Select map(i,j)\list 
        Case #list_closed 
          textebis$=" c" 
          FrontColor(RGB(0,0,255)) 
          DrawText(i*16,j*16,textebis$) 
        Case #list_open 
          textebis$=" o" 
          FrontColor(RGB(0,255,0)) 
          DrawText(i*16,j*16,textebis$) 
        Case #list_chemin 
          textebis$=" x"  
          FrontColor(RGB(255,0,0)) 
          DrawText(i*16,j*16,textebis$) 
      EndSelect 
      
    Next i 
  Next j 
  
  
  StopDrawing() 
  DisplayTransparentSprite(#spr_souris,16*Int(MouseX()/16)+8,16*Int(MouseY()/16)+8) 
  FlipBuffers() 
  ExamineKeyboard() 
  ExamineMouse() 
Until KeyboardPushed(#PB_Key_Escape) Or MouseButton(#PB_MouseButton_Right ) 
End

Pour un jeu (un jour j'espère

), je pense déclencher le pathfinding pour certains personnages et selon certaines conditions!
Certains personnages ont le droit d'être crétins et de faire n'importe quoi, non?
Dans "King's Valley II" de Konami, toutes les momies n'étaient pas aussi douées

Par contre j'ai du boulot avec les listes chaînées, c'est chaud

Hasta la vista!

Exelent !

Pour ma part, j'ai surtout repris le travail de comtois que j'ai modifié.
Un des premiers truc que j'ai fait c'est mettre le test de la map dans une autre procedure.
j'ai donc une procedure TestMap(X,Y) qui renvoie 0 si on peut passer et 1 si on ne peut pas. Pourquoi ?! tout simplement car selon le type de personnage, le chemin ne sera pas le même. Si c'est un homme il pourra ouvrir une porte donc ça ne pose pas de problème. si c'est un animal il ne pourra pas. Idem en fonction des elements.Si une porte est ouverte ça marche mais si la porte est verrouillé/soudé on ne passe pas.Et puis l'interêt c'est que la procedure TestMap(X,Y) est aussi utilisé pour d'autre recherche de chemin. Voir mon sujet http://www.purebasic.fr/french/viewtopic.php?t=6422 ou là le but est de s'eloigné d'un certain nombre de danger là aussi j'ai besoin de tester les cases au tour de moi et je réutilise cette procedure.

je suis en train aussi de mettre en place une mémoire pour les persos. C'est a dire que si un personnage a un chemin qui passe part une porte si il arrive devant la porte et qu'elle est bloqué alors hop il rajoute dans sa mémoire les coordonées de la case. donc TestMap(X,Y) renverra un 1 au test de cette case. Sauf si on ne trouve pas de chemin alors il efface de sa mémoire et retestera la porte (au cas où).

Mon jeu étant basé sur les films Alien/Aliens/etc... je me sert du Pathfinding pour les Oeufs. En effet ces oeuf s'ouvre lorsqu'il y a une présence pas trop loin d'eux. Ainsi j'ai rajouté (merci comtois) des limites a ma recherche et je teste le chemin pour tout personnage se trouvant dans le secteur tout les 2000ms. Donc si une porte est ouverte on peu le sentir, si elle est fermé on le sent pas. Le perso peux aussi être derrière une vitre et regardé l'oeuf sans que ce dernier ne le detecte. ça marche plutôt bien.

A oui sinon j'ai cherché une methode pour stocker le chemin de chaque personnage. Et pour l'instant ma fonction de pathfinding fait un allocatememory() je commence part mettre le resultate du chemin (1 chemin trouvé / 2 chemin le plus proche) ensuite le nombre de case utilisé pour le chemin pour les coordonnée de chaque case les une derrière les autres. Ainsi chaque perso a un pointeur et des que tu arrives sur une case tu deplaces le pointeur.

voilà et sinon j'ai prévu de rajouter un système de lissage des points trouvé part le pathfinding. Pas la technique des courbes de Beziers car les persos risquerait d'aller dans le décore mais celle de catmull-rom lisse sans sortir des cases.

voilà je sais pas si c'est ça que tu veux savoir (si je suis a côté de la plaque désolé). En tout cas bonne continuation, je suis ton travail de prêt !

@Thyphoon

voilà je sais pas si c'est ça que tu veux savoir (si je suis a côté de la plaque désolé)

Ben si!
Tout ce que j'ai lu sur le pathfinding, ça s'arrète souvent au tracé du chemin!
Il est très rare que les gens disent ce qu'ils en font!
J'ai lu un truc interessant sur vieartificielle.com sur quelqu'un qui avait travaillé sur un RTS commercial.
Actuellement, j'ai quelques idées pour mettre en mouvement les personnages sur les chemins mais ça reste très vague tout simplement parce que personne ne dit ce qu'il fait de son pathfinding.

Il y a des astuces pour déplacer les unités, en file indienne, en "flèche"...etc. Tout cela semble SECRET DEFENSE

Pas de problème, c'est le charme de l'informatique

A propos de ton jeu, tu vas faire des aliens super méchants à force (c'est vrai qu'ils le sont dans le film

)

Hasta la vista!

Huitbit a écrit :
Il y a des astuces pour déplacer les unités, en file indienne, en "flèche"...etc. Tout cela semble SECRET DEFENSE!

A oui j'ai oublié de te parler de ça ...
MOi aussi il se suivent. En verité a chaque fois que je dis a une personne d'en suivre une autre et bien il mémorise ça place je suis le 1er a la suivre, je suis le 2ème...Et lorsque je cherche le chemin pour aller jusqu'a lapersonne que je suis et bien je retire le nombre de case correspondant a sa place.
Exemple la personnes est le 3ème et bien je retire les 3 dernières cases du chemin

voilà l'astuce que j'utilise... Surtout si tu améliore ton pathfinding n'hesite pas...

Et oui mes aliens seront tres tres mechant !!

Dans la semaine qui vient je devrais poster une nouvelle "demo" qui n'est pas vraiment une demo car le jeu n'est pas finit mais plus pour montrer mon avancement.

Huitbit a écrit : Il est très rare que les gens disent ce qu'ils en font!
J'ai lu un truc interessant sur vieartificielle.com sur quelqu'un qui avait travaillé sur un RTS commercial.
Actuellement, j'ai quelques idées pour mettre en mouvement les personnages sur les chemins mais ça reste très vague tout simplement parce que personne ne dit ce qu'il fait de son pathfinding.

Il y a des astuces pour déplacer les unités, en file indienne, en "flèche"...etc. Tout cela semble SECRET DEFENSE

Parce qu'en fait tu titille un domaine bien précis que l'on appelle dans les
jeux l'IA (intelligence artificielle) et dans ce domaine, contrairement a pas
mal d'autre, on est pas encore trop pret a partager...
Regarde par exemple ici
http://www.pathengine.com

Pour un simple PathEngine, 4000€ pour la version de base...
Car si la PathEngine est le point de départ, derrière il y a tout ce qui touche
les algo décisionnels, comportements adaptatifs, etc...

Bref, la bonne nouvelle c'est que dans le monde amateur et libre tout (ou presque) reste a faire

@tmyke
Je ne soupçonnais pas tout ça!

Certains bienfaiteurs acceptent quand même de partager.

http://www.vieartificielle.com/article/ ... cle&id=178

Le pathfinding est ultra-rapide (au lieu de découper en petits carrés le décor, on choisit des zones biens précises qui vont servir de noeuds pour l'algorithme : bilan, il y a très peu de noeuds!).
Dans les 4 articles, il parle aussi des déplacements d'unités (celui de la queueleuleu à déjà été donné

Thyphoon)

[EDIT] j'ai rajouté la mesure du temps pris par la procedure "pathfinding" pour trouver le chemin.
Pour une ligne droite 0 ms(je crois que je vais aussi vite que lui sur le coup!

)
Pour l'exemple en haut entre 40 et 65 ms ça fait beaucoup mais sur l'image on comprend pourquoi(la recherche finit mieux qu'elle ne commence!)
Avec une carte aussi complexe mais où l'ordinateur trouve le chemin plus facilement entre 15 et 30 ms
Je pas trop de références avec une carte à explorer 64*64, mais ça à l'air correct non?
Si quelqu'un a déjà essayé avec un autre algorithme et une carte à explorer identique.
(j'ai un HP pavilion celeron D à 3,2 GHz avec 960 Mo de RAM)

@+

tu devrais pouvoir améliorer considérablement tes temps de calcul en utilisant un tas plutôt qu'un tri sur liste chaînées.

comtois a écrit :tu devrais pouvoir améliorer considérablement tes temps de calcul en utilisant un tas plutôt qu'un tri sur liste chaînées.

Oui c'est ce que tu as fait dans ta version ! J'ai vu ça

le pathfinding de comtois est tres efficace !:)

Huitbit a écrit : Certains bienfaiteurs acceptent quand même de partager.

http://www.vieartificielle.com

très bon lien en tous les cas

Il y a ce site aussi qui est très cool sur la vie artificielle et autre!
Sa page de liens est démente pour tous les automates cellulaires itou !
http://www.rennard.org/alife/french/liens.html

Apparemment un bon A* tourne avec un temps < 5ms (< 1ms pour les meilleurs!)
Avec ça, le pnj peut vérifier s'il doit pas passer chez Mère-Grand avant d'aller faire les courses et d'aller à la guerre

@Comtois
Merci pour le lien, je vais m'y mettre!
J'ai vu ton code sur le pathfinding, ça à l'air un peu chaud (ça doit être l'optimisation qui le rend moins accueillant!)
En tout cas ça marche nickel!
@tmyke
Le lien vieartificielle.com, Comtois l'a donné il y a deux ans (:oops:

j'avions point vu!)
@Frenchy Pilou
Interessant, je fouinerai un peu plus quand le tas m'aura livré ses secrets!

Hasta la vista!

Impressionant

, j'ai placé le tri de liste chaînée après le 2.c de l'algorithme(code modifié plus haut):
Je pense que j'avais mal interprété le texte:

 Si elle est déjà dans la "liste ouverte", on teste si le chemin passant par la case en cours est meilleur en comparant les coûts G. Un coût G inférieur signifie un meilleur chemin. Si c'est le cas, on change le parent de la case pour devenir la case en cours, en on recalcule les coûts F et G. Si vous conservez une "liste ouverte" triée par coût F, la liste doit être retriée à ce moment la.

et placé un tri inutile dans le 2.c

Maintenant, je reste entre 0 ms et 30 ms quelque soit la carte!

Quelques valeurs moyennes...
15 ms

0 ms

15 ms

Si avec les tas je descend systématiquement en dessous de 10 ms, ça sera encore mieux!

je ne sais pas si tu l'as déjà fait ou pas (je ne sais pas non plus si le code de comtois en utilise un) mais partout où on parle du A* on dit que pour améliorer les performances il faut aussi rajouter des fonctions d'heuristique !

Avec la pathfinding de comtois lorsque je l'utilise dans mon jeu je tourne a 0ms faut dire que plutôt que de laisser trouver un grand chemin en une seul fois.... je lui fais rechercher des petits chemin plus souvant...

Code : Tout sélectionner

 plutôt que de laisser trouver un grand chemin en une seul fois.... je lui fais rechercher des petits chemins plus souvent...

Quand tu fais du "drill" à l'armée, c'est la première chose qu'on t'apprend : "petits bonds, petit c.....!".
En plus, l'article sur vieartificielle.com le signalait, un pnj qui trouve le bon chemin tout de suite sur une grande carte c'est louche!

Grace au tuyau de Comtois (tri par tas), je compte améliorer mon programme.
C'est pour cela que pour l'instant je teste le programme avec des distances plus grandes que prévues!

En fait celui-là pourrait me suffire car les cartes que j'utilise (world of huibit) correspondent à celles qui donnent des temps inférieurs à 1 ms (îles, îlots de montagnes, châteaux fermés...)

En tout cas le tri de Fred ( d'ailleurs, c'est quel tri

)pour les listes chaînées est efficace!

H@sta la vista!

tient nous au courant si tu arrives a optimisé ton programme et a utilisé les tas. Comme je le disais dans le sujet du pathfinding de comtois, regarde son code pour les tas... peut être y comprendras tu plus facilement ! Bon courage

PureBasic

pathfinding A*, listes chaînées Vs tri par tas

pathfinding A*, listes chaînées Vs tri par tas

Pas d'IA pas de chocolat!

Re: Pas d'IA pas de chocolat!

"Tas" star!

tri placé correctement = gain de 40 ms!!!

Tout à fait Thyphoon...