Graph en Pb

Partagez votre expérience de PureBasic avec les autres utilisateurs.
Avatar de l’utilisateur
microdevweb
Messages : 1798
Inscription : mer. 29/juin/2011 14:11
Localisation : Belgique

Graph en Pb

Message par microdevweb »

Les graphes peuvent être pratique dans le développement de jeux de labyrinthe ou de plateau. Je doit réaliser (en Java) le jeux quoridor qui implémente un graphe. Dans ce jeux le joueur peux placer des murs pour ralentir adversaire mais ne peux pas bloquer l'accès au camp adverse.

Voici le début d' une teste en PureBasic pour trouver la sortie

Analyse
Image

Résultat (note une pause est volontairement faite)
Image

:arrow: Télécharger le code
L'algo en lui même

Code : Tout sélectionner

Procedure findPath (*this._struct,*nodeFrom,*nodeTo,Array cardinal(1),*callBack)
    With *this
      Protected.Node::Node currentNode = *nodeFrom,neighbor
      Protected NewMap  visitedNodes.Node::Node()
      ClearList(\path())
      Protected currentPoint.l,neighborIsFound.b
      ; we start with the from node
      AddMapElement(visitedNodes(),Str(currentNode)):visitedNodes() = currentNode
      AddElement(\path()): \path() = currentNode
      ; loop until we don't find the target and we have possibility
      Repeat
        ; look for a neighbor
        neighborIsFound = #False ;we start without neighbor found
        For currentPoint=0 To ArraySize(cardinal())-1
          neighbor = currentNode\getPath(cardinal(currentPoint))
          If neighbor ; a neighbor is find
                      ; if the node has not be already visited
            If Not FindMapElement(visitedNodes(),Str(neighbor))
              ; we take this node
              currentNode = neighbor
              AddMapElement(visitedNodes(),Str(currentNode)):visitedNodes() = currentNode
              AddElement(\path()):\path() = currentNode
              neighborIsFound = #True
              ; we call callback function if it exists
              If *callBack
                CallFunctionFast(*callBack,currentNode)
              EndIf
              Break ;don't search other neighbor
            EndIf
          EndIf
        Next
        If Not neighborIsFound ; no neighbor has not be found
                               ; we go back to back and remove it from path
          If LastElement(\path())
            currentNode = \path()
            DeleteElement(\path())
            If *callBack
              CallFunctionFast(*callBack,currentNode)
            EndIf
          EndIf   
        EndIf
      Until (currentNode = *nodeTo) And (ListSize(\path()))
      If ListSize(\path())
        ProcedureReturn #True ; a path has be found
      EndIf
      ProcedureReturn #False ;no path has be not found
    EndWith
  EndProcedure
Windows 10 64 bits PB: 5.70 ; 5.72 LST
Work at Centre Spatial de Liège
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Graph en Pb

Message par Fig »

Ça me semble assez peu efficace comme méthode.
Je ne suis pas sûr de comprendre... Tu cherche le chemin le plus court ?
Pourquoi tu n'utilise pas Dijkstra ou A* (en rajoutant une fonction heuristique) ?

Une explication de ton algo serait la bienvenue.
Bravo pour l'effort en tout cas...
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 : 6.00LTS - 64 bits
Avatar de l’utilisateur
microdevweb
Messages : 1798
Inscription : mer. 29/juin/2011 14:11
Localisation : Belgique

Re: Graph en Pb

Message par microdevweb »

@Fig,

Ce script ne cherche pas forcément le chemin le plus court, il est plutôt utiliser pour un labyrinthe (avec normalement un seul chemin vers la sortie).

Explication sur un graphe. ICI.

Explication du script...
On lui passe dans un tableau les points cardinaux par ordre de préférence
exemple:
  • Nord
  • Est
  • Ouest
  • Sud

Ainsi qu'un nœud de départ et d'arrivée
Le script suit les liaisons de nœud en nœud en respectant l'ordre des points cardinaux et à la condition que le nœud n'aie pas déjà été visité.
Quand il arrive sur un nœud qui ne débouche pas sur un nœud non-visité, il recule et cherche un nœud non-visité.

Maintenant je suis preneur pour un script avec le chemin le plus cour :wink:
Windows 10 64 bits PB: 5.70 ; 5.72 LST
Work at Centre Spatial de Liège
Avatar de l’utilisateur
djes
Messages : 4252
Inscription : ven. 11/févr./2005 17:34
Localisation : Arras, France

Re: Graph en Pb

Message par djes »

microdevweb a écrit :Maintenant je suis preneur pour un script avec le chemin le plus cour :wink:
Tu demandes ça à Fig ? http://www.purebasic.fr/english/viewtop ... athFinding :wink:
(au passage, très chouette code !)
Répondre