The A* algorithm in XNA

The A* search algorithm ("A star") is used for path finding and graph traversal. The following is my implementation in XNA.

The A* algorithm itself is very similar to Dijkstra's algorithm but the A* uses heuristics to achieve better performance.

Screenshots

Usage

Left Mouse Click - Create a barrier
CTRL + Left Mouse Click - Set the source
ALT + Left Mouse Click - Set the destination
Space - Toggle grid lines
Enter - Start pathfinding!
` - Open the developer console

Heuristics

The A* algorithm uses a heuristic to improve performance by trying to "guess" the best path, although this will not, unlike Dijkstra's which does not use a heuristic, guarantee the shortest path.

Diagonal Distance

public int GetEstimate(Point source, Point destination)
{
    return Math.Max(Math.Abs(destination.X - source.X), Math.Abs(destination.Y - source.Y));
}

Manhattan Distance

public int GetEstimate(Point source, Point destination)
{
    return Math.Abs(destination.X - source.X) + Math.Abs(destination.Y - source.Y);
}

Euclidean Distance

public int GetEstimate(Point source, Point destination)
{
    return (int)Math.Sqrt(Math.Pow(source.X - destination.X,2) + Math.Pow(source.Y - destination.Y,2));
}

Dijkstra

When the heuristic is 0, the A* algorithm turns into Dijkstra's algorithm

public int GetEstimate(Point source, Point destination)
{
    return 0;
}

Try it!

The source can be found on github: https://github.com/dreasgrech/AStarXNA

A String.Format for JavaScript

The following is my implementation of a miniature version of .NET's String.Format:

String.format = String.format || function (format) {
    var params = [].splice.call(arguments, 1), nextOpen, nextClose = 0, index, plValue, spaces, totalSpaces,
        removeCharAt = function (text, pos) {
            return text.substr(0, pos) + text.substr(pos + 1, text.length);
        };

    while ((nextOpen = format.indexOf('{', nextClose)) >= 0) {
        if (isNaN(+format[nextOpen+1])) { 
            if (format[nextOpen+1] === "{") {
                format = removeCharAt(format, nextOpen + 1);
                format = removeCharAt(format, format.indexOf('}', nextOpen-1));
                nextClose++;
                continue;
            }
            nextClose = nextOpen + 1;
            continue;
        }
        
        nextClose = format.indexOf('}', nextOpen);
        index = format.substring(nextOpen + 1, nextClose);
        if (index.indexOf(',') > 0) {
            spaces = +index.substring(index.indexOf(',') + 1);
            index = +index.substring(0, index.indexOf(','));
        }
        plValue = params[index] + '';
        if (spaces) {
            totalSpaces = new Array(Math.abs(spaces) - plValue.length + 1).join(" ");
            plValue = spaces > 0 ? totalSpaces + plValue : plValue + totalSpaces;
        }
        format = format.substring(0, nextOpen) + ((!plValue && plValue !== 0) ? "" : plValue) + format.substring(nextClose + 1);
        nextClose = nextOpen + plValue.length - 1;
        spaces = 0;
    }
    return format;
};

Usage

String.format("Hello {0} {1}", "Andreas", "Grech");  // "Hello Andreas Grech"

for (var i = 0; i <= 1000; i += 200) {
    String.format("{0, 5}. Something", i);
}

/* Output:
    0. Something
  200. Something
  400. Something
  600. Something
  800. Something
 1000. Something
*/

String.format("Padded from {0, 7} left", "the");  // "Padded from     the left"
String.format("{{0}}", "Ignored");  // "{0}"
String.format("{{{0}}}", "Not ignored");  // "{Not ignored}"
String.format("{{{{0}}}}", "Seeing the pattern?");  // "{{0}}"
String.format("{{{{{0}}}}}", "This is getting mental"); // "{{This is getting mental}}"

You can fork this project at github: https://github.com/dreasgrech/JSStringFormat