Среда, 13 Ноября 2024, 12:32

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 2
  • 1
  • 2
  • »
Реализация Pathfinding в 2D
KamiRoninДата: Пятница, 13 Декабря 2013, 21:30 | Сообщение # 1
почти ветеран
Сейчас нет на сайте
Привет всем!
для проекта возникла задача - реализовать поиск пути полностью в 2D среде.
на третий день поисков ФРИ контента стало понятно что таковых нет и нужно писать самому!

итог.
была создана реализация на EdgeCollider2D, спрайтах и Raycast2D системе, которая строит поле из любого замкнутого пространства сканируя его лучами и записывая клетки. Получилось конечно. Но ее еще облизывать и облизывать (строит поле с небольшим нахлестом на стены в НЕКОТОРЫХ местах).

В общем ВОПРОС:
у кого что есть на примете про чистый 2D поиск пути?! алгоритмы, реализации, готовые фри пакеты??


Мыслю - значит программирую...
Конструктивная критика - умных ведет к совершенству...
Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.


Сообщение отредактировал KamiRonin - Пятница, 13 Декабря 2013, 21:41
set16Дата: Пятница, 13 Декабря 2013, 22:41 | Сообщение # 2
постоянный участник
Сейчас нет на сайте
ссылка
Может это подойдет


=>The darkness of distant lands [3D]<=
tomkallenДата: Пятница, 13 Декабря 2013, 23:02 | Сообщение # 3
частый гость
Сейчас нет на сайте
Нашел!

Другого нет. Это чистая математика, на юнити прикручивается легко.


Если можешь не делать игру - не делай.

Сообщение отредактировал tomkallen - Пятница, 13 Декабря 2013, 23:24
lakorisДата: Пятница, 13 Декабря 2013, 23:21 | Сообщение # 4
постоянный участник
Сейчас нет на сайте
set16,
Цитата KamiRonin ()
конечно первым была найдена и скачана фри версия A*Pathfinding Project

...
tomkallenДата: Пятница, 13 Декабря 2013, 23:23 | Сообщение # 5
частый гость
Сейчас нет на сайте
Цитата set16 ()
Другого нет. Это чистая математика, на юнити прикручивается легко.


...


Если можешь не делать игру - не делай.
KamiRoninДата: Пятница, 13 Декабря 2013, 23:29 | Сообщение # 6
почти ветеран
Сейчас нет на сайте
Цитата tomkallen ()
на юнити прикручивается легко.

заминусовать твой тяжким гуглиньем заделанный кол что ли?? smile


Мыслю - значит программирую...
Конструктивная критика - умных ведет к совершенству...
Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
set16Дата: Пятница, 13 Декабря 2013, 23:46 | Сообщение # 7
постоянный участник
Сейчас нет на сайте
у вас free версия unity?

http://youtu.be/CiJROlXNUxg


=>The darkness of distant lands [3D]<=

Сообщение отредактировал set16 - Суббота, 14 Декабря 2013, 00:03
castielblackДата: Суббота, 14 Декабря 2013, 00:20 | Сообщение # 8
почетный гость
Сейчас нет на сайте
Разбиваешь пространство на сетку, привязываешь поиск путей - лучше всего, конечно же использовать A*.

Тут всё хорошо объясняется


Знания : C#, Lua, C++, Unity, Dreemchest, DirectX 11
Выпущенные проекты : BuildAndRun, Match 3 Cubes


Сообщение отредактировал castielblack - Суббота, 14 Декабря 2013, 00:29
KamiRoninДата: Суббота, 14 Декабря 2013, 01:45 | Сообщение # 9
почти ветеран
Сейчас нет на сайте
Цитата set16 ()
у вас free версия unity?

set16, совсем не читал пост да?? smile
навмеш не работает в 2D и со спрайтами (в виде карт местности и коллайдеров).

Добавлено (14.12.2013, 01:45)
---------------------------------------------
Цитата castielblack ()
Тут всё хорошо объясняется

твою ссылку я привел как свою В САМОМ НАЧАЛЕ
и "разбиваешь на сетку" ТОЖЕ ОБСУДИЛ в первом посте


Мыслю - значит программирую...
Конструктивная критика - умных ведет к совершенству...
Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.


Сообщение отредактировал KamiRonin - Суббота, 14 Декабря 2013, 01:46
castielblackДата: Суббота, 14 Декабря 2013, 02:52 | Сообщение # 10
почетный гость
Сейчас нет на сайте
Цитата KamiRonin ()
твою ссылку я привел как свою В САМОМ НАЧАЛЕ
и "разбиваешь на сетку" ТОЖЕ ОБСУДИЛ в первом посте

Извиняюсь за невнимательность.
Цитата KamiRonin ()
В общем ВОПРОС:
у кого что есть на примете про чистый 2D поиск пути?!

Чушь сморозили =)
Любое пространство разбивается на 2D - для поиска пути, когда путь найден - вам просто выдаётся лист с координатами точек по которым нужно пройти.


Знания : C#, Lua, C++, Unity, Dreemchest, DirectX 11
Выпущенные проекты : BuildAndRun, Match 3 Cubes
set16Дата: Суббота, 14 Декабря 2013, 05:43 | Сообщение # 11
постоянный участник
Сейчас нет на сайте
я когда то делал прохождение лабиринта мобом(в Blitz3D), разбил лабиринт на квадраты, весь мир занес в массив и сделал память мобу в виде стека, чтобы он помнил путь назад из тупиков. Все работало, но это было не поиск пути а нахождение пути путем исследования лабиринта. Выходит, что моб может пойти в другую сторону от перса, но если ему установить приоритет исследования в сторону игрока, он будет исследовать мир в том направлении и найдет путь. На Unity поиск пути не делал, но думаю что в с# стек можно реализовать вообще в список и тогда память мода будет динамической.

Это просто предложение, не ругайтесь, можете проигнорировать biggrin


=>The darkness of distant lands [3D]<=

Сообщение отредактировал set16 - Суббота, 14 Декабря 2013, 05:46
KamiRoninДата: Суббота, 14 Декабря 2013, 09:24 | Сообщение # 12
почти ветеран
Сейчас нет на сайте
Цитата castielblack ()
Любое пространство разбивается на 2D - для поиска пути, когда путь найден - вам просто выдаётся лист с координатами точек по которым нужно пройти.

нууу вооот!! теперь вся рыба наша! smile
И СНОВА: то, что мне это хорошо известно - ясно из первого поста.
Задача -- не в том, чтобы понять как вообще организована логика 2D поиска пути, а КАКИЕ ЕСТЬ ПРОГРАММНЫЕ ГОТОВЫЕ ФРИ РЕШЕНИЯ, алгоритмы для их ПРОГРАММНОЙ Unity реализации.
Самая сложная задача в ПРОИЗВОЛЬНОМ 2D пространстве - построить "поле" квадратов (треугольников, шестиугольников) внутри предлагаемого спрайта у которого нет четкой градации цветов (если бы признак стены - был цвет например), у которого есть только "физическая" стенка для теста лучом (например) и тп.

Внутри A* Pf Pr -- есть система построения сети опорных точек вручную - расставляешь пустышки-ГО по нужной тебе траектории, задаешь им определенный тег на этапе разработки и передаешь все это А*машине - она "автоматом" строит "поле" в котором можно перемещаться только по этим точкам во время поиска пути.
у меня поле не квадратное (см. фото в первом посте)! и возможных точек прохождения больше 1000!! вручную это расставлять??!?! думаю немного накладно будет!!

Сам поиск по гриду в 2D НИКАКОЙ сложности не представляет!! и его программная реализация известна.
Кстати, два лидирующих алгоритма по реализации это JumpPointSearch (в разы более быстрая разновидность А*) и алгоритм Ли (волновой).

Вопрос как в произвольном спрайте построить правильно и оперативно ГРИД!!?
А с учетом подвижных препятствий?!!
А с быстрым доступом к точке, если поле - не квадрат!?!? Нет, можно конечно сделать огромный квадрат из любой локации и просто вычеркнуть из обработки три четверти точек, но стоит ли?!

В одном из примеров с A*Pf Pr - пошли таким путем - создали чистое поле, а потом программно вычеркнули "стены" из него - с указанием координат прохождения стены. Опять ручной вариант!!! Легче?? Конечно даа.. smile

В моем варианте, результат которого показан на фото в первом посте - берется спрайт, ставится ему EdgeCollider по стенке, вешается скрипт генерации поля, в котором указывается точка старта (нулевой угол), и размер сектора - все. Он строит поле в любом пространстве - с прямыми углами, с косыми, в не квадратном поле и проч. Рассчитан на квадратный сектор пока... Но я на него слишком много времени потратил! И еще нужно обтесывать! Вот и возник вопрос - есть ли готовое что нибудь! smile


Мыслю - значит программирую...
Конструктивная критика - умных ведет к совершенству...
Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.


Сообщение отредактировал KamiRonin - Суббота, 14 Декабря 2013, 09:31
castielblackДата: Суббота, 14 Декабря 2013, 17:23 | Сообщение # 13
почетный гость
Сейчас нет на сайте
Да, проблемная вещь, конечно.
Я лично, решал это так :
Сначала делал сетку со стенами и т.д
А потом по этой сетке раставлял объекты.


Знания : C#, Lua, C++, Unity, Dreemchest, DirectX 11
Выпущенные проекты : BuildAndRun, Match 3 Cubes
RangerДата: Четверг, 30 Января 2014, 08:45 | Сообщение # 14
почти ветеран
Сейчас нет на сайте
делетед
сюда ушло




Сообщение отредактировал Ranger - Четверг, 30 Января 2014, 12:35
KamiRoninДата: Четверг, 30 Января 2014, 11:38 | Сообщение # 15
почти ветеран
Сейчас нет на сайте
Цитата Ranger ()
Как быть? Что делать?

создай отдельную тему - по патфайндингу в 3Д - напишу пару ссылок как решали другие, придумаем че нить сами.
тут хотел бы только 2Д решение увидеть. ок?!


Мыслю - значит программирую...
Конструктивная критика - умных ведет к совершенству...
Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
divol13Дата: Четверг, 30 Января 2014, 20:16 | Сообщение # 16
участник
Сейчас нет на сайте
не понимаю чего хочит тс?
если у тебя грид 2Д все понятно, есть проходимая клетка, а есть непроходимая
и для этого алгоритмов полно
ну допустим и нету в игре явного грида, ну дели сам тогда пространство на квадраты
своди все к гриду и используй грид алгоритм, стены то надеюсь у тебя не двигаются?
ну а столкновения с подвижными объектами смотри тоже разбив пространство на клетки
где записывай внутри все объекты в этой клетке находящиеся чтоб проверять на столкновения только их
(тут где-то тема пролетала такая)
вобщем сложность надумана.


KamiRoninДата: Четверг, 30 Января 2014, 20:46 | Сообщение # 17
почти ветеран
Сейчас нет на сайте
Цитата divol13 ()
не понимаю чего хочит тс?

он хочет реализацию разбивки на квадраты в нелинейном 2D пространстве - например внутри 2Д спрайта юнити 4.3. с коллайдерами стен.
нарисовал план помещения в спрайте - сунул туда ботов и они бегают себе по спрайту.
я реализовал 2Д разбивку на квадраты по алгоритму рекусрсивного рейтрейсинга на основе схемы "заливка многоугольника".
обошлось мне это участием в хорошем конкурсе... не успел я туда.
в итоге свелось все к ЭМУЛЯЦИИ 2Д патфайндинга внутри полноценного 3Д пространства - что и явилось главное причиной создания темы.

для лучшего понимания проблем поднятых в теме - ее лучше ЧИТАТЬ! и пробовать реализовать самому!
"где то тема пролетала" умиляет.. при том что в топике куча ссылок конкретно ГДЕ она пролетала!


Мыслю - значит программирую...
Конструктивная критика - умных ведет к совершенству...
Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
divol13Дата: Четверг, 30 Января 2014, 21:16 | Сообщение # 18
участник
Сейчас нет на сайте
Цитата KamiRonin ()
он хочет реализацию разбивки на квадраты

так
Цитата KamiRonin ()
например внутри 2Д спрайта юнити 4.3. с коллайдерами стен.
нарисовал план помещения в спрайте - сунул туда ботов и они бегают себе по спрайту.

мм, тут смысл не понятен, ты хочешь писать перемещения игрока в текстуру чтоли?
положи ее под низ сцены(не знаю как это в юнити, но наверное есть) а по верху поставь препятствия
Цитата KamiRonin ()
я реализовал 2Д разбивку на квадраты

реализовал, хорошо, значит получилось все
Цитата KamiRonin ()
по алгоритму рекусрсивного рейтрейсинга на основе схемы "заливка многоугольника"

круто, 5 строчек кода
Цитата KamiRonin ()
для лучшего понимания проблем поднятых в теме - ее лучше ЧИТАТЬ! и пробовать реализовать самому!

неоднократно применял
Цитата KamiRonin ()
"где то тема пролетала" умиляет.. при том что в топике куча ссылок конкретно ГДЕ она пролетала!

спецом проверил ссылки, нет там такого. и тут два вариант, либо я не донес суть, либо ты ее принял за что-то другое

ну вобщем как я понял, проблема решена, тогда выкладывай результаты. Мож пригодится кому здесь.


KamiRoninДата: Четверг, 30 Января 2014, 22:18 | Сообщение # 19
почти ветеран
Сейчас нет на сайте
Цитата divol13 ()
мм, тут смысл не понятен, ты хочешь писать перемещения игрока в текстуру чтоли?
положи ее под низ сцены(не знаю как это в юнити, но наверное есть) а по верху поставь препятствия

эта тема в разделе Unity, так что НЕПОНЯТНО зачем писать сюда - если ты не знаешь про тему ничего?!
Цитата divol13 ()
реализовал, хорошо, значит получилось все

то ли ты через слово читаешь то ли как!? я же сказал - что отняло слишком много времени! ищу - есть ли другие решения.
Цитата divol13 ()
круто, 5 строчек кода

дык ПОКАЖИ их нам, может мы тоже повосторгаемся!
Цитата divol13 ()
неоднократно применял

что именно? в каком движке? кинь ссылку, посмотрим на проекты, может научимся чему нибудь!
даже в Construct 2 есть встроенный 2Д патфайндинг.. если ты лихо воспользовался кинутым на сцену аплетом сделанным кем то другим - тогда мы все так "пользовались и неоднократно"!
Цитата divol13 ()
спецом проверил ссылки, нет там такого. и тут два вариант, либо я не донес суть, либо ты ее принял за что-то другое

даааа.. написание постов видать твой конек! biggrin
если бы существовала ссылка ВНИМАНИЕ Unity 2D Pathfinding (НЕ эмуляции, не 3Д системы в ортогональной камере, а чистый 2Д патфайндинг), то этой бы темы возможно не было бы вовсе!!
и просьба есть!
если у тебя НЕТ ТАКОЙ ССЫЛКИ - не нужно сюда писать! пиши в личку или хочешь дам ссылку на тему на этом форуме - называется ФЛЭЙМ - тебе туда с такими неконкретными выражениями своего видения алгоритмов А*, D*, правой руки, волнового алгоритма, Крэша, Дейстры, обхода препятствий или Jamp A* -- то лучше туда!! ОК?!

не, я понимаю что ты хотел чего то светлого и хорошего.. но темы не для флуда без конкретики, ага? wink smile


Мыслю - значит программирую...
Конструктивная критика - умных ведет к совершенству...
Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
divol13Дата: Пятница, 31 Января 2014, 21:12 | Сообщение # 20
участник
Сейчас нет на сайте
Цитата KamiRonin ()
эта тема в разделе Unity, так что НЕПОНЯТНО зачем писать сюда - если ты не знаешь про тему ничего?!

ну и что? проходил мимо решил помочь, потому что недавно как раз реализовывал такое, это раз.
где, как и когда мне писать, я решу сам. это два.

Цитата KamiRonin ()
то ли ты через слово читаешь то ли как!? я же сказал - что отняло слишком много времени! ищу - есть ли другие решения.

так и не понятно что тебе надо было, поэтому и уточнял.

Цитата KamiRonin ()
дык ПОКАЖИ их нам, может мы тоже повосторгаемся!

что тебе показать? как сделать рекурсивный алгоритм? Заполнение фигуры или к примеру лабиринта- это вызов одной рекурсивной функции с закраской, остальное- это проверки на доступность закраски.

Цитата KamiRonin ()
что именно? в каком движке? кинь ссылку, посмотрим на проекты, может научимся чему нибудь!
даже в Construct 2 есть встроенный 2Д патфайндинг.. если ты лихо воспользовался кинутым на сцену аплетом сделанным кем то другим - тогда мы все так "пользовались и неоднократно"!

кину в л.с. тестовый ехе-шник, где есть и закраска и поиск пути А-стар и волновой(ли). Если сам попросишь в л.с.

Цитата KamiRonin ()
даааа.. написание постов видать твой конек!

это вообще не понятно о чем. Если о той теме что я упомянул, но не стал искать ссылку, то не поленился и нашел свою демку с библиотекой столкновений.
смотри здесь http://gcup.ru/forum/66-28080-506625-16-1363517127

Цитата KamiRonin ()
и просьба есть!
если у тебя НЕТ ТАКОЙ ССЫЛКИ - не нужно сюда писать! пиши в личку или хочешь дам ссылку на тему на этом форуме - называется ФЛЭЙМ - тебе туда с такими неконкретными выражениями своего видения алгоритмов А*, D*, правой руки, волнового алгоритма, Крэша, Дейстры, обхода препятствий или Jamp A* -- то лучше туда!! ОК?!

повторяю еще раз. Я писал, пишу и буду писать там, где мне того хочется, а не там где твое величество мне позволит.

Ну и вообще, я смотрю по адекватности твоих ответов, с таким хамским поведением тебе и отвечать никто не будет.
Я и хотел и мог бы ответить, но теперь уже передумал.
Адью.


  • Страница 1 из 2
  • 1
  • 2
  • »
Поиск:

Все права сохранены. GcUp.ru © 2008-2024 Рейтинг