3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Hosch250 Jan 8 '17 at 23:41
  • \$\begingroup\$ 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. \$\endgroup\$ – Stud Jan 9 '17 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.