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



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



JD

F# Pathfinding

I've recently started to have a play around with F# and for my first non-trivial application I'm thinking of implementing a path finding algorithm as seen in games. Seeing as this is a learning exercise I'm going to try and be as "functional" as possible (trying to stay as "pure" as I can with immutable data).

First things first:
We'll need a world to 'path find' our way around. Lets start off with defining some simple utility functions. Below is my Tools module that contains functions to:

• Square ints to a float 
• Remove items from lists 
• Load ints from a file (2D arrays of numbers will serve as our tile maps, collision maps, monster & item locations, etc)

The map:
Ok we still need to describe the world we want to navigate: In our world a 0 represents an open space and a 1 represents an area we can not enter. For example a 4 unit long corridor, running left to right, would look like this:

* Wall 1 1 1 1
* Void 0 0 0 0
* Wall 1 1 1 1

Here is my level module that describes:

• Map point: an x,y location in our 2D space, plus the value of the tile at that location and a function to calculate distance from another map point
• Map: a list of map points and a function to get the neighboring tiles of any given tile

Pathfinding: Now comes the fun part. This contains the PathingNode type (that basically wraps a map location with information that the A* path-finding algorithm needs), some utility functions and the path-finding function itself.

Level 1: Now let's create a file to represent our world. Open up a text editor and and create a delimited 2D array of 0's and 1's with a definite path between 2 points. like so:

* 0; 0; 0; 0; 0;
* 0; 0; 0; 1; 0;
* 0; 0; 0; 1; 0;
* 0; 1; 1; 1; 1;
* 0; 0; 0; 0; 0;
* 1; 1; 1; 1; 0;
* 0; 0; 0; 0; 0;
* 1; 0; 1; 1; 1;
* 0; 0; 0; 0; 0;

(I've highlighted my start tile green and end tile red for reference)
...Save this text file some where on your hard drive for later.
The Results:
The code bellow shows the pathfinding in action: