• Overview
• Installation
• Configurator
• Animation
• Framework
• Tutorial

• Start
• Article 1
• Article 2
• Article 3
• Article 4
• Article 5
• Article 6
• Article 7
• Article 8
• Article 9
• Article 10
• Article 11

This menu will stay fixed with a proper browser.

Introduction

In the previous lesson we added the enemies. This lesson is a departure from the game to learn about the A* path-finding algorithm. The idea being that we can concentrate purely on path finding without the complexity of the game.
There are actually two projects/makefiles in this lesson:

• The first contains no A* at all, purely a little program to draw a maze and random blocks
• the second contains the A* path-finding

It is done like this so that we can differentiate between path-finding and the program that uses the path finding.

Test 1: Structure

If you are manually creating the project make file then use the one from lesson 8, delete all the game_*.* files and mappyal.c (i.e. just leave the axl*.* files) and then add test1.cpp. The end result is a makefile that compiles the following files: axl_animations.cpp, axl_config.cpp, axl_framework.cpp, test1.cpp
Note: Alternatively there is a version of test1.cpp, called test1_no_axl.cpp, that is pure allegro code and does not use the AXL system. i.e. you can just compile the one source file (with allegro). This is useful if you are here not for the TransAm tutorial, but somehow found this A* tutorial.

Test 1: Objectives

In test 2 we will be programming an A* path-finding system - i.e. generating the best possible route from A to B, avoiding obstacles. We will do this by creating a simple program that lets the user draw random blocks on the screen and a start/end point. Just to make it more interesting we will be adding a maze generator as well.
The program will let the user generate one of two blocks (a wall and a hedge) that cannot be passed. They are both treated the same within the program, they are here purely to show that you can have different block types in your map.
Compile/run the program and have a play. You can see that there are various methods of filling in the map - by hand, by randomness, by a maze generator. When we integrate the A* path-finding code we will be generating a path from the start (S) to the end (E).

Test 1: Map

The map is a 2-dimensional array, int MapGame[MapHeight][MapWidth]. The size is 29x30 blocks. We will not be explaining the main() function as it is just a standard function to run the program. The map is this size because we are drawing to a 640x480 screen and need space for the menu.
InitialiseData() method creates our two bitmaps for the blocks that populate the map (hedge/wall - each block is 16x16 pixels), and empties the map using ClearGameMap function.
Our map consists of an array of integers, that can be either 0 (empty), 1 (a wall), or 2 (a hedge). When we place a hedge or a wall or clear the cell we simply update the array with that value, this is shown in the ProcessKeys function for SETNONE, SETWALL, SETHEDGE.
The random options simply clears the map then places random blocks on it.

Test 1: Maze

The maze is a class called Grid. The Grid class is defined in the test1.h file. Internally it consists of linked list (MazeSquare) that contains x/y co-ordinates.
The method of creating a maze is as follows, and contained within the GenerateMaze function:

1. Create a new Grid object passing in the size of your maze and an array of that size. In our case we are passing in our Map (MapGame variable).
2. Tell the Grid the create a maze (Grid::GenerateMaze method)
3. Retrieve the start and end Y locations using Grid::GetStartY and Grid::GetGoalY methods
4. In our maze we are always using the leftmost and rightmost edges of the maze for the start and end point

Calling GenerateMaze populates the array you passed in with either 1 (a solid block) or a 0 (an empty block).
The internals of the maze are not necessary for using the program (or generatting your own maze), but you can see that it's pretty straightforward and will easily integrate into any code.
However, it works by using a path-growing (randomised depth-first) algorithm. Note, if you look at the Grid::GenerateMaze method you can uncomment the random seed to produce random mazes every time. I just left it out as having the same first maze seemed the best thing to do for this program - you also need time.h if using the seeder.
For information on various maze generating algorithms, see wikipedia

Test 2: Structure

If you are manually creating the project make file then use the one above but change the source file from test1.cpp to test2.cpp
Note: Alternatively you there is a version of test2.cpp, called test2_no_axl.cpp, that is pure allegro code and does not use the AXL system. i.e. you can just compile the one source file (with allegro). This is useful if you are here not for the TransAm tutorial, but somehow found this A* tutorial.

Test 2: Objectives

In this lesson we will be applying the A* path-finding algorithm to the code to find a path from the start (S) tile to the end (E) tile.
First, compile the code and run it. There are two new options available:

1. Generate Route 1: this generates a path and allows diagonal (8-way) movement
2. Generate Route 2: this generates a path and only allows straight (4-way) movement

Test 2: AStar Algorithm

Firstly, an apology for those who know a lot more than me. What follows is a simple guide to A* and by no means represents a thorough analysis and may contain some inaccurate information!
AStar algorithms determine a route by taking two factors into account. The first is the distance it has already travelled, and the second is a 'heuristic' (a guess) to estimate the distance to the goal. While it is the distance already travelled that makes the A* algorithm better than other path-finding algorithms (e.g. Dijkstra's algorithm that searches in all directions regardless), it is the heuristic that provides the algorithm with the choices of where to go next. A drawback of this algorithm is that it will always pick the shortest route, which may not be as aesthetically pleasing as you might hope for.
The formula applied (in finding the path) seems rather simple on the outset: f=g+h. 'h' is the heuristic and 'g' is the distance already travelled. What this gives us is a score for each node. From this it can work out the best path by discounting the high value 'f' values for each node. What the AStar class does is generate a list of possible paths, then picks the best one. These are sometimes called the 'open' and 'closed' lists, i.e. it knows which nodes (locations) it has been to and which ones it hasn't and uses these to determine which way to go next in searching.
As you might think, it is the 'h' (the heuristic) that both determines the speed and the accuracy of the search. If we didn't use 'h' then we'd end up with Dijkstra's method which will find the shortest path, but at the expense of doing a very wide search. This means the lower we set 'h' the more nodes are searched and the more accurate the search, but takes longer, and the higher we set 'h' the less nodes are searched and the less accurate the search, but it is much faster.
One way of speeding up the search is to use waypoints, i.e. instead of searching the entire map for a path, have a number of locations on the map that we can use instead and whatever object is using the path-finding will navigate between the waypoints it knows about. Obviously, how wide an area you do a search (A to B route) is a major factor that determines the speed of the algorithm, which is probably best tested in code. However an area of 40 tiles is not an unreasonable amount.

Heuristics

There are a number of ways of calculating this heuristic:

• Manhatten: Most A* routines use this. It is the minimum distance from where we are (i) to the goal (j), e.g. (i.x-j.x)+(i.y-j.y) - this is usually multiplied by a factor representing the cost of moving a standard space. This is a 4-directional method only
• Diagonal: Similar to Manhatten but allows diagonal movement, calculated by the max of x and y
• Euclidean: If we can use any angle, rather than fixed tiles then we can use pythagorus

For further information I'd recommend you visit one of the links below, the first one (Patrick Lester) is particularly pleasing to us with smaller brains. The A* code found here was taken from the code at AGDN (website down/unknown/changed) by DanielH and modified slightly for our needs.

Links

• Patrick Lester : This is my favourite as it's explains things graphically and simply
• Amit's : Probably the most read and exhaustive collection of A* and path-finding tutorials
• Justin Heyes-Jones : A quick intro to A*, but more importantly has a unique way of implementing A* by using it to solve a sliding puzzle game rather than a tile map for a game

Test 2: Objectives

To put it in context, we (hopefully) want a black-box solution that will give us a path from A to B. We want the solution to be as simple and easy to use as possible, and we want to be able to modify the code to match any of our requirements (e.g. changing the heuristic).
The algorithm supplied should hopefully do that, and to use it we do the following:

• Generate an array of integers representing blocked and open tiles (i.e. tile locations that we can go through and tile locations we cannot)
• Create an object of type AStarClass (this is our AStar algorithm) giving it our map as a read-only reference so that it can generate it's own internal representation
• Repopulate the array/inform the AStarClass whenever the map it represents changes, e.g. a once open tile becomes blocked)
• Call an AStarClass method (in our case NewPath) to generate a path between the given start and end locations
• To navigate the path we can use some AStarClass methods such as NodeGoFirst, ReachedGoal, PathNextNode, NodeGetX and NodeGetY

These are all described next.

Test 2: Code Walk-Through

In the header file, test2.h, we are adding three functions to wrap up the AStarClass algorithm:

• GenerateAStar: This will generate our path
• ReInitialiseStarMap: this will update the map array
• DrawAStarRoute: traverses the path to draw the route on the screen

The A* routine needs (read-only, it does not modify) an array representing the tile map. It is a simple integer based array representing zero for empty tiles and any non-zero for a blocked tile. Although in our maze this is all our map consists of and we could simply pass in our maze array, in the Trans-Am game, the the map is much more complicated so we will be generating a simpler version. For this reason we are doing the same in this lesson.
Obviously this means we cannot add weightings for different tiles, but that is easily modifiable, and is described below. Whether we do this in the game remains to be seen :)
The variable MapAstar[MapHeight*MapWidth] is created and matches that of our MapGame we are using for the maze.
In other words, we have our version of the map (MapGame) and an AStarClass friendly version (MapAstar), and we need to keep them synchronised. In the TransAm game MapGame will be the Mappy map, which is much more complicated, and shows why we need to have the two different versions (described in the next lesson).
We initialise the array by matching array elements with the maze array, storing 1 or 0 for a tile or no tile. This is handled by the function ReinitialiseStarMap and is called on starting the program and every time the A* map is generated: Our A* algorithm is represented by the class AStarClass and is held entirely in the files game_astar.h and game_astar.cpp. Note, the two arrays are the same, just the AStarClass version is a 1-dimensional array rather than 2-dimensional
Whenever we want to generate a path we call our GenerateAStar function (that takes a parameter to indicate if diagonal movement is allowed). This function firstly calls the ReInitialiseStarMap function to regenerate the array, we then call the AStar method, RedoAstarTileMap, passing in our array. This initialises our A* object ready for path-finding. When we want to generate a path we call the member function NewPath, passing in the start and end X/Y locations and the diagonal flag: The only odd thing there is the BlockSize multiplier. When we initialised our astar class we passed in the size of the array and the size of each tile. The A* algorithm we are using works in pixels. This will become apparent when we integrate the A* algorithm into the game.
In our MazeDraw function we call DrawAStarRoute. In this function we traverse our A* object's found path and for each item (known as a node), we output a '*' at it's location. We traverse the path as follows: NodeGoFirst() resets the path to the first item, ReachedGoal() tells us if we have reached the end, NodeGetX/NodeGetY retrieves the node's x/y location in pixels, PathNextNode() goes to the next item in the list. In our code we have a few extra lines of code to stop the '*' from overwriting our map labels 'S' and 'E'

Recap

• Create a integer based array for representing the map
• Create AStarClass object giving it the array as a reference point
• If we ever change the map, call RedoAStarTileMap method
• To generate the call the NewPath method
• To navigate the found path use ReachedGoal method to see if we are there, use PathNextNode method to go to the next node, use NodeGetX/Y methods to retrieve the x/y location in the node we are in. All locations are in pixels

Modifications

If we wish to alter the algorithm to take into account weighted tiles (e.g. some tiles may be passable but have a higher cost, e.g. represents a tile that slows down the player), we need to alter the AStar class:

• The heuristic (h) is calculated using the Euclidean (hypotenuse) method. This is shown in the FindPath method of the AstarClass, as well as the GenerateSucc method. Either adjust these lines or the 'distance' method. In the code you will see two versions of distance, the commented version returns the pythag version, the uncommented the Manhatten.
• Weightings can be added by multiplying all references to g and h (i.e. '->g' and '->h' in the code) by the TileMap value. TileMap is it's array taken from our map array

To be honest, the 'diagonal' flag passed in to the AStar algorithm NewPath should really alter the heuristic to calculate using Manhatten or Diagonal. What it actually does is calls the same euclidean (pythagorus method) but skips checking the diagonal nodes.

Allegro

Just to recap, we've learnt a little bit about the A-Star algorithm and made a program to test it out.

Next

The next lesson we will be using the code from this lesson and applying it to our game to find the best path from the enemy cars to the player.