|
Алгоритм А*, Поиск пути |
|
|
cirus |
24.4.2017, 2:19
|
Elder
Сообщений: 3.480
Регистрация: 18.8.2014 Группа: Пользователи Наличность: 26744
Пользователь №: 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
|
|
|
|
cirus |
25.4.2017, 11:13
|
Elder
Сообщений: 3.480
Регистрация: 18.8.2014 Группа: Пользователи Наличность: 26744
Пользователь №: 16.971
Возраст: 29
|
Цитата Вообще в моем понимании подобных алгоритм должен возвращать массив с координатами точек пути, а передвижение между ними не более чем пользовательская функция. Оно почти так и есть. Массив %resultarray содержит индексы для массива с координатами (%coord) и направление движения. Например, это массив %resultarray: Код 2 2 5 3 2 5 3 3 3 3 4 1 2 4 2 2 это начальная точка, 5 это направление движения (вниз). 2 4 конечная точка Если используются клики, то: left %coord [3 2] - первый ход left %coord [3 3] - второй left %coord [3 4] - третий left %coord [2 4] - четвёртый Сейчас скрипт останавливает поиск, если путь до конечной точки найден. Для нескольких точек нужно менять условие, или делать процедуру для поиска и искать сначала путь до одной точки, потом до другой.
|
|
|
|
cirus |
28.4.2017, 3:16
|
Elder
Сообщений: 3.480
Регистрация: 18.8.2014 Группа: Пользователи Наличность: 26744
Пользователь №: 16.971
Возраст: 29
|
Цитата Т.е. есть некоторый набор точек с указанием к каким точкам из них можно добраться. Возьмём тот же лабиринт, на котором есть 5 точек (A - начальная точка, остальные - B, C, D, E). Нужно добраться из точки A до указанных, например, C и D. Найти путь A-C-D, найти путь A-D-C. Выбрать тот, который короче. Так должно быть?
|
|
|
|
DarkMaster |
28.4.2017, 5:53
|
Модератор UOPilot
Сообщений: 9.467
Регистрация: 2.12.2008 Группа: Супермодераторы Наличность: 27724
Пользователь №: 11.279
|
Цитата Найти путь A-C-D, найти путь A-D-C. Выбрать тот, который короче. Так должно быть? Давай на более понятных тебе величинах (IMG: style_emoticons/default/smile.gif) Дано: орен, дарк елвен, глудин, глудио, дион, гиран, гиран харбор. Из каждого города мы можем переместиться только в соседний(ходим пешком). Нужно найти кротчайший путь из орена в глудин.
--------------------
Скрипты UOPilot под заказ. Консультации по UOpilot 15$/час. Услуги Lua разработчика (не пилот, проекты, постоянка) Disсоrd: Kov____
|
|
|
|
Aimed |
28.4.2017, 16:32
|
Grandmaster
Сообщений: 2.250
Регистрация: 29.12.2012 Группа: Пользователи Наличность: 8677
Пользователь №: 15.607
|
Цитата(DarkMaster @ 27.4.2017, 17:31) Ну вейпоинты не такая большая проблема на самом деле. У меня был (да и сейчас где-то валяется) алгоритм перемещения из коодинат x1, y1 в x2, y2 для вов. Игровые координаты дернуть не так сложно, как могло бы показаться.
Не, я о другом. Я об обобщении и вшивании его в пилот как функции для поиска пути. Проблема в том что есть слишком много разных факторов которые зависят от контекста. Допустим возьмем УО. Если на пути стоят персонажи, их все обходить или смотреть что по стамине и проходить через персонажа? Если ты находишься на крыше у которой нет бортиков и с неё можно спрыгнуть? Если на пути находится паутина, в которой ты застрянешь, но сама она непроходимой не является? И так с каждой игрой. Тут надо очень хорошо все нюансы игры знать, что-бы делать правильные расчеты кратчайшего пути через А*. Например в той-же РанУО, при патфайндинге у мобов ( там тоже А* используется), между каждый тайлом используется весь алгоритм с проверками на шаг, а это довольно много кода, ибо нюансов вагон и тележка. Пробежка по вей пойнтам х это тоже самое что запуск А* х раз. Зачем вам это как отдельная фича? Имхо в ней есть смысл только в том случае, если у вас есть пачка вей пойнтов и все они не упорядочены. Тоесть нужно получить общий кратчайший путь через все вей пойнты. Но в каком случае можно встретить такой сценарий, где у вас куча разных точек, разбросанных по карте и вам нужно по ним создать кратчайший маршрут?
|
|
|
|
DarkMaster |
28.4.2017, 16:51
|
Модератор UOPilot
Сообщений: 9.467
Регистрация: 2.12.2008 Группа: Супермодераторы Наличность: 27724
Пользователь №: 11.279
|
Цитата Не, я о другом. Я об обобщении и вшивании его в пилот как функции для поиска пути. Проблема в том что есть слишком много разных факторов которые зависят от контекста. Допустим возьмем УО. Если на пути стоят персонажи, их все обходить или смотреть что по стамине и проходить через персонажа? Если ты находишься на крыше у которой нет бортиков и с неё можно спрыгнуть? Если на пути находится паутина, в которой ты застрянешь, но сама она непроходимой не является?
И так с каждой игрой. Тут надо очень хорошо все нюансы игры знать, что-бы делать правильные расчеты кратчайшего пути через А*. Например в той-же РанУО, при патфайндинге у мобов ( там тоже А* используется), между каждый тайлом используется весь алгоритм с проверками на шаг, а это довольно много кода, ибо нюансов вагон и тележка.
Для этого должен быть разработан формат карты который будет учитывать данные детали. Т.е. в моем понимании это xyz координаты, модификатор стоимость пути, задание фиксированной стоимости. Карта должна создаваться непосредственно пользователем. Алгоритм же поиска не должен каждый раз вымучиваться на движке пилота. Цитата Пробежка по вей пойнтам х это тоже самое что запуск А* х раз. Каким это образом? Это будет запуск 1 раз, просто логика должна понимать различную ценность маршрута и ограничения связей. Цитата Зачем вам это как отдельная фича? Имхо в ней есть смысл только в том случае, если у вас есть пачка вей пойнтов и все они не упорядочены. Тоесть нужно получить общий кратчайший путь через все вей пойнты. Но в каком случае можно встретить такой сценарий, где у вас куча разных точек, разбросанных по карте и вам нужно по ним создать кратчайший маршрут? Навигация в любом полноценном 3д приложении.
--------------------
Скрипты UOPilot под заказ. Консультации по UOpilot 15$/час. Услуги Lua разработчика (не пилот, проекты, постоянка) Disсоrd: Kov____
|
|
|
|
pager |
28.4.2017, 17:21
|
Apprentice
Сообщений: 147
Регистрация: 10.1.2006 Группа: Пользователи Наличность: 0 Из: --
Пользователь №: 4.699
Возраст: --
|
Цитата(Aimed @ 28.4.2017, 19:32) Не, я о другом. Я об обобщении и вшивании его в пилот как функции для поиска пути. Проблема в том что есть слишком много разных факторов которые зависят от контекста. Допустим возьмем УО. Если на пути стоят персонажи, их все обходить или смотреть что по стамине и проходить через персонажа? Если ты находишься на крыше у которой нет бортиков и с неё можно спрыгнуть? Если на пути находится паутина, в которой ты застрянешь, но сама она непроходимой не является?
И так с каждой игрой. Тут надо очень хорошо все нюансы игры знать, что-бы делать правильные расчеты кратчайшего пути через А*. Например в той-же РанУО, при патфайндинге у мобов ( там тоже А* используется), между каждый тайлом используется весь алгоритм с проверками на шаг, а это довольно много кода, ибо нюансов вагон и тележка. Пробежка по вей пойнтам х это тоже самое что запуск А* х раз. Зачем вам это как отдельная фича? Имхо в ней есть смысл только в том случае, если у вас есть пачка вей пойнтов и все они не упорядочены. Тоесть нужно получить общий кратчайший путь через все вей пойнты. Но в каком случае можно встретить такой сценарий, где у вас куча разных точек, разбросанных по карте и вам нужно по ним создать кратчайший маршрут?
На мой взгляд Не думаю что в поиске пути правильно было бы учитывать динамические препятствия , получатель маршрута должен сам оценивать динамические препятствия и максимум что можно было бы сделать это системе поиска маршрута посылать уведомления что проложенный маршрут не подходит для использования и система его не учитывала в новом положении маршрута.
|
|
|
|
cirus |
29.4.2017, 21:38
|
Elder
Сообщений: 3.480
Регистрация: 18.8.2014 Группа: Пользователи Наличность: 26744
Пользователь №: 16.971
Возраст: 29
|
Пока черновой вариант. Путь считается только по расстоянию. код
Код // Алгоритм A* load_array %map C:\Users\abc\Desktop\map.txt // массив карта load_array %coord C:\Users\abc\Desktop\coord.txt // координаты точек
set $start 4 // начальная точка set $ending 1 // конечная
set #click 0 // делать ходы, клик по координатам точек. Нужна привязка в paint.
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)
// Позиция конечной точки на карте for #i 1 size(%map) if %map[#i 1] = $ending set %ending [1 1] $ending break end_if end_for
// Позиция начальной точки на карте set %start [1 1] 7 for #i 1 size(%map) if %map[#i 1] = $start set %start [1 1] $start break end_if end_for
// F, G, H, Текущая клетка, Родительская клетка, Текущая клетка:Родительская клетка init_arr %open (1) 0 0 0 %start [1 1] %start [1 1] %start [1 1]:%start [1 1]
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] // текущая клетка init_arr %close (#sizeclose) %open [1 1] %open [1 2] %open [1 3] %open [1 4] %open [1 5] %open [1 6] // добавить в закрытый список delete_array %open -1 // удалить с открытого списка for #t 2 size(%map[1]) // проверяем все точки, в которые можно дойти из текущей set #tmp %map [%curr[1 4] #t] if #tmp != 0 set #x %map [%curr[1 4] #t] // текущая точка // %curr[1 4] - родитель init_arr %tmp (1) #x : %curr [1 4] set #sizeopen size(%open) + 1 set #g %curr [1 2] + round(point_distance(%coord[%curr [1 4] 1] %coord[#x 1])) // стоимость G set #h round(point_distance(%coord[$ending 1] %coord[#x 1])) // стоимость H set #f #g + #h // стоимость F init_arr %tmp (1) #x : %curr [1 4] init_arr %open (#sizeopen) #f #g #h #x %curr [1 4] %tmp [1] else break end_if end_for
if size(%open) = 0 or %curr [1 4] = %ending [1 1] // если открытый список пуст или конечная точка найдена set size(%tmp) set #tmp %curr [1 4] if %curr [1 4] = %ending [1 1] // если конечная точка найдена set #z #z + 1 set %tmp [#z] #tmp // идём от конечной точки к начальной while #tmp != $start for #i 1 size(%close) if %close [#i 4] = #tmp set #zz #zz + 1 set #tmp %close[#i 5] set #z #z + 1 set %tmp [#z] #tmp break end_if end_for end_while // переворачиваем путь set #z 0 for #i size(%tmp) 1 -1 set #z #z + 1 set %resultarray [#z] %tmp[#i 1] end_for
// вывод в лог пути for #i 1 size(%resultarray) log %resultarray [#i] %coord[%resultarray [#i]] if #click = 1 kleft %coord[%resultarray [#i]] end_if end_for else log Ходов нет end_if end_script end_if end_while end_script В массиве %map содержатся все точки в виде: <точка1> [до каких точек можно добраться из точки1] <точка2> [до каких точек можно добраться из точки2] В массиве %coord содержатся координаты всех точек. Координаты взяты с картинки открытой в Paint. В архиве 2 тхт файла (%map и %coord) и картинка.
Astar2.zip ( 7,66 килобайт )
Кол-во скачиваний: 194
Прикрепленные файлы
map.bmp ( 265,59 килобайт )
Кол-во скачиваний: 199
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|