Corona SDK: Game Development Path Finding

This project steps through the basics of path finding in the Corona SDK via the A* path finding algorithm, a staple in the game industry since about 1970. This app lets you add obstacles to a 10x10 grid and view the path determined by A*.

Final Preview

Overview of the A* Algorithm

A* uses two functions to determine the path of "least cost" to the target. The first function, often called g(x), is the cost of moving between two adjacent squares. This is useful when your game has varying terrains such as swamps and paved roads that may have different movement effects. The second function, h(x), is an estimate of the distance from the current square to the target square along the ideal path. There are many different ways to calculate this distance, but for this program, we will utilize a relatively simple approach by adding remaining distance in the y direction to the remaining distance in the x direction.

We will use the following two lua functions to find the path. The function is called as follows, CalcPath(CalcMoves(board, startX, startY, targetX, targetY)). The CalcPath function returns a table of the coordinates to the target, or nil if no path could be found. This behavior will prove helpful in determining the validity of obstacle placement.

If you have no interest in the behind the scenes aspects of the algorithm, feel free to just copy and paste the functions from the full source at the top of the page. Otherwise, fasten your seatbelts: this may be a lot to take in at first.

Step 1: The First Path Finding Function

Let's take a look at CalcMoves first.

Declaring Variables

local openlist = {}  --Possible Moves
local closedlist = {}  --Checked Squares
local listk = 1  -- openlist counter
local closedk = 0  -- closedlist counter
local tempH = math.abs(startX-targetX) + math.abs(startY-targetY) --h(x)
local tempG = 0

Here we declare most of the variables used in the method.

openlist is a table that holds all of the possible moves from the current square (up, down, left, right in our example)
The second table is the closedlist, a list of squares that have already been checked (squares that are part of the path thus far)
Listk and closedk are counters for the open list and closed list respectively
tempH and tempG are temporary variables that hold the values of h(x) and g(x) for the current square. The value of tempH is calculated by adding the difference of the starting and target x/y values.

openlist[1] = {x = startX, y = startY, g = 0, h = tempH, f = 0 + tempH, par = 1}
local xsize = table.getn(board[1])
local ysize = table.getn(board)
local curSquare = {}
local curSquareIndex = 1	 -- Index of current base

Diving into the next chunk, we begin by setting the first sqare in the open list to the starting square. Then we create variables for the width and height of the board, declare a table for the current square being checked in the open list, and create a variable for the index in the open list of the current square. In case you were wondering, "Par" holds the index of the square's parent. This allows for easy reconstruction of the path.

Finding the Square of Least Cost

while listk > 0 do 
   	local lowestF = openlist[listk].f
  	curSquareIndex = listk
	for k = listk, 1, -1 do
	    if openlist[k].f < lowestF then
 	       lowestF = openlist[k].f
           curSquareIndex = k
       	end
	end
...

This method is sort of turned on its head. It loops through, first iterating through the open list, and second expanding the open list until it reaches the final square. The first nested loop iterates through the open list to find the square with the lowest F value. The f value is similar to the h value, except that the f value is the cost of the shortest path from start to end passing through the current square. The index of this square is stored in a variable. Note: If the open list ever becomes empty (i.e. There were no more spaces eligible for movement) a path could not be determined and the function returns nil. This possibility is checked in the while loop.

closedk = closedk + 1
table.insert(closedlist,closedk,openlist[curSquareIndex])

curSquare = closedlist[closedk]

Here we increment the closed list counter, insert the square with the lowest f score into the closed list, and set that square as the current square. The next lines will determine whether the squares adjacent to the new current square are eligible for movement.

Checking Adjacent Squares for Availability

local rightOK = true
local leftOK = true           				 -- Booleans defining if they're OK to add
local downOK = true             				 -- (must be reset for each while loop)
local upOK = true
-- Look through closedlist. Makes sure that the path doesn't double back
if closedk > 0 then
    for k = 1, closedk do
		if closedlist[k].x == curSquare.x + 1 and closedlist[k].y == curSquare.y then
			rightOK = false
		end
		if closedlist[k].x == curSquare.x-1 and closedlist[k].y == curSquare.y then
			leftOK = false
		end
		if closedlist[k].x == curSquare.x and closedlist[k].y == curSquare.y + 1 then
			downOK = false
		end
		if closedlist[k].x == curSquare.x and closedlist[k].y == curSquare.y - 1 then
			upOK = false
		end
    end
end

First, we check if they are already in the closed list:

	
if curSquare.x + 1 > xsize then
	rightOK = false
end

if curSquare.x - 1 < 1 then
	leftOK = false
end

if curSquare.y + 1 > ysize then
	downOK = false
end

if curSquare.y - 1 < 1 then
	upOK = false
end

Second, it ensures that the adjacent squares are within the bounds of the board:

if curSquare.x + 1 <= xsize and board[curSquare.x+1][curSquare.y].isObstacle ~= 0 then
	rightOK = false
end

if curSquare.x - 1 >= 1 and board[curSquare.x-1][curSquare.y].isObstacle ~= 0 then
	leftOK = false
end

if curSquare.y + 1 <= ysize and board[curSquare.x][curSquare.y+1].isObstacle ~= 0 then
	downOK = false
end

if curSquare.y - 1 >= 1 and board[curSquare.x][curSquare.y-1].isObstacle ~= 0 then
	upOK = false
end

Third, we check if the adjacent squares contain obstacles:

-- check if the move from the current base is shorter then from the former parrent
tempG =curSquare.g + 1
for k=1,listk do
	if rightOK and openlist[k].x==curSquare.x+1 and openlist[k].y==curSquare.y and openlist[k].g>tempG then
		tempH=math.abs((curSquare.x+1)-targetX)+math.abs(curSquare.y-targetY)
		table.insert(openlist,k,{x=curSquare.x+1, y=curSquare.y, g=tempG, h=tempH, f=tempG+tempH, par=closedk})
		rightOK=false
	end
		
	if leftOK and openlist[k].x==curSquare.x-1 and openlist[k].y==curSquare.y and openlist[k].g>tempG then
		tempH=math.abs((curSquare.x-1)-targetX)+math.abs(curSquare.y-targetY)
		table.insert(openlist,k,{x=curSquare.x-1, y=curSquare.y, g=tempG, h=tempH, f=tempG+tempH, par=closedk})
		leftOK=false
	end

	if downOK and openlist[k].x==curSquare.x and openlist[k].y==curSquare.y+1 and openlist[k].g>tempG then
		tempH=math.abs((curSquare.x)-targetX)+math.abs(curSquare.y+1-targetY)
		table.insert(openlist,k,{x=curSquare.x, y=curSquare.y+1, g=tempG, h=tempH, f=tempG+tempH, par=closedk})
		downOK=false
	end

	if upOK and openlist[k].x==curSquare.x and openlist[k].y==curSquare.y-1 and openlist[k].g>tempG then
		tempH=math.abs((curSquare.x)-targetX)+math.abs(curSquare.y-1-targetY)
		table.insert(openlist,k,{x=curSquare.x, y=curSquare.y-1, g=tempG, h=tempH, f=tempG+tempH, par=closedk})
		upOK=false
	end
end

Finally, the algorithm checks to make sure that it is "cheaper" to move from the current square to the next square than it would be to move from the parent square to the next square. This ensures that the path chosen is indeed the cheapest path possible, and there aren't any obvious shortcuts that were missed.

Expanding the Open List

-- Add point to the right of current point
if rightOK then
	listk=listk+1
	tempH=math.abs((curSquare.x+1)-targetX)+math.abs(curSquare.y-targetY)
	table.insert(openlist,listk,{x=curSquare.x+1, y=curSquare.y, g=tempG, h=tempH, f=tempG+tempH, par=closedk})
end

-- Add point to the left of current point
if leftOK then
	listk=listk+1
	tempH=math.abs((curSquare.x-1)-targetX)+math.abs(curSquare.y-targetY)
	table.insert(openlist,listk,{x=curSquare.x-1, y=curSquare.y, g=tempG, h=tempH, f=tempG+tempH, par=closedk})
end

-- Add point on the top of current point
if downOK then
	listk=listk+1
	tempH=math.abs(curSquare.x-targetX)+math.abs((curSquare.y+1)-targetY)
	table.insert(openlist,listk,{x=curSquare.x, y=curSquare.y+1, g=tempG, h=tempH, f=tempG+tempH, par=closedk})
end

-- Add point on the bottom of current point
if upOK then
	listk=listk+1
	tempH=math.abs(curSquare.x-targetX)+math.abs((curSquare.y-1)-targetY)
	table.insert(openlist,listk,{x=curSquare.x, y=curSquare.y-1, g=tempG, h=tempH, f=tempG+tempH, par=closedk})
end

This second to last chunk is where we finally expand the open list after all of that arduous testing. If a square adjacent to the current square was able to perservere through our rigorous conditions, it earns a spot on the open list, where it may be chosen as the next current square depending on its F value.

		...
		table.remove(openlist,curSquareIndex)
		listk=listk-1

		if closedlist[closedk].x==targetX and closedlist[closedk].y==targetY then
   			return closedlist
		end
	end

	return nil
end

At last we come to the end of the lengthy function. First we remove the current square from the open list. We then check if the current square's x and y positions equal those of the target square. If so, we pass the closed list to the CalcPath method where the data is refined.

Step 2: The Second Path Finding Function

function CalcPath(closedlist)
	if closedlist==nil then
        	return nil
	end
	local path={}
	local pathIndex={}
	local last=table.getn(closedlist)
	table.insert(pathIndex,1,last)

	local i=1
	while pathIndex[i]>1 do
		i=i+1
		table.insert(pathIndex,i,closedlist[pathIndex[i-1]].par)
	end

	for n=table.getn(pathIndex),1,-1 do
		table.insert(path,{x=closedlist[pathIndex[n]].x, y=closedlist[pathIndex[n]].y})
	end

	closedlist=nil
	return path
end

It's all downhill from here! This function cuts down the closed list to ensure that only the correct path is returned. Without this if the algorithm traversed a path, got stuck, and struck out on a new path, the table that was returned would contain coordinates for the correct path as well as the failed attempt. All it does is start at the end of the closed list, and reconstruct the path to the beginning via the parent property added earlier. After we have obtained our list of correct coordinates, we can use that information to create a finished path in the second loop. That's all there is to the A* algorithm. Next up we look at how we can use it in a program.

Step 3: Setting up the Grid

Whew! That was a lot of new information. Luckily the rest of this app is very easy to construct with even a basic understanding of the Corona API. The first thing you should do is create your main.lua file and put it in a new directory. That's all Corona requires in the way of setup! Next we are going to create the table that will hold our 10x10 grid, and While we're at it, we can get rid of that unsightly status bar at the top of the screen.

display.setStatusBar(display.HiddenStatusBar)

board = {}  --Create an empty table to hold the board

--Populate the Table
for i = 1, 10 do
	board[i] = {}
	for j = 1, 10 do
		board[i][j] = {}
		board[i][j].square = display.newRect((i-1) * 32, (j-1) * 32, 32, 32)
		board[i][j].square:setFillColor(255, 255, 255)
		board[i][j].isObstacle = 0
	end
end

There's nothing revolutionary here. All we did was hide the status bar and create a three dimensional array to hold the grid. In the for loops, we set the side length of our squares to 32 pixels and positioned them with some crafty multiplication. Note: Be sure to use the .square and .isObstacle keys instead of just saying board[2][3].

Step 4: Adding Obstacles

Adding obstacles is a simple task. For this tutorial, spaces that are eligible for movement will be white, obstacles will be black, and the markers that indicate the path will be red. Look at the following function:

addObstacle = function(event)
	if event.phase == "ended" and event.y < 320 then
		--Use event.x and event.y to calculate the coordinate in terms of the 10x10 grid
		x = math.ceil(event.x/32)
		y = math.ceil(event.y/32)
		board[x][y].isObstacle = 1
		if CalcPath(CalcMoves(board, 1, 1, 10, 10)) then
			board[x][y].square:setFillColor(0, 0, 0)
		else 
			board[x][y].isObstacle = 0
		end
	end
	return true
end
Runtime:addEventListener("touch", addObstacle)

Notice that the function is a runtime event listener. Runtime events are sent to all listeners and don't apply to a specific object. This is the desired behavior for this implementation. The addObstacle function begins by checking if the user has lifted his finger. Forgetting this step is sure to cause much frustration on the part of the user as the button could be pressed by an accidental swipe, and not a deliberate down and up motion of the finger. Users are accustomed to these nuances, so it is important to pay attention to them whenever possible. This same conditional also makes sure that only touch events that occur within the 320px tall grid are sent to this method. This keeps them from interfering with our buttons.

Besides that, this function uses some basic math to figure out what square was touched using event.y and event.x, and it calls the path finding function to ensure that the user leaves a path. Depending on your needs, this may or may not be desirable, but it's nice to know that you have the ability to make these determinations.

Step 5: Using the Path Finding Information

For the sake of brevity, this tutorial will skimp on animations, and just place markers along the path determined by A*.

placeMarkers = function(event)
	path = CalcPath(CalcMoves(board, 1, 1, 10, 10))
	for i = 1, table.getn(path) do
		local newX = path[i].x
		local newY = path[i].y
		local marker = display.newCircle((newX*32 - 16), (newY*32 - 16), 8)
		marker:setFillColor(255, 0, 0)
	end
end

This is all the code that is necessary. We simply put the coordinates into a table named path, and iterate through the entirety of the table, placing a marker with an eight pixel radius at each set of coordinates. Things can become a little hairy when you attempt to use animations in conjunction with this, but it shouldn't be too bad as long as you keep track of the index of your current coordinate, and increment it after a certain time interval.

Step 6: Finishing up With Buttons, and Reset Functionality

As it stands currently, the animate function will do absolutely nothing because it's never called. Using a runtime event really isn't appropriate in this instance, so we'll use an image with an event listener.

local goButton = display.newImage("PlaceMarkers.png", -200, 350)
goButton:addEventListener("touch", placeMarkers)

Voila! With two lines of code we are set to go.

If you run the program now, you will no doubt notice that the markers don't go away when you run the program again. The solution is to put the nested for loops that initially populated the table into a method that we can call whenever we need a clean slate. The beginning of the program should now look like this:

setup = function()
	counter = 1
	board = {}
	--Populate the Table
	for i = 1, 10 do
		board[i] = {}
		for j = 1, 10 do
			board[i][j] = {}
			board[i][j].square = display.newRect((i-1) * 32, (j-1) * 32, 32, 32)
			board[i][j].square:setFillColor(255, 255, 255)
			board[i][j].isObstacle = 0
		end
	end
end

Just two more lines and our program will be complete! I took the liberty of adding a better looking color scheme to the program. I encourage you to play around with this project. See if you can stump it. If you're feeling brave, try modifying the h(x) function and see what happens!

local resetButton = display.newImage("Reset.png", 300, 350)
resetButton:addEventListener("touch", setup)

Conclusion

This tutorial covers a lot of ground! The meat of it was the path finding algorithm. A* is a very powerful tool, and this was a fairly simple version of it. You may have noticed that it didn't account for diagonal movement and was based on squares. The truth is, you can modify the algorithm to accommodate any shape tile, and you can modify h(x) to achieve diagonal movement. The great thing is, while your algorithm code may become complex, the code for the UI and the rest of the application will remain simple and quick to write thanks to the power and simplicity of the Corona SDK. It provides you unprecedented ability in two dimensions without the complexity of Objective-C.

HIGHLIGHTS OF THE DAY