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