## Thursday, December 23, 2010

### 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.

#### 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

## Tuesday, December 21, 2010

### 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
*/