|
Алгоритм А*, Поиск пути |
|
|
cirus |
2.6.2017, 12:39
|
Elder
Сообщений: 3.480
Регистрация: 18.8.2014 Группа: Пользователи Наличность: 26703
Пользователь №: 16.971
Возраст: 29
|
A* Lua
Код --lua log ("clear") log ("mode compact")
-- ходы по диагонали, 0 - нет, 1 - да angle = 0
-- параметры findcolor find = {29, 25, 522, 516, 10, 10, "(0-16777215)", "%arr"}
-- создание карты function Create_Map(startX, startY, endX, endY, stepX, stepY, color, array) local z = 0 local a = findcolor(startX, startY, endX, endY, stepX, stepY, "(0-16777215)", "%arr") if #arr > 0 then local map = {} for i = 1, ((endY - startY) / stepY) + 1 do map[i] = {} for j = 1, ((endX - startX) / stepX) + 1 do z = z + 1 if tonumber(arr[z][3]) == 0 then map[i][j] = {1, arr[z][1], arr[z][2]} elseif tonumber(arr[z][3]) == 255 then map[i][j] = {"A", arr[z][1], arr[z][2]} elseif tonumber(arr[z][3]) == 16711680 then map[i][j] = {"B", arr[z][1], arr[z][2]} else map[i][j] = {0, arr[z][1], arr[z][2]} end end end return map end end
-- поиск в массиве A и B function index_of_A_B(arr, text) local result = {} for i = 1, #arr do for j = 1, #arr[i] do if arr[i][j][1] == text then table.insert(result, {i, j}) end end end return result end
-- поиск в массиве function index_of(arr, text) local result = {} for i = 1, #arr do for j = 1, #arr[i] do if arr[i][j] == text then table.insert(result, {i, j}) end end end return result end
-- A* function A_star(map) local g, g1, h, f, tmp = 0, 0, 0, 0, 0 local open, close, curr, index, resultclose, resultopen, vector = {}, {}, {}, {}, {}, {}, {} table.insert(vector, {-1, -1, 0, 1, 1, 1, 0, -1}) table.insert(vector, {0, 1, 1, 1, 0, -1, -1, -1})
table.insert(open, {0, 0, 0, 0, start [1][1], start [1][2], start [1][1]..":"..start [1][2], start [1][1], start [1][2]}) while 1 == 1 do table.sort (open, function (a, b) return (a[1] < b[1]) end) curr [1] = {open [1][1], open [1][2], open [1][3], open [1][4], open [1][5], open [1][6], open [1][7], open [1][8], open [1][9]} table.insert(close, {open [1][1], open [1][2], open [1][3], open [1][4], open [1][5], open [1][6], open [1][7], open [1][8], open [1][9]}) table.remove (open, 1) for i = 1, 8 do if angle == 1 or i%2 == 1 then local x, y = curr[1][5] + vector[1][i], curr[1][6] + vector[2][i] resultclose = index_of(close, x..":"..y) if x > 0 and y > 0 and x <= #map[i] and y <= #map then if (map[x][y][1] == 0 or map[x][y][1] == "B") and #resultclose == 0 then resultopen = index_of(open, x..":"..y) if #resultopen == 0 then if i%2 == 1 then g = curr[1][2] + 10 else g = curr[1][2] + 14 end h = (math.abs(x - ending[1][1]) + math.abs(y - ending[1][2])) * 10 f = g + h table.insert(open, {f, g, h, i, x, y, x..":"..y, curr[1][5], curr[1][6]}) else tmp = resultopen [1][1] g1 = open[tmp][2] if i%2 == 1 then g = curr[1][2] + 10 else g = curr[1][2] + 14 end if g < g1 then h = (math.abs(x - ending[1][1]) + math.abs(y - ending[1][2])) * 10 f = g + h table.insert(open, {f, g, h, i, x, y, x..":"..y, curr[1][5], curr[1][6]}) end end end end end end if (curr [1][5] == ending [1][1] and curr [1][6] == ending [1][2]) or #open == 0 then break end end
local pathAB, tmp, path = {}, {}, {} tmp [1] = {ending[1][1], ending[1][2]} table.insert(tmp, {close[#close][8], close[#close][9], close[#close][4]})
while tmp[#tmp][1] ~= start[1][1] or tmp[#tmp][2] ~= start[1][2] do pathAB = index_of(close, tmp[#tmp][1]..":"..tmp[#tmp][2]) table.insert (tmp, {close[pathAB[1][1]][8], close[pathAB[1][1]][9], close[pathAB[1][1]][4]}) end
for i = #tmp, 1, -1 do table.insert (path, {map[tmp[i][1]][tmp[i][2]][2], map[tmp[i][1]][tmp[i][2]][3]}) end return path end
-- создание карты map = Create_Map(find[1],find[2],find[3],find[4],find[5],find[6],find[7],find[8])
-- поиск точки A в массиве map start = {} start = index_of_A_B(map, "A")
-- поиск точки B в массиве map ending = {} ending = index_of_A_B(map, "B")
-- поиск пути if #start > 0 and #ending > 0 then path = {} path = A_star(map)
-- ход for i = 1, #path do kleft (path[i][1], path[i][2]) end
elseif #start == 0 then log ("Точка A не найдена") else log ("Точка B не найдена") end https://youtu.be/w4e9a3xjdwk
labirint.bmp ( 789,13 килобайт )
Кол-во скачиваний: 314
|
|
|
|
cirus |
3.6.2017, 13:15
|
Elder
Сообщений: 3.480
Регистрация: 18.8.2014 Группа: Пользователи Наличность: 26703
Пользователь №: 16.971
Возраст: 29
|
A* Lua, 2.0
Код --lua log ("clear") log ("mode compact")
-- ходы по диагонали, 0 - нет, 1 - да angle = 0
-- параметры findcolor find = {29, 25, 522, 516, 10, 10, "(0-16777215)", "%arr"}
-- создание карты function Create_Map(startX, startY, endX, endY, stepX, stepY, color, array) local z = 0 local a = findcolor(startX, startY, endX, endY, stepX, stepY, "(0-16777215)", "%arr") if #arr > 0 then local map = {} for i = 1, ((endY - startY) / stepY) + 1 do map[i] = {} for j = 1, ((endX - startX) / stepX) + 1 do z = z + 1 if tonumber(arr[z][3]) == 0 then map[i][j] = {1, arr[z][1], arr[z][2]} elseif tonumber(arr[z][3]) == 255 then map[i][j] = {"A", arr[z][1], arr[z][2]} -- точка A в массиве map start = {} start[1] = {i, j} elseif tonumber(arr[z][3]) == 16711680 then map[i][j] = {"B", arr[z][1], arr[z][2]} -- точка A в массиве map ending = {} ending[1] = {i, j} else map[i][j] = {0, arr[z][1], arr[z][2]} end end end return map end end
-- поиск в массиве function index_of(arr, text) local result = {} for i = 1, #arr do if arr[i][7] == text then table.insert(result, {i, 7}) end end return result end
-- A* function A_star(map) local g, g1, h, f, tmp = 0, 0, 0, 0, 0 local open, close, curr, index, resultclose, resultopen, vector = {}, {}, {}, {}, {}, {}, {} table.insert(vector, {-1, -1, 0, 1, 1, 1, 0, -1}) table.insert(vector, {0, 1, 1, 1, 0, -1, -1, -1})
table.insert(open, {0, 0, 0, 0, start [1][1], start [1][2], start [1][1]..":"..start [1][2], start [1][1], start [1][2]}) while 1 == 1 do table.sort (open, function (a, b) return (a[1] < b[1]) end) curr [1] = {open [1][1], open [1][2], open [1][3], open [1][4], open [1][5], open [1][6], open [1][7], open [1][8], open [1][9]} table.insert(close, {open [1][1], open [1][2], open [1][3], open [1][4], open [1][5], open [1][6], open [1][7], open [1][8], open [1][9]}) table.remove (open, 1) for i = 1, 8 do if angle == 1 or i%2 == 1 then local x, y = curr[1][5] + vector[1][i], curr[1][6] + vector[2][i] resultclose = index_of(close, x..":"..y) if x > 0 and y > 0 and x <= #map[i] and y <= #map then if (map[x][y][1] == 0 or map[x][y][1] == "B") and #resultclose == 0 then resultopen = index_of(open, x..":"..y) if #resultopen == 0 then if i%2 == 1 then g = curr[1][2] + 10 else g = curr[1][2] + 14 end h = (math.abs(x - ending[1][1]) + math.abs(y - ending[1][2])) * 10 f = g + h table.insert(open, {f, g, h, i, x, y, x..":"..y, curr[1][5], curr[1][6]}) else tmp = resultopen [1][1] g1 = open[tmp][2] if i%2 == 1 then g = curr[1][2] + 10 else g = curr[1][2] + 14 end if g < g1 then h = (math.abs(x - ending[1][1]) + math.abs(y - ending[1][2])) * 10 f = g + h table.insert(open, {f, g, h, i, x, y, x..":"..y, curr[1][5], curr[1][6]}) end end end end end end if (curr [1][5] == ending [1][1] and curr [1][6] == ending [1][2]) or #open == 0 then break end end
local pathAB, tmp, path = {}, {}, {} tmp [1] = {ending[1][1], ending[1][2]} table.insert(tmp, {close[#close][8], close[#close][9], close[#close][4]})
while tmp[#tmp][1] ~= start[1][1] or tmp[#tmp][2] ~= start[1][2] do pathAB = index_of(close, tmp[#tmp][1]..":"..tmp[#tmp][2]) table.insert (tmp, {close[pathAB[1][1]][8], close[pathAB[1][1]][9], close[pathAB[1][1]][4]}) end
for i = #tmp, 1, -1 do table.insert (path, {map[tmp[i][1]][tmp[i][2]][2], map[tmp[i][1]][tmp[i][2]][3]}) end return path end
-- создание карты map = Create_Map(find[1],find[2],find[3],find[4],find[5],find[6],find[7],find[8])
-- поиск пути if #start > 0 and #ending > 0 then path = {} path = A_star(map)
-- ход for i = 1, #path do kleft (path[i][1], path[i][2]) end
elseif #start == 0 then log ("Точка A не найдена") else log ("Точка B не найдена") end Подправил поиск в массиве. Теперь быстрее работает. Цитата Производительность тестил? Как работает os.clock я не понял, точнее что за число он выдаёт. Так что точных данных нет. На пилотовском языке на этот же лабиринт уходило примерно 20 секунд. На Lua меньше 1 секунды. Так что разница как минимум в 20 раз. Встроенные функции пилота работают быстрее, чем те что написаны на lua самим? Например, пилотовский index_of быстрее выдаст результат, чем это?: код
Код -- поиск в массиве function index_of(arr, text) local result = {} for i = 1, #arr do for j = 1, #arr[i] do if arr[i][j] == text then table.insert(result, {i, j}) end end end return result end
|
|
|
|
cirus |
3.6.2017, 18:06
|
Elder
Сообщений: 3.480
Регистрация: 18.8.2014 Группа: Пользователи Наличность: 26703
Пользователь №: 16.971
Возраст: 29
|
A* Lua, 3.0
Код --lua time_start = os.clock() log ("clear") log ("mode compact")
-- ходы по диагонали, 0 - нет, 1 - да angle = 0
-- параметры findcolor find = {5, 5, 620, 620, 1, 1, "(0-16777215)", "%arr"} -- большой лабиринт --find = {29, 25, 522, 516, 10, 10, "(0-16777215)", "%arr"} -- маленький лабиринт
-- создание карты function Create_Map(startX, startY, endX, endY, stepX, stepY, color, array) local z = 0 local a = findcolor(startX, startY, endX, endY, stepX, stepY, "(0-16777215)", "%arr") if #arr > 0 then local map = {} for i = 1, ((endY - startY) / stepY) + 1 do map[i] = {} for j = 1, ((endX - startX) / stepX) + 1 do z = z + 1 if tonumber(arr[z][3]) == 0 then map[i][j] = {1, arr[z][1], arr[z][2]} elseif tonumber(arr[z][3]) == 255 then map[i][j] = {"A", arr[z][1], arr[z][2]} -- точка A в массиве map start = {} start[1] = {i, j} elseif tonumber(arr[z][3]) == 16711680 then map[i][j] = {"B", arr[z][1], arr[z][2]} -- точка A в массиве map ending = {} ending[1] = {i, j} else map[i][j] = {0, arr[z][1], arr[z][2]} end end end return map end end
-- A* function A_star(map) local g, g1, h, f, tmp = 0, 0, 0, 0, 0 local open, close, curr, index, resultclose, resultopen, vector, close_map, open_map = {}, {}, {}, {}, {}, {}, {}, {}, {}
for i = 1, #map do close_map [i] = {} end
for i = 1, #map do open_map [i] = {} for j = 1, #map [i] do open_map[i][j] = {} end end
table.insert(vector, {-1, -1, 0, 1, 1, 1, 0, -1}) table.insert(vector, {0, 1, 1, 1, 0, -1, -1, -1}) table.insert(open, {0, 0, 0, 0, start [1][1], start [1][2], start [1][1]..":"..start [1][2], start [1][1], start [1][2]}) while 1 == 1 do table.sort (open, function (a, b) return (a[1] < b[1]) end) curr [1] = {open [1][1], open [1][2], open [1][3], open [1][4], open [1][5], open [1][6], open [1][7], open [1][8], open [1][9]} table.insert(close, {open [1][1], open [1][2], open [1][3], open [1][4], open [1][5], open [1][6], open [1][7], open [1][8], open [1][9]}) close_map [open [1][5]][open [1][6]] = 1 table.remove (open, 1) for i = 1, 8 do if angle == 1 or i%2 == 1 then local x, y = curr[1][5] + vector[1][i], curr[1][6] + vector[2][i] if x > 0 and y > 0 and x <= #map[i] and y <= #map then if (map[x][y][1] == 0 or map[x][y][1] == "B") and close_map[x][y] == nil then if open_map[x][y][1] == nil then if i%2 == 1 then g = curr[1][2] + 10 else g = curr[1][2] + 14 end h = (math.abs(x - ending[1][1]) + math.abs(y - ending[1][2])) * 10 f = g + h table.insert(open, {f, g, h, i, x, y, x..":"..y, curr[1][5], curr[1][6]}) open_map[x][y] = {i, curr[1][5], curr[1][6]} else g1 = open_map[x][y][2] if i%2 == 1 then g = curr[1][2] + 10 else g = curr[1][2] + 14 end if g < g1 then h = (math.abs(x - ending[1][1]) + math.abs(y - ending[1][2])) * 10 f = g + h table.insert(open, {f, g, h, i, x, y, x..":"..y, curr[1][5], curr[1][6]}) open_map[x][y] = {i, curr[1][5], curr[1][6]} end end end end end end if (curr [1][5] == ending [1][1] and curr [1][6] == ending [1][2]) or #open == 0 then break end end
local pathAB, tmp, path = {}, {}, {} tmp [1] = {ending[1][1], ending[1][2]} table.insert(tmp, {close[#close][8], close[#close][9], close[#close][4]})
while tmp[#tmp][1] ~= start[1][1] or tmp[#tmp][2] ~= start[1][2] do table.insert (tmp,{open_map[tmp[#tmp][1]][tmp[#tmp][2]][2],open_map[tmp[#tmp][1]][tmp[#tmp][2]][3], open_map[tmp[#tmp][1]][tmp[#tmp][2]][1]}) end
for i = #tmp, 1, -1 do table.insert (path, {map[tmp[i][1]][tmp[i][2]][2], map[tmp[i][1]][tmp[i][2]][3], map[tmp[i][1]][tmp[i][2]][1]}) end return path end
-- создание карты map = Create_Map(find[1],find[2],find[3],find[4],find[5],find[6],find[7],find[8]) time_create_map = os.clock() - time_start log ("Создание карты:".." "..time_create_map) -- поиск пути if #start > 0 and #ending > 0 then path = {} path = A_star(map) time_create_path = os.clock() - time_start - time_create_map log ("Поиск пути:".." "..time_create_path)
-- ход for i = 1, #path do kleft (path[i][1], path[i][2]) end time_paint_path = os.clock() - time_start - time_create_path - time_create_map log ("Рисование маршрута:".." "..time_paint_path) log ("Всего затрачено времени:".." "..time_create_map + time_create_path + time_paint_path) elseif #start == 0 then log ("Точка A не найдена") else log ("Точка B не найдена") end Чуть подправил. Теперь быстрее работает. На маленький лабиринт уходит 50 мсек. Тест на лабиринте 601*601 пиксель : https://youtu.be/9aQd-s86yFk
|
|
|
|
FREEON |
29.3.2018, 18:17
|
Journeyman
Сообщений: 365
Регистрация: 14.2.2017 Группа: Пользователи Наличность: 1318
Пользователь №: 18.346
Возраст: 25
|
|
|
|
|
nykep |
1.3.2023, 0:39
|
Apprentice
Сообщений: 233
Регистрация: 1.9.2012 Группа: Пользователи Наличность: 1196
Пользователь №: 15.246
Возраст: 25
|
пытался для игры сделать поиск пути и получилась прикольная штука, он не ищет кратчайший путь, просто пробегает по дорожке, пока примитивно но всё же Код --lua local startX, startY = 960, 520 --начало пути local nextX, nextY = 960, 520 --начало пути local ending = 0 local fat = 5 -- "толщина дорожки" local pcolor = 0 -- цвет дорожки (как запихнуть в переменную набор цветов или диапазон я не знаю) move (startX, startY) wait (50) kleft_down (startX, startY) repeat local path = findcolor(startX - fat, startY - fat, startX + fat, startY + fat, pcolor, '%p', 2, -1, 0) if path then for i = 1, path do dist = math.sqrt((nextX - p[i][1])^2 + (nextY - p[i][2])^2) if i == 1 then max = dist end if max <= dist then max = dist nextX2 = p[i][1] nextY2 = p[i][2] end end nextX, nextY = startX, startY startX, startY = nextX2, nextY2 ending = math.sqrt((startX - nextX)^2 + (startY - nextY)^2) move (startX, startY) end until ending < max * 0.4 --должен дойти до конца дорожки
|
|
|
|
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0
|
|