SHOW:
|
|
- or go back to the newest paste.
| 1 | - | let findIndex2D (p:'A -> bool) (a:'A [,]) = //finds index |
| 1 | + | let findIndex2D (p:'A -> bool) (a:'A [,]) = |
| 2 | a |> Array2D.mapi (fun x y v -> x,y,v) | |
| 3 | |> Seq.cast<int*int*'A> | |
| 4 | |> Seq.pick (fun (x,y,v) -> if p v then Some (x,y) else None) | |
| 5 | ||
| 6 | - | let totalManhattanDistance board goal = //manhatten distance for every tile for Fscore |
| 6 | + | let totalManhattanDistance board goal = |
| 7 | let manhattanDistance (x1, y1) (x2, y2) = | |
| 8 | abs(x1 - x2) + abs (y1 - y2) | |
| 9 | board |> Array2D.mapi (fun x y v -> manhattanDistance (x, y) | |
| 10 | <| findIndex2D ((=) v) goal) | |
| 11 | |> Seq.cast<int> // flatten | |
| 12 | |> Seq.reduce (+) | |
| 13 | ||
| 14 | let swap (arr : int[,]) i1 i2 = | |
| 15 | let map i j v = | |
| 16 | match (i,j) with | |
| 17 | | t when t = i1 -> arr.[fst i2, snd i2] | |
| 18 | | u when u = i2 -> arr.[fst i1, snd i1] | |
| 19 | | _ -> v | |
| 20 | arr |> Array2D.mapi map | |
| 21 | ||
| 22 | - | let neighbors board (zeroX, zeroY) = // gets every neighbor nodes given the empty "0" tile and the starting board |
| 22 | + | let neighbors board (zeroX, zeroY) = |
| 23 | let (x,y) = findIndex2D ((=) 0) board | |
| 24 | [if x > 0 then yield swap board (zeroX,zeroY) (zeroX - 1, zeroY) | |
| 25 | if x < Array2D.length1 board - 1 then yield swap board (zeroX,zeroY) (zeroX + 1, zeroY) | |
| 26 | if y > 0 then yield swap board (zeroX,zeroY) (zeroX, zeroY - 1) | |
| 27 | if y < Array2D.length2 board - 1 then yield swap board (zeroX,zeroY) (zeroX, zeroY + 1)] | |
| 28 | ||
| 29 | - | let notContainsTuple (b,g,f) list = not (List.exists ((=) b) list) |
| 29 | + | let notContainsTuple x list = not (List.forall (fun (b,g,f) -> |
| 30 | not (b = x)) list) | |
| 31 | ||
| 32 | let notContainsList x list = not (List.exists ((=) x) list) | |
| 33 | ||
| 34 | ||
| 35 | let Astar board goal = | |
| 36 | let gScore = 0 | |
| 37 | let fScore = gScore + totalManhattanDistance board goal | |
| 38 | let startState = (board, gScore, fScore) | |
| 39 | let openSet = [startState] | |
| 40 | let closedSet = [] | |
| 41 | - | let rec find currentBoard CS OS GS = |
| 41 | + | |
| 42 | let rec find currentBoard (CS : int[,] list) OS GS = | |
| 43 | if currentBoard = goal then GS | |
| 44 | else | |
| 45 | let zeroInd = findIndex2D ((=) 0) currentBoard | |
| 46 | let removedCurrent = List.tail OS | |
| 47 | let adjacentBoards = List.filter (fun elem -> | |
| 48 | (notContainsList elem CS) && (notContainsTuple elem removedCurrent)) (neighbors currentBoard zeroInd) | |
| 49 | let adjacentStates = List.map (fun x -> | |
| 50 | let newGS = GS + 1 | |
| 51 | let newFS = newGS + totalManhattanDistance x goal | |
| 52 | (x, newGS, newFS)) adjacentBoards | |
| 53 | let newCS = currentBoard::CS | |
| 54 | let newOS = List.sortBy (fun (b,g,f) -> f) (List.append removedCurrent adjacentStates) | |
| 55 | - | find board closedSet openSet gScore1) |
| 55 | + | |
| 56 | find board closedSet openSet gScore |
