A* (pronounced A star) is an algorithm for calculating an efficient path between two points
15.1 The Starting Point
In the previous Tutorial we implemented a very simple path finding algorithm which added or subtracted from our current (x,y) co-ordinates until we ended up at our target co-ordinates. As pointed out at the time, this approach has its limitations (e.g. it can't handle obstacles or differing terrain). There is a better way.
A* (pronounced A star) is an algorithm for calculating an efficient path between two points. This is useful for a variety of games like the real time strategy and the tower defence genre (not to mention route finding for robots and GPS devices). To illustrate how it works, assume we want to get from point A to point B. We want to be able to handle obstacles and different terrains. In order to work out the best route we divide the search area into a two dimensional grid, this allows us to represent the search area by a two dimensional array. Each item in the array represents a square on the grid which can have a state of walkable or un-walkable (if it contains an obstacle). Our path can then be represented by a list of the squares which we take to get from A to B. We could then use this in our SpaceWar! game to move the ship along the centre of each square until it reaches the destination. The centre of the square is defined as a node.
A* uses a best-first search and finds a least-cost path from our starting node A to the target node B. This is called a distance plus cost heuristic. To do this it uses two functions:
By overlaying a grid on the search area we have reduced the problem to a manageable number of nodes. The simplest approach to selecting a square size is to choose the same dimensions as your game sprites. This is not essential, it all depends on how much resolution you want your path to have and this will be related to how quickly the algorithm can traverse the paths and deliver a solution. The bigger the grid squares, the less precision in the path but the faster the algorithm will return a result. As with most engineering problems it will be a tradeoff (in this case between precision and speed). Note that you don't have to use a square grid, hexagon or rectangles are equally valid and the nodes can be placed at any point in your grid. Our test App uses squares which are 32 x 32 pixels in size on a 15 x 15 grid and the corresponding search is very quick even on an iPad1.
Starting at A, the algorithm searches outwards until it finds B, all the while keeping track of the path lengths so it knows which are the shortest and quickest. We will use two tables to keep track of things:
Initially the start cell A gets added to the open list. The algorithm then examines all of the adjacent cells and if they are passable (i.e. not a wall or some other illegal terrain), they get added to the open list. Cell A then gets removed from the open list and added to the closed list as the first step along our path.
We then select the cell with the lowest f(x) score (which is referred to as the current square i.e curSquare in the code) and repeat the process. Note that f(x) is defined as:
f(x) = g(x) + h(x)
The path is thus generated by repeatedly going through the openList and selecting the cell with the lowest f(x) score. As mentioned above, h(x), is an estimate of the distance from the current cell to the end cell along the shortest path. There are many different ways to calculate h(x), we will use the simple approach of adding remaining distance in the y direction to the remaining distance in the x direction. Our algorithm currently only allows horizontal and vertical movement (not diagonal - which will be added in a subsequent tutorial).
We have ported across a Corona implementation of the A* algorithm which was a trivial exercise since it already uses Lua. Adapting it to the MineSweeper cell class was simply a matter of changing their board table variable from isObstacle to using our cell state variable.
To illustrate the A* algorithm in action we will produce a simple level editor which could be used for a tower defence, RTS or dungeon crawler type game. To represent the game board we will reuse the MineSweeper grid code to save us some time. A collateral benefit of this tutorial is that it will demonstrate one way to use pre-rendered sprites as buttons.
You can use this App as follows:
We created the sprites using Sprite Something on the iPad and really recommend this as a tool for sprite development. Sprites can be saved directly to DropBox which is great for use with Codea.
The following links will download all the code and sprites you need to get dGenerator up and going:
The dGenerator level generator is ok for demonstrating the A* path finding algorithm but not much else at this stage. The next step is to allow the levels to be saved and then loaded by your game. Some extra sprite types would also be handy as would the ability to move diagonally. We will create a simple tower defence game to illustrate this functionality.