Un poco de ayuda F-Sharping up this código de búsqueda de ruta, por favor

Question

EDITAR La recompensa es con respecto a mi pregunta de seguimiento re: la versión genérica del código. Según mi último mensaje en este hilo, Gracias, JD

Hola a todos,

He intentado simplemente portar algunos de mi código C# ruta de búsqueda de 2D en C#. Pero actualmente estoy en el 'limbo' de ser un desarrollador de C# OO y también, probablemente, tratando demasiado duro para ser puramente funcional con mi F #.

Tomando este código, que es probablemente el F # menos trivial que he escrito hasta ahora, me gustaría obtener algunos consejos para convertirlo en una buena pieza de código F #. (perdón si esto también es un poco "haz mi tarea para mí", pero no puedo encontrar una buena muestra de F # A * búsqueda de ruta para referencia).

Una cosa que inmediatamente me viene a la mente es: ¿Es mi uso excesivo de if/else/elsef suficientemente "funcional"?

Algunas notas:

1) "eliminar" es una función de utilidad simple que elimina elementos de una lista

2) "nodeToPathNode" simplemente toma un punto en el espacio y hace que un nodo camino de salida de la misma (la adición de una referencia principal, y una h, g & f (como por típico a *))

---

EDIT (# 1): he actualizado el código con las sugerencias dadas (sans el de hacerlo genérico, lo abordaré más adelante) ... solo en caso de que alguien llegue aquí a través de Google y copie mi código con su mal formato y errores de lógica.
Una completa, Azulejos 2D específica, la aplicación se puede encontrar aquí: http://jdoig.net/blog/?p=81

EDITAR (# 2) o la versión genérica se puede encontrar aquí: 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 

Gracias,

JD

Answer 1

I h aven't observó de cerca el algoritmo/lógica, pero aquí es cómo iba a tocarla hasta:

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 - tipos comienzan con letras mayúsculas (list/option/array/ref son las únicas excepciones).

Espacios en blanco después de cada coma, punto y coma o barra vertical.

Reducir sangría después de hd::tl línea, y usar elif en lugar de else if.

Deshacerse de un montón de paréntesis innecesarios (f x no f(x), if cond then no if(cond) then).

Estilo de tuberías un poco más (let neighbours=...).

De lo contrario, de un vistazo esto se ve bien.

Answer 2

Aquí hay algunas ideas:

¡Agregue algunos comentarios! Es un poco difícil seguir lo que está pasando.

En general, prefiera las funciones currificadas a sus formularios agrupados. Esto hace posible usar aplicaciones parciales, que a menudo pueden ser más fáciles de leer. Por ejemplo, si reescribe la función nodeToPathNode para reordenar los parámetros, puede hacer List.map (nodeToPathNode openNodes.Head goal) en lugar de tener que introducir la variable temporal mp.

En lugar de usar listas, podría considerar usar el tipo de conjunto F #, ya que eso permite operaciones más eficientes que involucran el elemento mínimo.

Para mí, el mayor problema con su código es que es demasiado específico; A * es un algoritmo general; conceptualmente, está parametrizado por las funciones g y h, un nodo de inicio, un objetivo y una función que asigna un nodo a sus vecinos. Por lo tanto, esperaría que la firma de su algoritmo fuera más parecida a pathfind (g:'a -> float) (h:'a -> float) (start : 'a) (goal : 'a) (neighbors : 'a -> 'a list) : 'a list option. Entonces aún podría usar este algoritmo con sus tipos de nodo actuales, pero como las funciones de distancia y vecino no están codificadas, también podría usarlo para resolver cualquier otro problema de ruta que pueda encontrar.

Answer 3

@ kvb.

Gracias por el consejo sobre cómo hacer un algoritmo A * genérico. Fue divertido de implementar y una gran herramienta de aprendizaje.

Mi problema es que mi aplicación genérica es de entre 5 y 8 ms lento, tal vez me malinterprete el costo de los medicamentos genéricos, pero me imaginaba que cueste menos :(.

Aquí está mi código si fuera tan amable como para comprobar que para cualquier cosa que pudiera yo estar costando tanto tiempo (asumiendo que es mi código de la culpa y no la sobrecarga de los genéricos):

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 

Gracias,

JD