Posted on by

.

Putting A* to the Test

A* has many uses in game development. The best way to explain it is with a certain type of game — tower defense! In these games, a minion spawns at a certain location, point A. It has to get to the player’s base to damage it, point B. However, the player has placed obstacles around the map to stop the minions so the minion has to find the best path around the obstacles to get to the base. This is where A* comes in. So enough of what it’s supposed to do, let’s see it in action using Lerg’s A* pathfinding module.

In this tutorial, I will be building up a grid of cells. A white cell is a road, i.e. a free space that a minion can navigate on. Red cells represent walls that are impassable. The user first touches a white cell to set the start point, then touches another white cell to set the end point and then touches the screen anywhere to find the path from the start cell to the end cell (screenshot is at the bottom of this tutorial). So let’s get to the code.

Creating the map

The pathfinding module expects a 2 dimensional array representing the map. It should be noted however that the index of the array starts at 0. This differs from the conventional Lua table index that always starts at 1. This is a requirement to use the pathfinding module. Just keep that in mind.

The level will contain a series of 1′s and 0′s x cells wide by y cells tall. For this tutorial, rather than typing out a bunch of 1′s and 0′s in a table, I chose to randomly generate the dungeon…err…I mean map.

Building the Map Table

The first thing we have to do before we start building the map is determine how big we want to make it. I kept things easy and just defined a couple of “constants” that we can change in our code at the top of our main.lua file.

local kLevelRows = 50
local kLevelCols = 50

Since this is a randomly generated dungeon, it would be nice to also control the probability of generating a road. That way we could generate a map that has just a few roads, or generate a map that has a lot of roads. Again, we define another constant. This will be an integer value from 0 to 10 with 0 meaning no roads (all walls/red cells) and 10 meaning all roads (and no walls/red cells).


local kRoadProbability = 6

Let’s not forget to define our initial level table that we will be building.


local level = {}

Now we’re ready to build the map. The algorithm for this is extremely simple so really no explanation is necessary. We create a buildGrid() function which will build the map table and then following this section will build the display objects for the individual cells. Here’s the first part of the buildGrid method that builds our randomly generated map.


-- builds our grid --
function buildGrid()
-- build map array --
for x = 0, kLevelCols do
level[x] = {}
for y = 0, kLevelRows do
local probability = math.random(0,10)
if probability < = kRoadProbability then
level[x][y] = 1
else
level[x][y] = 0
end
end
end
end

Pretty simple. For the number of columns (x values) in the table we generate each row by setting individual cells (level[x][y]) to either 1 or 0 based on our simple probability condition.

Building the Screen

Now that we've built the map, we can actually build the UI for our sample program. Again, this will follow the same pattern. We enumerate through each row and column and for each cell that we encounter, we create a new display rectangle (display.newRect). Based on whether that cell in our level table is a 1 or 0, we either leave it white or set it to red if we encounter a 0 (wall) in the map. The entire buildGrid method is as follows (note that this contains our map building loop and our UI cell building loop:


-- builds our grid --
function buildGrid()
-- build map array --
for x = 0, kLevelCols do
level[x] = {}
for y = 0, kLevelRows do
local probability = math.random(0,10)
if probability < = kRoadProbability then
level[x][y] = 1
else
level[x][y] = 0
end
end
end

-- build screen now --
for x = 0, kLevelCols do
for y = 0, kLevelRows do
local cell = display.newRect(x*cellWidth, y*cellHeight, cellWidth, cellHeight)
cell.strokeWidth = 1
cell:setStrokeColor(0,0,0)
if level[x][y] == 0 then
cell:setFillColor(255, 0, 0)
end

if cells[x] == nil then
cells[x] = {}
end

cells[x][y] = cell
end
end

print2d(level)
end

I should also note that we need to figure out each individual cell width and height. It's a simple calculation that you can place above this function.


local cellWidth = display.contentWidth / kLevelCols
local cellHeight = display.contentHeight / kLevelRows

Implementing State Flow

This part really has nothing to do with the A* algorithm but I thought I would include it here in case you get confused going through the sample project. I have implemented a pseudo-state machine in the code. There are 4 basic states in the UI flow that are best captured by state handlers. These include selecting the start cell, selecting the ending cell, running the pathfinding algorithm and cleaning up for another run of the state machine (the end state).

To accomplish this, I use something akin to function pointers. Basically, our screen touch handler looks at a certain variable that is pointing to a certain function and calls that function. This is in fact our current state handler. When that state is finished processing, it sets that function pointer to another state handler (function) and the screen touch handler will then call that function.

Screen Touch Handler

As I said, our screen touch handler just has to call a function whenever the screen is touched. This function is defined in a variable called curGameFunction which we can define at the top of main.lua like so:


local curGameFunction = nil

Let’s build a skeleton of the screen touch handler and the several states our sample project contains to gain a better understanding of how it all works.


-- Touch handler. Delegates call to current selected game function --
function onBoardTouched(event)
if event.phase == "began" then
curGameFunction(event)
end
end

function onStartCellSelected(event)
end

function onEndCellSelected(event)
end

function onDetermineAStar(event)
end

function onEnd(event)
end

So the question is, how do we set the curGameFunction variable to point to one of the state handlers. At the bottom of our main.lua file we simply set curGameFunction equal to a function, similar to how callbacks or function pointers work.


curGameFunction = function(event) onStartCellSelected(event) end

As you can see, now curGameFunction, when called, will actually call onStartCellSelected passing the touch event object with it. In our onStartCellSelectedEvent, after we process the event object, will set curGameFunction to onEndCellSelected. onEndCellSelected will set curGameFunction to onDetermineAStar and finally, onDetermineAStar will set curGameFunction to onEnd. If we expand our code from above, it would look something like:


-- Touch handler. Delegates call to current selected game function --
function onBoardTouched(event)
if event.phase == "began" then
curGameFunction(event)
end
end

function onStartCellSelected(event)
curGameFunction = function(event) onEndCellSelected(event) end
end

function onEndCellSelected(event)
curGameFunction = function(event) onDetermineAStar(event) end
end

function onDetermineAStar(event)
curGameFunction = function(event) onEnd(event) end
end

function onEnd(event)
-- start over --
curGameFunction = function(event) onStartCellSelected(event) end
end

curGameFunction = function(event) onStartCellSelected(event) end

Utility Methods

Ok, with that little explanation of pseudo function pointers out of the way, we can start implementing our state handlers. But before we do that, we have to get a few utility functions out of the way. These utility functions will allow us to do a few things like return the index values into our level given an x and y location on the screen (i.e. if the user touches the location x,y on the screen, what value is that cell in our map table). Note that I could have simply added a touch listener to each display.newRect object we create but chose not to for performance reasons (we would end up creating 2500 listeners for a 50×50 grid as opposed to the single touch listener we added for the screen).

getIndices

This method will return the x and y index into our cells table given an x and y location that the user tapped on the screen.


-- returns table containing index values based on where a user clicked on the grid --
function getIndices(x, y)
return {math.floor(x / cellWidth), math.floor(y / cellHeight)}
end

getCell

This method will return the actual rect object (display.newRect) in our cells table given an x and y location the user tapped on the screen. Note that the above method simply returns the indices while this method returns the actual display.newRect object.

-- gets the display.newRect object based on x,y screen value --
function getCell(x, y)
local indices = getIndices(x, y)
return cells[indices[1]][indices[2]]
end

colorCell

This one is pretty self explanatory. This function will simply color/fill a display.newRect object with a certain color. We will use it when we color the start cell green, the end cell blue and the walls red.


-- colors a cell on the grid --
function colorCell(cell, red, green, blue)
cell:setFillColor(red, green, blue)
end

displayInstructions

This utility method simply displays some text to the user (albeit hard to read since it’s overlayed on top of our red and white map). We can call it at anytime to update the instructions to the user.


local instructions = nil

-- displays instructions (albeit hard to read) to the user
function displayInstructions(string)
if instructions ~= nil then
instructions:removeSelf()
end

instructions = display.newText(string, 0, 0, native.systemFontBold, 20)
instructions:setTextColor(0, 0, 0)
end

Implementing the State Handlers

Now with our utility methods out of the way, we can implement our state handlers. Remember that these are called by our main touch listerner whenever the user taps on the screen.

Implementing onStartCellSelected

The onStartCellSelected state handler is a pretty simple method. It will simply determine which cell the user tapped on the screen and save the x,y indices for that location (not the screen location as that is a different value but the actual indices into our cell and level tables). The first thing we do is determine the indices using our getIndices utility method. If that cell is red, it’s invalid we we try again. Otherwise the startCell variable it set to that location, we color the cell green and we set our state handler variable to point to the onEndCellSelected method.


-- called to select the starting point in the grid --
function onStartCellSelected(event)
local indices = getIndices(event.x, event.y)

if level[indices[1]][indices[2]] == 0 then
displayInstructions("Cannot select red. Try again")
else
startCell.col = indices[1]
startCell.row = indices[2]
displayInstructions("Select the ending cell")
colorCell(getCell(event.x, event.y), 0, 255, 0)
curGameFunction = function(event) onEndCellSelected(event) end
end
end

Don’t forget to define the startCell variable at the top of your main.lua file:


local startCell = {col = -1, row = -1}

Implementing onEndCellSelected

The onEndCellSelected method performs the same as the onStartCellSelected method. It determines the index values into our cell table, saves those indices into the endCell variable, colors the cell blue and sets our state handler function to the onDetermineAStar function.


-- called to select the ending point in the grid --
function onEndCellSelected(event)
local indices = getIndices(event.x, event.y)

if level[indices[1]][indices[2]] == 0 then
displayInstructions("Cannot select red. Try again")
else
endCell.col = indices[1]
endCell.row = indices[2]
colorCell(getCell(event.x, event.y), 0, 0, 255)
displayInstructions("Touch anywhere to see A* go")
curGameFunction = function(event) onDetermineAStar(event) end
end
end

Don’t forget to define the endCell variable at the top of your main.lua file:


local end= {col = -1, row = -1}

Implementing onEnd

We’re going to skip the onDetermineAStar state handler for now since it’s where all the magic happens and I like saving the best for last. The onEnd state handler is again a simple state handler. It’s job is to basically reset the data structures, generate a new grid and set the state back to the onStartCellSelected method so the user can run A* again.


-- called when the demonstration ends (resets the grid) --
function onEnd(event)
for x = 0, kLevelCols do
for y = 0, kLevelRows do
cells[x][y]:removeSelf()
end
end

cells = {}

buildGrid()
displayInstructions("Select the starting cell")
curGameFunction = function(event) onStartCellSelected(event) end
end

Implementing onDetermineAStar

Now we are ready to see how to use the A* pathfinding algorithm in our sample project. At this point, the grid (level and cell tables) has been built, the user has selected the start point and the end point and we’re ready to find the shortest path between those two points without going through a wall.

To do this, we call the pathfinder module’s pathFind method. This method expects a certain number of parameters. These are (in order)

pathfinder.pathFind parameters

  • the_map: The 2d array of 1′s and 0′s. In this case, our level table
  • mapW: The map width
  • mapH: The map height
  • startX: The starting column
  • startY: The starting row
  • targetX: The ending column
  • targetY: The ending row

At this point, we have all the information we need so we can call it like so:


local path = pathfinder.pathFind(level, kLevelCols, kLevelRows, startCell.col, startCell.row, endCell.col, endCell.row)

When this function returns we’ll have 1 of 2 things. If no suitable path is found, we’ll simply get a false value. That means that from our start location to our end location there is no road that connects the two, walls are in the way.

The second type we can expect from pathfinder.pathFind is a table of results showing the path we need to take. I’ll show you a sample of what it looks like (printed to the console) and explain what it means.


Path[0] = {dx=0,dy=-1,count=2}
[1] = {dx=1,dy=0,count=1}
[2] = {dx=0,dy=-1,count=1}
[3] = {dx=1,dy=0,count=2}
[4] = {dx=0,dy=-1,count=1}

In the above example, we have an array object. For each value in that array we have a dx value, a dy value and a count value. The dx and dy values represent directions. A 0 means that you don’t move in that direction, a 1 means you move in the positive direction and a -1 means you move in the negative direction. The count value tells you how many cells to move in that direction. Let’s take a look at the first value in the array:


Path[0] = {dx=0,dy=-1,count=2}

You intrepret this to mean that from the starting cell we passed to the method, you move 2 cells in the negative y direction. Basically, you are moving 2 cells up and 0 cells in the x direction. The next value:

[1] = {dx=1,dy=0,count=1}

means that you move 1 cell in the positive x direction and 0 cells in the y direction. You’re basically moving 1 cell to the right starting from the cell you last ended on. You continue this progression of moving until you get to the last value in the array. Once you do, you are at your ending cell.

So, now we have to write the code to handle these results. The algorithm again is pretty simple. We start at the starting cell and loop through the pathFind results. For each results, our cell direction in the x direction is the dx value and our cell direction in the y direction is the dy value. We create a for loop counting from 1 to the count value and simply start coloring cells as we move along our cells table. By the time we’ve looped through our results table and looped through the count value of each result we are done and can set our curGameFunction state handler variable to the onEnd method.

The full onDetermineAStar method is as follows:


-- called to get the A* algorithm going --
function onDetermineAStar(event)
displayInstructions("")

-- run A* --
local path = pathfinder.pathFind(level, kLevelCols, kLevelRows, startCell.col, startCell.row, endCell.col, endCell.row)
pprint("Path", path)

if path ~= false then
-- color the path --
local currentCell = {x=startCell.col, y=startCell.row}

for k = 0, #path do
local cellDirectionX = path[k].dx
local cellDirectionY = path[k].dy
local count = path[k].count

for l = 1, count do
currentCell.x = currentCell.x + cellDirectionX
currentCell.y = currentCell.y + cellDirectionY
if currentCell.x ~= endCell.col or currentCell.y ~= endCell.row then
colorCell(cells[currentCell.x][currentCell.y], 255, 255, 0)
end
end
end

curGameFunction = function(event) onEnd(event) end
else
displayInstructions("Suitable path not found")
curGameFunction = function(event) onEnd(event) end
end
end

Implementing walker

Given all that we know about the map and the best path to take, we can now demonstrate how to follow the path. Let’s create a walkin minion now. For simplicity it will be just a circle.
Add walker variable at the top of the main file so it will be accessible by our functions.

-- table contains display.newRect objects --
local cells = {}

– walks on the path
local walker

And let’s create a class for him, put it somewhere above the onDetermineAStar function.

function newWalker(path)
local walker = display.newCircle((startCell.col + 0.5) * cellWidth, (startCell.row + 0.5) * cellHeight, cellWidth)
walker.strokeWidth = 1
walker:setStrokeColor(0,0,0)
walker:setFillColor(0, 255, 255)
walker.pathIndex = 0
walker.pathLen = table_len(path)
walker.speed = 50

function walker:go()
if self.pathIndex < self.pathLen then
local dir = path[self.pathIndex]
self.transition = transition.to(self, { time = self.speed * dir.count,
x = self.x + dir.dx * dir.count * cellWidth,
y = self.y + dir.dy * dir.count * cellHeight,
onComplete = function () self:go() end})
end
self.pathIndex = self.pathIndex + 1
end

return walker
end

The first several lines of code just setup our circle, make it the size of the grid and paint it cyan.
Next we will need an indicator on the path to show where the walker is. We will use walker.pathIndex for that and it will be increment each time we move to next path node.
The speed variable is a time in milliseconds required to pass from one single cell to another so it's pretty small.

The walker:go() function does the actual moving - it is a simple transition that repeats itself on completion (notice the code in onComplete parameter). All transition parameters are defined with current path node values (dir.dx, dir.dy and dir.count).

Now we need to get the walker moving after a path has been found. Put this right after the "for" loops in the onDetermineAStar function:


-- create a moving object
walker = newWalker(path)
walker:go()

We now have a moving circle. The last thing we need to do is to properly dispose the walker. Add this to the onEnd function:

if walker then
walker:removeSelf()
walker = nil
end

Conclusion

This short demo demonstrates one way of using the A* pathfinding module by Lerg. It should give you a good idea of what type of data structures you need to use this wonderful module. The types of games this can be used for is numerous.

Complete code can be found in the code exchange section: pathfindng module, demo app.


Posted by . Thanks for reading...

24 Responses to “Tutorial: The A* Algorithm”

  1. Nicholas G

    Firsties!!!!

    No seriously. This makes my brain melt. I’ve been studying A* for a while and since math and programming are my weak area (never programmed anything before june 2011) learning A* is EXTRA fun :)

    I love the information, I actually understand this explanation.

    ng

    Reply
  2. Slightly Confused

    How does Corona know that the function onBoardTouched is only looking for touch events? Also, how would you isolate the scope of that function to a specific object or reagin of the screen?

    Reply
  3. Slightly Confused

    Figured out the first part…

    Runtime:addEventListener(“touch”, onBoardTouched)

    Any comments on the second? I’m still looking, so I may figure that out on my own too..hopefully! :)

    Reply
  4. Lerg

    >Also, how would you isolate the scope of that function to a specific object or reagin of the screen?

    Just attach it to a specific display object you want, like this:
    YourObject.touch = onBoardTouched
    YourObject:addEventListener(“touch”, YourObject)

    Reply
  5. Michael Hartlef

    Good article but I can’t see the point in using A* for a TD game. In a TD game, like the one above, you usually have fixed paths, a chain of waypoints. Normally you use a path finding algorythm when the path is not fixed and you COULD choose several ones.

    Anyway good article. Personally I like the one by Patrick Lester better and studied that when I created a pathfinding module for a different development tool.

    Reply
  6. Codepunk

    Michael, for a fixed path Tower Defense game you’re right, a waypoint system is easier. However, a lot of Tower Defense games start you off with a blank grid with no pathway for the “minions”. You are free to place your objects anywhere on the grid with the stipulation that you never completely block the path from the start point to the end point. In those type of TD games, A* is the way to go.

    Reply
  7. Lerg

    Michael Hartlef, apparently in my game where paths looks “fixed”, they are actually not. You’ll understand what I mean when I release the game, until then it’s sort of a secret.

    Reply
  8. Christer

    How does this reflect to the known routing algorithms used in printed circuit board design? Especially when you had the limit of using only one plane with several connections, then added a second layer, with a possibility of using a via, with an associated cost, and further with additional layers. And when squeezing more paths / routes through a congested area where there is an additional cost due to a cost of reduced manufacturing yield? How does A* play here?

    The reason for asking is using the cost of (Nth layer / yield / implementation time) as the limiting factor to find the best solution. Depending on the case, also the complexity factor, for example the risk of failure in implementation, will also add a factor. By mature industries a definitive = negative, by tornado industries to win.

    Reply
  9. ingemar

    Great article, and a HUGE thanks for posting the code.
    The Corona community is amazing.

    Reply
  10. Lerg

    Christer, routing algorithms are completely different story. A* can be applied there, but only as a small part of a bigger thing. In PCB wiring key requirements is to have wires not crossing each other and their angles of turns should not be sharp. Also generally PCB wires don’t have to follow the most short ways.
    And wise versa there is no point for PCB routing algos to be applied in games (maybe in only very unusual ones).

    ingemar, thank you.

    Reply
  11. Sven.Lua

    ok – interesting article anyway, but my first thoughts was – why should one need it for the simple ways in a TD game. So I agree completely with Michaels writing… and I’m sure Lerg know it.

    Then I thought – maybe there is space to use this algo if one would make the ways more complicated and interesting by … and Lerg and Codepunk came up with secrets ;)

    Everything is ok – I’m curious to see your TD game finished. My wife love this style of game.

    Reply
  12. Lerg

    You are right about simple TD games, waypoints system would do just fine for them.

    Also I forgot to mention in the article that the algo’s name “A” came from hexadecimal value A which is 10 in decimal. In cell’s cost calculation estimated distance to a target is multiplied by 10.

    Reply
  13. russell

    Wow!, just last night I was writing notes about Tower Defense Game and concluded it would be outside my realm of expertise. Especially the part where the enemies move more than just a straight line. Then I wake up and find this. This is great stuff I’m excited! I have been programming 3 months now so I will read this like 20 times.

    Can you use this also to have multiple tower bullets “seek” out multiple moving enemy invaders? Would the bullet be confused with multiple targets?

    This is a module yes? So I can use the pathfinder.lua and play around with moving objects and pathfinding and not necessarily have to understand the algorithm yes?

    thanks guys

    Reply
  14. Lerg

    Russell,
    Bullets usually travel straight lines or curves (like a missile approaching a moving target). Frankly, I don’t know how to apply A* for bullets.
    It is a module, you don’t need to know how algo works, just need to know how to feed it and how to use it’s results.

    Mario, you are welcome!

    Reply
  15. jonl

    @lerg and russell,

    A seek and destroy missile could use the A* algorithm to run a path to the target. It would have to constantly update based on the changing target position.

    Great article BTW

    Reply
  16. MikeHart

    @Jonl:

    Be careful with constantly updating the path. In context of Corona we are talking about an interpreted scripting language. If Corona would support something like this from the engine, when yes. But with Lua alone, I would not do that. That would bring your fps down a lot.

    @Lerg, it isn’t needed to multiply the cell cost with something. The pure vector distance could be enough. You will get the same results.

    Reply
  17. svn-repo

    Great Tutorial,

    Need help though, if anyone knows a formula or site i can read up on how to turn a single array ex: grid = { 0,0,0,0,0,
    1,1,1,1,1,
    0,0,0,0,0 }

    into a multidimensional array such as if a go in a loop on grid, then level[0][0] will be 0 and level[1][0] will 1. i am having trouble and want to use static paths with design based on the ex grid above. Thanks again and awesome tutorial

    Reply
  18. Lord Elsinore

    This is fantastic! I notice that Lerg’s underlying A* port states it will work for 8 direction in addition to 4 direction, but I can’t see to get that to work right. Any chance you two (Lerg and Codepunk) could get this demo working with the 8 direction option? It would help me out a ton!

    Thanks!

    Reply
  19. Michael

    Hi everyone,

    Firstly, congratulations and thank you for this demo. It’s a great resource and implementation of A*.

    Secondly, Lord Elsinore, did you find a solution to your 8-directional query? I’m very interested in finding out this solution too.

    Anyone any thoughts?

    Michael

    Reply
  20. peng

    I use the code, this’s work. But I have a problem that the path is one step left, one step right, i know it’s the shortest path. but it’s very weird。。。

    Reply

Leave a Reply

  • (Will Not Be Published)