2d path finder... sort way? need help :D

[zefiro_flashparty]

:roll: hi need help to make a path finder, to find the best way to sort object ....,

condicion... mmm the player see all map , need only walk the way if it exist...

i use a array 2d to make the map
Dim choka (600,600)
xchoka.b:ychoka.b:

1 = wall = #
0 = nothings


example...


------------------------------------------------------------------
point P to X
% is the way
# is the wall

P%%%%%%
# # # #% # #
#######% ####
### % ####
### ## % ####
######%% ####
#### %%######
%%%%%
%# ####
%######
%%X####


i make a other array to add --> directions to free spaces , but only in paper =P

ani idea?

[zefiro_flashparty]

madmax say me this link

http://theory.stanford.edu/~amitp/GameP ... stics.html

use the A* algorithm

[zefiro_flashparty]

http://www.policyalmanac.org/games/aStarTutorial.htm

[Comtois]

http://www.games-creators.org/wiki/Sour ... Finding.pb

[sec]

viewtopic.php?t=11149&highlight=
Find a path from a node u to v in graph...

[zefiro_flashparty]

this is an example , a good example but i dont know how make it =P is hard to #%###$""##"# discover

; ***********************************************************
; ** Comtois le 15/08/03 - Pathfinding pour Purebasic V0.2 **
; ***********************************************************
;Rapidement retouché le 24/01/05

; **********************************************************************
; ************************** Mode d'emploi *****************************
; **********************************************************************
; ** Touche [F1] pour Afficher les cases Closed / Open **
; ** Touche [F2] pour Afficher le chemin **
; ** Bouton Gauche de la souris ajoute un mur **
; ** Bouton Droit de la souris efface un mur **
; ** Bouton Gauche de la souris + la Touche [Shift] Déplace la cible **
; ** Bouton Droit de la souris + la touche [Shift] Déplace le départ **
; **********************************************************************


; --- Initialisation ---
If InitSprite() = 0 Or InitKeyboard() = 0 Or InitMouse() = 0
MessageRequester("Erreur", "Impossible d'initialiser DirectX 7 Ou plus", 0)
End
EndIf

; --- Plein écran ---
#ScreenWidth = 800
#ScreenHeight = 600
#ScreenDepth = 16
If OpenScreen(#ScreenWidth,#ScreenHeight,#ScreenDepth,"Essai Pathfinding") = 0
MessageRequester("Erreur", "Impossible d'ouvrir l'écran ", 0)
End
EndIf
; --- Variables globales ---
Global ciblex,cibley,departx,departy, AffOpenClosed,affPath
affPath=1

; --- dimension du tableau et taille d'une case ---
#max_x=48
#max_y=48
#taille=12
; --- positionne la cible sur la grille ---
ciblex=1+Random(#max_x-2)
cibley=1+Random(#max_y-2)

; --- positionne le départ sur la grille ---
departx=1+Random(#max_x-2)
departy=1+Random(#max_y-2)

; --- pour la recherche du chemin ---
Dim map(#max_x,#max_y)
Dim open(#max_x+1,#max_y+1)
Dim parent(#max_x,#max_y,1)
Dim F(#max_x,#max_y)
Dim G(#max_x,#max_y)
Dim H(#max_x,#max_y)
Dim closed(#max_x+1,#max_y+1)
Dim path(#max_x*#max_y,1)

; ************************************************************************************
; *** LES SPRITES ***
; ************************************************************************************
Enumeration
#depart
#cible
#Souris
EndEnumeration

;/Départ
CreateSprite(#depart, #taille, #taille)
StartDrawing(SpriteOutput(#depart))
Circle(#taille/2,#taille/2,(#taille/2),RGB(255,255,255))
StopDrawing()
;/Cible
CreateSprite(#cible, #taille, #taille)
StartDrawing(SpriteOutput(#cible))
Circle(#taille/2,#taille/2,(#taille/2),RGB(255,55,18))
StopDrawing()
;/ Souris
CreateSprite(#Souris, #taille, #taille)
StartDrawing(SpriteOutput(#Souris))
DrawingMode(4)
Box(1,1,#taille-1,#taille-1,RGB(100,200,255))
StopDrawing()

; ************************************************************************************
; *** LES PROCEDURES ***
; ************************************************************************************
Procedure mur()
Couleur=RGB(100,100,255)
StartDrawing(ScreenOutput())
For y=0 To #max_y
For x=0 To #max_x
If map(x,y)
xa=x*#taille
ya=y*#taille
Box(xa + 1,ya + 1,#taille - 1,#taille - 1,Couleur)
EndIf
Next x
Next y
StopDrawing()
EndProcedure
Procedure init()
path(0,0) = 0
;faire le point sur ce qui est vraiment utile d'initialiser
For a = 0 To #max_x
For b = 0 To #max_y
open(a,b) = 0
parent(a,b,0) = 0
F(a,b) = 0
G(a,b) = 0
H(a,b) = 0
closed(a,b) = 0
Next b
Next a
EndProcedure

Procedure.w ChercheChemin()
; C'est mon interprétation du fameux A*
init()
If departx=ciblex And departy=cibley
fin=2
EndIf
; --- on met le point de départ dans la liste open ---
open(departx,departy)=1
; --- calcul F = G + H pour la Case de départ ---
F(departx,departy)=-1
; --- tant que la liste open n'est pas vide et tant qu'on a pas trouvé la cible
While fin = 0
; --- on cherche la Case la plus avantageuse ( avec F le plus bas) ===
meilleurF = 0
For a = 0 To #max_x
For b = 0 To #max_y
; --- si la Case est open ---
If open(a,b) = 1 And closed(a,b) = 0 And (F(a,b) < meilleurF Or meilleurF = 0)
meilleurF = F(a,b)
x = a
y = b
EndIf
Next b
Next a
; --- il n'y a pas de chemin ---
If meilleurF = 0
fin = 2
EndIf
; --- on met la Case trouvée dans la liste closed
closed(x,y) = 1
; --- on teste les cases autour si fin = 0 ===
; dans cette version le déplacement se fait dans les huits directions
; il est possible d'ajouter un paramètre pour limiter les déplacements à 4 directions
If fin = 0
For a = x - 1 To x + 1
For b = y - 1 To y + 1
; ---- si la Case est libre et n'a pas encore été traitée
If a >= 0 And a <= #max_x And b >= 0 And b <= #max_y
If map(a,b) = 0 And closed(a,b) = 0
interdit = 0
If a=x-1 And b=y-1 And map(x,y-1)=1 And map(x-1,y)=1 : interdit=1 : EndIf
If a=x-1 And b=y+1 And map(x,y+1)=1 And map(x-1,y)=1 : interdit=1 : EndIf
If a=x+1 And b=y-1 And map(x,y-1)=1 And map(x+1,y)=1 : interdit=1 : EndIf
If a=x+1 And b=y+1 And map(x,y+1)=1 And map(x+1,y)=1 : interdit=1 : EndIf
If interdit = 0
; calcule G pour la Case en cours de test ( à adapter selon le jeu)
; si la distance n'a pas d'importance , on peut se contenter de calculer
; le nombre de cases , donc de faire G = G(x,y) + 1
If Abs(a - x) > 0 And Abs(b - y) > 0
G = 14 + G(x,y)
Else
G = 10 + G(x,y)
EndIf
; si la Case n'est pas dans la liste open
If open(a,b) = 0 Or G < G(a,b)
open(a,b) = 1
parent(a,b,0) = x
parent(a,b,1) = y
; --- calcule F = G + H
G(a,b) = G
distance = (Abs(ciblex-a) + Abs(cibley-b))*10
H(a,b) = distance
F(a,b) = G(a,b) + H(a,b)
; --- la cible est trouvée ---
If a = ciblex And b = cibley
fin = 1
Break 2
EndIf
EndIf
EndIf
EndIf
EndIf
Next b
Next a
EndIf
Wend
ProcedureReturn fin
EndProcedure
Procedure souris(ToucheShift)
If ExamineMouse()
SX = MouseX() / #taille
SY = MouseY() / #taille
If SX >= 0 And SX <= #max_x And SY >= 0 And SY <= #max_y
If ToucheShift = 0
If MouseButton(1)
map(SX,SY)=1 ;place un mur
ElseIf MouseButton(2)
map(SX,SY)=0 ; supprime un Mur
EndIf
Else
If MouseButton(1)
ciblex = SX : cibley = SY ; place la cible
ElseIf MouseButton(2)
departx = SX : departy = SY ; place le départ
EndIf
EndIf
EndIf
EndIf
EndProcedure
Procedure AffOpenClosed()
CoulOpen=RGB(200,255,200)
CoulClosed=RGB(255,200,200)
StartDrawing(ScreenOutput())
For y=0 To #max_y
For x=0 To #max_x
xa=x*#taille
ya=y*#taille
If closed(x,y)
Box(xa + 1,ya + 1,#taille - 1,#taille - 1,CoulClosed)
ElseIf open(x,y)
Box(xa + 1,ya + 1,#taille - 1,#taille - 1,CoulOpen)
EndIf
Next x
Next y
StopDrawing()
EndProcedure
Procedure affPath()
If ChercheChemin()=1
a=-1
b=-1
cx=ciblex
cy=cibley
Couleur=RGB(255,255,100)
StartDrawing(ScreenOutput())
While a <> departx Or b <> departy
a = parent(cx,cy,0)
b = parent(cx,cy,1)
xa=(cx*#taille)+#taille/2
ya=(cy*#taille)+#taille/2
xb=(a*#taille)+#taille/2
yb=(b*#taille)+#taille/2
LineXY(xa,ya,xb,yb,Couleur)
cx = a
cy = b
Wend
StopDrawing()
EndIf
EndProcedure
Procedure AffCadre()
Couleur=RGB(255,255,255)
StartDrawing(ScreenOutput())
DrawingMode(4)
Box(0,0,#taille*(#max_x+1),#taille*(#max_y+1),Couleur)
StopDrawing()
EndProcedure
; ************************************************************************************
; *** BOUCLE PRINCIPALE ***
; ************************************************************************************
Repeat
ClearScreen(0,0,0)
;/ état du clavier
If ExamineKeyboard()
If KeyboardReleased(#PB_Key_F1)
AffOpenClosed=1-AffOpenClosed
EndIf
If KeyboardReleased(#PB_Key_F2)
affPath=1-affPath
EndIf
ToucheShift = KeyboardPushed(#PB_Key_LeftShift) Or KeyboardPushed(#PB_Key_RightShift)
EndIf
;/ Gestion de la souris
souris(ToucheShift)
;/affiche le fond
mur()
AffCadre()
If AffOpenClosed
AffOpenClosed()
EndIf
;/Lance la recherche
If affPath
affPath()
EndIf
;/Affiche les sprites
DisplayTransparentSprite(#Souris,MouseX() - #taille / 2,MouseY() - #taille / 2)
DisplayTransparentSprite(#cible,ciblex * #taille,cibley * #taille)
DisplayTransparentSprite(#depart,departx * #taille,departy * #taille)
FlipBuffers()
Until KeyboardPushed(#PB_Key_Escape)
End

[Psychophanta]

Comtois and sec, should be good if you explain the algorithm used

[Comtois]

Comtois and sec, should be good if you explain the algorithm used

I use this tutorial

http://www.policyalmanac.org/games/aStarTutorial.htm

I can explain in french , not sur it will help

Sorry , i know only few words in english

[Psychophanta]

I use this tutorial

http://www.policyalmanac.org/games/aStarTutorial.htm

I can explain in french , not sur it will help

Oh! thanx! don't worry, with that link is enough