Поиск пути + карта проходимости???
Народ подскажите как реализовать поиск пути (ПП) с картой проходимости (КП) - Ну чтоб в итоге получилось как в "Проклятых землях"
Я подозреваю что эта история начинается с построения КП - потом на основе этой КП расставляются вэйпоинты... И если узер ткнул мышью по ландшафту и если она в КП то ищется путь от близжайшего вэйпоинта до игрока а от последнего вэипоинта до точки клика идет по прямой.... Народ подскажите....Может есть более грамотные алгоритмы...Может я ошибаюсь... И в каком виде хранить эту карту проходимости? - В изображении? в 3Д модели? |
Re: Поиск пути + карта проходимости???
A* в руки и пошол
|
Re: Поиск пути + карта проходимости???
|
Re: Поиск пути + карта проходимости???
Да но этот пример астара сделан под 2д... - А я 2д отродясь не знаю... - есть у кого пример этого исходника под 3д???
|
Re: Поиск пути + карта проходимости???
Да десятки вариантов. И нужно разбираться какой именно наиболее эффективен в данной конкретной ситуации.
А отличаются они алгоритмами поиска и формированием карты путей. Карты путей к примеру бывают (навскидку): - с регулярной сеткой. Карта путей состоит из квадратных или иных (шестиугольных) "клеток", для каждой из которых указана проходимость. Регулярные сетки удобно хранить в масивах и просто редактировать. Регулярные сетки охватывают всю заданную площадь, координаты узлов регулярной сетки всегда известны. Просто и универсально. - с нерегулярной сеткой. Точки-"узлы" сети, "вейпоинты", размещены по координатам неравномерно. Дальнейшее развитие нерегулярной сети приводит к появлению карты путей на основе вейпоинтов, когда немногочисленные по сравнению с количеством клеток регулярной сетки таких же масштабов точки пути размещены только на ключевых позициях вручную. Из-за малого количества точек, анализ карты проводится быстрее, карта занимает меньше памяти, однако падает качество "прокладки курса" и усложняется редактирование и дополнительные алгоритмы поиска. -вапще без сетки нах :). Карты препятствий, описаных отрезками или иными геометрическими фигурами, размещенными на карте. Алгоритмы поиска пути своеобразные- к примеру, анализ пересечения отрезка курса с препятствием и смещение курса вокруг края препятствия. Работают довольно быстро, иногда используются для поиска пути на очень больших, но простых картах (открытые пространства). -другие. Алгоритмы поиска по сеткам тоже сильно отличаются: -Волновой алгоритм и его вариации. Предельно прост, отличается высокими затратами времени на поиск. Существует исключительно в образовательных целях... -А* и его вариации. Производится именно "поиск" в заданном направлении, а не многократные "волновые проходы" всей карты. Качественный (или не очень) результат поиска достигается к.пр. намного быстрее, чем волновым алгоритмом. -с предварительным поиском. Выбирается один из заранее просчитанных и постоянно хранимых в памяти "курсов". -"Тактические". Алгоритм не производит анализ всей карты, а лишь своеобразным образом реагирует на появление препятствий на пути. -другие. Так что выбирай, что тебе нужно. Потом находи/спрашивай алгоритм и обрабатывай его под свои потребности. Цитата:
|
Re: Поиск пути + карта проходимости???
Не согласен что без разницы! трабла в другом! Я хотел сделать один из стандартных сэмплов А* (2-й) В 3Д графическом режиме. т.е. вместо Graphics - Graphics3d - и соответственно вместо картинок подставить спрайты (тайлы с точками в центре) и чтоб герой и монстры передвигались в 3д по этим точкам - но я тут попал в тупик! в функции PathFind(x,x,x,x,x,x,x) - есть входной параметр "TileSize" - это размер тайла в 2д (ширина\длинна тайла) - так вот! А че в 3д писать вместо него??? Я пытался ставить расстояние от точки до точки - ошибка! Скайлинг спрайтов - тоже ошибка! Вот! Может есть у кого пример этого алгоритма в 3д ? Ато я чето не догоняю...
|
Re: Поиск пути + карта проходимости???
Зря не согласен, ибо разницы таки ни малейшей: алгоритм путенахождения от разного "размера тайлов" не меняется ни на йоту. Так что сиди и разбирайся в коде,а не копипасть его.
А лучше сядь и сам напиши: ибо нужно не скатать, а понять. Благо уроков/описаний волнового алгоритма и А* в Сети, как грязи. |
Re: Поиск пути + карта проходимости???
Diplomat -> Ой ошибочка! я имел ввиду не это: "Не согласен что без разницы!" а это "Не!!! Я согласен что без разницы!" ;)
|
Re: Поиск пути + карта проходимости???
У вас в школе знаки препинания, кроме восклицательных, не учили?!
|
Re: Поиск пути + карта проходимости???
Можно и без 3D ( в смысле не переделывать AStar под 3D) сделать, как раньше в играх делали:
типа plane, а горы достаточно высокие и являются непроходимыми клетками (плюс непроходимые деревья, камни и т.д.) . Тогда в AStar'е даже менять ничё не придется :)! |
Часовой пояс GMT +4, время: 07:19. |
vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot