Поиск пути + карта проходимости???

Народ подскажите как реализовать поиск пути (ПП) с картой проходимости (КП) - Ну чтоб в итоге получилось как в "Проклятых землях"

Я подозреваю что эта история начинается с построения КП - потом на основе этой КП расставляются вэйпоинты...

И если узер ткнул мышью по ландшафту и если она в КП то ищется путь от близжайшего вэйпоинта до игрока а от последнего вэипоинта до точки клика идет по прямой....

Народ подскажите....Может есть более грамотные алгоритмы...Может я ошибаюсь...

И в каком виде хранить эту карту проходимости? - В изображении? в 3Д модели?

A* в руки и пошол

[impersonalis]

http://blitzetc.boolean.name/articles/astar.htm

Да но этот пример астара сделан под 2д... - А я 2д отродясь не знаю... - есть у кого пример этого исходника под 3д???

[Diplomat]

Да десятки вариантов. И нужно разбираться какой именно наиболее эффективен в данной конкретной ситуации.
А отличаются они алгоритмами поиска и формированием карты путей.

Карты путей к примеру бывают (навскидку):

- с регулярной сеткой. Карта путей состоит из квадратных или иных (шестиугольных) "клеток", для каждой из которых указана проходимость. Регулярные сетки удобно хранить в масивах и просто редактировать. Регулярные сетки охватывают всю заданную площадь, координаты узлов регулярной сетки всегда известны. Просто и универсально.

- с нерегулярной сеткой. Точки-"узлы" сети, "вейпоинты", размещены по координатам неравномерно. Дальнейшее развитие нерегулярной сети приводит к появлению карты путей на основе вейпоинтов, когда немногочисленные по сравнению с количеством клеток регулярной сетки таких же масштабов точки пути размещены только на ключевых позициях вручную. Из-за малого количества точек, анализ карты проводится быстрее, карта занимает меньше памяти, однако падает качество "прокладки курса" и усложняется редактирование и дополнительные алгоритмы поиска.

-вапще без сетки нах . Карты препятствий, описаных отрезками или иными геометрическими фигурами, размещенными на карте. Алгоритмы поиска пути своеобразные- к примеру, анализ пересечения отрезка курса с препятствием и смещение курса вокруг края препятствия. Работают довольно быстро, иногда используются для поиска пути на очень больших, но простых картах (открытые пространства).

-другие.

Алгоритмы поиска по сеткам тоже сильно отличаются:

-Волновой алгоритм и его вариации. Предельно прост, отличается высокими затратами времени на поиск. Существует исключительно в образовательных целях...

-А* и его вариации. Производится именно "поиск" в заданном направлении, а не многократные "волновые проходы" всей карты. Качественный (или не очень) результат поиска достигается к.пр. намного быстрее, чем волновым алгоритмом.

-с предварительным поиском. Выбирается один из заранее просчитанных и постоянно хранимых в памяти "курсов".

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

-другие.

Так что выбирай, что тебе нужно. Потом находи/спрашивай алгоритм и обрабатывай его под свои потребности.

Да но этот пример астара сделан под 2д... - А я 2д отродясь не знаю... - есть у кого пример этого исходника под 3д???

КАК ты себе представляешь ТРЕХМЕРНЫЙ АЛГОРИТМ? Да карты путей как правило двухмерны. А как оно графически отображается- ну не без разницы ли тебе?

Не согласен что без разницы! трабла в другом! Я хотел сделать один из стандартных сэмплов А* (2-й) В 3Д графическом режиме. т.е. вместо Graphics - Graphics3d - и соответственно вместо картинок подставить спрайты (тайлы с точками в центре) и чтоб герой и монстры передвигались в 3д по этим точкам - но я тут попал в тупик! в функции PathFind(x,x,x,x,x,x,x) - есть входной параметр "TileSize" - это размер тайла в 2д (ширина\длинна тайла) - так вот! А че в 3д писать вместо него??? Я пытался ставить расстояние от точки до точки - ошибка! Скайлинг спрайтов - тоже ошибка! Вот! Может есть у кого пример этого алгоритма в 3д ? Ато я чето не догоняю...

[Diplomat]

Зря не согласен, ибо разницы таки ни малейшей: алгоритм путенахождения от разного "размера тайлов" не меняется ни на йоту. Так что сиди и разбирайся в коде,а не копипасть его.
А лучше сядь и сам напиши: ибо нужно не скатать, а понять. Благо уроков/описаний волнового алгоритма и А* в Сети, как грязи.

Diplomat -> Ой ошибочка! я имел ввиду не это: "Не согласен что без разницы!" а это "Не!!! Я согласен что без разницы!"

[alcoSHoLiK]

У вас в школе знаки препинания, кроме восклицательных, не учили?!

[MiXaeL]

Можно и без 3D ( в смысле не переделывать AStar под 3D) сделать, как раньше в играх делали:
типа plane, а горы достаточно высокие и являются непроходимыми клетками (плюс непроходимые деревья, камни и т.д.) . Тогда в AStar'е даже менять ничё не придется !