Click here to Skip to main content
Click here to Skip to main content

Fast A-Star (2D) Implementation for C#

, 18 Oct 2010 MIT
Rate this:
Please Sign up or sign in to vote.
A functional, generic a-star solver with good performance

Update Notice

I have successfully ported this algorithm to C++ and it is coming with a C++ .NET wrapper. I never could imagine that C++ would increase the performance about one order of magnitudes. But in this very case, the C++ algorithm can work much more efficient, since it isn't generic or uses any other flexibility the C# version provides. For my tasks, the C++ algorithm is all I need so far. I will post it here as soon as it is more tested and I've also added A* instancing, issuing multiple paths queries at the cost of one, in common scenarios. For example the C++ algorithm completes in 230ms for a 1024x1024 grid, where the C# version takes about 2 seconds...

Introduction

This article won't explain how A-Star works, since there are tons of papers out there describing it, you will find one of them here. Instead, it provides you with a straightforward, fast and generic A-Star solver for 2D grids. The sample application just generates a 512x512 sample grid and computes a diagonal path through it, showing the computation time and dumping a PNG with the results into "dump.png".

In this article, I don't want to talk much, but just show you the easy steps to take advantage of A-Star in your application...

Background

I am currently working on a realtime strategy game. Till today, I used the A-Star solver of Gustavo Franco.

But now I recognized that a simple A-Star solver won't do the job in my case. I need a cooperative A-star solver for all those units on the map. The problem is that I couldn't find any implementation out there, so started with my own, based on a university paper. If it is ready, I also plan to post it on CodeProject, but this article is focused on spatial A-star. Gustavo's solver seems to have serious bugs like wallbreaks and suboptimal paths. My first Implementation also had serious bugs, but not only in my code. It seems to be impossible to find working PriorityQueues out there. I tried nearly all of them and almost all are bugged. This is really frustrating when you are relying on such components and looking for the bug in your own code instead!

The algorithm I am going to describe here is as fast as the one of Gustavo (at least with my measures on large grids). But I directly used the Wikipedia pseudo code and translated it into C#. Instead of optimizing the A-Star itself, I just optimized the Queue and Set operations used in pseudo code. This leads to a far better understandable implementation without significant performance losses. The following shows the results of the attached demo application:

dump.png

The pathfinding for this very example completes in 400ms on a "Core i5 Mobile" (which is really slow compared to a usual quad core).

But so far about the background.

Using the Code

When I saw most of the A-Star solvers out there I always thought, why is this so complicated?! After all, I never wrote an A-Star solver myself, till today, but it was rather easy... To take advantage of it, you first need to provide it with a 2D-grid structure (two-dimensional array). This array should be composed of a user defined class deriving from IPathNode:

public class MyPathNode : IPathNode<Object>
{
    public Int32 X { get; set; }
    public Int32 Y { get; set; }
    public Boolean IsWall {get; set;}

    public bool IsWalkable(Object unused)
    {
        return !IsWall;
    }
}

IsWalkable() is called by the search method. The return value is expected to be consistent during search but can change between searches without performance penalties! X, Y and IsWall are not required by IPathNode, we just use them for our convenience. The generic argument for IPathNode denotes the parameter type of IsWalkable (for performance reasons, I go the generic way). You may pass this parameter to every search invocation. This is the first point where my algorithm is very flexible. For example, you could make a "wall" walkable for a tank, but unbreakable for a soldier, without any changes to internal data structures or even using a second path finder instance...

Next you'll have to initialize the search space, the following should be self-explaining:

// setup grid with walls
MyPathNode[,] grid = new MyPathNode[Width, Height];

for (int x = 0; x < Width; x++)
{
    for (int y = 0; y < Height; y++)
    {
        Boolean isWall = ((y % 2) != 0) && (rnd.Next(0, 10) != 8);

        grid[x, y] = new MyPathNode()
        {
            IsWall = isWall,
            X = x,
            Y = y,
        };
    }
}  

The next thing is to create a solver instance. It is important to do this only once, because the initialization is very memory intensive. The second generic parameter denotes the IsWalkable() argument type.

SpatialAStar<MyPathNode, Object> aStar = new SpatialAStar<MyPathNode, Object>(grid); 

This is all setup you need so far. Since optimization, the A-star solver consumes about 50 MB of memory for a 1024x1024 grid. In times of cheap RAM this should be acceptable, but feel free to provide us with further optimizations! The next good thing is that the algorithm scales almost linear. This means when finding a path which goes over the entire grid, let's say 512x512, takes 300ms to complete, it will take around 800ms to complete on a 1024x1024 grid.

Finally, to invoke the search, just call:

 LinkedList<MyPathNode> path = aStar.Search(new Point(0, 0), 
				new Point(Width - 2, Height - 2), null);  

where the first parameter is the starting node and the second, the desired end node of the path. If no path is found, null is returned. The third parameter is directly passed to IsWalkable().

Customizations

By default, the solver is using the Euclidian metric for heuristic and exact distance. To overwrite this behavior, you need to create a subclass of the solver, for example to use the manhatten metric:

public class MySolver<TPathNode, TUserContext> : SettlersEngine.SpatialAStar<TPathNode, 
	TUserContext> where TPathNode : SettlersEngine.IPathNode<TUserContext>
{
    protected override Double Heuristic(PathNode inStart, PathNode inEnd)
    {
        return Math.Abs(inStart.X - inEnd.X) + Math.Abs(inStart.Y - inEnd.Y);
    }

    protected override Double NeighborDistance(PathNode inStart, PathNode inEnd)
    {
        return Heuristic(inStart, inEnd);
    }

    public MySolver(TPathNode[,] inGrid)
        : base(inGrid)
    {
    }
} 

Have fun with this algorithm and let me now about improvements and potential bugs, since I need it in my own gaming engine!

The PriorityQueue was taken from here with some bug fixes and modifications.

License

This article, along with any associated source code and files, is licensed under The MIT License

Share

About the Author

Christoph Husse
Software Developer SecurityRevolutions
Germany Germany
No Biography provided

Comments and Discussions

 
QuestionCan I disallow diagonal movement? PinmemberTevis Woods26-Mar-14 13:35 
AnswerRe: Can I disallow diagonal movement? PinmemberTevis Woods26-Mar-14 13:49 
Generalthanks Pinmembercumthyb13-Mar-14 2:50 
SuggestionCould be faster PinmemberRoy Lee26-Feb-14 2:01 
QuestionRegarding Linked list PinmemberVijay Kumar4-Jul-13 1:15 
QuestionIts Really Fast PinmemberMember 85177711-May-13 16:36 
Questioni want customize your source . help me Pinmembernguyen tung duong9-Apr-13 5:03 
AnswerThanks a lot! Pinmemberarbuzzo26-Apr-12 20:54 
GeneralMy vote of 4 PinmemberJpmon110-Feb-12 2:58 
QuestionHow is the C++ version coming? Pinmembermartin_haas30-Dec-11 11:46 
AnswerRe: How is the C++ version coming? PinmemberChristoph Husse25-Feb-12 5:23 
GeneralMy vote of 5 PinmemberFilip D'haene26-May-11 9:20 
GeneralGood Job PinmemberMember 771284217-Apr-11 22:01 
GeneralRe: Good Job PinmemberChristoph Husse18-Apr-11 7:10 
GeneralTo the f00ls that rated this article a 3... Pinmembercplas16-Mar-11 21:25 
GeneralIt seems not to bring the SHORTEST path PinmemberMember 14506495-Nov-10 1:21 
GeneralRe: It seems not to bring the SHORTEST path PinmemberChristoph Husse7-Nov-10 7:53 
GeneralRe: It seems not to bring the SHORTEST path [modified] PinmemberMember 14506497-Nov-10 22:43 
GeneralRe: It seems not to bring the SHORTEST path Pinmemberukram214-Nov-10 4:19 
GeneralRe: It seems not to bring the SHORTEST path PinmemberDavid Díaz Q.29-Nov-10 0:41 
GeneralRe: It seems not to bring the SHORTEST path PinmemberScott McCain2-Jun-11 13:39 
GeneralRe: It seems not to bring the SHORTEST path PinmemberErik Molenaar21-Apr-11 0:05 
GeneralRe: It seems not to bring the SHORTEST path PinmemberChristoph Husse21-Apr-11 6:35 
GeneralRe: It seems not to bring the SHORTEST path PinmemberErik Molenaar25-Apr-11 7:12 
GeneralMy vote of 5 PinmemberJohn Brett15-Oct-10 4:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.141015.1 | Last Updated 18 Oct 2010
Article Copyright 2010 by Christoph Husse
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid