summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-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 {