|
Алгоритм А*, Поиск пути |
|
|
cirus |
24.4.2017, 2:19
|
Elder
Сообщений: 3.480
Регистрация: 18.8.2014 Группа: Пользователи Наличность: 26843
Пользователь №: 16.971
Возраст: 29
|
Алгоритм А*, 2.0
Код // Алгоритм A* load_array %map C:\Users\abc\Desktop\map1.txt // массив карта load_array %coord C:\Users\abc\Desktop\coord1.txt // координаты точек
set $start A // обозначение точки A в массиве set $ending B // обозначение точки B в массиве
// 0 - ходы только по вертикали и горизонтали, 1 - по диагонали тоже set #angle 0
set #logmap 1 // выводить в лог карту set #readmap 1 // выводить ходы в лог set #skipstep 0 // 0 - не пропускать ходы, 1 - пропускать. Нужно, если ширина препятствия меньше ширины клетки, на которую можно сделать ход. set #click 1 // делать ходы, клик по координатам точек. set #send 0 // делать ходы, нажатия клавииш Up, Down, Left, Right set #hint 1 // показывать количество проверенных точек set #showpoint 0 // показывать проверенные точки (клик по ним) set #wait 30 // пауза между нажатиями клавиш Up, Down, Left, Right
// остальное менять не нужно // направление движения init_arr %vector (1) -1 -1 0 1 1 1 0 -1 // x init_arr %vector (2) 0 1 1 1 0 -1 -1 -1 // y
set #handle workwindow if workwindow = 0 Log Не сделана привязка Log Скрипт остановлен stop_script end_if if size(%map) = 0 Log Массив с картой не найден. Log Скрипт остановлен stop_script end_if if size(%coord) = 0 Log Массив с координатами не найден. Log Скрипт остановлен stop_script end_if
log clear log mode compact set size(%tmp) set size(%open) set size(%close) set size(%curr) set size(%resultarray) set #width size(%map[]) set #height size(%map) set %sizemap indexof (%map (0)) set #sizemap size(%sizemap) + 1
// Позиция конечной точки на карте set %ending indexof (%map ($ending)) // Позиция начальной точки на карте set %start indexof (%map ($start)) // если точка A или B не найдены if size(%ending) = 0 or size(%start) = 0 if size(%start) = 0 log Точка A не найдена else log Точка B не найдена end_if log Скрипт остановлен end_script end_if
// F, G, H, Направление_движения, Текущая клетка(X Y), Текущая клетка(X:Y), Родительская клетка (X Y) init_arr %open (1) 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 sort_array %open // сортировка по наименьшему F set #sizeclose size(%close) + 1 init_arr %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] // текущая клетка init_arr %close (#sizeclose) %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] // добавить в закрытый список if #showpoint = 1 left %coord[%curr[1 5] %curr[1 6]] wait 1 end_if delete_array %open -1 // удалить с открытого списка
// для каждой из 8 клеток просчёт хода for #i 1 8 if #angle = 1 or mod(#i 2) = 1 // если ходы по диагонали допустимы или проверяется ход не по диагонали set #x %curr [1 5] + %vector [1 #i] set #y %curr [1 6] + %vector [2 #i] init_arr %tmp (1) #x : #y // поиск клетки в закрытом списке set %resultclose indexof (%close (%tmp[1])) if #x > 0 and #y > 0 and #x <= #height and #y <= #width // проверка не вышли ли за пределы массива if (%map [#x #y] = 0 or %map [#x #y] = $ending) and size(%resultclose) = 0 // (если на клетку возможен ход или она является конечной) и не находится в закрытом списке set %resultopen indexof (%open (%tmp[1])) // Если клетка еще не в открытом списке, то добавляем ее туда. if size( %resultopen) = 0 set #sizeopen size(%open) + 1 if mod(#i 2) = 1 set #g %curr [1 2] + 10 // стоимость G else set #g %curr [1 2] + 14 end_if set #h (abs(eval(#x - %ending [1 1])) + abs(eval(#y - %ending [1 2]))) * 10 // стоимость H set #f #g + #h // стоимость F init_arr %open (#sizeopen) #f #g #h #i #x #y %tmp[1] %curr [1 5] %curr [1 6] else // если клетка уже в открытом списке set #tmp %resultopen [1 1] // позиция клетки в открытом списке set #g1 %open[#tmp 2] // стоимость G клетки находящейся в открытом списке if mod(#i 2) = 1 set #g %curr [1 2] + 10 // стоимость G текущей клетки + стоимость хода на клетку находящуюся в открытом списке else set #g %curr [1 2] + 14 end_if if #g < #g1 // если стоимость хода дешевле // меняем стоимость хода клетки находящейся в открытом списке // меняем родителя клетки на текущую set #h (abs(eval(#x - %ending [1 1])) + abs(eval(#y - %ending [1 2]))) * 10 set #f #g + #h init_arr %open (#tmp) #f #g #h #i #x #y %tmp[1] %curr [1 5] %curr [1 6] end_if end_if end_if end_if end_if end_for
// если конечная клетка добавлена в закрытый список или все точки проверены if (%curr [1 5] = %ending [1 1] and %curr [1 6] = %ending [1 2]) or size(%open) = 0 if %curr [1 5] != %ending [1 1] and %curr [1 6] != %ending [1 2] log Вариантов хода нет end_script end_if
// проходим весь путь от точки B до точки A и записываем путь в массив set size(%tmp) init_arr %tmp (1) %close [size(%close) 8] %close [size(%close) 9] while %tmp [size(%tmp) 1] != %start [1 1] or %tmp [size(%tmp) 2] != %start [1 2] set %pathAB indexof (%close (%tmp [size(%tmp) 1]:%tmp [size(%tmp) 2])) set #zz size(%tmp) + 1 init_arr %tmp (#zz) %close [%pathAB [1 1] 8] %close [%pathAB [1 1] 9] %close [%pathAB [1 1] 4] end_while set #z 0 set delimiter ' ' for #i size(%tmp) 1 -1 set #z #z + 1 init_arr %resultarray (#z) %tmp [#i] end_for set delimiter // save_array %open C:\Users\abc\Desktop\open.txt // открытый список // save_array %close C:\Users\abc\Desktop\close.txt // закрытый список // save_array %resultarray C:\Users\abc\Desktop\resultarray.txt // массив с индексами нужных точек находящихся в массиве %map log На поиск хода затрачено: timer мсек
// Вывод карты if #logmap = 1 gosub logmap end_if
// Вывод в лог ходов if #readmap = 1 gosub readmap end_if
// Сделать ход if #click = 1 gosub hod end_if end_script end_if if #hint = 1 hint Проверено size(%close) из #sizemap точек. end_if end_while end_script
:logmap for #i 1 size(%map) log %map [#i] end_for return
:readmap set workwindow #handle wait 500 showwindow #handle wait 500
set #tmpi size(%resultarray) - 1 for #i 1 size(%resultarray) if (#skipstep = 0) or (mod (#i 2) = 0 or #tmpi = #i) switch %resultarray [#i 3] case 1: log Вверх if #send = 1 send {Up} wait #wait end_if break case 2: log Вверх-Вправо if #send = 1 send {Up} wait #wait send {Right} wait #wait end_if break case 3: log Вправо if #send = 1 send {Right} wait #wait end_if break case 4: log Вниз-Вправо if #send = 1 send {Down} wait #wait send {Right} wait #wait end_if break case 5: log Вниз if #send = 1 send {Down} wait #wait end_if break case 6: log Вниз-Влево if #send = 1 send {Down} wait #wait send {Left} wait #wait end_if break case 7: log Влево if #send = 1 send {Left} wait #wait end_if break case 8: log Вверх-Влево if #send = 1 send {Up} wait #wait send {Left} wait #wait end_if break end_switch end_if end_for return :hod if #showpoint = 1 alarm set showscriptprocessing 1 log Путь найден. Скрипт на паузе. log Для вывода пути снять скрипт с паузы. pause_script set showscriptprocessing 0 end_if showwindow #handle wait 500 if #skipstep = 0 for #i 2 size(%resultarray) // делать все ходы kleft %coord[%resultarray [#i 1] %resultarray [#i 2]] // log %coord[%resultarray [#i 1] %resultarray [#i 2]] wait 1 end_for else for #i 3 size(%resultarray) 2 // пропускать не нужные ходы kleft %coord[%resultarray [#i 1] %resultarray [#i 2]] // log %coord[%resultarray [#i 1] %resultarray [#i 2]] wait 1 end_for end_if return Уменьшен код почти на 200 строк. Работает чуть медленнее первой версии. Алгоритм А*, 1.0
АлгоритмA__версия1.zip ( 3,1 килобайт )
Кол-во скачиваний: 256 Описание алгоритма: http://masters.donntu.org/2013/fknt/buga/library/AStar.htmСкрипт просчитывает самый короткий путь от точки A до точки B. Для его работы нужен массив-карта, содержащий: 0 - точки, по которым можно перемещаться 1 - препятствия A - точка A (англ.) B - точка B (англ.) Если для ходов используются клики, то ещё нужен массив с координатами всех точек. Пример работы скрипта: https://youtu.be/dC-bBCIYuwEВ архиве картинки 2 лабиринтов и массив-карта к ним.
A.zip ( 38,2 килобайт )
Кол-во скачиваний: 285
|
|
|
|
|
|
Ответов
cirus |
3.6.2017, 18:06
|
Elder
Сообщений: 3.480
Регистрация: 18.8.2014 Группа: Пользователи Наличность: 26843
Пользователь №: 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
|
|
|
|
Сообщений в этой теме
cirus Алгоритм А* 24.4.2017, 2:19 Mirage Жухала <_<
:D
Адаптировать такое на как... 24.4.2017, 20:17 Cockney Все конечно здорово, но для второй карты минута с ... 24.4.2017, 22:33 DarkMaster сам когда-то задавался данной задачей, но что-то з... 25.4.2017, 1:15 cirus
Если на lua будет findcolor, скорее всего, все ра... 25.4.2017, 2:43 DarkMaster
Графов да, но Дейкстры ли? Вроде тоже а-старом ре... 25.4.2017, 5:54 cirus
Оно почти так и есть.
Массив %resultarray содержи... 25.4.2017, 11:13 WKnight Красавчик.
Свитч полностью дублируется. Так имхо ... 25.4.2017, 18:18 cirus
Спасибо. Подправил. 26.4.2017, 2:52 Aimed Вы же понимаете что вам для нормальной работы этог... 26.4.2017, 17:45 DarkMaster
Ну вейпоинты не такая большая проблема на самом д... 27.4.2017, 18:31 Aimed
Ну вейпоинты не такая большая проблема на самом д... 28.4.2017, 16:32 pager
Не, я о другом. Я об обобщении и вшивании его в п... 28.4.2017, 17:21 cirus
Возьмём тот же лабиринт, на котором есть 5 точек ... 28.4.2017, 3:16 DarkMaster
Давай на более понятных тебе величинах :)
Дано: о... 28.4.2017, 5:53 DarkMaster Черные линии некоторая координатная сетка. Задача ... 28.4.2017, 6:15 DarkMaster
Для этого должен быть разработан формат карты кот... 28.4.2017, 16:51 DarkMaster
Имхо решаться должно опять же пользователем при с... 28.4.2017, 17:29 pager
Имхо решаться должно опять же пользователем при с... 28.4.2017, 18:17 cirus Пока черновой вариант. Путь считается только по ра... 29.4.2017, 21:38 cirus [code]--lua
log ("clear") log ... 2.6.2017, 12:39 DarkMaster Производительность тестил? 3.6.2017, 5:39 cirus --lua
log ("clear") log (... 3.6.2017, 13:15 Cockney RE: Алгоритм А* 3.6.2017, 13:54 cirus Вроде понял.
--lua
time_start = os.clock(... 3.6.2017, 14:09 DarkMaster
Жесть!
А как ты генерировал эти лабиринты?
... 5.6.2017, 23:19 Cockney На асме невозможно написать коряво,ибо кто пишет н... 6.6.2017, 1:01 cirus
В поисковике скачать картинки лабиринта :)
В ал... 6.6.2017, 2:06 dron4938 думал на ссд будет быстрее, оказалось ниочинь)
Мар... 24.3.2018, 16:28 cirus Диск не влияет. Скорее всего только процессор, хот... 24.3.2018, 17:09 FREEON Прикольно...а можно ли подобрать путь к выходам?
... 29.3.2018, 18:17 cirus В bmp или png картинку лабиринта скиньте. 30.3.2018, 12:37 FREEON
В bmp или png картинку лабиринта скиньте.
Да лан... 30.3.2018, 15:31 cirus
Обновил. http://masters.donntu.org/2013/fknt/buga... 31.3.2018, 1:34 nykep пытался для игры сделать поиск пути и получилась п... 1.3.2023, 0:39
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|