PureBasic

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

Résultat (note une pause est volontairement faite)

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

Ç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...

@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

microdevweb a écrit :Maintenant je suis preneur pour un script avec le chemin le plus cour

Tu demandes ça à Fig ? http://www.purebasic.fr/english/viewtop ... athFinding

(au passage, très chouette code !)

PureBasic

Graph en Pb

Graph en Pb

Re: Graph en Pb

Re: Graph en Pb

Re: Graph en Pb