So I’ve been working on a dungeon generator for a while now. Tried a few different approaches already like bsp tree and stuff but I’ still haven’t decide which one to use. The current one I’m using though is a little interesting , it’s a corridor first approach , using A* path finding algorithm to create corridors between random start and end points.
I remember implementing A* in a project , it was like 2 or 3 years ago I guess. It was a decent implementation and worked as it should but this time , I wanted something better and something elegant so I start looking for A* articles before jumping into code and found an A* article by Eric Lipper himself!
It was quite surprising as I follow Eric Lippert’s Fabulous Adventures in Coding closely for a long time now and haven’t seen this one before. For those who don’t know Eric Lippert , he’s a principal developer on the Microsoft Visual C# compiler team and a very good & active blogger.
After reading his Path Finding Using A* in C# 3.0 series ( 4 parts ) , I knew I had to implement it. It works perfectly , looks so elegant and extremely easy to manage ( like switching heuristic function etc) .
I won’t go into the A* details here , I’ll only talk about my implementation of Eric Lippert’s sample. I said “my implementation” as I had to change some stuff in order to make a stand-alone example/solution without any big dependencies ( like a grid structure to work on etc ) so if you want the original.
First of all , let’s take a look at some helper classes Eric Lippert used. There are 2 classes the used and first one is Path<T> ;
{
public T LastStep { get; private set; }
public Path<T> PreviousSteps { get; private set; }
public double TotalCost { get; private set; }
private Path(T lastStep, Path<T> previousSteps, double totalCost)
{
LastStep = lastStep;
PreviousSteps = previousSteps;
TotalCost = totalCost;
}
public Path(T start) : this(start, null, 0) { }
public Path<T> AddStep(T step, double stepCost)
{
return new Path<T>(step, this, TotalCost + stepCost);
}
public IEnumerator<T> GetEnumerator()
{
for (Path<T> p = this; p != null; p = p.PreviousSteps)
yield return p.LastStep;
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
This path class , using generic type , is the actual path or corridor we are trying to create. It has 3 properties , LastStep ( or tail ) is the last point of the path ( ending ) , PreviousSteps is yet another Path containing all previous points and the TotalCost which calculates total movement cost from start to finish. Think of this Path class as one simple node packaged with the other nodes before himself ( we’ll use it this was later on in the actual A* implementation )
Second one is a Priority Queue. Priority queue is a structure very similar to queue , just one obvious difference , items hold in queue are ordered by their priorities. Remember in A* we always have a pool of possible next points and select the “best” one from that pool in each step? This queue is that pool and the priorities we’ll set are the values ( cost + heuristic ) of those points.
And this is the PriorityQueue implementation ; ( I directly copy&pasted from Eric Lippert’s blog , even the comments are his very own comments. )
{
private SortedDictionary<TP, Queue<TV>> list = new SortedDictionary<TP, Queue<TV>>();
public void Enqueue(TP priority, TV value)
{
Queue<TV> q;
if (!list.TryGetValue(priority, out q))
{
q = new Queue<TV>();
list.Add(priority, q);
}
q.Enqueue(value);
}
public TV Dequeue()
{
// will throw if there isn’t any first element!
var pair = list.First();
var v = pair.Value.Dequeue();
if (pair.Value.Count == 0) // nothing left of the top priority.
list.Remove(pair.Key);
return v;
}
public bool IsEmpty
{
get { return !list.Any(); }
}
}
And we need one last helper class before we move into the actual A* , a grid for our calculations. Obviously you don’t need a grid for A* , it can be any sort of structure with randomly connected nodes but of course grid is the simplest. This is my implementation to make it a stand alone project.
{
public static float BigBlockSize = 1;
public Vector3 Point { get; set; }
public Block(Vector3 point)
{
Point = point;
}
public IEnumerable<Block> Neighbours
{
get
{
return new Block[]
{
new Block(new Vector3(Point.X + BigBlockSize, Point.Z)),
new Block(new Vector3(Point.X – BigBlockSize, Point.Z)),
new Block(new Vector3(Point.X, Point.Z + BigBlockSize)),
new Block(new Vector3(Point.X, Point.Z – BigBlockSize)),
};
}
}
}
If you can get over the incredibly uncreative name , there are few things to explain here.
First of all , what is BigBlockSize? It’s pretty much the base cost of moving from one node to another. Check this out ,
Notice you may have grid with much smaller squares but if you set BlockSize as anything bigger than 1 , your path will follow every n’th square to calculate the path. I needed this as I’m using this to create corridors , remember?
Then we got a Vector3 Point , I just created a small Vector3 class to wrap X and Z coordinates ( I’m working on XNA these days and Y is UP in DirectX ) of the points.
Oh we also got a simple interface , IHasNeighbours , it’s a very simple interface that contains Neighbors and Point.
{
IEnumerable<N> Neighbours { get; }
Vector3 Point { get; }
}
And last but not least , we have a Neighbors property that returns 4 other Blocks around current one. Obviously returning 4 new objects for every node is overkill but I decided to do it this way as your project will have your own grid structure anyway so you won’t need this part.
OK I guess we’re done with helper classes so now the real deal , actual implementation of A* !
I highly suggest you to read at least the first part of the Eric Lippert’s A* series , he explains it very well. Here is the method ;
T start,
T destination,
Func<T, T, double> distance,
Func<T, T, double> estimate)
where T : IHasNeighbours<T>
{
var closed = new Dictionary<int, T>();
var queue = new PriorityQueue<double, Path<T>>();
queue.Enqueue(0, new Path<T>(start));
while (!queue.IsEmpty)
{
var path = queue.Dequeue();
if (closed.ContainsKey(path.LastStep.Point.GetHashCode()))
continue;
if (path.LastStep.Point.X == destination.Point.X && path.LastStep.Point.Z == destination.Point.Z)
return path;
closed.Add(path.LastStep.Point.GetHashCode(), path.LastStep);
foreach (T n in path.LastStep.Neighbours)
{
double d = distance(path.LastStep, n);
var newPath = path.AddStep(n, d);
queue.Enqueue(newPath.TotalCost + estimate(n, destination), newPath);
}
}
return null;
}
This is a method that takes start and end points , a distance function , an estimate function and returns a path.
We have a dictionary “closed” for visited blocks ( Eric Lippert used Hashset in original implementation but I prefer Dictionary for node based systems as I’ll eventually need to find stuff by key. It’s just a personal preference , you’re perfectly fine with Hashset in this example too of course. ) and a priority queue.
And this is pretty much how it goes , we start by adding start point to the queue and then start a while loop.
In this loop ,
we dequeue and get the “best” block in the pool
if that block is already in the closed dictionary , we move on to the next best block
if that block is the destination point , we return the path ( result )
and if both statements above are false , we move on to adding this new block to the path ;
we add this new block to the closed dictionary
and add all it’s neighbors to the queue to process later
And that’s all. Now it’ll eventually reach the destination node and return the path back. Be careful with one thing though , if you change the BlockSize value , your destination coordinates must be on this new Grid using new BlockSize. In other words , destination X & Z must be divisible by BlockSize or it won’t be able to get to the destination point. Of course you can also add a check for that , like if current node is closer than any other nodes etc but that’s all up to you.
Oh and one last thing , distance and estimate functions. As I said before I used Manhattan distance for those, it’s pretty much like the simplest estimate function ever. If you will use A* to actually calculate paths for game characters or something , you’ll probably need something more complex with tie breakers etc etc.
{
return Math.Abs(start.Point.X – end.Point.X) + Math.Abs(start.Point.Z – end.Point.Z);
}
public static double Heuristic(Block start, Block end)
{
return Math.Abs(start.Point.X – end.Point.X) + Math.Abs(start.Point.Z – end.Point.Z);
}
That pretty much sums it up. I highly suggest reading Eric Lippert’s A* posts and his blog in general too ( his blog is just simply awesome and probably the best C# blog out there ). But if you really want to go deep in the path finding theory and how things works , then you MUST read Amit Patel’s incredible work on the topic . As far as I know it’s the best source you can find to learn how path finding works. Theory , examples , explanations , everything is there!
Oh and in case you’re curious about my corridors , here they are!
.jpg "DungeonTest (14)")
I also connect multiple corridors to create a network as you can see , it’s all based upon the codes above.
You can find the sample below , it doesn’t include the visuals ( in picture above ) of course. It’s just a simple console application that calculates the path , but you can see all those code in work.
Hope you like it or at least find it useful! Goodbye until the next post!
Visual Studio 2010 Solution