Вам знаком термин триангуляция? На ютубе к последнему ролику мне подкинули идею о создании поиска пути через треугольники Бориса Делонье

Вам знаком термин триангуляция? На ютубе к последнему ролику мне подкинули идею о создании поиска пути через треугольники Бориса Делонье, как в Старкрафт 2 или Варкрафт 3. Я не знал об этом. Погуглил - тема интересная.

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

1. Процедурная генерация ландшафта. Сначала создаётся алгоритм шума (Перлин или Вороной) и с помощью шума генерируются точки в пустом мировом пространстве. Затем необходимо по этим точкам создать треугольники. И далее с помощью меш генератора по треугольникам создать ландшафт. И вот у нас есть процедурный генератор карт и треугольной сетки.

2. Поиск пути. Воссоздать в UE алгоритм Делонье. Создать несколько типов поверхностей. Назначить им различные вес (стоимость), затем создать диапазоны уклонов и им тоже назначить стоимость и затем добавить эту информацию к треугольникам. Так путь будет строиться в зависимости от веса (стоимости). Необходимо интегрировать во встроенную навигационную систему NavMesh и будет вместо квадратной сетки - треугольная.

3. Валидация строительства. Треугольники автоматически будут получать статус «блокирован» если на нём размещается объект, есть юнит или крутой склон. К тому же здания можно привязать к этой сетке.

4. Радиусы и границы. Туман войны. Границы владений, диапазоны работы предприятий, радиус сбора ресурсов и прочее можно организовать на этой сетке.

5. Из пункта 2, 3 и 4 следует, что на такой сетке можно реализовать пространственное хеширование для кеширования данных и поиска объектов. Отличия от стандартного NavMesh в том, что стандартный перегенерируется полностью каждый раз при изменении. В случае с треугольниками обновляется только треугольник с изменениями.

6. Визуальное отображение. Можно сделать несколько режимов отображения для разных задач. Например отображение проходимых для юнитов участков. Доступные места для строительства. Радиусы залежей полезных ископаемых или других ресурсов. Границы владения. Либо просто подсветка треугольников, в которых есть хоть какая-то информация.

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