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