|
Алгоритм А*, Поиск пути |
|
|
cirus |
24.4.2017, 2:19
|
Elder
Сообщений: 3.480
Регистрация: 18.8.2014 Группа: Пользователи Наличность: 26745
Пользователь №: 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 килобайт )
Кол-во скачиваний: 253 Описание алгоритма: 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 килобайт )
Кол-во скачиваний: 280
|
|
|
|
|
|
Ответов
nykep |
1.3.2023, 0:39
|
Apprentice
Сообщений: 233
Регистрация: 1.9.2012 Группа: Пользователи Наличность: 1213
Пользователь №: 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 --должен дойти до конца дорожки
|
|
|
|
Сообщений в этой теме
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 cirus [code]--lua
time_start = os.clock()
log ... 3.6.2017, 18:06 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
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|