This tutorial utilizes the great A* pathfinding code uploaded by Lerg which is found here: http://developer.anscamobile.com/code/pathfinding-module

A* allows you to find the shortest path from point A to point B while navigating around obstacles (which for this tutorial we will call walls). A* has many uses in game development. The best way to explain it is with a certain type of game, Tower Defense. In those 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.

1
2

local kLevelRows = 50
local kLevelCols = 50

1

local kRoadProbability = 6

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

1

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

-- 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.

It should be noted that to use Lerg's pathfinding module, you also need to include his utility module. Within that utility module is a nice function called print2d which will print out our map on the debug console window. You can simple call it like this:

1

print2d(level)

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

-- 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.

1
2

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. I really hope that makes sense :-)

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:

1

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

-- 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.

1

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

-- 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 50x50 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.

1
2
3
4

-- 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.

1
2
3
4
5

-- 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.

1
2
3
4

-- 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.

1
2
3
4
5
6
7
8
9
10
11

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

-- 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:

1

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

-- 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:

1

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

-- 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:

1

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.

1
2
3
4
5

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:

1

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

    [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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

-- 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

Conclusion

This tutorial demonstrated one way of using the A* pathfinding module uploaded by Lerg on Code Exchange. 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. Feel free to email or comment on this tutorial should you have any questions. Keep in mind that if it's an A* implementation question though, I may refer you to Lerg instead :-)