Warning: Parameter 1 to wp_default_scripts() expected to be a reference, value given in /var/www/xnafan.net/public_html/wp-includes/plugin.php on line 571

Warning: Parameter 1 to wp_default_styles() expected to be a reference, value given in /var/www/xnafan.net/public_html/wp-includes/plugin.php on line 571
xnaFan's Blog » Blog Archive » Plug-n-Play pathfinding

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

Tags: , ,

5 Responses to “Plug-n-Play pathfinding”

  1. Nik Radford Says:

    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 😀

  2. Nik Radford Says:

    ah, it stripped my < and &rt; symbols. Meh at WordPress.

  3. admin Says:

    So busy at work I'm still catching up on the 3.0 (and 2.0 - *sigh*) framework. :)
    Thanks for the clarification Nik!

  4. Roy Says:

    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 !

  5. admin Says:

    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.

Leave a Reply