有點幫助F-Sharping這個路徑查找代碼，請

Question

編輯賞金是關於我的後續問題重新：代碼的通用版本。按我的最後一個職位在這個線程，謝謝，JD

大家好，

我只是試着端起我的一些C＃2D路徑查找代碼到F＃。但是我目前處於C＃OO開發人員的'殭屍'之中，也可能試圖用我的F＃來完全實現功能。因此，考慮到這段代碼，這可能是迄今爲止我寫的最不重要的F＃，我希望將它作爲一段F＃代碼的一些建議。 （對不起，如果這是有點太「做我的作業」，但我找不到一個很好的F＃A *路徑查找樣本供參考）。

立即想到的一件事是：我過度使用if/else/elseif「functional」夠了嗎？

一些注意事項：

1）「去除」是一個簡單的工具函數，從列表

2）「nodeToPathNode」僅僅需要一個點在空間中刪除的元素，使一個路徑節點出它（添加親參考，和H，G & F（按照典型的A *））

---

EDIT（＃1）：我已經更新與給定的（沒有建議的代碼關於使它通用的一個，我會在稍後介紹）...只是一些人通過谷歌來到這裏，並將它的錯誤的格​​式和邏輯錯誤複製我的代碼。
完整，2D瓷磚具體的實現，可以在這裏找到：http://jdoig.net/blog/?p=81

EDIT（＃2）或通用版本可以在這裏找到：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 

謝謝，

JD

Answer 1

我h aven't在算法/邏輯仔細地看了看，但這裏是我會怎樣觸及它：

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 - 類型以大寫字母（list/option/array/ref是唯一的例外）開始。

每個逗號，分號或豎線之後的空格。

刪除後縮進hd::tl行，並使用elif而不是else if。

擺脫很多不必要的圓括號（f x不f(x)，if cond then不if(cond) then）。

流水線風格多一點（let neighbours=...）。

否則，一目瞭然，這看起來不錯。

Answer 2

這裏有一些想法：

添加一些註釋！要了解正在發生的事情有點難。

一般來說，更喜歡curry函數到它們的元組形式。這使得可以使用部分應用程序，這通常可以更容易閱讀。例如，如果您重寫nodeToPathNode函數以重新排序參數，則只需執行List.map (nodeToPathNode openNodes.Head goal)而不必引入mp臨時變量。

而不是使用列表，你可能會考慮使用F＃的set類型，因爲它允許涉及最小元素的更高效的操作。

對我來說，你的代碼最大的問題是它太具體了; A *是通用算法;從概念上講，它由功能g和h，一個起始節點，一個目標和一個將節點映射到其鄰居的函數進行參數化。因此，我希望你的算法的簽名更像pathfind (g:'a -> float) (h:'a -> float) (start : 'a) (goal : 'a) (neighbors : 'a -> 'a list) : 'a list option。然後，您仍然可以將此算法用於當前節點類型，但由於距離和鄰居函數沒有進行硬編碼，因此您也可以使用它來解決可能遇到的任何其他尋路問題。

Answer 3

@ kvb。

感謝有關製作通用A *算法的建議。 實施起來很有趣，也是一個很好的學習工具。

我的問題是，我的通用實現毫秒5-8慢，也許是我誤解了仿製藥的成本，但我想像的成本較低:(。

這裏是我的代碼，如果你會這麼好心以檢查它的任何可能被我花費這麼多的時間（假設這是我的過錯代碼，而不是仿製藥的開銷）：

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 

感謝，

JD