1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
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
---@param x number
---@param y number
---@param origin table
---@param map table
---@param queue table
---@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
pos = {
x = x,
y = y - 1,
origin = origin
}
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
pos = {
x = x,
y = y + 1,
origin = origin
}
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
pos = {
x = x - 1,
y = y,
origin = origin
}
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
pos = {
x = x + 1,
y = y,
origin = origin
}
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
---
---@param start_pos table [x, y]
---@param target_pos table [x, y]
---@param map table 2D map array
---@return table best move to target [x, y]
---
local function pathfind(start_pos, target_pos, map)
local queue = Queue:new()
local visit_map = {}
for k, v in ipairs(map) do
row = {}
for ik, iv in ipairs(v) do
row[ik] = iv
end
visit_map[k] = row
end
if (push_moves(start_pos.x, start_pos.y, nil, visit_map, queue, target_pos)) then
return { dx = target_pos.x - start_pos.x, dy = target_pos.y - start_pos.y }
end
while queue:empty() ~= true do
local pos = queue:pop()
origin = pos.origin or { x = pos.x, y = pos.y }
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
end
return { dx = 0, dy = 0 }
end
return {
pathfind = pathfind,
print_map = print_map,
}
|