F# implementation of the A* algorithm

Question

This is my first attempt at writing something useful in F# and in a functional way in general. I would appreciate if you could point out any issue, even details, as I'd like to put all the bad habits aside as soon as possible. I tried to leave my OOP comfort zone when I wrote this but I feel like this is not enough. I would love to hear suggestions about how to make this code more functional.

Please consider that the code in Program.fs is for testing only and has a lot of ugly stuffs in it (magic numbers, poor logic). I've put it here so that you can see how the code in Pathfinding.fs is used. The code in main creates the following grid with 10 rows and 10 columns and sets which nodes are obstacles:

0  1  . . . 9
10          19
.           .
.           .
.           .
90 91 . . . 99

Pathfinding.fs

module Pathfinding

//Classic Vector2 type with distances calculation
type Vector2 =
    {
        mutable X : float;
        mutable Y : float;
    } with

    member this.EuclideanDistance(otherVector:Vector2) =
        let distanceX = otherVector.X - this.X
        let distanceY = otherVector.Y - this.Y
        sqrt (distanceX * distanceX + distanceY * distanceY)

    member this.ManhattanDistance(otherVector:Vector2) =
        let distanceX = abs (otherVector.X - this.X)
        let distanceY = abs (otherVector.Y - this.Y)
        distanceX + distanceY

// Open = Available to get chosen as the starting point for a new recursion
// Closed = Already used during one recursion, not available anymore
// NotUsed = Ready to be opened, never used before
// Obstacle = Can't be used and won't be reset
type NodeState = Open = 0 | Closed = 1 | NotUsed = 2 | Obstacle = 3

//A possible point on paths
type Node =
    {
        mutable g : float;          //Sum of the distances between each nodes from the starting node to this one, following the parents
        mutable h : float;          //Sum of all the manhattan distance of the parents nodes and this node
        mutable id : int;           //Unique id
        mutable state : NodeState;
        mutable parentNode : Node option;
        mutable position : Vector2;
        mutable neighbours : Node list
    } with

    static member createEmpty = {g = 0.0; h = 0.0; id = -1; state = NodeState.NotUsed; parentNode = None; 
                                position = {X = 0.0; Y = 0.0}; neighbours = []}


    static member createWithPositionAndId position id = 
        let newNode = Node.createEmpty
        newNode.Position <- position
        newNode.Id <- id
        newNode

    member this.H 
        with public get() = this.h
        and public set value = this.h <- value

    member this.G 
        with public get() = this.g
        and public set value = this.g <- value

    member this.Position 
        with public get() = this.position
        and public set value = this.position <- value

    member this.F = this.g + this.h

    member this.Id 
        with public get() = this.id
        and public set value = this.id <- value

    member this.State
        with public get() = this.state
        and public set value = this.state <- value

    member this.ParentNode
        with public get() = this.parentNode.Value
        and public set newParentId =  this.parentNode <- Some(newParentId)

    //Returns the manhattan distance between this node and the specified node
    member this.ManHattanDistance (endNode:Node) = this.position.ManhattanDistance endNode.Position

    //Returns the euclidean distance between this node and the specified node
    member this.EuclideanDistance (endNode:Node) = this.position.EuclideanDistance endNode.Position 

    member this.AddNeighbour neighbour = this.neighbours <- neighbour :: this.neighbours

//Handles all the pathfinding stuffs
type Pathfinder =
    {
        mutable allNodes : Node list;
        mutable startNode : Node;
        mutable goalNode : Node;
        mutable currentNode : Node;
    } with

    static member create = {allNodes = []; startNode = Node.createEmpty; 
                            goalNode = Node.createEmpty; currentNode = Node.createEmpty}

    //Sets all the nodes to their NotUsed state except for the obstacles
    member private this.reset = 
        let resetNodeAction (node:Node) =   if not (node.State = NodeState.Obstacle) 
                                            then node.State <- NodeState.NotUsed
                                            node
        this.allNodes <- this.allNodes |> List.map (fun x -> x |> resetNodeAction)

    //Set the initial value to the currentNode
    member private this.init =
        this.currentNode <- this.startNode
        this.currentNode.State <- NodeState.Closed

    //Find the most viable node i.e. the open node that has the lowest F value
    member this.findMostViableNode =
        let mutable mostViableNode = this.allNodes.Item(0)
        let mutable mostViableValue = 9999999.0
        let rec loopAction (listTail:Node list) =
            match listTail with
            | [] -> mostViableNode
            | head :: tail ->   if (head.State = NodeState.Open) && (head.F < mostViableValue) then
                                    mostViableValue <- head.F
                                    mostViableNode <- head
                                loopAction tail
        loopAction this.allNodes

    //Add a node to the pathfinder
    member this.addNode node = this.allNodes <- node :: this.allNodes

    //Start a new path search
    member this.findPath startNode endNode =
        this.startNode <- startNode
        this.goalNode <- endNode
        this.init
        this.checkNeighbourNodes

    //Recursive function that expands the search for a path on the grid
    member private this.checkNeighbourNodes =
        match this.currentNode.Id with
        | x when x = this.goalNode.Id -> this.generatePathList this.currentNode this.startNode  //Reached the goal, generating the result

        | _ ->  //Process pathfinding data on current node's neighbours
                this.currentNode.neighbours <- this.currentNode.neighbours |> List.map (fun x -> this.processNodeData x this.currentNode) 

                if this.canContinue this.allNodes then      //Still need to search
                    this.currentNode <- this.findMostViableNode
                    this.currentNode.State <- NodeState.Closed
                    this.checkNeighbourNodes 
                else                                         //There is no possible result
                    []

    //Calculate all the pathfinding data for the given node Id and sets it as Open
    member private this.processNodeData currentNode parentNode =
        if currentNode.State = NodeState.NotUsed then 
            //Update euclidian distance
            currentNode.G <- (currentNode.EuclideanDistance parentNode) + parentNode.G
            //Update manhanttan distance
            currentNode.H <- (currentNode.ManHattanDistance this.goalNode ) + parentNode.H
            currentNode.ParentNode <- parentNode
            currentNode.State <- NodeState.Open
            currentNode
        else currentNode        

    //We found a path, this function generate a Vector2 list as a result
    member private this.generatePathList currentNode lastNode =
        let mutable result = [currentNode.Position]
        match currentNode.Id with 
        | x when x = lastNode.Id -> result
        | _ ->  result <- (this.generatePathList currentNode.ParentNode lastNode) @ result
                result

    //Return true if any node is in the Open state.
    member private this.canContinue nodeList =
        match nodeList with
        | [] -> false
        | head :: tail ->   if head.State = NodeState.Open then
                                true
                            else
                                this.canContinue tail

Program.fs

open Pathfinding

let mutable nodeList = []

//Create a node a the given position and add it to the list
let addNodeToList (x:int) (y:int) =
    let newNode = Node.createWithPositionAndId {X = (float)x; Y = (float)y} (99 - nodeList.Length)
    nodeList <- newNode :: nodeList

//Create a row of the map
let rec createMapRow rowPosition (currentRowSize:int) =
    match currentRowSize with
    | x when x = -1 -> ()
    | _ ->  addNodeToList currentRowSize rowPosition
            createMapRow rowPosition (currentRowSize - 1)

//Generate all the nodes
let rec createMap currentColumnSize maxRowSize =
    match currentColumnSize with
    | x when x = -1 -> ()
    | _ ->  createMapRow currentColumnSize maxRowSize 
            createMap (currentColumnSize - 1) maxRowSize

//Add the node of the given id as a neighbour to the given node
let addOneNeighbour (currentNode:Node) idToAdd =
    let n = nodeList.Item(idToAdd)
    currentNode.AddNeighbour n

//Associate neighbours to nodes and consider grid sides.
// A    B       C
// D    node    E
// F    G       H
let addNeighbours (currentNode:Node) id (nodeList:Node list) =
    let x = currentNode.Position.X
    let y = currentNode.Position.Y
    let inFisrtColumn = (x = 0.0)
    let inLastColumn = (x = 9.0)

    if not inFisrtColumn then
        addOneNeighbour currentNode (id - 1)        //D
    if not inLastColumn then
        addOneNeighbour currentNode (id + 1)        //E

    if id >= 10 then
        addOneNeighbour currentNode (id - 10)       //B
        if not inFisrtColumn then
            addOneNeighbour currentNode (id - 11)   //A
        if not inLastColumn then
            addOneNeighbour currentNode (id - 9)    //C
    if id < 90 then
        addOneNeighbour currentNode (id + 10)       //G
        if not inFisrtColumn then
            addOneNeighbour currentNode (id + 9)    //F
        if not inLastColumn then
            addOneNeighbour currentNode (id + 11)   //H

    currentNode

//Iterates over nodes and for each node calls addNeighbours
let assignNeighbours (nodeList:Node list) =
    let action i n = addNeighbours n i nodeList
    let list = List.mapi action nodeList
    list

//Iterates over nodes and register each node to the pathfinder
let assignNodesToPathfinder (nodeList:Node list) (pathfinder:Pathfinder) =
    let action n = pathfinder.addNode n
    let list = List.map action nodeList
    nodeList

let setAsObstacle id =
    let nodeToClose = nodeList.Item(id)
    nodeToClose.State <- NodeState.Obstacle


[<EntryPoint>]
let main argv = 

    createMap 9 9
    nodeList <- assignNeighbours nodeList

    setAsObstacle 1
    setAsObstacle 11
    setAsObstacle 21
    setAsObstacle 22

    let pathfinder = Pathfinder.create
    nodeList <- assignNodesToPathfinder nodeList pathfinder

    let mutable startNode = nodeList.Item(0)
    let mutable goalNode = nodeList.Item(5)
    let mutable path = pathfinder.findPath startNode goalNode
    printfn "%A" path    
    startNode <- nodeList.Item(99)
    goalNode <- nodeList.Item(0)
    path <- pathfinder.findPath startNode goalNode
    printfn "%A" path

    0 // retourne du code de sortie entier

Answer 1

Typically, F# is written in functional style, and there are several things you are not doing in functional style here.

type Vector2 =
    {
        mutable X : float;
        mutable Y : float;
    } with

    member this.EuclideanDistance(otherVector:Vector2) =
        let distanceX = otherVector.X - this.X
        let distanceY = otherVector.Y - this.Y
        sqrt (distanceX * distanceX + distanceY * distanceY)

    member this.ManhattanDistance(otherVector:Vector2) =
        let distanceX = abs (otherVector.X - this.X)
        let distanceY = abs (otherVector.Y - this.Y)
        distanceX + distanceY

X and Y should not be mutable here. You should write these as a record:

type Vector2 = { X :float; Y :float }

Then, instead of having class members, you would make the EuclideanDistance and ManhattanDistance pure functions:

let euclideanDistance (vector1 :Vector2) (vector2: Vector2) =
    let distanceX = vector2.X - vector1.X
    let distanceY = vector2.Y - vector1.Y
    sqrt (distanceX * distanceX + distanceY * distanceY)

let manhattanDistance (vector1 :Vector2) (vector2: Vector2) =
    let distanceX = abs (vector2.X - vector1.X)
    let distanceY = abs (vector2.Y - vector1.Y)
    distanceX + distanceY

You will probably be able to remove the type hints as well, and F# will still be able to figure out what types the parameters are.

---

In a few places you assign a variable, then immediately return the variable. Instead of this, you should return the result of the calculation. One such place is here:

member private this.generatePathList currentNode lastNode =
    let mutable result = [currentNode.Position]
    match currentNode.Id with 
    | x when x = lastNode.Id -> result
    | _ ->  result <- (this.generatePathList currentNode.ParentNode lastNode) @ result
            result

That should be rewritten as:

member private this.generatePathList currentNode lastNode =
    match currentNode.Id with 
    | x when x = lastNode.Id -> [currentNode.Position]
    | _ -> (this.generatePathList currentNode.ParentNode lastNode) @ [currentNode.Position]

---

This looks like a bug:

let assignNodesToPathfinder (nodeList:Node list) (pathfinder:Pathfinder) =
    let action n = pathfinder.addNode n
    let list = List.map action nodeList
    nodeList

You iterate the list and create a new list based on the action, but return the original list and do nothing with the new list. Unless pathfinder.addNode has side effects somehow, in which case you should ignore the result of the List.map. Given the name of the function, it looks as if you really just want a void result, so you can return a unit, which is essentially the same. The unit literal in F# is (), but you can also get it by returning a unit from another expression. Give these assumptions, I would write it as:

let assignNodesToPathfinder (nodeList:Node list) (pathfinder:Pathfinder) =
    ignore <| List.map pathfinder.addNode nodeList

Notice that if you have a function that takes a single parameter and returns a new result, you can just place it inline like the way I did above.

Another way to write it would be using tail recursion:

let rec assignNodesToPathfinder (nodeList:Node list) (pathfinder:Pathfinder) =
    let head::tail = nodeList
    pathfinder.addNode head

    if not tail.IsEmpty then
        assignNodesToPathfinder tail pathfinder