В общем вопрос в следующем.
в чем состоит принцип действия ПП по вейпоинтам.
можно дать ответ в виде статьи.

да кстати А* я реализовал
поступила инфа, что алгоритмы похожи.
чем они отличаются,?

Re: ПП по Вейпоинтам
 

Для каждого жанра - свой алгоритм ПП. И нада его реализовывать самому ручками...на статью не расчитывай...так как ПП в 2д ничем не отличается ПП в 3д...единственное - это различия в типе сетки.

Re: ПП по Вейпоинтам
 

Ничем.
"Алгоритм путенахождения" и "структура карты путей" - это просто разные понятия, и термины "сходство"/"различие" при их сопоставлении мало уместны. С точки зрения значительной части алгоритмов, реализация карты путей регулярной сеткой (двухмерная матрица, массив) или вейпоинтами (нерегулярная сетка, расставленные "вручную" точки с назначенными им вручную же связями) вообще мало отличается.
...
Не растекаясь мыслию по древу, хочу посоветовать:
1. Запустить в Поиск по форуму слова "путенахождение" и, пардон, "путенах": полагаю, многочисленные обсуждения темы многое разьяснят.
2. Зайти в раздел Библиотек для Блица и взглянуть на мою библиотечку ДЕкзейк: несмотря на то, что она предназначена исключительно для работы с регулярными сетками, может оказать некоторую прикладную пользу.
3. Поискать в архивах старого Блицгеймса (тут существует соотв. тема) или спросить у Джимона: возможно где-то еще сохранились исходники моих старых тестов путенаха по вейпоинтам.

Re: ПП по Вейпоинтам
 

а если реализовал a*, то мне кажется вейпойнты это ничто иное как клетки по которым возможно передвижение, а остальные клетки - препятствия.
))

Re: ПП по Вейпоинтам
 

ИМХО:
Иррегулярная сетка предпочтительней в случаях:
А - больших пронстранств
Б - простой геометрии поля (т.е. большие однородные участки, в противоположность тому - запустанные лабиринты (в этом случае я думаю регулярная сетка предпочтительней)).

Re: ПП по Вейпоинтам
 

насчет поиска пути курим доклад Андрея Плахова с КРИ 2003 =)

Re: ПП по Вейпоинтам
 

Нерегулярная сетка - применяется наоборот в играх со сложной формой и конфигурацией ландшафта, препятствий....(так как все препятствия - будет проблематично привязать к регулярной сетке...)

Re: ПП по Вейпоинтам
 

у мну поиск по вейпоинт карте идет волновым путем :)
просто карты у меня обычно маленькие (вейпоинт карты - не больше 120 обычно) и применять A* смысла нету

Re: ПП по Вейпоинтам
 

Всем спасибо за ответы.

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

сначала в памяти сохраняем множество карт путей по алгоритму Флойда. расположенных рядом друг с другом.(много карт потому что по флойду время высчитывание самих карт и объем карт в кубической зависимости от кол-во вейпоинтов)
доставание карт из памяти составляем очень и очень мала времени так как все пути уже прописаны.
ну вот создаем множество квадратных карт рядом и одну общюю карту на все. если точка оправки и назначения у движимого объекта находятся в одном квадрате то поиск пути осуществляем в нем если в разных то поиск пути осуществляем сначала в общем квадрате который на всю карту а потом как точки (прибытия и отправки) будут находиться в одном маленьком квадрате поиск осуществляем по нему.

думаю понятно.

Re: ПП по Вейпоинтам
 

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

ЗЫ: Джокх - была необходимость)

Re: ПП по Вейпоинтам
 

протестил еще раз дикзейк..
подумал что не флойд все таки... слишком долго. и вейпоинтов много.
но баги теже....

тоесть эффект практически тот же(всего в 500 раз медленнее(это нормально если учесть что флойд за секунду 100000 найдет путь)) но вейпоинтов раз в 500 больше можно поствить.

Re: ПП по Вейпоинтам
 

2 Лейто:

0. В DExeik ней вейпоинтов. В DExeik используется регулярная сетка aka двухмерный массив. Упоминания тождества неуместны.

1. В DExeik не используется поиск по Флойду.

2. Смею преискреннейше заверить, что Ваш покорный ни в коей мере не настаивает на использовании DExeik с его многочисленными недостатками, огрехами, глюками, багами и крайне низкой производительностью вообще, и его использовании г-ном Лейто в частности. Ежели г-ну Лейто преблагоугодно использовать алгоритм Флойда, или даже алгоритм Уоршолла, то Ваш покорный не вправе упрекать г-на Лейто в таковом предпочтении, поелику обратное было бы прямым ущемлением прав г-на Лейто.

3. Засим, имею смелость нижайше попросить г-на Лейто облагодетельствовать комьюнити своей реализацией поиска пути с применением алгоритма Флойда (или любого другого алгоритма), которая в соответствии с обещанием г-на Лейто проводила бы корректный расчёт среднесложного пути в 500 (или хотя бы в 250) раз быстрее, чем это делает DExeik.

P.S. Ссылка в тему:
http://gamesanatomy.ru/index.php?nam...er=asc&start=0
Мне почему-то неосознанно вспомнился профессор Выбегалло. Интерсно, почему бы это?..

Re: ПП по Вейпоинтам
 

Дипломат.

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

сейчас практически доделал ПП.
тоесть то, что я сделал хуже чем алгоритм флойда, но допустим чтобы по флойду создать 1600 вейпоинтов нада минут 14 а с моим алгоритмом за 5 секунд. правда эффект чуть хуже на дальних расстояниях. на близких тот же.

Re: ПП по Вейпоинтам
 

а что мешает создавать вейпойнты по флойду еще на этапе создания карты (в редакторе)?
там 14 минут не критично.

Re: ПП по Вейпоинтам
 

я так и собираюсь делать, но!14 минут это на 1600 вейпоинтов или меньше, что мала для моей игры с теми картами что там будут. поэтому я разработал гениальную)) систему с двумя картами. эффект хуже но намного быстрее создавать карту и больше тем самым вейпоинтов.