Пилю A*, 2D и 3D Tile Map Editor

[bwolf88]

Если кому нужно, QuadTree и алгоритм авторазметки выложил на Гугл диск ассетами:

Авторазметка
https://drive.google.com/folderview?id= ... sp=sharing

QuadTree 2 варианта
https://drive.google.com/folderview?id= ... sp=sharing

[bwolf88]

Не очень производительный вариант симуляции процедурной воды по сетке. Сетка 32х32, если заполнить полностью, то отжирается 3 млс. Для очень больших площадей будет не очень. Долго возился с подъемом воды, без подьема скрипт элементарный. Помогла вот http://w-shadow.com/blog/2009/09/01/simple-fluid-simulation/ статья и вот это видео http://vimeo.com/34789201. Теперь не знаю как избавиться от флоатов, с Int переходами нормально разливаться отказывается.

Получилось, но стремно, точнее медленно. Если кто знает более быструю версию, буду рад если поделитесь .

Upd^ Попробовал 64х64 (4000+ водных ячеек) - 10 млс.

[bwolf88]

Интереса ради объединил алгоритм построения сетки для поиска пути и алгоритм авторазбивки поля на зоны для построения проходимости по высоте игрового поля. В этом варианте для Псевдо 3Д поиска пути, то есть одноуровневая 3Д сетка. Может работать с любым контентом у которого есть коллайдер.
Сетка строится путем сравнения высоты рядомстоящих клеток и автоматически разбивает поле на несколько зон. Гизмо для наглядности выводит только первую зону. Работает довольно шустро .

Несложно переделать и под простой полный 3Д вариант с несколькими уровнями по "Y" , но сложнее под полный 3Д с несколькими условиями определяющими проходимость диагоналей по высоте.

[bwolf88]

Теперь алгоритм поиска пусти работает еще в 3 раза быстрее предыдущей версии (то есть уже раз в 300-400 быстрее первоначального варианта). И теперь более стабилен и не вылетает на огромных дистанциях .

картинкО не будет .

[bwolf88]

Провел стресст тест своего ПП.
Моя реализация против библиотеки Crystal PathFinding. Как утверждает автор - самая быстрая реализаци А* http://www.gamedev.ru/code/forum/?id=148004
Равные условия:
Размер поля 20х30, Количество повторений расчета маршрута 1000. Учет диагоналей. Практически одинаковая преграда. ( Да и это однопоточный вариант)
CrystalPF - среднее время 31 млс. Моя реализация ~140 млс.
Проигрывает в 4 раза, но считаю что это неплохой результат, поскольку у автора CPF дикие оптимизации, которые для меня на сегодняшний день в силу моего незнания остаются недоступными. Так что я доволен как слон

[bwolf88]

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

[bwolf88]

Несколько дней пилю генератор сетки проходимости с автоподстройкой под местность.
Уже есть:
- генерация сетки 2D, 2,5D (одноуровневый 3D), 3D;
- в 2,5D, 3D подстройка по высоте поверхности;
- в 2,5D деление игрового поля на зоны проходимости в зависимости от наличия препятствий;
- в 2,5D выравнивание по самой нижней /верхней поверхности в заданной высоте;
- в 2,5D, 3D определение статических препятствий для исключения точек из проходимых (очень долго парился, в итоге сделал через render.bounds с дополнительной проверкой лучами);
- проверка доступной высоты прохода;
- проверка доступного угла подъема/спуска поверхности;
и т.д. )

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

На алгоритме ПП пока еще не проверял, но по идее должно работать .

[bwolf88]

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

[NeroXT]

Отлично получается! Буду следить за обновлениями.

[bwolf88]

Переписал ПП и добавил свой простенький менеджер потоков.

Карта 100х100. 4 дополнительных рабочих потока. Такси берутся по одному, а не кучей, как в случае с тредпулом, что не может не радовать + никаких захлебываний.
Каждый бот прокладывает путь каждый кадр к курсору мыши - пока без передвижения.
Первый тест (на первом видео) боты рисуют LineRenderer, поэтому в конце начало проседать до 50-60 ФПС. Больше 200 ботов ставить не стал.
На втором видео без Linerenderer и карта чуть попроще - в конце было 363 бота и вполне терпимо .

Видео 1

Скрытый текст: показать

Видео 2

Скрытый текст: показать

[getAlex]

Почитал статью кристала, посмотрел твои видео. Если уж на то пошло, то самый быстрый алгоритм в мире - хранить информацию для каждой точки перехода в каждую точку. Это займёт реально дофигища места(как там автор говорил..."компромисс между памятью и скоростью"), но поиск пути будет заключаться в поиске нужного готового решения в массиве, а не поиск самого пути.
Есть ещё промежуточные варианты: есть основные "дороги"(карта основных путей) и там уже всё заранее просчитано как и куда дойти(или в сложных участках). И есть биомы вокруг дороги, внутри которых ищется путь к ближайшей точки дороги.
Есть ещё алгоритмы, как в "казаках", только не двухслойные, а N-слойные, где N №1 задаёт минимальный уровень точности пути, а все последующие генерируются, допустим 1 к 16.

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

[Paul Siberdt]

Мнэээ... а эти все эксперименты, в конечном счете, приведут к созданию оптимизированного navigation mesh, или так и останутся в виде стопицотмильенов узлов?

[bwolf88]

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

Это все неправильный костыльный подход, потому что в этом случае это уже не "поиск пути", а просто выбор маршрута. Я делал еще на первых этапах хранения ссылок ближайших соседей в каждой точке - это было на 20-30% быстрее, но памяти кушало в 10 раз больше. + предпросчет даже карты 100х100 точек может затянуться хз на сколько времени (10000х10000 возможных вариантов)

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

Это в старом видео ?
Это 2.5D генерация точек - тот же 2Д только с учетом Y составляющей. Там 2 варианта построения точек - либо берется самая верхняя и тогда точки ставятся на самую высокую поверхность, либо самая нижняя, и тогда все что выше не учитывается.

Там же есть и 3Д генерация, где точки расставлялись уже и внизу и вверху если плоскость отвечала условиям (были соблюден угол подъема и установленная высота для прохода бота).

Есть ещё алгоритмы, как в "казаках", только не двухслойные, а N-слойные, где N №1 задаёт минимальный уровень точности пути, а все последующие генерируются, допустим 1 к 16.

А это можно простым QuadTree сделать .

Мнэээ... а эти все эксперименты, в конечном счете, приведут к созданию оптимизированного navigation mesh, или так и останутся в виде стопицотмильенов узлов?

Теоретически я уже сейчас могу сделать что то типа навмеша, у меня ведь есть алгоритм который делит карту на зоны. На основе этих зон по идее и можно сделать навмеш. Стремно то, что большую карту долго обновлять, я пока не думал над тем как обновлять конкретные участки.

[getAlex]

Теоретически я уже сейчас могу сделать что то типа навмеша, у меня ведь есть алгоритм который делит карту на зоны. На основе этих зон по идее и можно сделать навмеш. Стремно то, что большую карту долго обновлять, я пока не думал над тем как обновлять конкретные участки.

Но зачем ты убил столько времени, чтоб прийти к уже готовому варианту?
Я мог бы понять, если бы ты хотел изучить область для изобретения в дальнейшем своих алгоритмов и улучшений, т.е. создать свою технологию, превосходящую текущую и на основе неё скажем сделать игру(как гугл на основе иноваторского алгоритма поиска создал себя). Но это же поиск пути. Тут люди собаку съели. Вообще бесперспективно было копаться в этой области. Есть куча областей, в которых всё находится в состоянии 20% "абы работало", но ты взял саму протёртую, где дай бог чтоб за 50 лет улучшили алгоритм на 10-20% в каком-то британском или американском университете

То же самое могу сказать по поповоду лодов для террейна и по поводу перлин нойса в вокселях. Это протёртые до дырок области.

[bwolf88]

Но зачем ты убил столько времени, чтоб прийти к уже готовому варианту?

Это из разряда:
Зачем ты убил столько времени чтобы изучить ЯП ведь есть уже готовые программы, бери тыкай кнопки, а еще лучше если есть кнопка "чтобы работало зашибись".
Зачем ты убил столько времени на модель ведь есть куча готовых и даже бесплатных.
Зачем ты убил столько времени на сеть если есть фотон, шматон и еще куча _тонов.
Зачем ты убил столько времени на эту игру, если уже есть 100 таких же и в нее будет играть 2,5 человека, а с рекламы ты получишь 12 копеек.

Я учусь строить программы, для хорошей программы нужно не только уметь писать код, но и знать как его правильно написать. Отличие моего кода от того что есть в сети - лаконичность, вместо 1000 строк у меня 150, вместо непонятных и сложных конструкций у меня простая схема.

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

Вот вам еще вопрос: зачем инженеры в качестве хобби сидят и мастерят свои радиоприемники, телевизоры, а кто то еще и умудряется это продавать - ведь есть целая индустрия, которая этим занимается ?

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