1 files changed, 60 insertions, 36 deletions
diff --git a/include/algs.lua b/include/algs.lua
index ad0016a..2541102 100644
--- a/include/algs.lua
+++ b/include/algs.lua
@@ -1,6 +1,24 @@
 require "include.constants"
 local Queue = require "include.queue"
 
+---@param map table
+local function print_map(map)
+    for i = 1, #map do
+        row = map[i]
+        line = ""
+        for j = 1, #row do
+            if row[j] == MAP_WALL then
+                line = line .. "# "
+            elseif row[j] == MAP_VISITED then
+                line = line .. "x "
+            else
+                line = line .. "  "
+            end
+        end
+        print(line)
+    end
+end
+
 local function can_move(x, y, map)
     return map[y][x] == MAP_SPACE
 end
@@ -10,43 +28,62 @@ end
 ---@param origin table
 ---@param map table
 ---@param queue table
-local function push_moves(x, y, origin, map, queue)
+---@return boolean found goal
+local function push_moves(x, y, origin, map, queue, target_pos)
+    map[y][x] = MAP_VISITED -- should be but just in case
     -- UP
-    if can_move(x, y -1, map) then
-        queue:push({
+    if can_move(x, y - 1, map) then
+        pos = {
             x = x,
             y = y - 1,
             origin = origin
-        })
-        map[y-1][x] = MAP_VISITED
+        }
+        map[pos.y][pos.x] = MAP_VISITED
+        if (pos.x == target_pos.x and pos.y == target_pos.y) then
+            return true
+        end
+        queue:push(pos)
     end
     -- DOWN
-    if can_move(x, y +1, map) then
-        queue:push({
+    if can_move(x, y + 1, map) then
+        pos = {
             x = x,
             y = y + 1,
             origin = origin
-        })
-        map[y+1][x] = MAP_VISITED
+        }
+        map[pos.y][pos.x] = MAP_VISITED
+        if (pos.x == target_pos.x and pos.y == target_pos.y) then
+            return true
+        end
+        queue:push(pos)
     end
     -- LEFT
     if can_move(x - 1, y, map) then
-        queue:push({
+        pos = {
             x = x - 1,
             y = y,
             origin = origin
-        })
-        map[y][x - 1] = MAP_VISITED
+        }
+        map[pos.y][pos.x] = MAP_VISITED
+        if (pos.x == target_pos.x and pos.y == target_pos.y) then
+            return true
+        end
+        queue:push(pos)
     end
     -- RIGHT
     if can_move(x + 1, y, map) then
-        queue:push({
+        pos = {
             x = x + 1,
             y = y,
             origin = origin
-        })
-        map[y][x+1] = MAP_VISITED
+        }
+        map[pos.y][pos.x] = MAP_VISITED
+        if (pos.x == target_pos.x and pos.y == target_pos.y) then
+            return true
+        end
+        queue:push(pos)
     end
+    return false
 end
 
 ---
@@ -66,32 +103,19 @@ local function pathfind(start_pos, target_pos, map)
         visit_map[k] = row
     end
 
-    push_moves(start_pos.x, start_pos.y, nil, visit_map, queue)
+    if (push_moves(start_pos.x, start_pos.y, nil, visit_map, queue, target_pos)) then
+        return { dx = start_pos.x - target_pos.x, dy = start_pos.y - target_pos.y }
+    end
+
     while queue:empty() ~= true do
         local pos = queue:pop()
-        if (pos.x == target_pos.x and pos.y == target_pos.y) then
-            return { dx = pos.origin.x - start_pos.x, dy = pos.origin.y - start_pos.y }
-        end
         origin = pos.origin or { x = pos.x, y = pos.y }
-        push_moves(pos.x, pos.y, origin, map, queue)
-    end
-    return { dx = 0, dy = 0 }
-end
-
----@param map table
-local function print_map(map)
-    for i = 1, #map do
-        row = map[i]
-        line = ""
-        for j = 1, #row do
-            if row[j] == MAP_WALL then
-                line = line .. "# "
-            else
-                line = line .. "  "
-            end
+        hit_target = push_moves(pos.x, pos.y, origin, visit_map, queue, target_pos)
+        if hit_target then
+            return { dx = origin.x - start_pos.x, dy = origin.y - start_pos.y }
         end
-        print(line)
     end
+    return { dx = 0, dy = 0 }
 end
 
 return {