Plug-n-Play pathfinding
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
}
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
Node start, Node destination,
Func
Func
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
A very, very elegant solution - thanks Eric!
Tags: A*, Generics, Pathfinding
January 26th, 2010 at 14:32
Just to let you know, Func isn't a key word, it's a delegate type. Actually, several generic delegates Func, Func, Func etc, etc,etc.
There are also similar delegates which are similar Action, Action, etc are used the same as Func except where no return value is required
Predicate used when you want a function that compares and return true or false based on the comparison (Pretty much the same as Func, except it's just Predicate :))
Delegates are useful things 😀
January 26th, 2010 at 14:33
ah, it stripped my < and &rt; symbols. Meh at WordPress.
January 26th, 2010 at 17:39
So busy at work I'm still catching up on the 3.0 (and 2.0 - *sigh*) framework.
Thanks for the clarification Nik!
January 26th, 2010 at 23:54
Altough Eric Lipperts' sollution is indeed much more sophisticated than a solution I wrote a while ago, I would like to point out that 46ms for finding a path in a 10x10 is a bit long, even for a maze.
I've got a few tips to improve speed:
-Give the nodes an open and closed lists boolean flags so the lookup for "is in open" is O(1) (you can now even get rid of the closed list).
-Use integers for scores rather than floats. (diagonal movement is usual 1.4x the cost of orthogonal movement, so make the standard costs 14(dia) and 10(ortho)).
-Use a MinHeap for the openlist.
This should make your implementation a lot faster. You can have a look at my sample code:
http://roy-t.nl/index.php/2009/07/07/new-version-a-pathfinding-in-3d/ but I think it would be faster to change your existing code with some speed ups you find usefull. than to change to my "not so elegant and pluggable" version.
My implementation takes an average of 1.7ms on 10x10x10 grid. Although this was not a maze but a randomly constructed 3d grid I think you should be able to get your code down to taking at most 10ms to find a path.
(This is really handy because it means you might not have to spawn a seperate thread for pathfinding, an extra 50ms would really disrupt the game loop, but an extra 10ms might not be noticeable enough to need an extra pathfinding thread, as long as you only try to find one path per iteration).
Anyway I hope these are some useful tips! Oh and btw, you've been featured on http://www.sgtconker.com !
January 27th, 2010 at 10:10
Excellent Roy - thanks for the tips. I will certainly have a look at your code as well :).
I have a penchant for optimization and you seem to have quite a few really worthy goldnuggets there.