Re: Pathfinding dans jeu d'aventure Point'n Click 2D
Publié : lun. 27/janv./2020 22:22
Courage 
Code : Tout sélectionner
;
;AdventurePathfinding
;
;http://www.groebelsloot.com/2015/12/24/pathfinding-part-1/
;http://www.groebelsloot.com/2016/03/13/pathfinding-part-2/
;
;Haxe Source : https://github.com/MicUurloon/AdventurePathfinding
;
;LUA Source : https://github.com/To-mos/love2d-pathfinding-polygon
;https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape/
;https://github.com/bladecoder/bladecoder-adventure-engine
;-Vector
DeclareModule vector
Declare new(*v.point,x.l,y.l)
Declare set(*from.point,*target.point)
Declare.s toString(*v.point)
Declare add(*vResult.point,*v1.point, *v2.point )
Declare diff(*vResult.point,*v1.point, *v2.point )
Declare.l dist(*v1.point, *v2.point )
Declare.l length(*v.point)
Declare normalized(*vResult.point,*v.point)
EndDeclareModule
Module vector
EnableExplicit
Procedure new(*v.point,x.l,y.l)
*v\x=x
*v\y=y
EndProcedure
Procedure set(*from.point,*target.point)
*target\x=*from\x
*target\y=*from\y
EndProcedure
Procedure.s toString(*v.point)
ProcedureReturn "<"+Str(*v\x)+", "+Str(*v\y)+">"
EndProcedure
Procedure add(*vResult.point,*v1.point, *v2.point )
*vResult\x=*v1\x+*v2\x
*vResult\y=*v1\y+*v2\y
EndProcedure
Procedure diff(*vResult.point,*v1.point, *v2.point )
*vResult\x=*v2\x-*v1\x
*vResult\y=*v2\y+*v1\y
EndProcedure
Procedure.l dist(*v1.point, *v2.point )
Protected vResult.point
vResult\x=*v2\x-*v1\x
vResult\y=*v2\y-*v1\y
ProcedureReturn length(@vResult)
EndProcedure
Procedure.l length(*v.point)
ProcedureReturn Sqr(*v\x * *v\x + *v\y * *v\y)
EndProcedure
Procedure normalized(*vResult.point,*v.point)
Protected len.l = length(@*v)
*vResult\x = *v\x / len
*vResult\y = *v\y / len
EndProcedure
EndModule
;-PathFinding
DeclareModule Pathfinding
Declare dijkstra(Array graph(2),List walkPath.i(), srcIndex.i,destIndex.i)
EndDeclareModule
Module Pathfinding
#M=999999 ; Infinity
Procedure dijkstra(Array graph.l(2),List walkPath.l(), srcIndex.i,destIndex.i)
Protected Nb.l=ArraySize(graph(),1)
; Démarrer et arrêter le nœud
; Distances par rapport au nœud de départ
Dim Distance(Nb - 1)
; Prédécesseur du nœud
Dim Predecessor(Nb - 1)
; Noeuds où vous connaissez déjà le chemin le plus court
Dim Mark(Nb-1)
For z = 0 To Nb - 1
Mark(z) = #False
Next
; Nœud de départ déjà visité!
Mark(srcIndex) = #True
; Distance par rapport à vous-même = 0
Distance(srcIndex) = 0
; Prédécesseurs d'eux-mêmes
Predecessor(srcIndex) = srcIndex
; Définissez les distances et les prédécesseurs pour tous les autres nœuds.
For z = 0 To Nb - 1
; ausser srcIndexnoten (s.o.)
If z <> srcIndex
Distance(z) = Graph(srcIndex, z)
Predecessor(z) = srcIndex
EndIf
Next
; Tant que le plus court Chemin vers le noeud cible est introuvable
While Mark(destIndex) = #False
; Trouvez la distance la plus courte pour les nœuds qui ne sont pas marqués
MinK = -1
MinD = #M
For z = 0 To Nb - 1
; Si non marqué
If Mark(z) = #False
; sidistance plus courte
If Distance(z) < MinD
MinK = z
MinD = Distance(z)
EndIf
EndIf
Next
; Si aucun plus court n'a été trouvé (ie distance = infini) -> aucun chemin disponible
If MinD = #M
Debug "Il n'y a pas de connexion entre srcIndex et destIndex"
Break
ElseIf MinK = destIndex
; Dle plus court trouvé
Debug "Walk Path Found"
Break
Else
; Marquez-le, donc un moyen le plus court a été trouvé
Mark(MinK) = #True
EndIf
; Pour tous les nœuds non marqués: vérifiez s'il existe un chemin plus court via MinK
For z = 0 To Nb - 1
If Mark(z) = #False
; Si le détour par MinK est plus court que l'itinéraire direct
If Distance(MinK) + Graph(MinK, z) < Distance(z)
; Calculer la nouvelle longueur de chemin
Distance(z) = Distance(MinK) + Graph(MinK, z)
; Enregistrez le détour à 'z'
Predecessor(z) = MinK
EndIf
EndIf
Next
Wend
If MinK = destIndex
ClearList(walkPath())
; Retracer le chemin depuis le destIndex
s.s = Str(destIndex)
z = MinK
AddElement(walkPath())
walkPath()=destIndex
While Predecessor(z) <> srcIndex
FirstElement(walkPath())
InsertElement(walkPath())
walkPath()=Predecessor(z)
s = ">"+Str(Predecessor(z)) + ", " + s
z = Predecessor(z)
Wend
FirstElement(walkPath())
InsertElement(walkPath())
walkPath()=Predecessor(z)
s = Str(Predecessor(z)) + ", " + s
Debug "Distance: " + Str(Distance(destIndex))
EndIf
ForEach walkPath()
Debug ">"+walkPath()
Next
EndProcedure
EndModule
;-Polygon
DeclareModule polygon
Structure Polygon
List Polygon.point()
EndStructure
Declare addPoint(List polygon.point(), x.l, y.l )
Declare.f distanceBetwenPoint(x1, y1, x2, y2)
Declare pointInside( *p.point,List polygon.point())
Declare.f distanceToSegment(Px.l, Py.l, x1.l, y1.l, x2.l, y2.l)
Declare getClosestPointOnEdge(*resultV.point,*p3.point,List polygon.point() )
Declare.b inLineOfSight(*p1.point, *p2.point,List Polygon.point(),obstacle.b=#False)
Declare.b inLineOfSightGlobal(*p1.point, *p2.point,List walkArea.Polygon())
Declare drawPoly(List polygon.point(),lineColor=#White,pointColor=#White)
Declare walkInit(List walkArea.Polygon(),*Start.point,*Target.point,drawWalkPath.b=#True)
EndDeclareModule
Module polygon
EnableExplicit
;UseModule vector
Procedure addPoint(List polygon.point(), x.l, y.l )
AddElement(polygon())
polygon()\x=x*2
polygon()\y=y*2-400
EndProcedure
Procedure.f distanceBetwenPoint(x1, y1, x2, y2)
ProcedureReturn Sqr((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
EndProcedure
Procedure pointInside( *p.point,List polygon.point())
Protected cn.l = 0 ;the crossing number counter
Define pa.point, pb.point
; loop through all edges of the polygon
Protected i.l
For i=0 To ListSize(polygon())-1 ; edge from V[i] To V[i+1]
SelectElement(polygon(),i)
pa\x=polygon()\x
pa\y=polygon()\y
;si on arrive a la fin de la liste on prend comme point i+1 le premier point
If i=ListSize(polygon())-1
SelectElement(polygon(),0)
Else
SelectElement(polygon(),i+1)
EndIf
pb\x=polygon()\x
pb\y=polygon()\y
If (((pa\y <= *P\y) And (pb\y > *P\y)) Or ((pa\y > *P\y) And (pb\y <= *P\y))) ; an upward crossing Or // a downward crossing
; compute the actual edge-ray intersect x-coordinate
Protected vt.f
vt= (*P\y - pa\y) / (pb\y - pa\y);
If (*P\x < pa\x + vt * (pb\x - pa\x)) ; *P\x < intersect
cn+1 ; ; a valid crossing of y=*P\y right of *P\x
EndIf
EndIf
Next
ProcedureReturn (cn&1); // 0 if even (out), and 1 if odd (in)
EndProcedure
Procedure.f distanceToSegment(Px.l, Py.l, x1.l, y1.l, x2.l, y2.l)
Define.f Ratio, Dx, Dy, Result
If x1 = x2 And y1 = y2
Result = distanceBetwenPoint(Px, Py, x1, y1)
Else
Dx = x2 - x1
Dy = y2 - y1
Ratio = ((Px - x1) * Dx + (Py - y1) * Dy) / (Dx * Dx + Dy * Dy)
If Ratio < 0
Result = distanceBetwenPoint(Px, Py, x1, y1)
ElseIf Ratio > 1
Result = distanceBetwenPoint(Px, Py, x2, y2)
Else
Result = distanceBetwenPoint(Px, Py, (1 - Ratio) * x1 + Ratio * x2, (1 - Ratio) * y1 + Ratio * y2)
EndIf
EndIf
ProcedureReturn Result
; If Result > -#Epsilon And Result < #Epsilon
; ProcedureReturn 1
; Else
; ProcedureReturn 0
; EndIf
EndProcedure
Procedure getClosestPointOnEdge(*resultV.point,*p3.point,List polygon.point() )
Protected tx.f = *p3\x
Protected ty.f = *p3\y
Protected vi1 = -1
Protected vi2 = -1
Protected mindist.f = 100000
Protected.l ia,ib
For ia=0 To ListSize(polygon())-1
Protected.point va,vb
SelectElement(polygon(),ia)
va\x=polygon()\x
va\y=polygon()\y
If ia=ListSize(polygon())-1
ib=0
Else
ib=ia+1
EndIf
SelectElement(polygon(),ib)
vb\x=polygon()\x
vb\y=polygon()\y
Protected dist.l = distanceToSegment(tx, ty, va\x, va\y, vb\x, vb\y)
If dist< mindist
mindist = dist
vi1 =ia
vi2 =ib
EndIf
Next
Protected.f x1,x2,x3,y1,y2,y3
SelectElement(polygon(),vi1)
x1 = polygon()\x
y1 = polygon()\y
SelectElement(polygon(),vi2)
x2 = polygon()\x
y2 = polygon()\y
x3 = *p3\x
y3 = *p3\y
Protected u.f = (((x3 - x1) * (x2 - x1)) + ((y3 - y1) * (y2 - y1))) / (((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1)))
Protected xu.f = x1 + u * (x2 - x1)
Protected yu.f = y1 + u * (y2 - y1)
If u < 0
vector::new(*resultV,x1, y1)
ElseIf u > 1
vector::new(*resultV,x2, y2)
Else
vector::new(*resultV,xu, yu)
EndIf
EndProcedure
Procedure isVertexConcave(List Polygon.point(), Index.i)
Protected.i nextIndex,prevIndex
Protected.f currentX,currentY
SelectElement(Polygon(),Index)
currentX = Polygon()\x
currentY = Polygon()\y
Protected.f nextX,nextY
nextIndex=Index+1
If nextIndex>ListSize(Polygon())-1:nextIndex=0:EndIf
SelectElement(Polygon(),nextIndex)
nextX = Polygon()\x
nextY = Polygon()\y
Protected.f previousX,previousY
prevIndex=Index-1
If prevIndex<0:prevIndex=ListSize(Polygon())-1:EndIf
SelectElement(Polygon(),prevIndex)
previousX = Polygon()\x
previousY = Polygon()\y
;Debug Str(prevIndex)+" "+Str(Index)+" "+Str(nextIndex)
Protected.f leftX,leftY,rightX,rightY,cross
leftX = currentX - previousX;
leftY = currentY - previousY;
rightX = nextX - currentX ;
rightY = nextY - currentY ;
cross = (leftX * rightY) - (leftY * rightX)
;Debug "cross :"+StrF(cross)+" ="+Str(Bool(cross < 0))
ProcedureReturn Bool(cross < 0)
EndProcedure
Procedure LineSegmentsCross(*A.point,*B.point, *C.point, *D.point)
Protected.f denominator,numerator1,numerator2,r,s
denominator = ((*B\x - *A\x) * (*D\y - *C\y)) - ((*B\y - *A\y) * (*D\x - *C\x));
If denominator = 0
ProcedureReturn #False
EndIf
numerator1 = ((*A\y - *C\y) * (*D\x - *C\x)) - ((*A\x - *C\x) * (*D\y - *C\y));
numerator2 = ((*A\y - *C\y) * (*B\x- *A\x)) - ((*A\x - *C\x) * (*B\y - *A\y));
If numerator1 = 0 Or numerator2 = 0
ProcedureReturn #False
EndIf
r = numerator1 / denominator
s = numerator2 / denominator
ProcedureReturn Bool((Bool(r > 0) And Bool(r < 1)) And (Bool(s > 0) And Bool(s < 1)))
EndProcedure
Procedure Max(A, B)
If A > B
ProcedureReturn A
EndIf
ProcedureReturn B
EndProcedure
Procedure Min(A, B)
If A < B
ProcedureReturn A
EndIf
ProcedureReturn B
EndProcedure
Procedure nearestSegment(*P.point,List polygon.point(),distMax=5)
Protected pa.point
Protected pb.point
Protected segment.l=-1
Protected minDist.l=4096
Protected i.l
For i=0 To ListSize(polygon())-1
SelectElement(polygon(),i)
pa\x=polygon()\x
pa\y=polygon()\y
;si on arrive a la fin de la liste on prend comme point i+1 le premier point
If i=ListSize(polygon())-1
SelectElement(polygon(),0)
Else
SelectElement(polygon(),i+1)
EndIf
pb\x=polygon()\x
pb\y=polygon()\y
Protected dist.l
dist=distanceToSegment(*P\x,*P\y,pa\x, pa\y, pb\x, pb\y)
If dist<=distMax And dist<minDist
segment=ListIndex(polygon())
Debug "Trouve Segment:"+Str(segment)
minDist=dist
EndIf
Next
ProcedureReturn segment
EndProcedure
Procedure LineIntersection(*L1PA.point,*L1PB.point,*L2PA.point,*L2PB.point, *Cross.point)
Protected.l A1,B1,C1,A2,B2,C2
A1 = *L1PB\y - *L1PA\y
B1 = *L1PA\x - *L1PB\x
C1 = A1 * *L1PA\x + B1 * *L1PA\y
A2 = *L2PB\y - *L2PA\y
B2 = *L2PA\x - *L2PB\x
C2 = A2 * *L2PA\x + B2 * *L2PA\y
Protected det.d = A1*B2 - A2*B1
If det = 0
ProcedureReturn 0 ; No intersection
Else
*cross\x = (B2*C1 - B1*C2)/det
*Cross\y = (A1*C2 - A2*C1)/det
; On *L1 line segment?
If Min(*L1PA\x, *L1PB\x) <= *cross\x And Max(*L1PA\x, *L1PB\x) >= *cross\x
If Min(*L1PA\y, *L1PB\y) <= *cross\y And Max(*L1PA\y, *L1PB\y) >= *cross\y
; On *L2 line segment?
If Min(*L2PA\x, *L2PB\x) <= *cross\x And Max(*L2PA\x, *L2PB\x) >= *cross\x
If Min(*L2PA\y, *L2PB\y) <= *cross\y And Max(*L2PA\y, *L2PB\y) >= *cross\y
ProcedureReturn 1
EndIf
EndIf
EndIf
EndIf
ProcedureReturn 2 ; Lines intersect, but line segments do not
EndIf
EndProcedure
Procedure.b inLineOfSightA(*p1.point, *p2.point,List Polygon.point())
Protected epsilon.f = 0.5 ;
;Not in LOS If any of the ends is outside the polygon
If Not pointInside(*p1,Polygon()) Or Not pointInside(*p2,Polygon())
ProcedureReturn #False
EndIf
;In LOS If it's the same start and end location
; If ( Vector . Subtract ( start , End ) . length & lt ; epsilon ) {
; Return false ;
; }
;Not in LOS If any edge is intersected by the start-End line segment
Protected inSight.b=#True ;
;For ( polygon in polygons ) {
Protected.l i,ni
For i=0 To ListSize(Polygon())-1
SelectElement(Polygon(),i)
Protected.point v1,v2
vector::set(@Polygon(),@v1)
ni=i+1:If ni>ListSize(Polygon())-1:ni=0:EndIf
SelectElement(Polygon(),ni)
vector::set(@Polygon(),@v2)
If LineSegmentsCross ( *p1 , *p2 , @v1 , @v2 )
;In some cases a 'snapped' endpoint is just a little over the line due To rounding errors. So a 0.5 margin is used To tackle those cases.
If polygon::distanceToSegment( *p1\x , *p1\y , v1\x , v1\y , v2\x , v2\y ) > 0.5 And polygon::distanceToSegment ( *p2\x , *p2\y , v1\x , v1\y , v2\x , v2\y ) > 0.5
ProcedureReturn #False ;
EndIf
EndIf
Next
;}
;Finally the middle point in the segment determines If in LOS Or Not
vector::add(@v1,*p1,*p2)
vector::new(@v2,v1\x/2,v1\y/2)
Protected inside.b = polygon::pointInside(@v2,Polygon())
;For ( i in 1...polygons.length ) {
;If ( polygons [ i ] . pointInside ( v2 , false ) ) {
; inside = #False ;
;EndIf
;Next
ProcedureReturn inside ;
EndProcedure
Procedure.b inLineOfSight(*p1.point, *p2.point,List Polygon.point(),obstacle.b=#False)
Protected.point tmp,tmp2,c,d,tmp3
vector::set(*p1,@tmp)
vector::set(*p2,@tmp2)
Protected.l i,ni
For i=0 To ListSize(Polygon())-1
SelectElement(Polygon(),i)
vector::set(@Polygon(),@c)
ni=i+1:If ni>ListSize(Polygon())-1:ni=0:EndIf
SelectElement(Polygon(),ni)
vector::set(@Polygon(),@d)
If (*p1\x=c\x And *p1\y=c\y And *p2\x=d\x And *p2\y=d\y) Or (*p1\x=d\x And *p1\y=d\y And *p2\x=c\x And *p2\y=c\y)
ProcedureReturn #True
EndIf
If LineSegmentsCross(@tmp,@tmp2, @c, @d)
If polygon::distanceToSegment( tmp\x , tmp\y , c\x , c\y , d\x , d\y ) > 0.5 And polygon::distanceToSegment ( tmp2\x , tmp2\y , c\x , c\y , d\x , d\y ) > 0.5
ProcedureReturn #False ;
EndIf
EndIf
Next
vector::add(@tmp3,@tmp,@tmp2)
tmp3\x=tmp3\x/2
tmp3\y=tmp3\y/2
Protected result.b = PointInside(@tmp3,polygon());
If obstacle=#True
result=1-result
EndIf
ProcedureReturn result
EndProcedure
Procedure.b inLineOfSightGlobal(*p1.point, *p2.point,List walkArea.Polygon())
Protected.b result,obstacle=#False
ForEach walkArea()
If ListIndex(walkArea())>0
obstacle=#True
EndIf
result.b=inLineOfSight(*p1, *p2,walkArea()\Polygon(),obstacle)
If result=#False:Break:EndIf
Next
ProcedureReturn result
EndProcedure
Procedure drawPoly(List polygon.point(),lineColor=#White,pointColor=#White)
Protected pa.point
Protected pb.point
Protected dist.l
Protected i.l
For i=0 To ListSize(polygon())-1
SelectElement(polygon(),i)
pa\x=polygon()\x
pa\y=polygon()\y
;si on arrive a la fin de la liste on prend comme point i+1 le premier point
If i=ListSize(polygon())-1
SelectElement(polygon(),0)
Else
SelectElement(polygon(),i+1)
EndIf
pb\x=polygon()\x
pb\y=polygon()\y
LineXY(pa\x,pa\y,pb\x,pb\y,lineColor)
Circle(pa\x,pa\y,5,pointColor)
;DrawText(pa\x+10,pa\y+10,Str(i),pointColor)
Next
EndProcedure
Procedure drawWalkPath(Array graph.l(2),List walkPointCoord.point())
Protected pa.point
Protected pb.point
Protected.l i,j,Nb=ArraySize(graph(),1)
For i=0 To Nb-1
For j=0 To Nb-1
If graph(i,j)<>0 And graph(i,j)<>999999
SelectElement(walkPointCoord(),i)
pa\x=walkPointCoord()\x
pa\y=walkPointCoord()\y
SelectElement(walkPointCoord(),j)
pb\x=walkPointCoord()\x
pb\y=walkPointCoord()\y
LineXY(pa\x,pa\y,pb\x,pb\y,#Green)
Circle(pa\x,pa\y,5,#Yellow)
Circle(pb\x,pb\y,5,#Yellow)
EndIf
Next
Next
EndProcedure
Procedure drawShortestPath(List walkPointCoord.point(),List walkPointIndex.l())
;Draw Walk
Protected.l Ax,Ay,Bx,By,n
For n=0 To ListSize(walkPointIndex())-1
SelectElement(walkPointIndex(),n)
SelectElement(walkPointCoord(),walkPointIndex())
Ax.l=walkPointCoord()\x
Ay.l=walkPointCoord()\y
If SelectElement(walkPointIndex(),n+1)
SelectElement(walkPointCoord(),walkPointIndex())
Bx.l=walkPointCoord()\x
By.l=walkPointCoord()\y
Circle(Ax,Ay,5,#Yellow)
LineXY(Ax,Ay,Bx,By,RGB(255,255,255))
Circle(Bx,By,5,#Yellow)
EndIf
Next
EndProcedure
Procedure walkInit(List walkArea.Polygon(),*Start.point,*Target.point,drawWalkPath.b=#True)
Protected pa.point
Protected pb.point
Protected.l dist,i
Protected p.point
NewList walkPointCoord.Point() ; List with only walkable point
NewList walkPointIndex.l() ;Sort wakable point with shortest path
;-Id Target out walk area
Protected.b result
ForEach walkArea()
;SelectElement(walkArea(),0)
result=pointInside(*Target,walkArea()\Polygon())
If ListIndex(walkArea())=0
result=1-result
EndIf
If result=#True
If *Target\x>0 And *Target\y>0
getClosestPointOnEdge(@p,*Target,walkArea()\Polygon()) ;get Closest Point on Edge
*Target\x=p\x
*Target\y=p\y
EndIf
EndIf
Next
;Add point to list with only walkable point
;Add Start Point
AddElement(walkPointCoord())
walkPointCoord()\x=*Start\x
walkPointCoord()\y=*Start\y
;Add Target Point
AddElement(walkPointCoord())
walkPointCoord()\x=*Target\x
walkPointCoord()\y=*Target\y
;If not in line of Sight we must to found the path
If Not inLineOfSightGlobal(*Start, *Target,walkArea());inLineOfSight(*Start, *Target,walkArea()\Polygon())
;Select all point to found the way
;SelectElement(walkArea(),0)
ForEach(walkArea())
For i=0 To ListSize(walkArea()\Polygon())-1
SelectElement(walkArea()\Polygon(),i)
pa\x=walkArea()\Polygon()\x
pa\y=walkArea()\Polygon()\y
If ListIndex(walkArea())=0
; Add only concave point
If IsVertexConcave(walkArea()\Polygon(),i)=#True
AddElement(walkPointCoord())
walkPointCoord()\x=pa\x
walkPointCoord()\y=pa\y
EndIf
Else
; Add only convex point
If IsVertexConcave(walkArea()\Polygon(),i)=#False
AddElement(walkPointCoord())
walkPointCoord()\x=pa\x
walkPointCoord()\y=pa\y
EndIf
EndIf
Next
Next
;generate Graph
Dim Graph.l(ListSize(walkPointCoord()),ListSize(walkPointCoord()))
For i=0 To ListSize(walkPointCoord())-1
SelectElement(walkPointCoord(),i)
pa\x=walkPointCoord()\x
pa\y=walkPointCoord()\y
Protected j.l
For j=0 To ListSize(walkPointCoord())-1
If i<>j
SelectElement(walkPointCoord(),j)
pb\x=walkPointCoord()\x
pb\y=walkPointCoord()\y
; (i>2 And j>2 : because Point 0 is Start and 1 target
; And (j=i+1 Or i=j+1)) : because in polygon previous and next point are always connected
; Or inLineOfSightB(@pa, @pb,polygon()) : if Points are in line of sight
If inLineOfSightGlobal(@pa, @pb,walkArea())
Graph(i,j)=distanceBetwenPoint(pa\x,pa\y,pb\x,pb\y)
Else ; Points are not connected to do walkpath
Graph(i,j)=999999
EndIf
Else ; it's the same point
Graph(i,j)=0
EndIf
Next
Next
Pathfinding::dijkstra(Graph(),walkPointIndex(),0,1)
;In line of Sight it's easy, start to target directly
Else
AddElement(walkPointIndex())
walkPointIndex()=0
AddElement(walkPointIndex())
walkPointIndex()=1
EndIf
If drawWalkPath=#True
;drawWalkPath(Graph(),walkPointCoord())
drawShortestPath(walkPointCoord(),walkPointIndex())
EndIf
EndProcedure
EndModule
;-Test
Structure room
List walkArea.Polygon::Polygon()
EndStructure
Structure chara
coord.point
target.point
List walkPointCoord.Point() ; List with only walkable point
List walkPointIndex.l() ; Sort wakable point with shortest path
EndStructure
Define mainChara.chara
mainChara\coord\x=63
mainChara\coord\y=290
Define room.room
AddElement (room\walkArea())
polygon::addpoint(room\walkArea()\Polygon(),5,248)
polygon::addpoint(room\walkArea()\Polygon(),5,248)
polygon::addpoint(room\walkArea()\Polygon(),235,248)
polygon::addpoint(room\walkArea()\Polygon(),252,277)
polygon::addpoint(room\walkArea()\Polygon(),214,283)
polygon::addpoint(room\walkArea()\Polygon(),217,300)
polygon::addpoint(room\walkArea()\Polygon(),235,319)
polygon::addpoint(room\walkArea()\Polygon(),265,339)
polygon::addpoint(room\walkArea()\Polygon(),275,352)
polygon::addpoint(room\walkArea()\Polygon(),310,350)
polygon::addpoint(room\walkArea()\Polygon(),309,312)
polygon::addpoint(room\walkArea()\Polygon(),322,308)
polygon::addpoint(room\walkArea()\Polygon(),304,279)
polygon::addpoint(room\walkArea()\Polygon(),307,249)
polygon::addpoint(room\walkArea()\Polygon(),419,248)
polygon::addpoint(room\walkArea()\Polygon(),431,262)
polygon::addpoint(room\walkArea()\Polygon(),389,274)
polygon::addpoint(room\walkArea()\Polygon(),378,295)
polygon::addpoint(room\walkArea()\Polygon(),408,311)
polygon::addpoint(room\walkArea()\Polygon(),397,316)
polygon::addpoint(room\walkArea()\Polygon(),378,309)
polygon::addpoint(room\walkArea()\Polygon(),365,323)
polygon::addpoint(room\walkArea()\Polygon(),342,360)
polygon::addpoint(room\walkArea()\Polygon(),358,379)
polygon::addpoint(room\walkArea()\Polygon(),205,379)
polygon::addpoint(room\walkArea()\Polygon(),206,338)
polygon::addpoint(room\walkArea()\Polygon(),212,320)
polygon::addpoint(room\walkArea()\Polygon(),198,316)
polygon::addpoint(room\walkArea()\Polygon(),162,298)
polygon::addpoint(room\walkArea()\Polygon(),119,305)
polygon::addpoint(room\walkArea()\Polygon(),99,338)
polygon::addpoint(room\walkArea()\Polygon(),91,362)
polygon::addpoint(room\walkArea()\Polygon(),79,372)
polygon::addpoint(room\walkArea()\Polygon(),90,380)
polygon::addpoint(room\walkArea()\Polygon(),4, 379)
AddElement (room\walkArea())
polygon::addpoint(room\walkArea()\Polygon(),120,280)
polygon::addpoint(room\walkArea()\Polygon(),120,260)
polygon::addpoint(room\walkArea()\Polygon(),140,260)
polygon::addpoint(room\walkArea()\Polygon(),140,280)
AddElement (room\walkArea())
For z=0 To 360 Step 36
Debug Str(120+10*Cos(Radian(z)))+","+Str(200+10*Sin(Radian(z)))
polygon::addpoint(room\walkArea()\Polygon(),60+20*Cos(Radian(z)),300+20*Sin(Radian(z)))
Next
If InitSprite()
If InitKeyboard() And InitMouse()
Define winMain.i = OpenWindow(#PB_Any,0,0,1024,800,"Press [Esc] to close",#PB_Window_ScreenCentered | #PB_Window_SystemMenu)
OpenWindowedScreen(WindowID(winMain), 0, 0,1024,800, 1, 0, 0)
EndIf
Else
MessageRequester("","Unable to initsprite") :
EndIf
Define EventID.l,mode.b,result.l
Repeat
Delay(1)
EventID = WindowEvent()
ExamineKeyboard()
;ExamineMouse()
ClearScreen(0)
StartDrawing(ScreenOutput())
mainChara\target\x=WindowMouseX(winMain)
mainChara\target\y=WindowMouseY(winMain)
ForEach room\walkArea()
Define.point target
If ListIndex(room\walkArea())=0
color=RGB(0,0,255)
Else
color=RGB(100,100,255)
EndIf
polygon::drawPoly(room\walkArea()\Polygon(),color)
;ForEach polyMap()\Polygon()
; Debug "no"
; EndIf
;Next
Next
polygon::walkInit(room\walkArea(),@mainChara\coord,@mainChara\target,#True)
Circle(mainChara\target\x,mainChara\target\y,5,#Blue)
Circle(mainChara\Coord\x,mainChara\Coord\y,5,#Red)
StopDrawing()
FlipBuffers()
Until KeyboardReleased(#PB_Key_Escape) Or EventID = #PB_Event_CloseWindow
ok 
Alors la bravo Thyphoon,
ça fonctionne a merveille. Merci du partage et d'avoir montrer tes avancées a travers ce post.
) j'ai beaucoup appris et j'ai réussi...