PureBasic
https://www.purebasic.fr/french/

Pathfinding pour jeu Point'n Click 2D (ça fonctionne ^_^)
https://www.purebasic.fr/french/viewtopic.php?f=2&t=17904
Page 1 sur 2

Auteur:  Thyphoon [ Mar 21/Jan/2020 14:58 ]
Sujet du message:  Pathfinding pour jeu Point'n Click 2D (ça fonctionne ^_^)

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.
Image
http://www.groebelsloot.com/2015/12/24/pathfinding-part-1/
http://www.groebelsloot.com/2016/03/13/pathfinding-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:
;
;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

Auteur:  Shadow [ Mar 21/Jan/2020 19:17 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

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 :)

Auteur:  Micoute [ Mer 22/Jan/2020 10:53 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

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

Auteur:  Thyphoon [ Mer 22/Jan/2020 14:16 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

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

Auteur:  Ar-S [ Jeu 23/Jan/2020 9:58 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

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

Auteur:  Thyphoon [ Jeu 23/Jan/2020 12:53 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

Ar-S a écrit:
Très intéressant.
Merci pour ce partage.

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

Auteur:  Thyphoon [ Ven 24/Jan/2020 16:13 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

ç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 :(

Image

Auteur:  Thyphoon [ Ven 24/Jan/2020 16:53 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

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

Auteur:  Marc56 [ Ven 24/Jan/2020 16:53 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

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

Auteur:  MLD [ Sam 25/Jan/2020 9:29 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

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. :mrgreen: :oops: :oops:

Auteur:  Fig [ Sam 25/Jan/2020 15:34 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

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.

Auteur:  venom [ Sam 25/Jan/2020 18:00 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

8O Oula... C'est pointu ce que tu demande Thyphoon :lol:

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






@++

Auteur:  Thyphoon [ Sam 25/Jan/2020 21:45 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

c'est pas grave je continue a avancer... doucement ... là je bloque sur la pathfinding ...
https://www.purebasic.fr/french/viewtopic.php?f=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... :P
Mais pour l'instant :roll: je galère

Auteur:  Thyphoon [ Lun 27/Jan/2020 13:55 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

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:
;
;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

Auteur:  Thyphoon [ Lun 27/Jan/2020 17:56 ]
Sujet du message:  Re: Pathfinding dans jeu d'aventure Point'n Click 2D

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

Code:
;
;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


Page 1 sur 2 Heures au format UTC + 1 heure
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/