# F# implementation of the A* algorithm round 2

This is my second attempt at implementing the A* algorithm using F#, the first one is here.

What I changed:

• I removed the Node class and added two records named MapNode and PathNode that respectively store map and pathfinding data. This leads to more immutable variables and an implementation that will help split pre-computed data and runtime data.
• I removed the Pathfinder class and only use functions instead
• I changed the implementation of canContinue to use List.exists
• I did all the modification suggested by @Dain II Ironfoot in the previous post

It feels better to works like this with F# but it looks a bit messy too. As in the previous question, all suggestions are welcome!

Pathfinding.fs

module PathfindingRound2

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

let euclideanDistance v1 v2 =
let distanceX = v2.X - v1.X
let distanceY = v2.Y - v1.Y
sqrt (distanceX * distanceX + distanceY * distanceY)

let manhattanDistance v1 v2 =
let distanceX = abs (v2.X - v1.X)
let distanceY = abs (v2.Y - v1.Y)
distanceX + distanceY

//Possible states of a MapNode:
// Walkable = Can be used in a path
// Obstacle = Can't be used in a path
type MapNodeState = Walkable = 0 | Obstacle = 1

// A node that store map related data, no pathfinding data here
type MapNode = { uniqueId:int; position:Vector2; mutable neighbours: MapNode list; mutable state:MapNodeState }

let createMapNode id position state=
{ uniqueId = id; position = position; neighbours = []; state = state}

//Possible states of a PathNode
// 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
type PathNodeState = Open = 0 | Closed = 1 | NotUsed = 2

//A node that stores pathfinding related data and links them with a mapNode
type PathNode = { g:int; h:int; parent:PathNode option; mutable state:PathNodeState; mapNode:MapNode }

//Sum of the distances between each nodes from the starting node to this one, following the parents
let calculateNodeG parentG parent targetMapNode =
parentG + int(euclideanDistance parent.mapNode.position targetMapNode.position)

//Sum of all the manhattan distance of the parents nodes and this node
let calculateNodeH parentH parent targetMapNode =
parentH + int(manhattanDistance parent.mapNode.position targetMapNode.position)

let calculateNodeF node = node.g + node .h

let createPathNode parentG parentH targetMapNode parent =
let newG = calculateNodeG parentG parent targetMapNode
let newH = calculateNodeH parentH parent targetMapNode
{ g = newG; h = newH; parent = Some parent; state = PathNodeState.Open; mapNode = targetMapNode }

//PATHFINDING FUNCTIONS

//We found a path, this function generates a Vector2 list as a result
let rec generatePathList currentNode lastNode =
match currentNode.mapNode.uniqueId with
| x when x = lastNode.uniqueId -> [currentNode.mapNode.position]
| _ ->  match currentNode.parent with
| Some parent -> (generatePathList parent lastNode) @ [currentNode.mapNode.position]
| None ->   printfn "Logic error, lastNode should be the only node with parent = None. Returning computed path."
[currentNode.mapNode.position]

//Return true if any node is in the Open state.
let canContinue nodeList =
nodeList |> List.exists (fun n -> n.state = PathNodeState.Open)

let isAlreadyInThePath nodeList node =
nodeList |> List.exists (fun n -> n.mapNode.uniqueId = node.uniqueId)

//Find the most viable node i.e. the open node that has the lowest F value
//At this point we know that nodeList is no empty.
let findMostViableNode (nodeList:PathNode list) =
let mutable mostViableNode = nodeList.Head
let mutable mostViableValue = 9999999
let rec loopAction listTail =
match listTail with
| [] -> mostViableNode
| head :: tail ->   let nodeF = calculateNodeF head
if (head.state = PathNodeState.Open) && (nodeF < mostViableValue) then
mostViableValue <- nodeF
mostViableNode <- head
loopAction tail
loopAction nodeList

//Calculate all the pathfinding data for the given node Id and sets it as Open
let processNodeData nodeList currentNode =
let mutable neighbourPathNodes = []
let rec loopAction neighbours currentNode =
match neighbours with
| [] -> neighbourPathNodes
| head :: tail ->   if not (isAlreadyInThePath nodeList head) then   //Don't add duplicated node
if head.state = MapNodeState.Walkable then  //Only use walkable nodes
neighbourPathNodes <- (createPathNode currentNode.g currentNode.h head currentNode) :: neighbourPathNodes
loopAction tail currentNode
loopAction currentNode.mapNode.neighbours currentNode

//Recursively looks for a path
let rec checkNeighboursNode nodeList startNode endNode currentNode =
match currentNode.mapNode.uniqueId with
| x when x = endNode.uniqueId -> generatePathList currentNode startNode
| _ ->  let openNodeList = (processNodeData nodeList currentNode) @ nodeList
if canContinue openNodeList then
let newCurrentNode = findMostViableNode openNodeList
newCurrentNode.state <- PathNodeState.Closed
checkNeighboursNode openNodeList startNode endNode newCurrentNode
else
[]  //There is no path to the goal node

//Initiate pathfinding routine
let findPath startNode endNode =
let currentNode = { g = 0; h = 0; parent = None; state = PathNodeState.Closed; mapNode = startNode }
checkNeighboursNode [] startNode endNode currentNode


Program.fs

open PathfindingRound2

//let pathfinder = Pathfinder.create
let mutable nodeList = []

//Create a node a the given position and add it to the list
let addNodeToList x y =
let node = createMapNode (99 - nodeList.Length) {X = (float)x; Y = (float)y} MapNodeState.Walkable;
nodeList <- node :: 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 idToAdd =
let n = nodeList.Item(idToAdd)
currentNode.neighbours <- n :: currentNode.neighbours

//Associate neighbours to nodes and consider grid sides.
// A    B       C
// D    node    E
// F    G       H
let addNeighbours currentNode id nodeList =
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 =
let action i n = addNeighbours n i nodeList
List.mapi action nodeList |> ignore

let closeNode id =
let nodeToClose = nodeList.Item(id)
nodeToClose.state <- MapNodeState.Obstacle

[<EntryPoint>]
let main argv =

createMap 9 9
assignNeighbours nodeList

closeNode 1
closeNode 11
closeNode 21
closeNode 22

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

0 // retourne du code de sortie entier

• Looks much better. I'd suggest trying to remove mutable entirely and reducing ifs in favor of matches. I was told that if should only be used when checking a boolean variable. – 23fc9a62-56de-47fb-97b4-737890 Jan 8 '17 at 23:41
• I don't know how I can remove the last mutables without over complicating the code. I'll try to find a solution to this. – Stud Jan 9 '17 at 8:09