# lua – I wrote my first pathfinding algorithm 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
$$```$$
`````` 