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.

Tutorial 14 - SpaceWar! & Extended Ship Class

   

14.1 The Extended Ship Class

    
In Interlude 11 we introduced a ship class. We will use this to explore some new concepts in game design. In particular we will look at:

1. Using a mesh to represent our ship image;
2. Simple path finding for our ship;
3. The use of polar co-ordinates to determine the angle and distance to a destination point; and
4. Simple collision detection by testing for the intersection of two bounding rectangles.

The updated ship class is shown below. This class will automatically move your selected ship to a point that you tap on the screen. The init() function sets up the following variables:

   

x, y -  Are the screen co-ordinates of the ship. Depending on the mode variable, these will refer to either the bottom left of the bounding rectangle (CORNER) or the centre (CENTER). If x and y aren't specified in the constructor then (0,0) is assigned because nil evaluates to false and hence the second parameter in the "or" construct is assigned. We use this trick for all of the specified init() parameters to provide default values.

  

enemy - is a boolean. If true the ship will be drawn in red and wont be selectable.

  

heading - is the bearing in degrees that the ship will point towards. 0 (the default) positions the ship facing right. A value of 180 degrees will face the ship left.

    

speed - determines how far the ship will move each frame (if it is moving which is determined by the boolean shipMoving).

   

width and height - refer to the rectangle which bounds the ship. Changing these will alter the dimensions of your ship.

    

selected - a boolean which indicates whether the ship has been selected. You can select one of your ships by tapping it. A selected ship will be indicated by a rectangle drawn around it. Tapping the same ship again will deselect it.

  

imageMesh - is a mesh containing the representation of your ship. It is built up using two overlapping triangles.

  

destination - this variable is a vec2 which contains the (x, y) co-ordinates of the point you want to move the ship to. If the boolean shipMoving is true then this class will automatically move its ship object towards this point every frame. Initially this variable is nil.
  

      

The Ship class currently contains three functions to provide the appropriate ship behaviours. We will look at each of these in turn.

  

Ship:updatePosition() - if the ship is moving, this function provides a simple path finding algorithm to move the ship towards the destination co-ordinates. In addition, it will automatically point your ship in the right direction. It does this by working out the polar co-ordinates of the destination using the current ship position as the origin. The two variables returned by math.polar (found in the Math tab of the project) are the distance from the ship to the destination and the angle (or heading). We use the distance to determine when to stop moving the ship. When the distance is less than the width of the bounding box we are roughly where we want to be. If we try to get much closer the angle starts getting a bit wonky. The angle is assigned to the heading class variable and is used to rotate the ship in the right direction when we draw it.

Ship:draw() - is responsible for drawing your ship each frame. If the ship is moving (shipMoving is true) then we first call the Ship:updatePosition() function to calculate the new ship position (x, y). We then translate to the new ship position and rotate the ship to the current heading. If the ship is selected a green rectangle will be drawn around the ship. The last thing we do is draw() the mesh (imageMesh) which represents the ship.

  

Ship:touched(touch) - This function does the touch handling. We only use this function for our own ships not enemy ships. Tapping your ship will toggle its selection. If there is a tap on another part of the screen when a ship is selected, it will start moving towards that point. This is achieved by setting shipMoving to true and assigning the destination co-ordinates. The pointInRect() function (found in the Math tab) determines whether the current tap was on the ship.

    

14.2 The Main Class

       

The Main class is very simple. We create two ships in init() and our twinkling star background using the old favourite Twinkle class. In the touched(touch) function we pass on the touches to both ships and in draw() we draw the twinkling stars and the two ships by calling their associated draw() functions.

The only other point of interest is the simple collision detection provided by the intersectRects() function (found in the Math tab). At the moment, if there is a collision between ships we just print out "BANG!!!" This will be enhanced in later versions of the program.

        

14.3 Download the Source Code

       

As usual, the source code for this tutorial may be downloaded from dropbox using the following links.

   

1. Main Class - described in section 14.2;

2. Ship Class - described in section 14.3;

3. Math File - which contains a number of helper & collision detection functions;

4. Colors File - which defines some standard colours; and

5. Twinkle Class - which provides our background star field.

        

14.4 Problems with this Design

      

This code is functional but it has some issues. In no particular order these include:

1. Our ship speed is dependant on our frame rate. In a later tutorial we will look at methods we can use to move our ship at a constant speed regardless of the frame rate.
2. The path finding algorithm is rudimentary at best. It doesn't handle obstacles, different "terrain" or take account of enemy positions. Our next tutorial will develop the A* path finding technique which is much more sophisticated.
3. Collision detection is very rough. As with the other issues we will evolve our collision detection in subsequent tutorials.
4. The selection methodology when there are multiple own ships is a bit flakey.
5. Portrait orientation is not handled properly.

All of these issues will be addressed in subsequent tutorials.