Un peu d'aide F-Sharping up ce code de recherche de chemin, s'il vous plaît

Question

EDIT La prime est en ce qui concerne ma question de suivi re: la version générique du code. Selon mon dernier post dans ce fil, Merci, JD

Salut à tous,

Je viens d'essayer le portage une partie de mon C# code 2D chemin recherche en F #. Mais je suis actuellement dans le «limbe» d'être un développeur C# OO et aussi, probablement, d'essayer trop dur d'être purement fonctionnel avec mon F #.

Donc, en prenant ce morceau de code, c'est probablement le F # le moins trivial que j'ai écrit jusqu'à présent, je voudrais un conseil pour en faire un bon morceau de code F #. (désolé si c'est un peu trop "fais mes devoirs pour moi", mais je ne trouve pas un bon échantillon de F # A * path-finding pour référence.). Une chose qui me vient immédiatement à l'esprit est: Est-ce que mon utilisation excessive de if/else/elseif est "fonctionnelle"?

Quelques remarques:

1) « Supprimer » est une simple fonction d'utilité qui supprime les éléments d'une liste

2) « nodeToPathNode » prend simplement un point dans l'espace et fait un noeud de chemin sur de celui-ci (l'ajout d'une référence parent, et un h, g & f (selon type a *))

---

EDIT (# 1): Je l'ai mis à jour le code avec les suggestions données (sans celui sur le fait de le rendre générique, je le ferai plus tard) ... juste au cas où quelqu'un arriverait ici via Google et devait copier mon code avec ses mauvaises erreurs de formatage et de logique.
A pleine, carreaux 2D spécifique, se trouve mise en œuvre ici: http://jdoig.net/blog/?p=81

EDIT (# 2) Ou la version générique est disponible ici: http://jdoig.net/blog/?p=127

---

let rec pathFind (area:Map) goal start (openNodes:PathingNode list) (closedNodes:PathingNode list) = 
let pointToPathNode = pointToPathNode openNodes.Head goal //localy specific version of nTPN 

let rec checkNeighbours neighbours openNodeAcc= //Loop over list of neighbours accumalating a list of open nodes 
    match neighbours with 
    |[] -> openNodeAcc //When list of neighbours is exhausted return the open nodes. 
    |hd::tl -> 
     let checkNeighbours = checkNeighbours tl       //localy specific version of cn 
     let node = {hd with parent = Some(openNodes.Head)} 
     if (List.exists (isShorter hd) openNodeAcc) then  //if a higher costingnode is in open... 
      let shorterPath = remove openNodeAcc (nodePointEquals hd.point)   //... remove it.. 
      checkNeighbours (node::shorterPath) 
     elif not(List.exists (nodePointEquals hd.point) closedNodes) && not (List.exists (nodePointEquals hd.point) openNodeAcc) then //If path is not open or closed... 
      checkNeighbours (node::openNodeAcc) 
     else checkNeighbours openNodeAcc //Else carry on. 

let neighbours = 
     area.GetNeighboursOf openNodes.Head.point //Get the neighbours of our current node (openNodes.Head) ... 
     |> List.filter isClear      //...filter out collidable tiles... 
     |> List.map pointToPathNode     //...for each neighbour we can walk to: generate a pathing node     

let pathToGoal = List.tryFind (nodePointEquals goal) neighbours //Try and find the goal node in the walkable neighbours of this tile. 
if pathToGoal.IsSome then pathToGoal      //If we found our goal return it... 
else 
    let nextSet = 
     checkNeighbours neighbours openNodes.Tail 
     |> List.sortBy(fun x -> x.f) 
    if nextSet.Length > 0 then 
     pathFind area goal start nextSet (nextSet.Head::closedNodes) //...Else carry on 
    else None 

Merci,

JD

Answer 1

I h aven't a examiné de près l'algorithme/logique, mais voici comment je toucher jusqu'à:

let rec pathFind (area:map,start, goal, openNodes:PathingNode list, closedNodes:PathingNode list)=   
    let rec checkNeighbours (opn, neighbours) = 
     match neighbours with 
     | [] -> opn 
     | hd::tl -> 
      if List.exists (fun x -> x.point = hd.point && x.f > hd.f) opn then 
       checkNeighbours(remove opn (fun x -> x.point = hd.point), tl) 
      elif not(List.exists (fun x -> x.point = hd.point) closedNodes) 
       && not(List.exists (fun x -> x.point = hd.point) opn) then 
       checkNeighbours({hd with parent = Some(openNodes.Head)}::opn, tl) 
      else  
       checkNeighbours(opn, tl) 

    let neighbours = 
     area.GetNeighboursOf(openNodes.Head.point) 
     |> List.map (fun mp -> nodeToPathNode(mp, openNodes.Head, goal)) 
     |> List.filter (fun pnd ->pnd.point.value = 0) 

    let openLocalNodes = checkNeighbours(openNodes.Tail, neighbours)  

    if List.exists (fun x -> x.point = goal) openLocalNodes then 
     {point=goal; h=0; g=goal.Distance(start); parent=Some(openNodes.Head)} 
    else 
     pathFind(area, start, goal, openLocalNodes, openNodes.Head::closedNodes)  

PathingNode - types commencent par les lettres majuscules (list/option/array/ref sont les seules exceptions).

Espace après chaque virgule, point-virgule ou barre verticale.

Diminuer l'indentation après la ligne hd::tl et utiliser elif au lieu de else if.

Débarrassez-vous de beaucoup de parenthèses inutiles (f x pas f(x), if cond then pas if(cond) then).

Style de pipeline un peu plus (let neighbours=...).

Sinon, en un coup d'œil, cela semble bon.

Answer 2

Voici quelques idées:

Ajoutez des commentaires! C'est un peu difficile de suivre ce qui se passe.

Généralement, préférez les fonctions carnées à leurs formes tuplées. Cela permet d'utiliser une application partielle, qui peut souvent être plus facile à lire. Par exemple, si vous réécrivez la fonction nodeToPathNode pour réorganiser les paramètres, vous pouvez simplement faire List.map (nodeToPathNode openNodes.Head goal) au lieu de devoir introduire la variable temporaire mp. Plutôt que d'utiliser des listes, vous pouvez envisager d'utiliser le type d'ensemble F # car cela permet des opérations plus efficaces impliquant l'élément minimum.

Pour moi, le plus gros problème avec votre code est qu'il est trop spécifique; A * est un algorithme général; conceptuellement, il est paramétré par les fonctions g et h, un nœud de départ, un objectif et une fonction qui mappe un nœud à ses voisins. Ainsi, je m'attendrais à ce que la signature de votre algorithme soit plus proche de pathfind (g:'a -> float) (h:'a -> float) (start : 'a) (goal : 'a) (neighbors : 'a -> 'a list) : 'a list option. Ensuite, vous pouvez toujours utiliser cet algorithme avec vos types de nœuds actuels, mais comme les fonctions de distance et de voisinage ne sont pas codées en dur, vous pouvez également l'utiliser pour résoudre d'autres problèmes de pathfinding que vous pourriez rencontrer.

Answer 3

@ kvb.

Merci pour les conseils sur la création d'un algorithme générique A *. C'était amusant à mettre en œuvre et un excellent outil d'apprentissage.

Mon problème est que mon implémentation générique est comprise entre 5 et 8 ms plus lent, peut-être que je comprends mal le coût des médicaments génériques, mais je l'imaginais coûter moins :(.

Voici mon code si vous voulez bien de vérifier pour tout ce qui pourrait être me coûte beaucoup de temps (en supposant qu'il est mon code fautif et non les frais généraux des génériques):

let rec aStar value g h neighbours goal start (openNodes: 'a list) (closedNodes: 'alist) = 
    let f x:float = (g x)+(h x) //f will be the value we sort open nodes by. 
    let isShorter nodeA nodeB = nodeA = nodeB && f nodeA < f nodeB 

let rec checkNeighbours neighbours openNodeAcc = 
    match neighbours with 
    | [] -> openNodeAcc 
    | currentNode::rest -> 
     let likeCurrent = fun n -> (value n) = (value currentNode) //vale of n == value of current 
     let containsCurrent = List.exists likeCurrent    //list contains likeCurrent 
     let checkNeighbours = checkNeighbours rest 

     if openNodeAcc |> List.exists (isShorter currentNode) then //The current node is a shorter path than than one we already have. 
      let shorterPath = remove openNodeAcc likeCurrent //So remove the old one... 
      checkNeighbours (currentNode::shorterPath) //...and arry on with the new one. 
     elif not(containsCurrent closedNodes) && not(containsCurrent openNodeAcc) then //The current node has not been queried 
      checkNeighbours (currentNode::openNodeAcc) //So add it to the open set 
     else checkNeighbours openNodeAcc // else carry on 

let nodes = neighbours openNodes.Head //The next set of nodes to work on 

let pathToGoal = nodes |> List.tryFind (fun x -> (value x) = goal) 
if pathToGoal.IsSome then pathToGoal //Found the goal! 
else 
    let nextSet = 
     checkNeighbours nodes openNodes.Tail 
     |> List.sortBy f //sort open set by node.f 
    if nextSet.Length > 0 then //Carry on pathfinding 
     aStar value g h neighbours goal start nextSet (nextSet.Head::closedNodes) 
    else None //if there are no open nodes pathing has failed 

Merci,

JD