summaryrefslogtreecommitdiff
path: root/include/algs.lua
diff options
context:
space:
mode:
authorSteph Enders <smenders@gmail.com>2022-06-16 16:53:34 -0400
committerSteph Enders <smenders@gmail.com>2022-06-16 16:53:34 -0400
commit49bb775d4cf9935b0f0d54daa358423ac786c9be (patch)
tree8a14766eb4c825af7e19da822644e5d1695d0206 /include/algs.lua
parentc57ae8c42c1f2f2ed576719c00cff5cf613fe650 (diff)
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
Diffstat (limited to 'include/algs.lua')
-rw-r--r--include/algs.lua96
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 {