Posts Tagged ‘Generics’

Plug-n-Play pathfinding

Wednesday, November 4th, 2009

I once implemented the A* (A-star) pathfinding algorithm in Java, and was ready to do it again in C# for the Klima Konflikt game, but while Googling a bit for referenceimplementations I stumbled across Eric Lippert's very, very elegant solution.
He has basically created a class with a static generic method which will pathfind on anything if you just supply:

1) Items which can tell what their neighbors are - by implementing:
interface IHasNeighbours
{
IEnumerable Neighbours { get; }
}
2) A "Begin" and "End" item
3) A function which gives an estimate on the expected distance from an item to an item (WalledTiles in my case).
The distance can be calculated easily using the Pythagorean theorem.
4) [optional] A function which returns a cost for a tile (based on a weighting system you decide).

Here's the signature for the method:

static public Path FindPath(
Node start, Node destination,
Func distance,
Func estimate)
where Node : IHasNeighbours

It took me 20 minutes to implement, just because I am fairly new to the idea of the Func keyword. Thank you Jesper for walking me through it :)
Pathfinding takes approximately 46 ms on our 10x10 tile board.

Screenshot from the current version of the game

Screenshot from the current version of the game

A very, very elegant solution - thanks Eric!