Привет всем! для проекта возникла задача - реализовать поиск пути полностью в 2D среде. на третий день поисков ФРИ контента стало понятно что таковых нет и нужно писать самому!
конечно первым была найдена и скачана фри версия A*Pathfinding Project найден просто замечательный тутор от Rocket Studios есть платные плагины (старые довольно), например Waypoints for 2D Pathfinding или список в ассет сторе куча идей философов от программирования на Хабре. и вот наконец нашел на C# пример реализации А* алгоритма для плоского пространства.. НО попробуйте его в Unity прикрутить! А на спрайтах!!? А без навмеша!! В общем оказалось - хочешь 2D пиши свое!! И основная задача свелась к построению поля логических ячеек внутри предлагаемых обстоятельств имеющегося условного пространства!
Тут в ход пошли алгоритмы "заливки многоугольника" и алгоритм принадлежности точки многоугольнику и прочая и прочая. А ведь хотелось бы универсальности!! Не писать каждый раз поле вручную, а создавать его как в том же A*Pathfnd Proj нажав на одну кнопку при конструировании уровня. Кстати на А*Pf P почти получилось его прикрутить к чистому 2D (не делать ортогональную камеру и полноценные 3D декорации в виде аля 2D, а настоящие спрайты повсюду!)!! Но получилось тааааак муторно и потребовал установки такого количества скриптов и утилит что я просто сразу его выгрузил!!! В ссылке от RocketStudios автор (умница) переписал основной скрипт A*Pf Pr под свое 2D и таким способом выкрутился.. но когда качаешь его простенькую игрушку - 98% контента занимает патфайндер скрипты и проч!
итог. была создана реализация на EdgeCollider2D, спрайтах и Raycast2D системе, которая строит поле из любого замкнутого пространства сканируя его лучами и записывая клетки. Получилось конечно. Но ее еще облизывать и облизывать (строит поле с небольшим нахлестом на стены в НЕКОТОРЫХ местах).
В общем ВОПРОС: у кого что есть на примете про чистый 2D поиск пути?! алгоритмы, реализации, готовые фри пакеты?? Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
Сообщение отредактировал KamiRonin - Пятница, 13 Декабря 2013, 21:41
твою ссылку я привел как свою В САМОМ НАЧАЛЕ и "разбиваешь на сетку" ТОЖЕ ОБСУДИЛ в первом посте Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
Сообщение отредактировал KamiRonin - Суббота, 14 Декабря 2013, 01:46
твою ссылку я привел как свою В САМОМ НАЧАЛЕ и "разбиваешь на сетку" ТОЖЕ ОБСУДИЛ в первом посте
Извиняюсь за невнимательность.
ЦитатаKamiRonin ()
В общем ВОПРОС: у кого что есть на примете про чистый 2D поиск пути?!
Чушь сморозили =) Любое пространство разбивается на 2D - для поиска пути, когда путь найден - вам просто выдаётся лист с координатами точек по которым нужно пройти. Знания : C#, Lua, C++, Unity, Dreemchest, DirectX 11 Выпущенные проекты : BuildAndRun, Match 3 Cubes
я когда то делал прохождение лабиринта мобом(в Blitz3D), разбил лабиринт на квадраты, весь мир занес в массив и сделал память мобу в виде стека, чтобы он помнил путь назад из тупиков. Все работало, но это было не поиск пути а нахождение пути путем исследования лабиринта. Выходит, что моб может пойти в другую сторону от перса, но если ему установить приоритет исследования в сторону игрока, он будет исследовать мир в том направлении и найдет путь. На Unity поиск пути не делал, но думаю что в с# стек можно реализовать вообще в список и тогда память мода будет динамической.
Любое пространство разбивается на 2D - для поиска пути, когда путь найден - вам просто выдаётся лист с координатами точек по которым нужно пройти.
нууу вооот!! теперь вся рыба наша! И СНОВА: то, что мне это хорошо известно - ясно из первого поста. Задача -- не в том, чтобы понять как вообще организована логика 2D поиска пути, а КАКИЕ ЕСТЬ ПРОГРАММНЫЕ ГОТОВЫЕ ФРИ РЕШЕНИЯ, алгоритмы для их ПРОГРАММНОЙ Unity реализации. Самая сложная задача в ПРОИЗВОЛЬНОМ 2D пространстве - построить "поле" квадратов (треугольников, шестиугольников) внутри предлагаемого спрайта у которого нет четкой градации цветов (если бы признак стены - был цвет например), у которого есть только "физическая" стенка для теста лучом (например) и тп.
Внутри A* Pf Pr -- есть система построения сети опорных точек вручную - расставляешь пустышки-ГО по нужной тебе траектории, задаешь им определенный тег на этапе разработки и передаешь все это А*машине - она "автоматом" строит "поле" в котором можно перемещаться только по этим точкам во время поиска пути. у меня поле не квадратное (см. фото в первом посте)! и возможных точек прохождения больше 1000!! вручную это расставлять??!?! думаю немного накладно будет!!
Сам поиск по гриду в 2D НИКАКОЙ сложности не представляет!! и его программная реализация известна. Кстати, два лидирующих алгоритма по реализации это JumpPointSearch (в разы более быстрая разновидность А*) и алгоритм Ли (волновой).
Вопрос как в произвольном спрайте построить правильно и оперативно ГРИД!!? А с учетом подвижных препятствий?!! А с быстрым доступом к точке, если поле - не квадрат!?!? Нет, можно конечно сделать огромный квадрат из любой локации и просто вычеркнуть из обработки три четверти точек, но стоит ли?!
В одном из примеров с A*Pf Pr - пошли таким путем - создали чистое поле, а потом программно вычеркнули "стены" из него - с указанием координат прохождения стены. Опять ручной вариант!!! Легче?? Конечно даа..
В моем варианте, результат которого показан на фото в первом посте - берется спрайт, ставится ему EdgeCollider по стенке, вешается скрипт генерации поля, в котором указывается точка старта (нулевой угол), и размер сектора - все. Он строит поле в любом пространстве - с прямыми углами, с косыми, в не квадратном поле и проч. Рассчитан на квадратный сектор пока... Но я на него слишком много времени потратил! И еще нужно обтесывать! Вот и возник вопрос - есть ли готовое что нибудь! Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
Сообщение отредактировал KamiRonin - Суббота, 14 Декабря 2013, 09:31
Да, проблемная вещь, конечно. Я лично, решал это так : Сначала делал сетку со стенами и т.д А потом по этой сетке раставлял объекты. Знания : C#, Lua, C++, Unity, Dreemchest, DirectX 11 Выпущенные проекты : BuildAndRun, Match 3 Cubes
создай отдельную тему - по патфайндингу в 3Д - напишу пару ссылок как решали другие, придумаем че нить сами. тут хотел бы только 2Д решение увидеть. ок?! Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
не понимаю чего хочит тс? если у тебя грид 2Д все понятно, есть проходимая клетка, а есть непроходимая и для этого алгоритмов полно ну допустим и нету в игре явного грида, ну дели сам тогда пространство на квадраты своди все к гриду и используй грид алгоритм, стены то надеюсь у тебя не двигаются? ну а столкновения с подвижными объектами смотри тоже разбив пространство на клетки где записывай внутри все объекты в этой клетке находящиеся чтоб проверять на столкновения только их (тут где-то тема пролетала такая) вобщем сложность надумана.
он хочет реализацию разбивки на квадраты в нелинейном 2D пространстве - например внутри 2Д спрайта юнити 4.3. с коллайдерами стен. нарисовал план помещения в спрайте - сунул туда ботов и они бегают себе по спрайту. я реализовал 2Д разбивку на квадраты по алгоритму рекусрсивного рейтрейсинга на основе схемы "заливка многоугольника". обошлось мне это участием в хорошем конкурсе... не успел я туда. в итоге свелось все к ЭМУЛЯЦИИ 2Д патфайндинга внутри полноценного 3Д пространства - что и явилось главное причиной создания темы.
для лучшего понимания проблем поднятых в теме - ее лучше ЧИТАТЬ! и пробовать реализовать самому! "где то тема пролетала" умиляет.. при том что в топике куча ссылок конкретно ГДЕ она пролетала! Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
например внутри 2Д спрайта юнити 4.3. с коллайдерами стен. нарисовал план помещения в спрайте - сунул туда ботов и они бегают себе по спрайту.
мм, тут смысл не понятен, ты хочешь писать перемещения игрока в текстуру чтоли? положи ее под низ сцены(не знаю как это в юнити, но наверное есть) а по верху поставь препятствия
ЦитатаKamiRonin ()
я реализовал 2Д разбивку на квадраты
реализовал, хорошо, значит получилось все
ЦитатаKamiRonin ()
по алгоритму рекусрсивного рейтрейсинга на основе схемы "заливка многоугольника"
круто, 5 строчек кода
ЦитатаKamiRonin ()
для лучшего понимания проблем поднятых в теме - ее лучше ЧИТАТЬ! и пробовать реализовать самому!
неоднократно применял
ЦитатаKamiRonin ()
"где то тема пролетала" умиляет.. при том что в топике куча ссылок конкретно ГДЕ она пролетала!
спецом проверил ссылки, нет там такого. и тут два вариант, либо я не донес суть, либо ты ее принял за что-то другое
ну вобщем как я понял, проблема решена, тогда выкладывай результаты. Мож пригодится кому здесь.
мм, тут смысл не понятен, ты хочешь писать перемещения игрока в текстуру чтоли? положи ее под низ сцены(не знаю как это в юнити, но наверное есть) а по верху поставь препятствия
эта тема в разделе Unity, так что НЕПОНЯТНО зачем писать сюда - если ты не знаешь про тему ничего?!
Цитатаdivol13 ()
реализовал, хорошо, значит получилось все
то ли ты через слово читаешь то ли как!? я же сказал - что отняло слишком много времени! ищу - есть ли другие решения.
Цитатаdivol13 ()
круто, 5 строчек кода
дык ПОКАЖИ их нам, может мы тоже повосторгаемся!
Цитатаdivol13 ()
неоднократно применял
что именно? в каком движке? кинь ссылку, посмотрим на проекты, может научимся чему нибудь! даже в Construct 2 есть встроенный 2Д патфайндинг.. если ты лихо воспользовался кинутым на сцену аплетом сделанным кем то другим - тогда мы все так "пользовались и неоднократно"!
Цитатаdivol13 ()
спецом проверил ссылки, нет там такого. и тут два вариант, либо я не донес суть, либо ты ее принял за что-то другое
даааа.. написание постов видать твой конек! если бы существовала ссылка ВНИМАНИЕ Unity 2D Pathfinding (НЕ эмуляции, не 3Д системы в ортогональной камере, а чистый 2Д патфайндинг), то этой бы темы возможно не было бы вовсе!! и просьба есть! если у тебя НЕТ ТАКОЙ ССЫЛКИ - не нужно сюда писать! пиши в личку или хочешь дам ссылку на тему на этом форуме - называется ФЛЭЙМ - тебе туда с такими неконкретными выражениями своего видения алгоритмов А*, D*, правой руки, волнового алгоритма, Крэша, Дейстры, обхода препятствий или Jamp A* -- то лучше туда!! ОК?!
не, я понимаю что ты хотел чего то светлого и хорошего.. но темы не для флуда без конкретики, ага? Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
эта тема в разделе Unity, так что НЕПОНЯТНО зачем писать сюда - если ты не знаешь про тему ничего?!
ну и что? проходил мимо решил помочь, потому что недавно как раз реализовывал такое, это раз. где, как и когда мне писать, я решу сам. это два.
ЦитатаKamiRonin ()
то ли ты через слово читаешь то ли как!? я же сказал - что отняло слишком много времени! ищу - есть ли другие решения.
так и не понятно что тебе надо было, поэтому и уточнял.
ЦитатаKamiRonin ()
дык ПОКАЖИ их нам, может мы тоже повосторгаемся!
что тебе показать? как сделать рекурсивный алгоритм? Заполнение фигуры или к примеру лабиринта- это вызов одной рекурсивной функции с закраской, остальное- это проверки на доступность закраски.
ЦитатаKamiRonin ()
что именно? в каком движке? кинь ссылку, посмотрим на проекты, может научимся чему нибудь! даже в Construct 2 есть встроенный 2Д патфайндинг.. если ты лихо воспользовался кинутым на сцену аплетом сделанным кем то другим - тогда мы все так "пользовались и неоднократно"!
кину в л.с. тестовый ехе-шник, где есть и закраска и поиск пути А-стар и волновой(ли). Если сам попросишь в л.с.
ЦитатаKamiRonin ()
даааа.. написание постов видать твой конек!
это вообще не понятно о чем. Если о той теме что я упомянул, но не стал искать ссылку, то не поленился и нашел свою демку с библиотекой столкновений. смотри здесь http://gcup.ru/forum/66-28080-506625-16-1363517127
ЦитатаKamiRonin ()
и просьба есть! если у тебя НЕТ ТАКОЙ ССЫЛКИ - не нужно сюда писать! пиши в личку или хочешь дам ссылку на тему на этом форуме - называется ФЛЭЙМ - тебе туда с такими неконкретными выражениями своего видения алгоритмов А*, D*, правой руки, волнового алгоритма, Крэша, Дейстры, обхода препятствий или Jamp A* -- то лучше туда!! ОК?!
повторяю еще раз. Я писал, пишу и буду писать там, где мне того хочется, а не там где твое величество мне позволит.
Ну и вообще, я смотрю по адекватности твоих ответов, с таким хамским поведением тебе и отвечать никто не будет. Я и хотел и мог бы ответить, но теперь уже передумал. Адью.
