Pathfinding pour jeu Point'n Click 2D (ça fonctionne ^_^)

[Thyphoon]

J'ai découvert un article très intéressant pour faire un pathfinding pour un jeu d'aventure. Ayant commencé un moteur pour ce genre de jeu il y a quelques années je me suis dit que ça serait sympa a implémenter.

http://www.groebelsloot.com/2015/12/24/ ... ng-part-1/
http://www.groebelsloot.com/2016/03/13/ ... ng-part-2/

Après quelques galères ... voici le code qui fonctionne (il reste quelques imperfection) et le code est pas super propre...

Edit: Ajout PointInside()
Edit : Ajout de LineSegmentsCross()
Edit : Ajout InLineOfSight() et j'ai retiré plein d'erreur que j'avais laissé suite a des mauvais copier/coller
Edit : Ajout IsVertexConcave()
Edit : Quelques corrections du code ...
Edit : mise au propre du code ! IsVertexConcave() fonctionne maintenant parfaitement
Edit : debut de WalkInit()
Edit : quelques corrections... ça fonctionne déjà mieux...
Edit : Ajout du Pathfinding
Edit : Ajout du point le plus prêt de la zone de placement si le pointeur en sort
Edit : Ajout du contournement des obstacles
Edit : Correction dans la commande InLineOfSight() pour certain cas (quand le point d'arrivé est sur un segment la commande envoyait #False)

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 points are a polygon segment
      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 first point is start of polygon segment and second point is on the segment
      If (*p1\x=c\x And *p1\y=c\y And polygon::distanceToSegment ( *p2\x ,   *p2\y ,   c\x ,   c\y ,   d\x ,   d\y   )  < 3) Or (*p1\x=d\x And *p1\y=d\y And polygon::distanceToSegment ( *p2\x ,   *p2\y ,   c\x ,   c\y ,   d\x ,   d\y   )  < 3)
        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   And   polygon::distanceToSegment ( tmp2\x ,   tmp2\y ,   c\x ,   c\y ,   d\x ,   d\y   )  >   0
          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   

;AddElement (room\walkArea())
;polygon::addpoint(room\walkArea()\Polygon(),250,280)
;polygon::addpoint(room\walkArea()\Polygon(),250,460)
;polygon::addpoint(room\walkArea()\Polygon(),260,460)
;polygon::addpoint(room\walkArea()\Polygon(),260,280)


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

[Shadow]

Salut, je ne suis pas assez calé pour se genre de chose mais c'est intéressant se que tu fais
Faire un genre d'éditeur de pathfinding serais pas mal

[Micoute]

Les félicitations sont de rigueur, c'est du bon travail, j'aime bien.

[Thyphoon]

merci, j'avance doucement car je n'ai pas encore compris toute la logique mais j'y travaille

[Ar-S]

Très intéressant.
Merci pour ce partage.

[Thyphoon]

Très intéressant.
Merci pour ce partage.

Je trouve aussi
J'ai mis à jour le code... déjà le début fonctionne comme ça doit... reste a comprendre le reste ^_^

[Thyphoon]

ça avance ... mais je seche ...

il semble qu'il y ai un problème avec ma fonction inLineOfSight() qui permet de savoir si 2 point sont en ligne de vu directe ... sans être coupé par le polygon qui sert a délimité la zone de marche
je tourne sur ce problème depuis ce matin

[Thyphoon]

du mieux mais c'est pas encore ça... je ne sais pas pourquoi mais certain segment manque ... a creuser

[Marc56]

Désolé, je te lis aussi et j'admire , mais je ne suis bon ni en math ni en graphisme je programme comme un Shadock donc je ne peux pas t'aider là.

[MLD]

Marc56 programme comme un shadock
Donc il met le code de devant derrière, et celui de derrière devant, c'est ce qui lui permet d'avancer.

[Fig]

Je ne vois pas de problème particulier... Juste le chemin ne se calcule pas parce qu'il n'y a pas de code A* pour le pathfinding.

[venom]

Oula... C'est pointu ce que tu demande Thyphoon

Je n'ai pas eu le temps de me pencher sur ton code, mais je ne pense pas connaître la solution désolé.






@++

[Thyphoon]

c'est pas grave je continue a avancer... doucement ... là je bloque sur la pathfinding ...
https://www.purebasic.fr/french/viewtop ... =3&t=17908
une fois ça résolu je mettrai a jour le code ici ... on devrait avoir quelques choses qui commence a être utilisable...
Mais pour l'instant je galère

[Thyphoon]

Histoire de partager avec vous mes avancés...
La ligne rouge est le parcours le plus rapide...
Oui il y a des erreurs mais ce n'est pas du au Pathfinding mais avant a la commande inLineOfSight()
Le code est pas propre du tout... mais je ferais du nettoyage des que ça marchera ...

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(2),List walkPath.i(), 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
  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 inLineOfSightA(*p1.point, *p2.point,List Polygon.point())
  Declare.b inLineOfSightB(*p1.point, *p2.point,List Polygon.point(),obstacle.b=#False)
  Declare drawPoly(List polylist.point())
  Declare walkInit(List polylist.point(),*From.point,*Target.point)
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.l = *p3\x
    Protected ty.l = *p3\y
    Protected vi1 = -1
    Protected vi2 = -1
    Protected mindist = 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.l 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.i = (((x3 - x1) * (x2 - x1)) + ((y3 - y1) * (y2 - y1))) / (((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1)))
   
    Protected xu = x1 + u * (x2 - x1)
    Protected yu = 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.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 inLineOfSightB(*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 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 drawPoly(List polylist.point())
    Protected pa.point
    Protected pb.point
    Protected dist.l
    Protected i.l
    For i=0 To ListSize(polylist())-1
      SelectElement(polylist(),i)
      pa\x=polylist()\x
      pa\y=polylist()\y
      ;si on arrive a la fin de la liste on prend comme point i+1 le premier point
      If i=ListSize(polylist())-1
        SelectElement(polylist(),0)
      Else 
        SelectElement(polylist(),i+1)
      EndIf 
      pb\x=polylist()\x
      pb\y=polylist()\y
      LineXY(pa\x,pa\y,pb\x,pb\y,RGB(255,255,255))
      Circle(pa\x,pa\y,5,RGB(255,255,255))
      DrawText(pa\x+10,pa\y+10,Str(i))
     
    Next
   
  EndProcedure
 
  Procedure walkInit(List polylist.point(),*From.point,*Target.point)
    Protected pa.point
    Protected pb.point
    Protected.l  dist,i
    Protected baryCenter.point
    NewList walkpath.Point()
    ;Add Start Point
    AddElement(walkpath())
    walkpath()\x=*From\x
    walkpath()\y=*From\y
    ;Add Target Point
    AddElement(walkpath())
    walkpath()\x=*Target\x
    walkpath()\y=*Target\y   
    
    If inLineOfSightB(*From, *Target,polylist())
      LineXY(*From\x,*From\y,*Target\x,*Target\y,#Red )
    Else
     ;Select all point to found the way
    For i=0 To ListSize(polylist())-1
      SelectElement(polylist(),i)
      pa\x=polylist()\x
      pa\y=polylist()\y
      ;si on arrive a la fin de la liste on prend comme point i+1 le premier point
      If IsVertexConcave(polylist(), i)=#True
        Circle(pa\x,pa\y,10,RGB(255,0,0))
        AddElement(walkpath())
        walkpath()\x=pa\x
        walkpath()\y=pa\y
      EndIf
    Next
    Dim Graph(ListSize(walkpath()),ListSize(walkpath()))
    For i=0 To ListSize(walkpath())-1
      SelectElement(walkpath(),i)
      pa\x=walkpath()\x
      pa\y=walkpath()\y
      Protected j.l
      For j=0 To ListSize(walkpath())-1
        If i<>j
          SelectElement(walkpath(),j)
          pb\x=walkpath()\x
          pb\y=walkpath()\y
          If inLineOfSightB(@pa, @pb,polylist()) ;TODO ICI LE PROBLEME
            LineXY(pa\x,pa\y,pb\x,pb\y,#Green)
            Circle(pa\x,pa\y,5,#Green)
            Circle(pb\x,pb\y,5,#Green)
            Graph(i,j)=distanceBetwenPoint(pa\x,pa\y,pb\x,pb\y)
           
          Else
            Graph(i,j)=999999
            ;LineXY(pa\x,pa\y,pb\x,pb\y,#Blue)
           ; Circle(pa\x,pa\y,5,#Blue)
           ; Circle(pb\x,pb\y,5,#Blue)
          EndIf
        Else
          Graph(i,j)=0
        EndIf
      Next
      
     
    Next
    
    NewList walk()
    Pathfinding::dijkstra(Graph(),walk(),0,1)
    Protected.l n,Ax,Ay,Bx,By
      For n=0 To ListSize(walk())-1
        SelectElement(walk(),n)
        SelectElement(walkpath(),walk())
        Ax.l=walkpath()\x
        Ay.l=walkpath()\y
        If SelectElement(walk(),n+1)
          SelectElement(walkpath(),walk())
        Bx.l=walkpath()\x
        By.l=walkpath()\y
          LineXY(Ax,Ay,Bx,By,#Red)
        EndIf 
      Next
    
    
    EndIf
  EndProcedure
 
EndModule



;-Test

playerPos.point
playerPos\x=63
playerPos\y=290

Structure Polygon
  List Polygon.point()
EndStructure

NewList PolyMap.Polygon()
AddElement (polyMap())
polygon::addpoint(polyMap()\Polygon(),5,248)
polygon::addpoint(polyMap()\Polygon(),5,248)
polygon::addpoint(polyMap()\Polygon(),235,248)
polygon::addpoint(polyMap()\Polygon(),252,277)
polygon::addpoint(polyMap()\Polygon(),214,283)
polygon::addpoint(polyMap()\Polygon(),217,300)
polygon::addpoint(polyMap()\Polygon(),235,319)
polygon::addpoint(polyMap()\Polygon(),265,339)
polygon::addpoint(polyMap()\Polygon(),275,352)
polygon::addpoint(polyMap()\Polygon(),310,353)
polygon::addpoint(polyMap()\Polygon(),309,312)
polygon::addpoint(polyMap()\Polygon(),322,308)
polygon::addpoint(polyMap()\Polygon(),304,279)
polygon::addpoint(polyMap()\Polygon(),307,249)
polygon::addpoint(polyMap()\Polygon(),419,248)
polygon::addpoint(polyMap()\Polygon(),431,262)
polygon::addpoint(polyMap()\Polygon(),389,274)
polygon::addpoint(polyMap()\Polygon(),378,295)
polygon::addpoint(polyMap()\Polygon(),408,311)
polygon::addpoint(polyMap()\Polygon(),397,316)
polygon::addpoint(polyMap()\Polygon(),378,309)
polygon::addpoint(polyMap()\Polygon(),365,323)
polygon::addpoint(polyMap()\Polygon(),342,360)
polygon::addpoint(polyMap()\Polygon(),358,379)
polygon::addpoint(polyMap()\Polygon(),205,379)
polygon::addpoint(polyMap()\Polygon(),206,341)
polygon::addpoint(polyMap()\Polygon(),212,325)
polygon::addpoint(polyMap()\Polygon(),198,316)
polygon::addpoint(polyMap()\Polygon(),162,298)
polygon::addpoint(polyMap()\Polygon(),119,305)
polygon::addpoint(polyMap()\Polygon(),99,338)
polygon::addpoint(polyMap()\Polygon(),91,362)
polygon::addpoint(polyMap()\Polygon(),79,372)
polygon::addpoint(polyMap()\Polygon(),90,380)
polygon::addpoint(polyMap()\Polygon(),4, 379)


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())
  ForEach polyMap()
    Define.point target
    target\x=WindowMouseX(winMain)
    target\y=WindowMouseY(winMain)
    polygon::drawPoly(polyMap()\Polygon())
    Debug target\x
    polygon::walkInit(polyMap()\Polygon(),@playerPos,@target)
    ;ForEach polyMap()\Polygon()
   
   
    ;    Debug "no"
    ;  EndIf
    ;Next
  Next
  Circle(target\x,target\y,5,#Blue)
 
  Circle(playerPos\x,playerPos\y,5,#Red)
  StopDrawing()
  FlipBuffers()
Until KeyboardReleased(#PB_Key_Escape) Or EventID = #PB_Event_CloseWindow

[Thyphoon]

Je touche au but ...
quelques petits detail a régler et puis faudra mettre au propre le code

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(2),List walkPath.i(), 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
  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 inLineOfSightA(*p1.point, *p2.point,List Polygon.point())
  Declare.b inLineOfSightB(*p1.point, *p2.point,List Polygon.point(),obstacle.b=#False)
  Declare drawPoly(List polylist.point())
  Declare walkInit(List polylist.point(),*From.point,*Target.point)
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
    Debug "x3="+Str(x3)
    Debug "x2="+Str(x2)
    Debug "x1="+Str(x1)
    Debug "y3="+Str(x3)
    Debug "y2="+Str(x2)
    Debug "y1="+Str(x1)
    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 polylist.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(polylist())-1
      SelectElement(polylist(),i)
      pa\x=polylist()\x
      pa\y=polylist()\y
      ;si on arrive a la fin de la liste on prend comme point i+1 le premier point
      If i=ListSize(polylist())-1
        SelectElement(polylist(),0)
      Else  
        SelectElement(polylist(),i+1)
      EndIf  
      pb\x=polylist()\x
      pb\y=polylist()\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(polylist())
        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 inLineOfSightB(*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 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 drawPoly(List polylist.point())
    Protected pa.point
    Protected pb.point
    Protected dist.l
    Protected i.l
    For i=0 To ListSize(polylist())-1
      SelectElement(polylist(),i)
      pa\x=polylist()\x
      pa\y=polylist()\y
      ;si on arrive a la fin de la liste on prend comme point i+1 le premier point
      If i=ListSize(polylist())-1
        SelectElement(polylist(),0)
      Else 
        SelectElement(polylist(),i+1)
      EndIf 
      pb\x=polylist()\x
      pb\y=polylist()\y
      LineXY(pa\x,pa\y,pb\x,pb\y,RGB(0,0,255))
      Circle(pa\x,pa\y,5,RGB(0,0,255))
      DrawText(pa\x+10,pa\y+10,Str(i))
      
    Next
    
  EndProcedure
  
  Procedure walkInit(List polylist.point(),*From.point,*Target.point)
    Protected pa.point
    Protected pb.point
    Protected.l  dist,i
    Protected p.point
    NewList walkpath.Point()
    NewList walk()
    
    
          ;-Id Target out zone
      If Not pointInside(*Target,polylist())
        ;Protected n=nearestSegment(*Target,polylist(),300)
        ;If n>-1
        ;  n=n-1
        ;  SelectElement(polylist(),n)
        ;  pa\x=polylist()\x
        ;  pa\y=polylist()\y
        ;  n=n+1: If n>ListSize(polylist())-1:n=0:EndIf 
        ;  SelectElement(polylist(),n+1)
        ;  pb\x=polylist()\x
        ;  pb\y=polylist()\y
          If *Target\x>5 And *Target\y>5
          getClosestPointOnEdge(@p,*Target,polylist())
        ;  LineIntersection(@pa,@pb,*Target,*From, @p)
          SelectElement(walkpath(),1) ;Target Alway second position
          *Target\x=p\x
          *Target\y=p\y
          EndIf 
        ;EndIf 
      EndIf 
    
    
    
    ;Add Start Point
    AddElement(walkpath())
    walkpath()\x=*From\x
    walkpath()\y=*From\y
    ;Add Target Point
    AddElement(walkpath())
    walkpath()\x=*Target\x
    walkpath()\y=*Target\y   
    
    
    
    If inLineOfSightB(*From, *Target,polylist())
      LineXY(*From\x,*From\y,*Target\x,*Target\y,#Red )
    Else
      ;Select all point to found the way
      For i=0 To ListSize(polylist())-1
        SelectElement(polylist(),i)
        pa\x=polylist()\x
        pa\y=polylist()\y
        ;si on arrive a la fin de la liste on prend comme point i+1 le premier point
        If IsVertexConcave(polylist(), i)=#True
          Circle(pa\x,pa\y,8,#Red)
          AddElement(walkpath())
          walkpath()\x=pa\x
          walkpath()\y=pa\y
        EndIf
      Next
      Dim Graph(ListSize(walkpath()),ListSize(walkpath()))
      For i=0 To ListSize(walkpath())-1
        SelectElement(walkpath(),i)
        pa\x=walkpath()\x
        pa\y=walkpath()\y
        Protected j.l
        For j=0 To ListSize(walkpath())-1
          If i<>j
            SelectElement(walkpath(),j)
            pb\x=walkpath()\x
            pb\y=walkpath()\y
            If (i>2 And j>2 And (j=i+1 Or i=j+1)) Or inLineOfSightB(@pa, @pb,polylist()) ;TODO ICI LE PROBLEME
              LineXY(pa\x,pa\y,pb\x,pb\y,#Green)
              Circle(pa\x,pa\y,5,#Yellow)
              Circle(pb\x,pb\y,5,#Yellow)
              Graph(i,j)=distanceBetwenPoint(pa\x,pa\y,pb\x,pb\y)
              
            Else
              Graph(i,j)=999999
              ;LineXY(pa\x,pa\y,pb\x,pb\y,#Blue)
              ; Circle(pa\x,pa\y,5,#Blue)
              ; Circle(pb\x,pb\y,5,#Blue)
            EndIf
          Else
            Graph(i,j)=0
          EndIf
        Next
        
        
      Next
      
      

      
      
      Pathfinding::dijkstra(Graph(),walk(),0,1)
      
      
      
      
    EndIf
    
    
    
    
    ;Draw Walk
    Protected.l Ax,Ay,Bx,By,n
    For n=0 To ListSize(walk())-1
      SelectElement(walk(),n)
      SelectElement(walkpath(),walk())
      Ax.l=walkpath()\x
      Ay.l=walkpath()\y
      If SelectElement(walk(),n+1)
        SelectElement(walkpath(),walk())
        Bx.l=walkpath()\x
        By.l=walkpath()\y
        Circle(Ax,Ay,5,#Yellow)
        LineXY(Ax,Ay,Bx,By,RGB(255,255,255))
        Circle(Bx,By,5,#Yellow)
      EndIf 
    Next
    
    
  EndProcedure
  
EndModule



;-Test

playerPos.point
playerPos\x=63
playerPos\y=290

Structure Polygon
  List Polygon.point()
EndStructure

NewList PolyMap.Polygon()
AddElement (polyMap())
polygon::addpoint(polyMap()\Polygon(),5,248)
polygon::addpoint(polyMap()\Polygon(),5,248)
polygon::addpoint(polyMap()\Polygon(),235,248)
polygon::addpoint(polyMap()\Polygon(),252,277)
polygon::addpoint(polyMap()\Polygon(),214,283)
polygon::addpoint(polyMap()\Polygon(),217,300)
polygon::addpoint(polyMap()\Polygon(),235,319)
polygon::addpoint(polyMap()\Polygon(),265,339)
polygon::addpoint(polyMap()\Polygon(),275,352)
polygon::addpoint(polyMap()\Polygon(),310,353)
polygon::addpoint(polyMap()\Polygon(),309,312)
polygon::addpoint(polyMap()\Polygon(),322,308)
polygon::addpoint(polyMap()\Polygon(),304,279)
polygon::addpoint(polyMap()\Polygon(),307,249)
polygon::addpoint(polyMap()\Polygon(),419,248)
polygon::addpoint(polyMap()\Polygon(),431,262)
polygon::addpoint(polyMap()\Polygon(),389,274)
polygon::addpoint(polyMap()\Polygon(),378,295)
polygon::addpoint(polyMap()\Polygon(),408,311)
polygon::addpoint(polyMap()\Polygon(),397,316)
polygon::addpoint(polyMap()\Polygon(),378,309)
polygon::addpoint(polyMap()\Polygon(),365,323)
polygon::addpoint(polyMap()\Polygon(),342,360)
polygon::addpoint(polyMap()\Polygon(),358,379)
polygon::addpoint(polyMap()\Polygon(),205,379)
polygon::addpoint(polyMap()\Polygon(),206,341)
polygon::addpoint(polyMap()\Polygon(),212,325)
polygon::addpoint(polyMap()\Polygon(),198,316)
polygon::addpoint(polyMap()\Polygon(),162,298)
polygon::addpoint(polyMap()\Polygon(),119,305)
polygon::addpoint(polyMap()\Polygon(),99,338)
polygon::addpoint(polyMap()\Polygon(),91,362)
polygon::addpoint(polyMap()\Polygon(),79,372)
polygon::addpoint(polyMap()\Polygon(),90,380)
polygon::addpoint(polyMap()\Polygon(),4, 379)


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())
  ForEach polyMap()
    Define.point target
    target\x=WindowMouseX(winMain)
    target\y=WindowMouseY(winMain)
    polygon::drawPoly(polyMap()\Polygon())
    polygon::walkInit(polyMap()\Polygon(),@playerPos,@target)
    ;ForEach polyMap()\Polygon()
    
    
    ;    Debug "no"
    ;  EndIf
    ;Next
  Next
  Circle(target\x,target\y,5,#Blue)
  
  Circle(playerPos\x,playerPos\y,5,#Red)
  StopDrawing()
  FlipBuffers()
Until KeyboardReleased(#PB_Key_Escape) Or EventID = #PB_Event_CloseWindow