The first thing I want to be able to do in MicroQuest is move my "unit" around the "game world". So I need to establish a mechanism for the movement of the unit.
Given this is a tile based game then it seems obvious that my unit can move a certain number of tiles per turn. Taking my cue from GBA games such as Advance Wars then those games use (at least something similar to) the A* algorithm to perform pathfinding and costing on a map. I just need to code up a generic A* algorithm (it won't be super optimal) to provide the movement capability for my unit.
The AStar class only needs to perform one job, and that is to solve the current path from a starting location to a goal location.
I'm not going to describe how the AStar algorithm works - you can see that in the Wikipedia article, suffice to say that it relies on a sorted set of costs for a given 'node' in a search space (in other words, a tile on the map has a cost which is an assessment of its value as a possible solution).
To make AStar efficient, we try to ensure that we trim the available set of nodes such as those that have already been evaluated. These are kept in the lists of open and closed nodes. So, our AStar class looks like:
The costing algorithm can vary according to need, but the easiest heuristic for a square tile map is that of 'Manhattan Distance' which calculates how many blocks away from a goal a given node is using some basic maths. (In a regular space, then Euclidean Distance may be preferable). I've implemented this as a simple strategy pattern. Not so much because I'm likely to change the algorithm: just for clarity/intent.
The 'Node' is the main class we need. A node essentially wraps a tile on the map (which I'm calling a Location at this point, as Tile has UI connotations).
A Node knows where it is (from its Location) and can assess its cost. This is described as f = g + h which means: total cost = cost so far + estimated cost to goal.
It's important to understand the cost so far and the estimated cost separately as the actual cost may differ from the Manhattan distance heuristic. (For instance, on a tile map, the tiles may have differing movement costs representative of the 'terrain' of the tile).
Finally, a Node can return its 'children' (or neighbours I suppose). And it can generate the path from itself to its origin.
LINQ comes in really handy here as you can see. The GenerateChildren method doesn't just return all possible children. It will also trim that set for those locations that are not passable (obstacles or some such).
This leaves the core of the AStar Solve method looking something like:
Finally, the GetPath method on a Node will return a list of co-ordinates (it could also just return a list of nodes, or locations. That may be helpful later on but this will do for now.
Testing this is straightforward. Creating a simple 10x10 map and then solving various paths (with and without obstacles) are the basic tests needed.
Now this is written, I need to be able to interact with the map in a UI and build on the work so far thinking about Locations and Units. So I'll kick up a WPF application to do just that.
In the process of this, I came across this excellent guide on AStar from the smart chaps at Vertigo. I toyed with the idea of using that implementation, but decided I didn't need the flexibility that it offered and I was also keen on implementing AStar as I understand it which is not necessarily the correct way, but it works for me... ;)
Ah, and then I discovered Eric Lippert's 4 part series on implementing A* in C#3.0. Oh well, done now!
Technorati Tags:
wpf,
game,
microquest