[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
), 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!
j'avions point vu!)
)pour les listes chaînées est efficace!