StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>@ kvb.</p> <p>Thanks for the advice on making a generic A* algorithm. It was fun to implement and a great learning tool.</p> <p>My problem is that my generic implementation is between 5 and 8 ms slower, maybe I misunderstand the cost of generics, but I imagined it to cost less :( .</p> <p>Here's my code if you would be so kind as to check it for anything that could be costing me so much time (Assuming it's my code at fault and not the overhead of generics):</p> <pre><code>let rec aStar value g h neighbours goal start (openNodes: 'a list) (closedNodes: 'alist) = let f x:float = (g x)+(h x) //f will be the value we sort open nodes by. let isShorter nodeA nodeB = nodeA = nodeB && f nodeA < f nodeB let rec checkNeighbours neighbours openNodeAcc = match neighbours with | [] -> openNodeAcc | currentNode::rest -> let likeCurrent = fun n -> (value n) = (value currentNode) //vale of n == value of current let containsCurrent = List.exists likeCurrent //list contains likeCurrent let checkNeighbours = checkNeighbours rest if openNodeAcc |> List.exists (isShorter currentNode) then //The current node is a shorter path than than one we already have. let shorterPath = remove openNodeAcc likeCurrent //So remove the old one... checkNeighbours (currentNode::shorterPath) //...and arry on with the new one. elif not(containsCurrent closedNodes) && not(containsCurrent openNodeAcc) then //The current node has not been queried checkNeighbours (currentNode::openNodeAcc) //So add it to the open set else checkNeighbours openNodeAcc // else carry on let nodes = neighbours openNodes.Head //The next set of nodes to work on let pathToGoal = nodes |> List.tryFind (fun x -> (value x) = goal) if pathToGoal.IsSome then pathToGoal //Found the goal! else let nextSet = checkNeighbours nodes openNodes.Tail |> List.sortBy f //sort open set by node.f if nextSet.Length > 0 then //Carry on pathfinding aStar value g h neighbours goal start nextSet (nextSet.Head::closedNodes) else None //if there are no open nodes pathing has failed </code></pre> <p>Thanks,</p> <p>JD</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload