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

[Huitbit]

J'ai répondu sur le post de Comtois!
Je vais essayer le tri par tas dès que mes neurones seront d'accord

@+

PS: le code n'est pas encore optimisé..., si vous avez des idées
J'ai déjà supprimé la structure H (intermédiaire de calcul)

[Huitbit]

J'ai repris le même programme mais avec le tri par tas.
La liste chaînée liste_ouverte() et remplacée par le tableau de même nom et de même structure

Cette fois-ci, il suffit d'avoir uniquement un sprite 64*64 noir et blanc pour faire le décor(voir posts précédents)

sprite "decor"



Super lien pour comprendre le tri par tas!
http://www.infres.enst.fr/~charon/SDA/index.html(C'est là que les choses sont devenues très claires!)
(aller à "polycopié sur les structures...et algorithmes de base")

La grosse difficulté (déjà rencontrée avec les listes chaînées) : passer la case en cours de la liste ouverte à la liste fermée.
Ici, j'ai "simplement" déplacé l'index de début de lecture du tableau.

Le code n'est pas du tout optimisé(ça viendra)
C'est exactement le même "squelette" que le code précédent(mais on perd un peu en clarté avec le tri par tas).
Par contre pour le temps de recherche , il n'y a aucune comparaison possible! 0ms, 0ms, 0ms,....



Ne faites pas comme moi, compilez sans déboggueur

Code : Tout sélectionner

;************************
;essai algorithme A* tri par tas 
;ECHAP ou click droit pour quitter 
;auteur Huitbit 
;utilisation de l'article "Pathfinding A* pour les débutants 
;gestion  du chemin le plus proche
;********************************
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 
  list.b 
EndStructure 

Structure liste 
  id.w 
  f.w 
EndStructure 

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

Global Dim map.infos(#x_max-1,#y_max-1) 
Global Dim liste_ouverte.liste((#x_max-1)*(#y_max-1)) 
Global     position_premier_element.w 
;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 

;construction du tas**************** 
Procedure.w ajout_dans_liste_ouverte(p.w) 
  k.w=p 
  f_a_placer.w =liste_ouverte(p)\f 
  id.w=liste_ouverte(p)\id 
  While k>=(position_premier_element+1)   And f_a_placer< liste_ouverte(Int(k*0.5))\f 
    liste_ouverte(k)\f=liste_ouverte(Int(k*0.5))\f 
    liste_ouverte(k)\id=liste_ouverte(Int(k*0.5))\id 
    
    k=Int(k*0.5) 
  Wend 
  liste_ouverte(k)\f=f_a_placer 
  liste_ouverte(k)\id=id 
  
EndProcedure 

;remaniement du tas après suppression de la racine************************ 
Procedure.w reformer_tas(p.w) 
  travail.b=0; 0 : en cours, 1 : effectué 
  k.w=position_premier_element 
  
  f_a_replacer.w= liste_ouverte(position_premier_element)\f 
  id.w=liste_ouverte(position_premier_element)\id 
  While travail=0 And 2*k<=p 
    If 2*k =p 
      indice_grand.w=p 
    Else 
      If liste_ouverte(2*k)\f<=liste_ouverte(2*k+1)\f 
        indice_grand=2*k 
      Else 
        indice_grand=2*k+1 
      EndIf 
    EndIf    
    
    If f_a_replacer>liste_ouverte(indice_grand)\f 
      liste_ouverte(k)\f=liste_ouverte(indice_grand)\f    
      liste_ouverte(k)\id=liste_ouverte(indice_grand)\id 
      k=indice_grand 
    Else 
      travail=1 
    EndIf 
  Wend 
  liste_ouverte(k)\f=f_a_replacer 
  liste_ouverte(k)\id=id  
EndProcedure 

  ;recherche du chemin******************************* 
Procedure .w pathfinding(x.b,y.b) 
  f_min.w=manhattan(x,y) 
  id_f_min.w=map(x,y)\id 
  
  ;étape n°1 ajout de la case de départ à la liste ouverte 
  liste_ouverte(1)\id=map(x,y)\id 
  liste_ouverte(1)\f=manhattan(x,y) 
  map(x,y)\list=#list_open 
  
  ;étape n°2 boucle de recherche 
  position.w=1 
  position_premier_element=1 
  
  Repeat 
    
    ;étape n°2.a choix case en cours   
    x_temp.b=liste_ouverte(position_premier_element)\id%#x_max 
    y_temp.b=Int(liste_ouverte(position_premier_element)\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 
    liste_ouverte(position_premier_element)\f=0        
    position_premier_element=position_premier_element+1    
    Swap liste_ouverte(position_premier_element)\f,liste_ouverte(position)\f 
    Swap liste_ouverte(position_premier_element)\id,liste_ouverte(position)\id 
    reformer_tas(position) 
    
    
    ;é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)\g=map(x_temp,y_temp)\g+10+Abs(i*j)*4 
          map(x_temp+i,y_temp+j)\f=manhattan(x_temp+i,y_temp+j)+map(x_temp+i,y_temp+j)\g 
          map(x_temp+i,y_temp+j)\list=#list_open 
          position=position+1 
          liste_ouverte(position)\f=map(x_temp+i,y_temp+j)\f 
          liste_ouverte(position)\id=map(x_temp+i,y_temp+j)\id 
          ajout_dans_liste_ouverte(position) 
        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)\g=map(x_temp,y_temp)\g+10+Abs(i*j)*4 
            map(x_temp+i,y_temp+j)\f=manhattan(x_temp+i,y_temp+j)+map(x_temp+i,y_temp+j)\g 
          EndIf  
        EndIf        
      Next j 
    Next i  
    ;sauvegarde du f_min de la carte au cas où il n'y ait pas de chemin possible
    If  map(x_temp,y_temp)\f<f_min And map(x_temp,y_temp)\f<>0
      f_min=map(x_temp,y_temp)\f
      id_f_min=map(x_temp,y_temp)\id   
      
    EndIf
  Until     map(#x_arrivee,#y_arrivee)\list=#list_closed Or liste_ouverte(position_premier_element)\f=0  
  
  ;3. enregistrement du chemin
  x_parent.b=0 
  y_parent.b=0 
  ;3.a. cas où il y a un chemin
  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  
  ;3.b. chemin le plus proche
  Else
    x_temp=id_f_min%#x_max
    y_temp=Int(id_f_min/#x_max)
    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() 
;****************carte à explorer***************************** 
LoadSprite(#spr_decor,"decor_7.png") 
;********************************************************************** 
;création des sprites**************** 
CreateSprite(#spr_mur,16,16) 
StartDrawing(SpriteOutput(#spr_mur)) 
Box(0,0,16,16,RGB(100,100,100)) 
StopDrawing() 

CreateSprite(#spr_depart,16,16) 
StartDrawing(SpriteOutput(#spr_depart)) 
Box(0,0,16,16,RGB(0,255,0)) 
StopDrawing() 

CreateSprite(#spr_arrivee,16,16) 
StartDrawing(SpriteOutput(#spr_arrivee)) 
Box(0,0,16,16,RGB(0,255,255)) 
StopDrawing() 

CreateSprite(#spr_souris,16,16) 
StartDrawing(SpriteOutput(#spr_souris)) 
Box(0,0,16,16,RGB(255,0,255)) 
Box(0,0,6,6,RGB(255,255,0)) 
StopDrawing() 

initialisation() 

;temps pris pour la recherche du chemin 
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(manhattan(x_souris,y_souris))) 
  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

Hasta la vista!

Merci à Thyphoon et Comtois pour leur contribution

PS reste plus qu'à optimiser!

[Huitbit]

(code modifé sur le post précédent)
sprite decor_7 (à charger)




Dans la situation où la case d'arrivée est inaccessible, j'ai choisi (arbitrairement) de mémoriser le plus petit F trouvé (rappel F=H+G et F= 0 quand on est à l'arrivée).

Donc deux nouvelles variables dans la procédure pathfinding ; au départ, à la fin de l'étape n° 2.c. et au niveau de l'étape n° 3 : f_min et id_f_min ( 7 ou 8 lignes de code en plus).

Il n'y a toujours pas d'optimisation (mais il y a toujours 0 ms au chrono vive le tri par tas )!

J'aurais pû faire un tri du tableau map() après la boucle de recherche "repeat -until", mais bon ça marche très bien comme ça (quand j'arrangerai le code j'essayerai!)
je testerai aussi avec des conditions sur G et H, peut-être que ça donne quelque chose!

@+

[Thyphoon]

Tres beau Travail !!

[Huitbit]

@Thyphoon
Merci! L'"objectif"est encore très loin mais j'ai tout mon temps!


Pour les sprites j'aimerais du "topview"
Exemple(jeu MSX2 Bastard)


Après retouche et passage à 16 couleurs:


Le problème c'est que c'est long à faire!
Je compte un jour faire mes personnages en 3D et mettre la caméra au dessus!
Facile à dire mais je suis plus à l'aise avec un crayon HB qu'avec une souris!

En attendant, je cherche des sprites qui me serviront pour des test!
Les Artistes de Nintendo sont impressionnants dans le maniement du pixel! (même avec du 8*8, ils arrivent à faire des trucs!!!)

Il y a un jeu que je compte essayer, c'est Gauntlet
(je vais chercher la version Atari car je crois me souvenir que c'était la meilleure!)
Je trouverai bien un émulateur!

Ci-dessous : sprites Gauntlet version Nintendo(source The shy guy's kingdom)


c'est ce genre de sprites que je cherche, mais c'est une denrée très rare!


Hasta la vista et joyeuses Pâques!

[Thyphoon]

@Thyphoon
Merci! L'"objectif"est encore très loin mais j'ai tout mon temps!


Pour les sprites j'aimerais du "topview"
Exemple(jeu MSX2 Bastard)

Après retouche et passage à 16 couleurs:


Le problème c'est que c'est long à faire!
Je compte un jour faire mes personnages en 3D et mettre la caméra au dessus!
Facile à dire mais je suis plus à l'aise avec un crayon HB qu'avec une souris!

En attendant, je cherche des sprites qui me serviront pour des test!
Les Artistes de Nintendo sont impressionnants dans le maniement du pixel! (même avec du 8*8, ils arrivent à faire des trucs!!!)

Il y a un jeu que je compte essayer, c'est Gauntlet
(je vais chercher la version Atari car je crois me souvenir que c'était la meilleure!)
Je trouverai bien un émulateur!

Ci-dessous : sprites Gauntlet version Nintendo(source The shy guy's kingdom)
c'est ce genre de sprites que je cherche, mais c'est une denrée très rare!


Hasta la vista et joyeuses Pâques!

Aaaaaaaa Gauntlet ! ça c'était du jeu ! J'ai fait les 255 premiers niveau sur Macintosh (on croyait que ça serait finit a 256 mais non....), j'y ai aussi beaucoup joué sur Amstrad ...mais la plus belle version reste l'original en Arcade. Pour trouver les sprites ça doit être possible en chechant sur le web. Si j'ai le temps je vais essayer de les retrouver, je crois que je les avaient vu une fois.

[comtois]

C'est de mieux en mieux , bravo , vivement le jeu

[Huitbit]

@Comtois
Merci! Pour le jeu, c'est pas pour tout de suite

En ce moment je fais mumuse avec MAME (un émulateur de borne d'arcade).
J'ai découvert (ou redécouvert certains jeux)
Heureusement que je dois pas mettre des "coins"!!!!!
Gaunlet, Goulsh'n ghosts.....

@+

[Thyphoon]

@Comtois
Merci! Pour le jeu, c'est pas pour tout de suite

En ce moment je fais mumuse avec MAME (un émulateur de borne d'arcade).
J'ai découvert (ou redécouvert certains jeux)
Heureusement que je dois pas mettre des "coins"!!!!!
Gaunlet, Goulsh'n ghosts.....

@+

Hé hé Mame... ça c'est un emulateur. j'ai une borne d'arcade chez moi qui tourne sous Mame ! Et un Frontend fait maison en Purebasic... )
Je te conseille d'essayé Toki ! Un des meilleurs jeux de plateau au monde....

[Huitbit]

J'ai plusieurs versions d'émulateurs, pour ceux qui marchent en DOS, je ne sais faire que glisser les roms. Très peu de roms fonctionnent(l'interface disparaît et rien ne se passe ).
Ceux qui ont une interface windows ne reconnaissent pas beaucoup de jeux(message d'erreur : fichiers xxxxxx manquants)
Pour l'instant Toki n'est pas accepté

Pour les saisies d'écran de Gaunlet, c'est pas pratique du tout

@+

[Ouaf-Ouaf]

Lut,

Recement j'ai decidé de passer le pavage de mes maps en hexagonal.. Avant, je calculais les chemins tres simplement, avec une algo de berschman , breschman, sbredchman.. enfin bref ... le mec là.

Quand la ligne rencontrait un obstacle, j'avais une fonction qui recuperrait les infos de l'obstacle (taille en x et y, pour savoir de quel coté contourner).. bref un truc pas genial.. mais bon...

En passant en hexa, j'me suis galeré à adapter Mister B à ce pavage, j'y ai passé une journée entière, n'etant pas d'esprit matheux. Et alors qu'il restait encore quelques bugs dans mon "algo".. J'suis tombé sur un article de Amit sur le pathfinding et A star..

En f'sant une recherche là dessus içi, j'suis tombé sur ce post comme adaptation la plus recente de A Star en PB.. Maaaais ... Je galère pour l'adapter à mon programme

Le truc c'est que X_temp et Y_temp se retrouvent parfois egal à la taille de mon array, c'qui a pour effet de faire planter le prog quand le test Map( x_temp+i, y_temp + J ) à lieu .. o.o

J'ai essayé de border ma map()\list de #list_mur et map()\mur de 1.. Ce qui a pour effet au moins doffrir un sursis au plantage o.o, le problème reste le même mais arrive moins vite.

Y a quelques chose que manifestement je comprends pas dans le principe et j'me dmandais si j'pouvais trouver de l'aide la dessus auprés de quelqu'un d'avisé

Sur ce je retourne à mes laborieuses recherches lol


Edit :

Le problème m'as l'air tout bête, en enlevant la bordure noire de "decor.bmp" on obtiens le même bug.. A priori donc j'peux regler l'prob...

Faut que je dissèque patiement le code de Mister Huitbit, c'est pas evident de comprendre le code des autres, surtout que l'auteur n'as pas l'air d'avoir besoin de beaucoup de mise en page pour s'y retrouver

[Huitbit]

Hello Ouaf-Ouaf,
Ce sujet date un peu...
J'ai toujours ce jeu comme gros objectif , en attendant j'explore le monde de Purebasic . En ce moment, je bosse pour rajouter un peu plus de physique dans mes programmes.

Un conseil, bosse sur le code avec les listes chaînées, il est plus parlant pour comprendre le principe.
N'hésite pas à aller sur les sites proposés tout au long du sujet!
Utilise le programme de Comtois pour comprendre le fonctionnement du A*!

Au fait...
J'ai utilisé le pathfinding dans un jeu ("dragon's fury" qui n'est pas fini , d'ailleurs, il y a deux bugs que je dois virer!) et dans plusieurs sujets dans la partie débutant !

Bon courage !

[Ouaf-Ouaf]

Hellow,

En faite j'ai eu la curiosité d'voir si l'algo avait été traitée en Pure aprés être tombé sur des articles là dessus, y me semble justement que tu t'es basé sur larticle que j'ai imprimé juste avant de faire ma recherche içi ^^

J'avais donc vaguement enregistré le principe du F,G,H, l histoire des parents et du chien aveugle abandoné à la naissance ( pardon j'ai pas pu m'empecher ), mais faudrait vraiment que je reconstitue ça etape par etape, par ce que là c'eeest esoterique x)

C'est vrais que cette histoire de paquet obscurcit un peu l'tout. Mais bon, j'vais decortiquay tout ça tranquillement.

J'ai fait toute une serie de tests aujourd'hui pour comprendre le comportement du prog sur ma map, donc ça avanceouille..

Utilise le programme de Comtois pour comprendre le fonctionnement du A*!

J'vais essayer de chopper ça =].
+ le tuto imprimé + un bon kawa ça devrait tripper =]

Bon courage !

Merci ^^, bonnes decouvertes de ton côté ! :p

[lionel_om]

Beau travail.

Nénmoins, tu ne toruve pas le meilleurs chemin on dirait: dans l'image en haut de la page 2, tu trouve un chemin, mais pas le meilleurs !!!

Après tout dépend de ce que tu veux: un calcul bcp plus rapide ou vraiment le meilleurs chemin.

Je n'ai pas lu tous les posts, donc dans le cas où tu en as déjà parlé: "désolé pour cette remarque inutile" !!!

/Lio