4
\$\begingroup\$

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
```
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.