# F# implementation of the A* algorithm

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
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
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 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

//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


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) =


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) =

if not tail.IsEmpty then
assignNodesToPathfinder tail pathfinder

• Thanks a lot for your answer! I don't really know when I should use a record or a class. Should Node be rewritten with the same logic? Should Pathfinder disappear completely and be replaced by functions only? Maybe I should read more about functional programming!
– Stud
Jan 8, 2017 at 19:42
• You typically want to use F# types (records, unions, and such) over classes and structs. Typically, you avoid state and mutable variables in FP and use pure functions and immutability.
– user34073
Jan 8, 2017 at 19:44
• Continuing along that line, in assignNodesToPathfinder, you would typically construct a new Pathfinder instance with the new nodes and return it (and update the name to represent the new action).
– user34073
Jan 8, 2017 at 19:45
• This makes sense, the Pathfinder is defined by the map it holds. Also I realize I used List.map several time in the code when I just wanted to iterate over the list, not when I wanted to create a new list with the result (as you pointed in your answer). I'll fix that too.
– Stud
Jan 8, 2017 at 19:51
• One way to do that is recursion, which also supports early-returns, if that is an option.
– user34073
Jan 8, 2017 at 19:55