Tutorial 15 - A* Path Finding

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.
     

15.2 The Search Algorithm

  
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:

1. g(x) - To calculate the cost of moving between two adjacent squares (which can simulate terrain effects i.e. the movement cost); and
2. h(x) - To calculate the distance from the current node to the target node along the path.

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:

1. openList - the surrounding nodes that we need to check as possible path waypoints; and
2. closedList - the list of nodes already checked which are part of the current path.

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.

      

         

15.3 dGenerator - A Level Editor with Path Finding

  

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:

1. When dGenerator fires up, the "Start" button will be preselected and you will be shown a solid grid of bricks which represent obstacles. The four buttons enclosed by the recessed rectangle are sprites which you can place on the grid. You can only select one of these buttons at a time. With Start pressed you can select where you want your path to begin by tapping anywhere on the grid. Only one cell can be selected as the start cell and one as the end cell. The "Path" button will place blue walkable cells. These cells are areas that your character or creep can traverse. The "Wall" button will allow you to place obstacles on the grid.
2. The "Grid" button toggles a grid overlay to assist with sprite placement. The way we implemented this grid was to have a boolean in the cell class which if true draws a rectangle around the cell. 
3. The "A*" button will try and find a path using the A* algorithm from the start cell to the end cell (assuming you have placed these). If it can't find a path then the function will return nil. If a path is found, the co-ordinates of the path will be shown in the Output pane and a red dot will be drawn on each cell which is on the path.

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.  

    

15.4 Downloading the Code and Graphic Assets

     

The following links will download all the code and sprites you need to get dGenerator up and going:

1. The complete code in one file - dGenerator v1.lua
2. The main class - Main.lua
3. The Cell class which represents each square on the grid - Cell_v1.lua
4. The sprite for Button implementation class - Button.lua
5. The A* Find Path functions - FindPath.lua
6. Our standard UIColor list - Colors v1_1.lua
7. A handy function which creates strings from strings, numbers, booleans and tables - ToString.lua
8. All the graphic assets sprites for the grid and button images - dGenerator Sprites

15.5 What Next?

    

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.