Click here to Skip to main content
15,355,605 members
Articles / Programming Languages / C#
Posted 13 Oct 2010

Tagged as


59 bookmarked

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

Rate me:
Please Sign up or sign in to vote.
4.79/5 (29 votes)
18 Oct 2010MIT5 min read
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...


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


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:


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().


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.


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


About the Author

Christoph Husse
Software Developer SecurityRevolutions
Germany Germany
No Biography provided

Comments and Discussions

QuestionC++ Fast A Star 2D Implementation Pin
Anden Castillo18-Nov-20 14:11
MemberAnden Castillo18-Nov-20 14:11 
Suggestionnice code Pin
stjrna10-Jun-20 9:59
Memberstjrna10-Jun-20 9:59 
QuestionOn/Off diagonals Pin
Member 1026255214-Aug-18 12:24
professionalMember 1026255214-Aug-18 12:24 
GeneralMy vote of 5 Pin
Member 1026255214-Aug-18 12:22
professionalMember 1026255214-Aug-18 12:22 
BugYour fix is here. Pin
Member 134943372-Nov-17 10:04
MemberMember 134943372-Nov-17 10:04 
PraiseUnity optimization tip Pin
Member 1336435616-Aug-17 10:38
MemberMember 1336435616-Aug-17 10:38 
QuestionSweet! Pin
It's Eddie!7-May-16 2:00
MemberIt's Eddie!7-May-16 2:00 
QuestionNot the shortest path Pin
Member 40585963-Nov-15 4:02
MemberMember 40585963-Nov-15 4:02 
AnswerMuch better than my own Pin
testees13-Oct-15 4:44
Membertestees13-Oct-15 4:44 
QuestionCan I disallow diagonal movement? Pin
Tevis Woods26-Mar-14 13:35
MemberTevis Woods26-Mar-14 13:35 
AnswerRe: Can I disallow diagonal movement? Pin
Tevis Woods26-Mar-14 13:49
MemberTevis Woods26-Mar-14 13:49 
GeneralRe: Can I disallow diagonal movement? Pin
htmlmaster1-Sep-17 4:16
professionalhtmlmaster1-Sep-17 4:16 
Generalthanks Pin
cumthyb13-Mar-14 2:50
Membercumthyb13-Mar-14 2:50 
SuggestionCould be faster Pin
Roy Lee26-Feb-14 2:01
MemberRoy Lee26-Feb-14 2:01 
GeneralRe: Could be faster Pin
Psytec16-Oct-15 6:50
MemberPsytec16-Oct-15 6:50 
QuestionRegarding Linked list Pin
Vijay Kumar4-Jul-13 1:15
MemberVijay Kumar4-Jul-13 1:15 
QuestionIts Really Fast Pin
xXTariqoO1-May-13 16:36
MemberxXTariqoO1-May-13 16:36 
Questioni want customize your source . help me Pin
nguyen tung duong9-Apr-13 5:03
Membernguyen tung duong9-Apr-13 5:03 
AnswerThanks a lot! Pin
arbuzzo26-Apr-12 20:54
Memberarbuzzo26-Apr-12 20:54 
GeneralMy vote of 4 Pin
Jpmon110-Feb-12 2:58
MemberJpmon110-Feb-12 2:58 
QuestionHow is the C++ version coming? Pin
martin_haas30-Dec-11 11:46
Membermartin_haas30-Dec-11 11:46 
AnswerRe: How is the C++ version coming? Pin
Christoph Husse25-Feb-12 5:23
MemberChristoph Husse25-Feb-12 5:23 
GeneralMy vote of 5 Pin
Filip D'haene26-May-11 9:20
MemberFilip D'haene26-May-11 9:20 
GeneralGood Job Pin
Member 771284217-Apr-11 22:01
MemberMember 771284217-Apr-11 22:01 
GeneralRe: Good Job Pin
Christoph Husse18-Apr-11 7:10
MemberChristoph Husse18-Apr-11 7:10 

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

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