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

• Download source - 97.36 KB

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:

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.