From 49bb775d4cf9935b0f0d54daa358423ac786c9be Mon Sep 17 00:00:00 2001
From: Steph Enders <smenders@gmail.com>
Date: Thu, 16 Jun 2022 16:53:34 -0400
Subject: Made shortest path alg more efficent

In the previous commit this algo waited until the "success" step came up
in the queue. Now we have the check during the push - and if an hits we
return true from the push_moves fn.

Since we're only interested in the initial move (since we check moves
every frame) we can only return true and then use the current step as
the origin position to diff against the start to get the dx,dy
---
 include/algs.lua | 96 +++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 60 insertions(+), 36 deletions(-)

(limited to 'include/algs.lua')

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 {
-- 
cgit v1.2.3-54-g00ecf