A little help F-Sharping up this path-finding code, please

Question

EDIT The bounty is regarding my follow up question re: the generic version of the code. As per my last post in this thread, Thanks, JD

Hi all,

I've just tried porting some of my C# 2D path-finding code into F#. But I'm currently in the 'limbo' of being a C# OO developer and also, probably, trying too hard to be purely functional with my F#.

So taking this piece of code, that is probably the least trivial F# I've written so far, I'd like some advice on making it a good piece of F# code. (sorry if this is a little too "do my homework for me", but I can't find a good sample of F# A* path-finding for reference.).

One thing that immediately springs to mind is: Is my excessive use of if/else/elseif "functional" enough?

Some notes:

1)"remove" is a simple utility function that removes elements from a list

2) "nodeToPathNode" simply takes a point in space and makes a path node out of it (adding a parent reference, and an h,g & f (as per typical A*))

---

EDIT(#1): I've updated the code with the suggestions given (sans the one about making it generic, i'll get on that later)... just incase some one arrives here via Google and was to copy my code with its bad formatting and logic errors.
A full, 2D Tile specific, implementation can be found here: http://jdoig.net/blog/?p=81

EDIT(#2) Or the generic version can be found here: 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

Thanks,

JD

Answer 1

I haven't looked closely at the algorithm/logic, but here is how I would touch it up:

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 begin with capital letters (list/option/array/ref are the only exceptions).

Whitespace after every comma, semicolon, or vertical bar.

Lessen indent after hd::tl line, and use elif rather than else if.

Get rid of lots of unneeded parentheses (f x not f(x), if cond then not if(cond) then).

Pipelining style a little more (let neighbours=...).

Otherwise, at a glance this looks good.

Answer 2

Here are some thoughts:

Add some comments! It's a bit hard to follow what's going on.

Generally, prefer curried functions to their tupled forms. This makes it possible to use partial application, which can often be easier to read. For instance, if you rewrite the nodeToPathNode function to reorder the parameters, then you could just do List.map (nodeToPathNode openNodes.Head goal) instead of having to introduce the mp temporary variable.

Rather than using lists you might consider using F#'s set type since that allows more efficient operations involving the minimum element.

To me, the biggest problem with your code is that it's too specific; A* is a general algorithm; conceptually, it is parameterized by the functions g and h, a start node, a goal, and a function which maps a node to its neighbors. Thus I'd expect your algorithm's signature to be more like pathfind (g:'a -> float) (h:'a -> float) (start : 'a) (goal : 'a) (neighbors : 'a -> 'a list) : 'a list option. Then you could still use this algorithm with your current node types, but since the distance and neighbor functions aren't hardcoded, you could also use it to solve any other pathfinding problems you might run into.

Answer 3

@ kvb.

Thanks for the advice on making a generic A* algorithm. It was fun to implement and a great learning tool.

My problem is that my generic implementation is between 5 and 8 ms slower, maybe I misunderstand the cost of generics, but I imagined it to cost less :( .

Here's my code if you would be so kind as to check it for anything that could be costing me so much time (Assuming it's my code at fault and not the overhead of generics):

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

Thanks,

JD