A* With F#

First of all please accept my apologies if you find this post and my last one rather scant on details and description.
I'm mega-busy at the moment, I'll pop back soon and try to flesh some of these posts out with detailed descriptions.

I've updated my path finding to use a generic version of the A* algorithm. This slows it down (~6 milliseconds on my box, in debug mode) but it does make for more reusable code.

My Tools module has become the home of this new algorithm and is as follows

	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 *)

view raw Tools.fs hosted with ❤ by GitHub

And my Pathfinding module has shed some weight to look like so:

	module Pathfinding
	open Level
	open Tools
	(* a wrapper for mapPoint that can contain pathing data as per typical A* pathfinding *)
	(* g = cost of path so far, h = estimated cost to goal, parent = tile we came here from *)
	type PathingNode =
	{point:MapPoint; h:float; g:float; parent:PathingNode option}
	(* returns a pathnode based on a given map point *)
	let pointToPathNode parent goal node = {point=node; h=node.Distance goal; g=(parent.g+1.0); parent=Some(parent)}
	(* A 2D tile specific version of the A* algorithm *)
	let pathFind
	(map:Map) goal = aStar (fun n-> n.point) (fun n-> n.g) (fun n-> n.h) (fun n-> (map.GetNeighborsOf n.point)
	|> List.filter(fun n-> n.value =0)
	|> List.map (pointToPathNode n goal)) goal

view raw Pathfinding.fs hosted with ❤ by GitHub

JD