La première méthode (lecture de la valeur des cases du tableau) demandait trop de bidouillage dès qu'on prenait deux sprites, alors j'ai essayé une autre idée : la chaîne de caractères
Exemple de chaîne parcours: "id_arrivée|id_avantdernierpoint|...|...|id_2ièmepoint|id_départ".
Le Fmin pour le chemin le plus proche, ça marche pas toujours, faudra que j'arrange ça!
Code : Tout sélectionner
;essai "poursuite" avec algorithme A* tri par tas
;ECHAP ou click droit pour quitter
;click du gauche(en dehors des murs gris) pour lancer la course
;auteur Huitbit
;utilisation de l'article "Pathfinding A* pour les débutants
Enumeration
#spr_ecran
#spr_decor
#spr_mur
#spr_arrivee
#spr_depart
#spr_lutin_rouge
#spr_lutin_vert
#spr_lutin_bleu
#spr_lutin_orange
#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
Structure donnees
lutin.b
parcours.s
longueur_parcours.w
chercher_chemin.b
x1_lutin.b
y1_lutin.b
x2_lutin.b
y2_lutin.b
x.w
y.w
dx.b
dy.b
EndStructure
#x_max=64
#y_max=64
#x_depart_rouge=1
#y_depart_rouge=1
#x_depart_vert=62
#y_depart_vert=62
#x_depart_bleu=62
#y_depart_bleu=1
#x_depart_orange=1
#y_depart_orange=62
rouge.donnees
rouge\x1_lutin=#x_depart_rouge
rouge\y1_lutin=#y_depart_rouge
rouge\lutin=#spr_lutin_rouge
vert.donnees
vert\ x1_lutin=#x_depart_vert
vert\ y1_lutin=#y_depart_vert
vert\lutin=#spr_lutin_vert
bleu.donnees
bleu\x1_lutin=#x_depart_bleu
bleu\y1_lutin=#y_depart_bleu
bleu\lutin=#spr_lutin_bleu
orange.donnees
orange\x1_lutin=#x_depart_orange
orange\y1_lutin=#y_depart_orange
orange\lutin=#spr_lutin_orange
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 , x_arrivee.b, y_arrivee.b
;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()
;affichage des murs
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
;affichage des points de départ
DisplaySprite(#spr_depart,#x_depart_vert*16,#y_depart_vert*16)
DisplaySprite(#spr_depart,#x_depart_rouge*16,#y_depart_rouge*16)
DisplaySprite(#spr_depart,#x_depart_bleu*16,#y_depart_bleu*16)
DisplaySprite(#spr_depart,#x_depart_orange*16,#y_depart_orange*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 de H**************
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,*couleur.donnees)
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 sous la forme d'une chîne de caractères
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
*couleur\parcours=Str(map(x_temp,y_temp)\id)+"|"
Repeat
*couleur\parcours= *couleur\parcours+Str(map(x_temp,y_temp)\parent)+"|"
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(à perfectionner!)
Else
x_temp=id_f_min%#x_max
y_temp=Int(id_f_min/#x_max)
*couleur\parcours=Str(map(x_temp,y_temp)\id)+"|"
Repeat
*couleur\parcours= *couleur\parcours+Str(map(x_temp,y_temp)\parent)+"|"
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
*couleur\longueur_parcours= CountString(*couleur\parcours,"|")
EndProcedure
Procedure.w deplacement(*couleur.donnees)
If *couleur\chercher_chemin=1
If *couleur\longueur_parcours>1
*couleur\longueur_parcours= *couleur\longueur_parcours-1
EndIf
id_case.w=Val(StringField(*couleur\parcours, *couleur\longueur_parcours,"|"));lecture de la chaîne "parcours" en commençant par la fin
*couleur\chercher_chemin=0
;coordonnées de début de déplacement
*couleur\x=16**couleur\x1_lutin
*couleur\y=16**couleur\y1_lutin
;coordonnées de fin de déplacement
*couleur\x2_lutin=id_case%#x_max
*couleur\y2_lutin=Int(id_case/#x_max)
;informations sur la direction et la vitesse du déplacement
*couleur\dx=(*couleur\x2_lutin-*couleur\x1_lutin)*4
*couleur\dy=(*couleur\y2_lutin-*couleur\y1_lutin)*4
EndIf
*couleur\x=*couleur\x+*couleur\dx
*couleur\y=*couleur\y+*couleur\dy
DisplayTransparentSprite(*couleur\lutin, *couleur\x, *couleur\y)
If *couleur\x=16**couleur\x2_lutin And *couleur\y=16**couleur\y2_lutin
*couleur\chercher_chemin=1
*couleur\x1_lutin= *couleur\x2_lutin
*couleur\y1_lutin= *couleur\y2_lutin
EndIf
EndProcedure
;"nettoyage des matrices
Procedure.w preparer_pathfinding()
For j=0 To #y_max-1
For i=0 To #x_max-1
If map(i,j)\list<>#list_mur
map(i,j)\list=0
map(i,j)\f=0
map(i,j)\g=0
map(i,j)\parent=0
EndIf
Next i
Next j
For i=1 To (#x_max-1)*(#y_max-1)
liste_ouverte(i)\f=0
Next i
EndProcedure
;programme principal***********************
InitSprite()
InitKeyboard()
InitMouse()
OpenScreen(1280,1024,32,"algo_A*")
UsePNGImageDecoder()
;****************carte à explorer*****************************
LoadSprite(#spr_decor,"decor_8.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(255,255,0))
StopDrawing()
CreateSprite(#spr_arrivee,16,16)
StartDrawing(SpriteOutput(#spr_arrivee))
Circle(8,8,8,RGB(255,0,0))
Circle(8,8,6,RGB(255,255,255))
Circle(8,8,4,RGB(255,0,0))
Circle(8,8,2,RGB(255,255,255))
StopDrawing()
CreateSprite(#spr_lutin_vert,16,16)
StartDrawing(SpriteOutput(#spr_lutin_vert))
Circle(8,8,8,RGB(0,255,0))
StopDrawing()
CreateSprite(#spr_lutin_rouge,16,16)
StartDrawing(SpriteOutput(#spr_lutin_rouge))
Circle(8,8,8,RGB(255,0,0))
StopDrawing()
CreateSprite(#spr_lutin_bleu,16,16)
StartDrawing(SpriteOutput(#spr_lutin_bleu))
Circle(8,8,8,RGB(0,0,255))
StopDrawing()
CreateSprite(#spr_lutin_orange,16,16)
StartDrawing(SpriteOutput(#spr_lutin_orange))
Circle(8,8,8,RGB(255, 128, 0))
StopDrawing()
initialisation()
MouseLocate(512,512)
Repeat
Delay(1)
x_souris.b=Int(MouseX()/16)
y_souris.b=Int(MouseY()/16)
DisplaySprite(#spr_ecran,0,0)
deplacement(@rouge)
deplacement(@vert)
deplacement(@bleu)
deplacement(@orange)
DisplayTransparentSprite(#spr_arrivee,16*Int(MouseX()/16),16*Int(MouseY()/16))
FlipBuffers()
ExamineKeyboard()
ExamineMouse()
If MouseButton(#PB_MouseButton_Left )
x_arrivee=Int(MouseX()/16)
y_arrivee=Int(MouseY()/16)
preparer_pathfinding()
pathfinding(#x_depart_rouge,#y_depart_rouge,@rouge)
rouge\chercher_chemin=1
rouge\ x1_lutin=#x_depart_rouge
rouge\ y1_lutin=#y_depart_rouge
preparer_pathfinding()
pathfinding(#x_depart_vert,#y_depart_vert,@vert)
vert\chercher_chemin=1
vert\ x1_lutin=#x_depart_vert
vert\ y1_lutin=#y_depart_vert
preparer_pathfinding()
pathfinding(#x_depart_bleu,#y_depart_bleu,@bleu)
bleu\chercher_chemin=1
bleu\ x1_lutin=#x_depart_bleu
bleu\ y1_lutin=#y_depart_bleu
preparer_pathfinding()
pathfinding(#x_depart_orange,#y_depart_orange,@orange)
orange\chercher_chemin=1
orange\ x1_lutin=#x_depart_orange
orange\ y1_lutin=#y_depart_orange
EndIf
Until KeyboardPushed(#PB_Key_Escape) Or MouseButton(#PB_MouseButton_Right )
End