PureBasic

Forums PureBasic
Nous sommes le Sam 24/Oct/2020 4:19

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 11 messages ] 
Auteur Message
 Sujet du message: Pathfinding Dijkstra A l'aide !
MessagePosté: Ven 24/Jan/2020 22:57 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 25/Aoû/2004 6:31
Messages: 2637
Localisation: Eragny
Est ce que quelqu'un pourrais m'aider j'essayer d'appliquer l'ago Dijkstra pour resoudre ce chemin
Image
j'ai trouvé ce code sur le forum Allemand,
http://forums.purebasic.com/german/viewtopic.php?f=8&t=3759
J'ai essayé de développer mon propre code a partir de tuto mais je dois avouer que j'ai atteinds mes limites :oops:
Est-ce quelqu'un a une idée pourquoi le résultat n'est pas bon ?

Merci d'avance

Code:
#N = 8  ;  Num. Noeud

#M = 99999  ; = infini
; Longueur des arcs entre les nœuds
Dim Boegen.l(#N - 1, #N - 1)

Restore distanzen
For y = 0 To #N - 1
  For x = 0 To #N - 1
    Read.l Boegen(x, y)
  Next
Next


; Démarrer et arrêter le nœud
StartK = 0
StopK  = 5

; ; Distances par rapport au nœud de départ
Dim Distanz(#N - 1)

; Prédécesseur du nœud
Dim Vorgaenger(#N - 1)

; Noeuds où vous connaissez déjà le chemin le plus court
Dim Markierte(#N - 1)
For z = 0 To #N - 1
  Markierte(z) = #False
Next

; Nœud de départ déjà visité!
Markierte(StartK) = #True
; Distance par rapport à vous-même = 0
Distanz(StartK) = 0
; Prédécesseurs d'eux-mêmes
Vorgaenger(StartK) = StartK

; Définissez les distances et les prédécesseurs pour tous les autres nœuds.
For z = 0 To #N - 1
  ; ausser Startknoten (s.o.)
  If z <> StartK
    Distanz(z)    = Boegen(StartK, z)
    Vorgaenger(z) = StartK
  EndIf
Next


; Tant que le court. Chemin vers le noeud cible introuvable
While Markierte(StopK) = #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 #N - 1
    ; Si non marqué
    If Markierte(z) = #False
      ; sidistance plus courte
      If Distanz(z) < MinD
        MinK = z
        MinD = Distanz(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 StartK et StopK"
    Break
   
  ElseIf MinK = StopK
    ; Dle plus court trouvé
    Debug "Gefunden"
    Break
   
  Else
    ; Marquez-le, donc un moyen le plus court a été trouvé
    Markierte(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 #N - 1
    If Markierte(z) = #False
       ; Si le détour par MinK est plus court que l'itinéraire direct
      If Distanz(MinK) + Boegen(MinK, z) < Distanz(z)
        ; Calculer la nouvelle longueur de chemin
        Distanz(z)    = Distanz(MinK) + Boegen(MinK, z)
        ; Enregistrez le détour à 'z'
        Vorgaenger(z) = MinK
      EndIf
    EndIf
  Next

Wend


If MinK = StopK
  ; Retracer le chemin depuis le StopK
  s.s  = Str(StopK)
  z    = MinK
  While Vorgaenger(z) <> StartK
    s = Str(Vorgaenger(z)) + ", " + s
    z = Vorgaenger(z)
  Wend
  s = Str(Vorgaenger(z)) + ", " + s

  Debug s
  Debug "Distanz: " + Str(Distanz(StopK))
EndIf




DataSection
distanzen:

;-https://www.geeksforgeeks.org/wp-content/uploads/Fig-11.jpg

;       0   1   2   3   4   5   6   7   8
Data.l  0,  4,  #M, #M, #M, #M, #M, 8,  #M  ;0
Data.l  4,  0,  8,  #M, #M, #M, #M, 11, #M  ;1
Data.l  #M, 8,  0,  7,  #M,  4, #M, #M, 2   ;2
Data.l  #M,#M,  7,  0,  9,  14, #M, #M, #M  ;3
Data.l  #M,#M,  #M, 9,  0,  10, #M, #M, #M  ;4
Data.l  #M, #M, 4,  14, 10, 0,  2,  #M, #M  ;5
Data.l  #M, #M, #M, #M, #M, 2,  0,  1,  #M  ;6
Data.l  8,  11, #M, #M, #M, #M, 1,  0,  7   ;7
Data.l  #M, #M, 2,  #M, #M, #M, 6,  7,  0   ;8
EndDataSection


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Pathfinding Dijkstra A l'aide !
MessagePosté: Sam 25/Jan/2020 0:45 
Hors ligne
Avatar de l’utilisateur

Inscription: Dim 09/Oct/2005 16:51
Messages: 9027
J'ai pas le cerveau pour me pencher dessus mais j'ai regardé ce tuto qui est excellent.
Je ne sais pas si tu l'as vu.
https://www.youtube.com/watch?v=rHylCtXtdNs
et celui ci aussi un peu plus long.
https://www.youtube.com/watch?v=rI-Rc7eF4iw
Enfin il y a ce TP en Python?
https://www.ljll.math.upmc.fr/pegon/documents/BCPST/TP06_cor.pdf

_________________
~~~~Règles du forum ~~~~
.: Ar-S :. Tour + portable W10 x64 PB 5.6x / 5.7x
Section HORS SUJET : ICI
LDV MULTIMEDIA : Dépannage informatique & mes Logiciels PB


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Pathfinding Dijkstra A l'aide !
MessagePosté: Sam 25/Jan/2020 9:45 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 29/Juin/2011 14:11
Messages: 1733
Localisation: Belgique
Normalement on utilise une procédure récursive, on visite chaque nœud et on sauve le nœud visité

Voici une code en java que j'avais fais pour un jeu (quoridor) la je n'avais pas utilisé de fonction récursive

Code:
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package quoridor.model;

import java.util.HashMap;


/**
* GrapheFind
* Look for a road from source to multiple targets
* @author Bielen Pierre
* @version Alpha 1.0
*/
public class GrapheFind {
    private final HashMap<Node,Node> targets;
    private final Node starting;
    private final HashMap<Node,NodeFound> myNodesFound;
    // CONSTRUCTOR
    /**
     * Contructor
     * @param targets -> multiple targets node
     * @param starting   -> starting node
     */
    public GrapheFind(HashMap<Node, Node> targets, Node starting) {
        this.targets = targets;
        this.starting = starting;
        myNodesFound = new HashMap();
    }
    // PUBLIC METHODS
    public boolean find() {
        boolean returnedValue = false;
        Node current;
        Node neighbor;
        boolean neighborFound;
        // mark the stating node
            current = starting;
            myNodesFound.put(current, new NodeFound(null, current));
        while (true) {
            // Look for a neighbor
            neighborFound = false;
            for (Direction d : Direction.values()) {
                neighbor = current.getPath(d);
                // The neighbor is found
                if (neighbor != null) {
                    // the node path must be not into the list to be deleted
                    // The neighbor is not mark
                    if (!myNodesFound.containsKey(neighbor)) {
                       
                        // we mark the node
                        myNodesFound.put(neighbor, new NodeFound(current, neighbor));
                        current = neighbor;
                        neighborFound = true;
                        break;
                    }
                }
            }
            // we look if the found node is into the targets map.
            if(targets.containsKey(current)){ 
                returnedValue = true;
                break;
            }
            // we are again on the starting node
            if(current.equals(starting)){
                // and we not found other neighbors
                if(! neighborFound){
                    returnedValue = false;
                    break;
                }
            }
            //we come back to previous node
            if(! neighborFound){
                current = myNodesFound.get(current).from;
            }
        }
        return returnedValue;
    }
    // INTERNAL CLASS
    class NodeFound{
        public final Node from;
        public final Node node;
        // CONSTRUCTORS
        public NodeFound(Node from, Node node) {
            this.from = from;
            this.node = node;
        }
       
    }
}


_________________
Windows 10 64 bits PB: 5.70 ; 5.72 LST
Work at Centre Spatial de Liège


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Pathfinding Dijkstra A l'aide !
MessagePosté: Sam 25/Jan/2020 21:37 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 25/Aoû/2004 6:31
Messages: 2637
Localisation: Eragny
Merci microdevweb 8)

Je trouve plein de code mais jamais aucun ne fonctionne une fois passé en purebasic. C'est certain que j'interprète mal quelques choses... mais quoi ... :roll:
J'ai passé une partie a réécrire a partir d'un autre code trouver sur internet et j'ai toujours pas de résultat cohérent :(
Code:
;https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/


#INT_MAX=999999
#M=#INT_MAX
 
;A utility function To find the vertex With minimum distance value, from
;the set of vertices Not yet included in shortest path tree
Procedure.i minDistance(Array dist.i(1), Array sptSet.b(1))
VNb=ArraySize(dist(),1)
    ;Initialize min value
Protected min.i = #INT_MAX
Protected min_index.i 
 
    For v = 0 To VNb
        If sptSet(v) = #False And dist(v) <= min
          min = dist(v)
          min_index = v;
        EndIf
    Next
 
    ProcedureReturn min_index;
EndProcedure
 
;A utility function To print the constructed distance Array
Procedure.i printSolution(Array dist(1))
VNb=ArraySize(dist(),1)
    Debug ("Vertex \t\t Distance from Source\n");
    For i = 0 To VNb
      Debug  Str(i)+"     "+Str(dist(i));
    Next
EndProcedure 
  #V=8
; Function that implements Dijkstra's single source shortest path algorithm
;For a graph represented using adjacency matrix representation
  Procedure  dijkstra(Array graph(2),src.i)
    ;Number of vertices in the graph
    VNb=ArraySize(graph(),1)
    Debug VNb
    Dim dist.i(VNb); // The output array.  dist[i] will hold the shortest
    ;distance from src To i
 
    Dim sptSet.b(VNb); // sptSet[i] will be true if vertex i is included in shortest
    ;path tree Or shortest distance from src To i is finalized
 
    ;Initialize all distances As INFINITE And stpSet[] As false
    For i = 0 To  VNb
      dist(i) = #INT_MAX
      sptSet(i) = #False
    Next
 
    ;Distance of source vertex from itself is always 0
    dist(src) = 0;
 
    ;Find shortest path For all vertices
    For count = 0 To VNb - 1
        ;Pick the minimum distance vertex from the set of vertices Not
        ; yet processed. u is always equal To src in the first iteration.
       
 
        Protected u.i = minDistance(dist(), sptSet());
 
        ;Mark the picked vertex As processed
        sptSet(u) = #True;
 
        ;Update dist value of the adjacent vertices of the picked vertex.
        For v = 0 To VNb
 
            ; Update dist[v] only If is Not in sptSet, there is an edge from
            ; u To v, And total weight of path from src To  v through u is
            ; smaller than current value of dist[v]
            If (Not sptSet(v) And graph(u,v) And dist(u) <> #INT_MAX And dist(u) + graph(u,v) < dist(v))
              dist(v) = dist(u) + graph(u,v);
            EndIf
        Next
    Next
 
   ;print the constructed distance Array
    printSolution(dist());
EndProcedure
 

Dim graph(8, 8)

Restore distanzen
For y = 0 To 8
  For x = 0 To 8
    Read.l graph(x, y)
  Next
Next
dijkstra(graph(),5)
DataSection
distanzen:

;-https://www.geeksforgeeks.org/wp-content/uploads/Fig-11.jpg

;       0   1   2   3   4   5   6   7   8
Data.l  0,  4,  #M, #M, #M, #M, #M, 8,  #M  ;0
Data.l  4,  0,  8,  #M, #M, #M, #M, 11, #M  ;1
Data.l  #M, 8,  0,  7,  #M,  4, #M, #M, 2   ;2
Data.l  #M,#M,  7,  0,  9,  14, #M, #M, #M  ;3
Data.l  #M,#M,  #M, 9,  0,  10, #M, #M, #M  ;4
Data.l  #M, #M, 4,  14, 10, 0,  2,  #M, #M  ;5
Data.l  #M, #M, #M, #M, #M, 2,  0,  1,  #M  ;6
Data.l  8,  11, #M, #M, #M, #M, 1,  0,  7   ;7
Data.l  #M, #M, 2,  #M, #M, #M, 6,  7,  0   ;8
EndDataSection


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Pathfinding Dijkstra A l'aide !
MessagePosté: Sam 25/Jan/2020 22:14 
Hors ligne
Avatar de l’utilisateur

Inscription: Lun 10/Sep/2007 11:13
Messages: 1383
une explication simple de l'algo.
https://www.youtube.com/watch?v=rHylCtXtdNs

tes résultats sont corrects

Citation:
8
Vertex / Distance
0 / 11
1 / 12
2 / 4
3 / 11
4 / 10
5 / 0
6 / 2
7 / 3
8 / 6

vu que tu pars du vertex 5

Code:
dijkstra(graph(),5)


les distances vers les autre vertex sont bien les bons

_________________
ImageImage


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Pathfinding Dijkstra A l'aide !
MessagePosté: Sam 25/Jan/2020 23:26 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 25/Aoû/2004 6:31
Messages: 2637
Localisation: Eragny
merci 8O :oops:

Je viens de comprendre... je vais pouvoir avancer ...

Merci à tous


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Pathfinding Dijkstra A l'aide !
MessagePosté: Dim 26/Jan/2020 11:30 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 29/Juin/2011 14:11
Messages: 1733
Localisation: Belgique
Voici un petit code que j'ai fais en vitesse qui illustre le principe, j'espère qu'il pourra t'aider :wink:

Code:
#MAIN_FORM = 0
#MAIN_CANVAS = 0
#NODE_RADIUS = 4
#ROAD_H = 20
#ROAD_W = 3
#NODE_N = 50
Structure node
  *n.node
  *s.node
  *w.node
  *e.node
  *from.node
  x.l  ; only for debuging
  y.l  ; only for debuging
EndStructure
; create first
Global *first.node = AllocateStructure(node)
; make a random road
Procedure make_road(*node.node)
  Static n = 0
  Protected *new.node
  *new = AllocateStructure(node) ; create new node to N
  *new\from = *node              ; save from node
  Select Random(3,1)
    Case 1 ; s
      *node\s = *new                    ; set a road node to s
    Case 2                              ; e
      *node\e = *new                    ; set a road node to e
    Case 3                              ; w
      *node\w = *new                    ; set a road node to w
  EndSelect 
  n + 1
  If n < #NODE_N
    make_road(*new)
  EndIf
EndProcedure

Procedure draw_road(*node.node,x,y)
  Circle(x,y,#NODE_RADIUS,$0000FF)
  *node\x = x
  *node\y = y
  If *node\s
    Box(x,y,#ROAD_W,#ROAD_H,$FF0000)
    draw_road(*node\s,x,y+#ROAD_H)
  EndIf
  If *node\e
    Box(x,y,#ROAD_H,#ROAD_W,$FF0000)
    draw_road(*node\e,x+#ROAD_H,y)
  EndIf
  If *node\w
    Box(x,y,-#ROAD_H,#ROAD_W,$FF0000)
    draw_road(*node\w,x-#ROAD_H,y)
  EndIf
EndProcedure

Procedure find(*node.node)
  With *node
    Delay(100)
   
    If Not \n And Not \s And Not \w And Not \e
      StartDrawing(CanvasOutput(#MAIN_CANVAS))
      Circle(\x,\y,#NODE_RADIUS,$32CD32)
      StopDrawing()
    Else
      StartDrawing(CanvasOutput(#MAIN_CANVAS))
      Circle(\x,\y,#NODE_RADIUS,$ABABAB)
      StopDrawing()
      If \n
        find(\n)
      EndIf
      If \e
        find(\e)
      EndIf
      If \w
        find(\w)
      EndIf
      If \s
        find(\s)
      EndIf
    EndIf
   
  EndWith
EndProcedure

Procedure start()
  OpenWindow(#MAIN_FORM,0,0,800,600,"Test",#PB_Window_SystemMenu|#PB_Window_ScreenCentered)
  CanvasGadget(#MAIN_CANVAS,0,0,800,600)
  make_road(*first)
  StartDrawing(CanvasOutput(#MAIN_CANVAS))
  Box(0,0,800,600,$FFFFFF)
  draw_road(*first,400,10)
  StopDrawing()
  MessageRequester("Find path","ok")
  find(*first)
EndProcedure

start()

Repeat
  WaitWindowEvent()
Until Event()=#PB_Event_CloseWindow


_________________
Windows 10 64 bits PB: 5.70 ; 5.72 LST
Work at Centre Spatial de Liège


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Pathfinding Dijkstra A l'aide !
MessagePosté: Dim 26/Jan/2020 12:31 
Hors ligne
Avatar de l’utilisateur

Inscription: Lun 10/Sep/2007 11:13
Messages: 1383
je ne vois pas ou tu veux en venir microdevweb,
tu parcours tout les nodes et cela ne trace pas le chemin le plus court entre un point et un autre.
ou alors il y a un bug quelque part car a chaque fois cela m'affiche une 'cartographie' avec des points rouges et des traits bleus
puis tout les points sont remplaces par des points gris sauf le dernier en vert.
cela n'indique donc pas le chemin le plus rapide ce qui est l’intérêt de cet algorithme.

_________________
ImageImage


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Pathfinding Dijkstra A l'aide ![Resolu]
MessagePosté: Dim 26/Jan/2020 19:31 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 25/Aoû/2004 6:31
Messages: 2637
Localisation: Eragny
En attendant voici mon code qui fonctionne
Code:
#M = 99999  ; = infini

Procedure dijkstra(Array graph(2),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
  ; Retracer le chemin depuis le destIndex
  s.s  = Str(destIndex)
  z    = MinK
  While Predecessor(z) <> srcIndex
    s = Str(Predecessor(z)) + ", " + s
    z = Predecessor(z)
  Wend
  s = Str(Predecessor(z)) + ", " + s

  Debug s
  Debug "Distanz: " + Str(Distance(destIndex))
EndIf

EndProcedure




            ; Longueur des arcs entre les nœuds
nb=9
Dim Graph(nb, nb)

Restore graph
For y = 0 To nb - 1
  For x = 0 To nb - 1
    Read.l Graph(x, y)
  Next
Next


dijkstra(Graph(),4,8)

End
DataSection
graph:

;-https://www.geeksforgeeks.org/wp-content/uploads/Fig-11.jpg

;       0   1   2   3   4   5   6   7   8
Data.l  0,  4,  #M, #M, #M, #M, #M, 1,  #M  ;0
Data.l  4,  0,  8,  #M, #M, #M, #M, 11, #M  ;1
Data.l  #M, 8,  0,  7,  #M,  4, #M, #M, 2   ;2
Data.l  #M,#M,  7,  0,  9,  14, #M, #M, #M  ;3
Data.l  #M,#M,  #M, 9,  0,  10, #M, #M, #M  ;4
Data.l  #M, #M, 4,  14, 10, 0,  2,  #M, #M  ;5
Data.l  #M, #M, #M, #M, #M, 2,  0,  1,  6  ;6
Data.l  1,  11, #M, #M, #M, #M, 1,  0,  7   ;7
Data.l  #M, #M, 2,  #M, #M, #M, 6,  7,  0   ;8
EndDataSection


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Pathfinding Dijkstra A l'aide !
MessagePosté: Dim 26/Jan/2020 20:56 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1138
Dijkstra c'est un A* avec la fonction heuristique égale à 0.
J'ai codé ça, ça fonctionne aussi. Si tu peux calculer la distance à ta destination (en pixel), c'est facilement modifiable pour le transformer en A* (plus efficace).
La fonction prend une liste dynamique en paramètre.
J'ai utilisé la fonction SortStructuredList() au lieu d'un tas binaire pour ne pas charger le code inutilement puisque tu n'as que peu de nœuds à chercher de toute façon... (jusqu’à quelques milliers ça ne posera pas de problème...)

Code:
Structure poids
  noeud.i
  poids.i
EndStructure
Structure noeud
  List voisin.poids()
  noeudparent.i
  liste.i ;(0=ouverte; 1=fermée)
  F.i
  G.i
  H.i
EndStructure
Structure recherche
  noeud.i
  F.i
EndStructure
NewList graph.noeud()
#openlist=1
#closelist=2

Procedure Dijkstra(List Graph.noeud(), Start.i,Goal.i)
  NewList Recherche.recherche()
  ;examen du noeud de depart
  SelectElement(graph(),start)
  ;insert le premier noeud dans la liste
  graph()\F=0
  graph()\G=0
  graph()\H=0
  graph()\liste=#openlist
  AddElement(recherche())
  Recherche()\noeud=start
  recherche()\F=0
 
  While ListSize(recherche())<>0
    ;trie la liste de recherche, le F le plus petit en tête
    SortStructuredList(recherche(),#PB_Sort_Ascending,OffsetOf(recherche\F),TypeOf(recherche\F)) 
    FirstElement(Recherche())
    F=recherche()\F
    parent=recherche()\noeud
    SelectElement(graph(),parent)
    graph()\liste=#closelist
    DeleteElement(recherche())
   
    ;destination trouvée, on reconstitue le chemin à l'envers
    If parent=goal
      Debug "chemin trouvé"
      Debug goal
      parent=graph()\noeudparent
      Repeat
        Debug parent
        SelectElement(graph(),parent)
        parent=graph()\noeudparent
      Until parent=start
      Debug start
      End
    EndIf
   
    ;on examine chaque voisin du noeud, on les insert dans la liste
    ForEach(graph()\voisin())
      n=graph()\voisin()\noeud
      newF=graph()\voisin()\poids+F
      PushListPosition(graph())
      SelectElement(graph(),n)
      liste.i=graph()\liste
      PrevF.i=graph()\F
      ;noeud déja visité, on passe au suivant...
      If liste=#closelist
        PopListPosition(graph())
        Continue
      EndIf
      ;noeud déja évalué et meilleur, on passe au suivant...
      If liste=#openlist And newF>=PrevF
        PopListPosition(graph())
        Continue
      EndIf
      ;on met à jour le noeud
      graph()\G=newF
      graph()\H=0
      graph()\F=graph()\G+graph()\H
      graph()\noeudparent=parent
      graph()\liste=#openlist
      ;on l'ajoute à la liste
      AddElement(recherche())
      recherche()\noeud=n
      recherche()\F=newF
      PopListPosition(graph())
    Next
  Wend
  Debug "Pas de chemin trouvé"
EndProcedure

;on peuple le graphe avec les 9 noeuds
#nbNoeud=9
For noeud=0 To #nbNoeud-1
  AddElement(graph())
  Repeat
    Read.i noeudvoisin.i
    If noeudvoisin=100:Break:EndIf
    Read.i poids.i
    AddElement(graph()\voisin())
    graph()\voisin()\noeud=noeudvoisin
    graph()\voisin()\poids=poids
  ForEver
Next noeud
;On choisit un noeud de depart et un noeud de destination
#Depart=0:#destination=4
Dijkstra(graph(),#depart,#destination)


DataSection
  ;noeud 0
  ;noeud voisin, poids, etc...
  Data.i 1,4,7,8
  Data.i 100
  ;noeud 1
  Data.i 0,4,7,11,2,8
  Data.i 100
  ;noeud 2
  Data.i 1,8,8,2,5,4,3,7
  Data.i 100
  ;noeud 3
  Data.i 2,7,5,14,4,9
  Data.i 100
  ;noeud 4
  Data.i 5,10,3,9
  Data.i 100
  ;noeud 5
  Data.i 6,2,2,4,3,14,4,10,4,10
  Data.i 100
  ;noeud 6
  Data.i 7,1,8,6,5,2
  Data.i 100
  ;noeud 7
  Data.i 0,8,1,11,8,7,6,2
  Data.i 100
  ;noeud 8
  Data.i 7,7,2,2,6,6
  Data.i 100
EndDataSection

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Dernière édition par Fig le Dim 26/Jan/2020 21:28, édité 2 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Pathfinding Dijkstra A l'aide !
MessagePosté: Dim 26/Jan/2020 21:26 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 25/Aoû/2004 6:31
Messages: 2637
Localisation: Eragny
Merci Fig je vais regarder ça de plus prêt 8)


Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 11 messages ] 

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 26 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages

Rechercher:
Aller à:  
cron

 


Powered by phpBB © 2008 phpBB Group | Traduction par: phpBB-fr.com
subSilver+ theme by Canver Software, sponsor Sanal Modifiye