I'm currently writing a small game in Lua, using the Love2d framework. I guess I'm doing it as a practice of sorts, but it did give me the opportunity to write my first pathfinding algorithm. I wrote it based off of a 10 minute Youtube video I saw explaining A*, and luckily it works fine. The pathfind function outputs a table of coordinates that traverse between two points, and it works based off my vague understanding of A*. I've stripped out most of the game code, so it's just the pathfinding function and a skeleton of the board that it traverses. I would love any and all critiques of it, as I'm trying to improve my programming skills. Thank you all for your time!
local board = {}
local board_width = 12
local board_height = 12
-- initialize board
for i=1,board_height do
local t = {}
for j=1,board_width,1 do
t[j] = 0
end
board[i] = t
end
function is_in_bounds(x, y)
if x == nil or y == nil then
return false
end
if x < 1 or x > board_width or y < 1 or y > board_height then
return false
else
return true
end
end
function get_tile(x, y)
return board[y][x]
end
function pathfind(from_x, from_y, to_x, to_y)
local coord_to_index = function(x, y)
return (x - 1) + (y - 1) * board_width + 1
end
local index_to_coord = function(i)
return ((i - 1) % board_width) + 1, math.floor((i - 1) / board_width) + 1
end
local dist = function(x1, y1, x2, y2) -- gets manhattan distance
return math.abs(x1 - x2) + math.abs(y1 - y2)
end
local is_traversable = function(x, y)
if is_in_bounds(x, y) and get_tile(x, y) == 0 then
return true
else
return false
end
end
if not is_traversable(to_x, to_y) then
-- goal is on an obstacle; return nil
return
end
local open_nodes = {}
local open_nodes_count = 1
local closed_nodes = {}
open_nodes[coord_to_index(from_x, from_y)] = { -- initialize first node
g_cost = 0,
h_cost = dist(from_x, from_y, to_x, to_y),
come_from = nil
}
while open_nodes_count > 0 do
local current
local lowest_f_cost = nil
open_nodes_count = -1 --current node is going to be removed; start counting from -1
--find lowest f_cost and make it the current node
for index, node in pairs(open_nodes) do
if lowest_f_cost == nil or node.g_cost + node.h_cost < lowest_f_cost then
lowest_f_cost = node.g_cost + node.h_cost
current = index
elseif node.g_cost + node.h_cost == lowest_f_cost then -- tiebreaker; if f_costs are the same, get the lowest g_cost
if node.h_cost < open_nodes[current].h_cost then
lowest_f_cost = node.g_cost + node.h_cost
current = index
end
end
open_nodes_count = open_nodes_count + 1
end
closed_nodes[current] = open_nodes[current]
open_nodes[current] = nil
local current_x, current_y = index_to_coord(current)
if current_x == to_x and current_y == to_y then
-- path found; return the path of nodes
local found_path = {}
local step_path = current
while step_path ~= nil do
local point = {}
local step_x, step_y = index_to_coord(step_path)
point[1] = step_x
point[2] = step_y
found_path[#found_path + 1] = point
step_path = closed_nodes[step_path].come_from
end
return found_path
end
for i,neighbor in ipairs({{1,0}, {-1, 0}, {0, 1}, {0, -1}}) do
local check_x, check_y = current_x + neighbor[1], current_y + neighbor[2]
local check_index = coord_to_index(check_x, check_y)
if is_traversable(check_x, check_y) and closed_nodes[check_index] == nil then -- is traversable and not a closed node
if open_nodes[check_index] == nil or closed_nodes[current].g_cost + 1 < open_nodes[check_index].g_cost then -- if not open or g_cost can be improved
if open_nodes[check_index] == nil then
-- increase open_nodes_count if creating a new open node
open_nodes_count = open_nodes_count + 1
end
open_nodes[check_index] = {
g_cost = closed_nodes[current].g_cost + 1,
h_cost = dist(check_x, check_y, to_x, to_y),
come_from = current
}
-- the following code is a hacky solution to make the path follow nice straight lines
-- prioritize a node if the current node came from the same direction that this neighbor is coming from
-- if not, apply a penalty to the g_cost
-- is the current node didnt come from anywhere (i.e. is the first in the sequence), prefer horizontal directions
-- this probably doesn't do a great job at finding the shortest route, but i think it looks better
if closed_nodes[current].come_from ~= nil then
local prev_x, prev_y = index_to_coord(current)
local prev_x2, prev_y2 = index_to_coord(closed_nodes[current].come_from)
if not (math.abs(prev_x - prev_x2) == math.abs(neighbor[1]) and math.abs(prev_y - prev_y2) == math.abs(neighbor[2])) then
open_nodes[check_index].g_cost = open_nodes[check_index].g_cost + 0.1
end
else
if i > 2 then
open_nodes[check_index].g_cost = open_nodes[check_index].g_cost + 0.1
end
end
end
end
end
end
end
```
2 Answers 2
You can always return the condition expression itself instead of using if:
local is_traversable = function(x, y)
return is_in_bounds(x, y) and get_tile(x, y) == 0
end
As a side note, the operator and returns its first argument if it is false; otherwise, it returns its second argument.
Having a "global" board (the variable is local, but there can only ever be one in the file) has a high potential for future headache; instead I'd just pass the board as the first argument to the other functions and have a newboard function that creates, initialises and returns a new board. The board's dimensions can be saved inside the board itself, since Lua tables can act as both arrays and objects at the same time.
function is_in_bounds(x, y)
if x == nil or y == nil then
return false
end
-- ...
end
If you're going through the trouble of checking your arguments for nil, you might as well properly type-check them:
if type(x)=="number" and type(y)=="number" then
or simply
if tonumber(x) and tonumber(y) then
Declaring the is_traversable function inside the pathfind function is a potential performance problem. In your problem, the algorithm itself will by far outweigh the single function declaration, but you should be aware that you should avoid doing this in functions that a) otherwise run very fast and b) get called very often, as the performance loss will add up in those cases.