Created
July 29, 2011 10:23
-
-
Save jdoig/1113576 to your computer and use it in GitHub Desktop.
Tools for generic pathfinding
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module Tools | |
open System | |
let sqr x = float(x * x) | |
let rec remove l predicate = | |
match l with | |
| [] -> [] | |
| hd::tl -> if predicate(hd) then | |
(remove tl predicate) | |
else | |
hd::(remove tl predicate) | |
let loadMap path = | |
IO.File.ReadAllText(path).Split(';') | |
|> Array.filter(fun s -> s<> String.Empty) | |
|> Array.map(fun s-> Int32.Parse(s.Replace(";",String.Empty))) | |
(* The A* Algorithm *) | |
let rec aStar value g h neighbors goal start (openNodes: 'a list) (closedNodes: 'a list) = | |
let f x:float = (g x)+(h x) (*f will be the value we sort open nodes buy *) | |
let isShorter nodeA nodeB = nodeA = nodeB && f nodeA < f nodeB | |
let rec checkNeighbors neighbors openNodeAcc = | |
match neighbors with | |
| [] -> openNodeAcc | |
| currentNode::rest -> | |
let likeCurrent = fun n -> (value n) = (value currentNode) | |
let containsCurrent = likeCurrent |> List.exists (* list contains likeCurrent *) | |
let checkNeighbors = checkNeighbors rest | |
(* The current node is a shorter path than than one we already have. *) | |
if openNodeAcc |> List.exists (isShorter currentNode) then | |
(* So remove the old one... *) | |
let shorterPath = remove openNodeAcc likeCurrent | |
(* ...and carry on with the new one. *) | |
checkNeighbors (currentNode::shorterPath) | |
(* The current node has not been queried *) | |
elif not(containsCurrent closedNodes) && not(containsCurrent openNodeAcc) then | |
checkNeighbors (currentNode::openNodeAcc) (* So add it to the open set *) | |
else checkNeighbors openNodeAcc (* else carry on *) | |
let nodes = neighbors openNodes.Head (* The next neighbors to work on *) | |
let pathToGoal = nodes |> List.tryFind (fun x -> (value x) = goal) | |
if pathToGoal.IsSome then pathToGoal (* Found the goal! *) | |
else | |
let nextSet = | |
checkNeighbors nodes openNodes.Tail | |
|> List.sortBy f (* sort open set by node.f *) | |
if nextSet.Length > 0 then (* Carry on pathfinding *) | |
aStar value g h neighbors goal start nextSet (nextSet.Head::closedNodes) | |
else None (* if there are no open nodes pathing has failed *) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment