![]() |
![]() |
cirus |
![]()
Сообщение
#1
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Elder Сообщений: 2.865 Регистрация: 18.8.2014 Группа: Пользователи Наличность: 18209 Пользователь №: 16.971 Возраст: 29 ![]() |
Алгоритм А*, 2.0
Код // Алгоритм A* Уменьшен код почти на 200 строк. Работает чуть медленнее первой версии. Алгоритм А*, 1.0
Описание алгоритма: http://masters.donntu.org/2013/fknt/buga/library/AStar.htm Скрипт просчитывает самый короткий путь от точки A до точки B. Для его работы нужен массив-карта, содержащий: 0 - точки, по которым можно перемещаться 1 - препятствия A - точка A (англ.) B - точка B (англ.) Если для ходов используются клики, то ещё нужен массив с координатами всех точек. Пример работы скрипта: https://youtu.be/dC-bBCIYuwE В архиве картинки 2 лабиринтов и массив-карта к ним. ![]() |
Mirage |
![]() ![]()
Сообщение
#2
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Наличность: 0 Из: Иваново Пользователь №: 13.089 Возраст: 35 ![]() |
Жухала
![]() ![]() Адаптировать такое на какую нибудь рогрпг аля дьяблы что бы искал кротчайший путь по карте до выхода их подземелья. Все проходящие игру на скоростью сдохнут от зависти. -------------------- |
Cockney |
![]()
Сообщение
#3
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() Adept Сообщений: 1.112 Регистрация: 22.6.2013 Группа: Пользователи Наличность: 13907 Пользователь №: 16.156 ![]() |
Все конечно здорово, но для второй карты минута с лишним расчет. Встроить в пилот было бы замечательно. Да и предусмотреть бы возможность сохранения результата.
|
DarkMaster |
![]()
Сообщение
#4
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Модератор UOPilot Сообщений: 8.505 Регистрация: 2.12.2008 Группа: Супермодераторы Наличность: 25428 Пользователь №: 11.279 ![]() |
сам когда-то задавался данной задачей, но что-то заглохло все.
В состоянии ли данная реализация выдать путь для некоторого набора вейпонитов? Т.е. есть некоторый набор точек с указанием к каким точкам из них можно добраться. -------------------- Скрипты под заказ.
Консультации по UOpilot через ICQ, Skype, Ventrilo, TeamSpeak, TeamViewer 700р/час. |
cirus |
![]()
Сообщение
#5
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Elder Сообщений: 2.865 Регистрация: 18.8.2014 Группа: Пользователи Наличность: 18209 Пользователь №: 16.971 Возраст: 29 ![]() |
Цитата но для второй карты минута с лишним расчет. Если на lua будет findcolor, скорее всего, все расчёты займут минимум времени. Можно функцию написать. Цитата В состоянии ли данная реализация выдать путь для некоторого набора вейпонитов? Т.е. есть некоторый набор точек с указанием к каким точкам из них можно добраться. Это скорее в сторону графов. Алгоритм Дейкстры. Если доработать можно и этим искать путь, только на пилотовском языке устанешь ждать. Самая большая проблема - это создание карты, а не поиск пути. |
DarkMaster |
![]()
Сообщение
#6
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Модератор UOPilot Сообщений: 8.505 Регистрация: 2.12.2008 Группа: Супермодераторы Наличность: 25428 Пользователь №: 11.279 ![]() |
Цитата Это скорее в сторону графов. Алгоритм Дейкстры. Графов да, но Дейкстры ли? Вроде тоже а-старом решается... По крайней мере принципиальных отличий не вижу. Вообще в моем понимании подобных алгоритм должен возвращать массив с координатами точек пути, а передвижение между ними не более чем пользовательская функция. -------------------- Скрипты под заказ.
Консультации по UOpilot через ICQ, Skype, Ventrilo, TeamSpeak, TeamViewer 700р/час. |
cirus |
![]()
Сообщение
#7
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Elder Сообщений: 2.865 Регистрация: 18.8.2014 Группа: Пользователи Наличность: 18209 Пользователь №: 16.971 Возраст: 29 ![]() |
Цитата Вообще в моем понимании подобных алгоритм должен возвращать массив с координатами точек пути, а передвижение между ними не более чем пользовательская функция. Оно почти так и есть. Массив %resultarray содержит индексы для массива с координатами (%coord) и направление движения. Например, это массив %resultarray: Код 2 2 5 2 2 это начальная точка, 5 это направление движения (вниз). 2 4 конечная точка Если используются клики, то: left %coord [3 2] - первый ход left %coord [3 3] - второй left %coord [3 4] - третий left %coord [2 4] - четвёртый Сейчас скрипт останавливает поиск, если путь до конечной точки найден. Для нескольких точек нужно менять условие, или делать процедуру для поиска и искать сначала путь до одной точки, потом до другой. |
WKnight |
![]()
Сообщение
#8
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Разработчик UO Pilot'а Сообщений: 1.639 Регистрация: 9.1.2006 Группа: Модераторы Наличность: 6438 Пользователь №: 4.688 ![]() |
Красавчик.
Свитч полностью дублируется. Так имхо чуть короче. Код for #i 1 size(%resultarray) Сообщение отредактировал WKnight - 25.4.2017, 18:19 |
cirus |
![]()
Сообщение
#9
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Elder Сообщений: 2.865 Регистрация: 18.8.2014 Группа: Пользователи Наличность: 18209 Пользователь №: 16.971 Возраст: 29 ![]() |
Цитата Свитч полностью дублируется. Так имхо чуть короче Спасибо. Подправил. |
Aimed |
![]()
Сообщение
#10
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Grandmaster Сообщений: 2.131 Регистрация: 29.12.2012 Группа: Пользователи Наличность: 10243 Пользователь №: 15.607 ![]() |
Вы же понимаете что вам для нормальной работы этого алгоритма в пилоте нужно так-же правила передвижения от ноде к ноде знать.
Мож для какого-нибудь 2Д лабиринта где только стенка и не стенка есть и сойдет, а все остальное... я не вижу как можно обобщить это и вшить в пилот. Тут для каждой игры свои правила будут. |
DarkMaster |
![]()
Сообщение
#11
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Модератор UOPilot Сообщений: 8.505 Регистрация: 2.12.2008 Группа: Супермодераторы Наличность: 25428 Пользователь №: 11.279 ![]() |
Цитата Мож для какого-нибудь 2Д лабиринта где только стенка и не стенка есть и сойдет, а все остальное... я не вижу как можно обобщить это и вшить в пилот. Тут для каждой игры свои правила будут. Ну вейпоинты не такая большая проблема на самом деле. У меня был (да и сейчас где-то валяется) алгоритм перемещения из коодинат x1, y1 в x2, y2 для вов. Игровые координаты дернуть не так сложно, как могло бы показаться. -------------------- Скрипты под заказ.
Консультации по UOpilot через ICQ, Skype, Ventrilo, TeamSpeak, TeamViewer 700р/час. |
cirus |
![]()
Сообщение
#12
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Elder Сообщений: 2.865 Регистрация: 18.8.2014 Группа: Пользователи Наличность: 18209 Пользователь №: 16.971 Возраст: 29 ![]() |
Цитата Т.е. есть некоторый набор точек с указанием к каким точкам из них можно добраться. Возьмём тот же лабиринт, на котором есть 5 точек (A - начальная точка, остальные - B, C, D, E). Нужно добраться из точки A до указанных, например, C и D. Найти путь A-C-D, найти путь A-D-C. Выбрать тот, который короче. Так должно быть? |
DarkMaster |
![]()
Сообщение
#13
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Модератор UOPilot Сообщений: 8.505 Регистрация: 2.12.2008 Группа: Супермодераторы Наличность: 25428 Пользователь №: 11.279 ![]() |
Цитата Найти путь A-C-D, найти путь A-D-C. Выбрать тот, который короче. Так должно быть? Давай на более понятных тебе величинах ![]() Дано: орен, дарк елвен, глудин, глудио, дион, гиран, гиран харбор. Из каждого города мы можем переместиться только в соседний(ходим пешком). Нужно найти кротчайший путь из орена в глудин. -------------------- Скрипты под заказ.
Консультации по UOpilot через ICQ, Skype, Ventrilo, TeamSpeak, TeamViewer 700р/час. |
DarkMaster |
![]()
Сообщение
#14
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Модератор UOPilot Сообщений: 8.505 Регистрация: 2.12.2008 Группа: Супермодераторы Наличность: 25428 Пользователь №: 11.279 ![]() |
Черные линии некоторая координатная сетка. Задача добраться из синего в красный. Предполагается, что цена пути помимо значения расстояния может дополнительны иметь модификатор (на некоторых локациях невозможно использовать ездовых животных, например), либо задан константой (частные случаи).
Эскизы прикрепленных изображений ![]() -------------------- Скрипты под заказ.
Консультации по UOpilot через ICQ, Skype, Ventrilo, TeamSpeak, TeamViewer 700р/час. |
Aimed |
![]()
Сообщение
#15
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Grandmaster Сообщений: 2.131 Регистрация: 29.12.2012 Группа: Пользователи Наличность: 10243 Пользователь №: 15.607 ![]() |
Ну вейпоинты не такая большая проблема на самом деле. У меня был (да и сейчас где-то валяется) алгоритм перемещения из коодинат x1, y1 в x2, y2 для вов. Игровые координаты дернуть не так сложно, как могло бы показаться. Не, я о другом. Я об обобщении и вшивании его в пилот как функции для поиска пути. Проблема в том что есть слишком много разных факторов которые зависят от контекста. Допустим возьмем УО. Если на пути стоят персонажи, их все обходить или смотреть что по стамине и проходить через персонажа? Если ты находишься на крыше у которой нет бортиков и с неё можно спрыгнуть? Если на пути находится паутина, в которой ты застрянешь, но сама она непроходимой не является? И так с каждой игрой. Тут надо очень хорошо все нюансы игры знать, что-бы делать правильные расчеты кратчайшего пути через А*. Например в той-же РанУО, при патфайндинге у мобов ( там тоже А* используется), между каждый тайлом используется весь алгоритм с проверками на шаг, а это довольно много кода, ибо нюансов вагон и тележка. Пробежка по вей пойнтам х это тоже самое что запуск А* х раз. Зачем вам это как отдельная фича? Имхо в ней есть смысл только в том случае, если у вас есть пачка вей пойнтов и все они не упорядочены. Тоесть нужно получить общий кратчайший путь через все вей пойнты. Но в каком случае можно встретить такой сценарий, где у вас куча разных точек, разбросанных по карте и вам нужно по ним создать кратчайший маршрут? |
DarkMaster |
![]()
Сообщение
#16
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Модератор UOPilot Сообщений: 8.505 Регистрация: 2.12.2008 Группа: Супермодераторы Наличность: 25428 Пользователь №: 11.279 ![]() |
Цитата Не, я о другом. Я об обобщении и вшивании его в пилот как функции для поиска пути. Проблема в том что есть слишком много разных факторов которые зависят от контекста. Допустим возьмем УО. Если на пути стоят персонажи, их все обходить или смотреть что по стамине и проходить через персонажа? Если ты находишься на крыше у которой нет бортиков и с неё можно спрыгнуть? Если на пути находится паутина, в которой ты застрянешь, но сама она непроходимой не является? И так с каждой игрой. Тут надо очень хорошо все нюансы игры знать, что-бы делать правильные расчеты кратчайшего пути через А*. Например в той-же РанУО, при патфайндинге у мобов ( там тоже А* используется), между каждый тайлом используется весь алгоритм с проверками на шаг, а это довольно много кода, ибо нюансов вагон и тележка. Для этого должен быть разработан формат карты который будет учитывать данные детали. Т.е. в моем понимании это xyz координаты, модификатор стоимость пути, задание фиксированной стоимости. Карта должна создаваться непосредственно пользователем. Алгоритм же поиска не должен каждый раз вымучиваться на движке пилота. Цитата Пробежка по вей пойнтам х это тоже самое что запуск А* х раз. Каким это образом? Это будет запуск 1 раз, просто логика должна понимать различную ценность маршрута и ограничения связей. Цитата Зачем вам это как отдельная фича? Имхо в ней есть смысл только в том случае, если у вас есть пачка вей пойнтов и все они не упорядочены. Тоесть нужно получить общий кратчайший путь через все вей пойнты. Но в каком случае можно встретить такой сценарий, где у вас куча разных точек, разбросанных по карте и вам нужно по ним создать кратчайший маршрут? Навигация в любом полноценном 3д приложении. -------------------- Скрипты под заказ.
Консультации по UOpilot через ICQ, Skype, Ventrilo, TeamSpeak, TeamViewer 700р/час. |
pager |
![]()
Сообщение
#17
|
![]() ![]() ![]() ![]() ![]() Apprentice Сообщений: 147 Регистрация: 10.1.2006 Группа: Пользователи Наличность: 0 Из: -- Пользователь №: 4.699 Возраст: -- ![]() |
Не, я о другом. Я об обобщении и вшивании его в пилот как функции для поиска пути. Проблема в том что есть слишком много разных факторов которые зависят от контекста. Допустим возьмем УО. Если на пути стоят персонажи, их все обходить или смотреть что по стамине и проходить через персонажа? Если ты находишься на крыше у которой нет бортиков и с неё можно спрыгнуть? Если на пути находится паутина, в которой ты застрянешь, но сама она непроходимой не является? И так с каждой игрой. Тут надо очень хорошо все нюансы игры знать, что-бы делать правильные расчеты кратчайшего пути через А*. Например в той-же РанУО, при патфайндинге у мобов ( там тоже А* используется), между каждый тайлом используется весь алгоритм с проверками на шаг, а это довольно много кода, ибо нюансов вагон и тележка. Пробежка по вей пойнтам х это тоже самое что запуск А* х раз. Зачем вам это как отдельная фича? Имхо в ней есть смысл только в том случае, если у вас есть пачка вей пойнтов и все они не упорядочены. Тоесть нужно получить общий кратчайший путь через все вей пойнты. Но в каком случае можно встретить такой сценарий, где у вас куча разных точек, разбросанных по карте и вам нужно по ним создать кратчайший маршрут? На мой взгляд Не думаю что в поиске пути правильно было бы учитывать динамические препятствия , получатель маршрута должен сам оценивать динамические препятствия и максимум что можно было бы сделать это системе поиска маршрута посылать уведомления что проложенный маршрут не подходит для использования и система его не учитывала в новом положении маршрута. -------------------- S: nightowl0786
М: xyz0135792468@gmail.com Не good delete msg тема реальная . ПРО :D ВРАЧЕЙ Скрипт на ламбер uopilot wk ver 1.07 beta 8 тема скрипты Д: 12.01. 2007 в той теме было send msg 11.06.2018 (бн до 26) Вы это называете демакратией? |
DarkMaster |
![]()
Сообщение
#18
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Модератор UOPilot Сообщений: 8.505 Регистрация: 2.12.2008 Группа: Супермодераторы Наличность: 25428 Пользователь №: 11.279 ![]() |
Цитата На мой взгляд Не думаю что в поиске пути правильно было бы учитывать динамические препятствия , получатель маршрута должен сам оценивать динамические препятствия и максимум что можно было бы сделать это системе поиска маршрута посылать уведомления что проложенный маршрут не подходит для использования и система его не учитывала в новом положении маршрута. Имхо решаться должно опять же пользователем при составлении карты и если так нужно динамическое изменение, то можно назначить фиксированное значение которое будет несопостовимо дорогим для прокладки данного маршрута, либо использовать зарезервированное значение для отмены данного маршрута. В любом случае это должно решаться картой. Нужна тебе динамика - динамически изменяй карту. Тут алгоритм поиска по карте, а не составления карты. -------------------- Скрипты под заказ.
Консультации по UOpilot через ICQ, Skype, Ventrilo, TeamSpeak, TeamViewer 700р/час. |
pager |
![]()
Сообщение
#19
|
![]() ![]() ![]() ![]() ![]() Apprentice Сообщений: 147 Регистрация: 10.1.2006 Группа: Пользователи Наличность: 0 Из: -- Пользователь №: 4.699 Возраст: -- ![]() |
Имхо решаться должно опять же пользователем при составлении карты и если так нужно динамическое изменение, то можно назначить фиксированное значение которое будет несопостовимо дорогим для прокладки данного маршрута, либо использовать зарезервированное значение для отмены данного маршрута. В любом случае это должно решаться картой. Нужна тебе динамика - динамически изменяй карту. Тут алгоритм поиска по карте, а не составления карты. А я и не говорил о составление карты я под динамическими объектами имел в веду мобов тех же самых паутин и временных препятствий.Просто если система проложения маршрута начала бы делать проверки на тех же самых мобов то производительность системы вразы бы была меньше чем если бы эти проверки делал бы получатель маршрута -------------------- S: nightowl0786
М: xyz0135792468@gmail.com Не good delete msg тема реальная . ПРО :D ВРАЧЕЙ Скрипт на ламбер uopilot wk ver 1.07 beta 8 тема скрипты Д: 12.01. 2007 в той теме было send msg 11.06.2018 (бн до 26) Вы это называете демакратией? |
cirus |
![]()
Сообщение
#20
|
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Elder Сообщений: 2.865 Регистрация: 18.8.2014 Группа: Пользователи Наличность: 18209 Пользователь №: 16.971 Возраст: 29 ![]() |
Пока черновой вариант. Путь считается только по расстоянию.
код
Код // Алгоритм A* В массиве %map содержатся все точки в виде: <точка1> [до каких точек можно добраться из точки1] <точка2> [до каких точек можно добраться из точки2] В массиве %coord содержатся координаты всех точек. Координаты взяты с картинки открытой в Paint. В архиве 2 тхт файла (%map и %coord) и картинка. ![]() Прикрепленные файлы ![]() |