“Суп из полигонов” для души программиста: Поиск пути в 3D-среде

08.10.2012

Этот материал является переводом статьи Патрика Смита. Оригинал публикации доступен здесь.

Одна из главных задач системы AI – сделать так, чтобы юнит не казался “тупым”. В корне этой задачи лежит сложнейшая проблема – поиск пути (pathfinding). В наши дни 3D-графика и звуковые технологии начинают достигать уровня реализма, который попросту исчезает, когда мы видим, как юнит, наделенный искусственным интеллектом, входит в сплошную стену, “скользит” по ее периметру и в итоге застревает в “блуждающих” полигонах. Традиционные технологии, которые хорошо работали в играх, вышедших несколько лет назад, терпят крах, когда сталкиваются с нынешними сложными 3D-средами.

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

Где найти нужные данные?

Существует множество хороших алгоритмов, использующих связные графы для определения пути. Для простых 2D-игр использование связных графов было побочным эффектом плиточной системы создания карт. Для 3D-игр, особенно тех, которые построены из произвольной геометрии, такого простого решения не существует. Итак, проблема остается, где же мы можем получить нужные данные?

Представьте себе, что вы нарисовали контуры витража в своём любимом графическом редакторе. Изображение состоит из больших кусочков белого пространства неправильной формы. Ваша задача: закрасить каждый из этих кусочков для завершения витража. Теперь подумайте — какой инструмент лучше всего подходит для этой работы — карандаш (которым нужно закрашивать каждый пиксель) или заливка (которая может рекурсивно заполнить выбранную вами область любым цветом)? Решение очевидно, не так ли? Так почему же многие дизайнеры вынуждены вручную заполнять уровни многочисленными узлами поиска пути, секторами, сетками, зонами, плоскостями, частями, входами или чем-нибудь ещё? Теперь, представьте автоматизированную систему, которая сможет обнаружить все возможные проходимые места в вашей самой сложной среде с помощью всего лишь одного щелчка мыши. Представили? Отлично! Давайте её построим.

Для решения этой сложнейшей задачи мы позаимствуем простую идею из нашего примера с витражом, а именно, рекурсивную заливку. Единственные инструменты, которые нам понадобятся — качественная система обнаружения столкновений и знание единственной точки в “супе из полигонов”, где может стоять юнит. Алгоритм работает следующим образом:

Используем систему обнаружения столкновений, чтобы определить, может ли юнит существовать в начальной точке. Если область позволяет, добавим эту точку в список (который будет нашим списком задач). Теперь, проциклируем все записи в списке задач (пока что у нас одна запись). Для каждой записи в списке, смоделируем юнита, делающего шаг в направлении каждой из четырех сторон света (север, восток, юг и запад). Если одна из этих точек проходит проверку на столкновения (collision check), добавим её в список задач. Сохраним информацию о соединении между этими двумя точками (точка А может дойти до точки B).

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

Деталь первая: фигуры и плоскости

При выполнении проверок на столкновения, мы имеем дело с объемами, но никак не с точками. Всё это потому, что мы пытаемся моделировать объект, а он в свою очередь имеет объем. Мы должны решить, какой объем дает лучшие результаты. Различные системы столкновений используют различные представления объема столкновения объекта; некоторые используют цилиндры, некоторые сферы, в то время как другие используют “боксы”. Для того, чтобы полностью покрыть пространство, не оставляя пробелов между плоскостями, мы будем использовать “боксы”.

Расположенные вплотную круглые формы образуют пробелы, в то время как боксы охватывают пространство непрерывно.

В этот момент вы начнете замечать знакомую форму, которую принимают данные — сетку! Тем не менее, это не простая 2D сетка, которую вы себе возможно представляете. Если вы проигнорируете высоту каждого “бокса”, получится равномерная сетка. Однако, поскольку мы моделируем ходьбу из одной ячейки сетки к другой, в некоторых местах наша сетка может подниматься вверх и вниз, например, проходя через мосты, над и под эстакадами. Это означает, что для любой координаты, заданной на плоскости, может существовать более одной ячейки сетки (учитывая высоты). Хороший пример — винтовая лестница. Алгоритм будет заполнять каждый поворот лестницы вверх по кругу, как если бы это было на плоской поверхности. Однако, если бы вы стояли на вершине этой лестницы и направили вниз луч, он столкнулся бы с ячейками сетки на каждом её повороте.

Деталь вторая: размер имеет значение

Очень важно, чтобы размер ячейки подходил для поиска пути объекта на уровне. Если размер слишком большой — объект не сможет пройти через не прямоугольные двери. Если наоборот — слишком маленький, вы обнаружите, что вашему компьютеру не хватает оперативной памяти для завершения заливки. Предлагаем сделать из объема столкновения объекта выровненный по осям ограничивающий бокс. Он должен полностью содержать объект, независимо от его ориентации. Теперь разделим его размеры по осям X и Y на 2 и получим “высокий, худой” бокс.

Ячейки правильного размера, как правило, составляют четверть максимизированного бокса столкновения объектов.

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

Деталь третья: важно не то, что вы знаете, а кого вы знаете

Как минимум, каждая ячейка сетки должна знать, которые из её соседей являются проходимыми. Можно достигнуть этого посредством простой структуры данных, которая содержит четыре указателя, по одному на каждого из соседей. Если указатель NULL, то пройти в этом направлении нельзя.

class CPathCell
{
    .
    .
    .
    CPathCell * NorthCell;
    CPathCell * SouthCell;
 
    CPathCell * EastCell;
    CPathCell * WestCell;
};

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

Деталь четвертая: бонуса за дополнительную работу не будет

Будьте внимательны — избегайте вторичной обработки проходимых ячеек. Например, мы начинаем с ячейки А и успешно моделируем движение к ячейке B. Когда приходит время обработать ячейку Б, мы уже знаем – ячейка А была обработана, поэтому она не должна быть добавлена в список. Однако, нам также нужно смоделировать движение из ячейки B в ячейку A — то, что мы прошли от А до B не гарантирует, что мы сможем пройти от B до А (например, если А – крутой обрыв, а Б – яма под обрывом).

Деталь пятая: не много ли требуется памяти?

Честно говоря, довольно много. Поэтому крайне важно, чтобы структура ваших данных была как можно плотнее. Например, мы видели, как для большого уровня создается свыше 10 миллионов ячеек.
Имейте в виду, что это этап предварительной обработки, мы просто генерируем данные. Прежде чем мы сможем использовать эти данные, они должны быть сжаты в формат, допустимый для выполнения приложения.

Двери, лифты и лестницы — подумать только!

Очень радует, когда даешь AI команду «Goto (X, Y, Z)» и видишь, как юнит выполняет сложную последовательность шагов. Например, задан единственный пункт назначения — AI может подойти к входной двери здания, открыть её, пройти к лифту, подождать пока приедет лифт, подняться на лифте на крышу, выйти из него, подойти к лестнице в основании башни и подняться на её вершину.

Но что нас обрадует больше? — Сделать так, чтобы информация о “телепортах” автоматически определялась на этапе создания данных. Чтобы достичь этой цели, мы должны знать расположение каждой двери, лифта, лестницы или другого устройства телепортации, а также их зоны входа и выхода. Теперь алгоритм работает следующим образом:

Во время выполнения заливки, возьмите необработанные ячейки из списка задач. Выполните моделирование (как мы делали это ранее), если ячейка проходит, проверьте, полностью ли она содержится в зоне входа одного из устройств телепорта. Если эта ячейка  действительно внутри зоны входа, создайте новую ячейку в центре зоны выхода и выполните проверку на столкновения, чтобы убедиться может ли она там находиться. Если новая ячейка пройдет проверку, добавьте ее обратно в список задач – это действие обеспечит продолжение моделирования движения на другой стороне портала.

Не поддавайтесь искушению сохранить связь между ячейками входа и выхода. Дополнительная информация будет излишне “раздувать” размер каждой ячейки из вашей 10 миллионной заливки.  Информация о соединениях может быть легко установлена после окончания заливки.  Мы вернёмся к этому позже, когда будем обсуждать сжатие данных.

Что делать, если вы не можете уделить 500 МБ оперативной памяти поиску пути

Теперь у нас есть отличный простой алгоритм генерации связного графа уровня. Настало время начать проверку данных. Скажем, для каждой ячейки требуется около 50 байт данных, а мы сгенерировали порядка 10 миллионов ячеек. Это значит, что данные поиска пути у нас занимают 500 МБ. При решении задач, чем больше данных, тем лучше, но половина гигабайта это просто смешно! Пришло время сжать данные до чего-то более управляемого.

Рассмотрим простой сценарий. Если ячейка А соединяется с ячейкой Б, а ячейка Б с ячейкой А, действительно ли мы нуждаемся в двух ячейках? Нет, не нуждаемся. Мы можем объединить две ячейки в сектор и избавиться от первоначальных ячеек. Определим сектор как выпуклый многогранник свободно проходимого пространства. Учитывая наш конкретный набор данных и наши цели, бокс является наиболее эффективным выпуклым многогранником.

Рассмотрим следующую схему:

Ячейка А связана с B и C, ячейка C соединяется с А и D, D с С и В, а В связана с ячейками D и A. Здесь мы можем объединить все четыре ячейки в один сектор и отказаться от первоначальных ячеек. Обобщая, мы можем объединить в сектор любой прямоугольной набор смежных, соединенных между собой ячеек. В конечном счете, мы хотим сжать все ячейки в сектора. Тогда сектор становится основным типом данных, используемых во время выполнения решения пути.

Как только сектор создан, необходимо сохранить информацию о соединениях, которая изначально содержалась в его ячейках. Чтобы достичь этого, сохраняют крайние и избавляются от внутренних ячеек сектора. Крайние ячейки “делятся” информацией о соединении с ячейками в других секторах, в сущности, связывая сектора между собой.

Чтобы сохранить данные о соединениях секторов, оставьте крайние ячейки.

После того как все сектора были созданы, объединим крайние ячейки, которые совместно используют общий сектор назначения, в портал. Определим портал как связь между секторами; то есть, чтобы добраться от сектора А к сектору B – вам нужно пройти из вашего текущего местоположения (сектор А) через портал AB. Физическая форма портала – объем, ограничивающий его крайние ячейки.

Портал — связь между двумя секторами.

Порталы могут быть односторонними или двусторонними. Если крайние ячейки в секторе А связаны с крайними ячейками в секторе B и наоборот, то портал – двусторонний. В противном случае портал является односторонним.

Как только портал будет создан, он будет добавлен в список порталов сектора, который содержит крайние ячейки. Если это двусторонний портал, он будет добавлен в portal-list обоих секторов.

И снова — двери, лифты и лестницы!

Ранее мы обсуждали, как сделать процедуру Flood Fill (заливку) через устройства телепорта, такие как двери, лифты и лестницы. Теперь, когда мы превратили все наши ячейки в сектора и порталы, пришло время объединить информацию об этих устройствах, для того, чтобы наш AI мог их использовать.

Для создания портала, в первую очередь пересекают его зоны входа и выхода с существующими pathfind-секторами. Если проверка на пересечение дает по крайней мере один сектор для зон входа и выхода, то мы можем создать портал между ними. Ограничительный бокс входного/выходного портала — это объем, созданный пересечением зоны входа с pathfind-сектором.

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

Строение сектора

После того, как сектор создан он содержит два важных сведения: ограничительный бокс и список порталов (portal-list). Ограничительный бокс используется в динамическом режиме для того, чтобы определить, где в pathfind-мире, в настоящее время находится AI. Портал-лист — информация о соединениях, которую решатель использует для вычисления того, каким образом объект достигает места назначения из своей текущей позиции.

class CPathfindSector
{
    .
    .
    .
    CAABox BoundingBox;
    CVector PortalList;
};

Как видите, сектор на самом деле просто пространственная связь портала; большинство важных данных содержится в портале.

Строение портала

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

class CPathfindPortal
{
    .
    .
    .
    CPathfindSector * DestSector1;
    CPathfindSector * DestSector2;
    int MechanismID;
    MECHANISM_TYPE MechanismType;
    CPathfindPortal * MechanismExitPortal;
    ACTION_TYPE ActionType;
};

Как видите, вся информация о соединениях хранится в портале. Следовательно, там же хранится и «ключ» к решению пути.

Решение пути

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

К счастью для Боба, мы можем использовать его местоположение (X,Y,Z), чтобы выяснить в каком pathfind-секторе он стирает свои носки. Этот сектор содержит список порталов, которые он может использовать, чтобы добраться до других секторов. Эти сектора, в свою очередь, содержат собственные списки порталов, которые могут быть использованы, чтобы добраться до других секторов, и так далее.

На этой стадии, чтобы доставить Боба к зданию ООН, может быть применено любое количество алгоритмов нахождения лучшего пути. Мы выяснили, что изменённый алгоритм поиска A* отлично справляется с данной задачей. Простая реализация будет использовать накопленное между порталами расстояние как траверсированные издержки и прямолинейное расстояние до цели как эвристические издержки.

Теперь представьте, что Боб и двадцать его приятелей должны добраться до здания ООН одновременно. Двадцать различных запросов на нахождение сложных путей могут значительно превысить количество CPU, которое ваша игра в каждом фрейме уделяет AI. К счастью для нас, это будет не очень заметно, если мы распределим обработку этих путей по нескольким фреймам. Например, если Боб, прежде чем встать и выйти через дверь, полсекунды сидит и думает, кто-нибудь сможет заметить это? Половины секунды (500 миллисекунд, ~ 1 миллиард тактов) будет более чем достаточно для системы поиска пути, чтобы решить несколько путей одновременно.

Для распределения решения пути по нескольким фреймам можно использовать алгоритм, изложенный в следующем псевдокоде:

while (Time_Has_Not_Elapsed () && CurrentPathSolver != NULL)
{
    if (CurrentPathSolver->Process (Time_Remaining_This_Frame))
    {
        RELEASE (CurrentPathSolver);
        CurrentPathSolver = Get_Next_Path_Solver ();
    }
}

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

Для распределения самого решения пути по нескольким фреймам, учитывайте следующий псевдокод:

CPathSolver::Process (float time)
{
    while (Time_Has_Not_Elapsed)
    {
        CPathfindSector * sector = Get_Least_Cost_Sector ();
 
        if (sector == NULL)
        {
            Handle_No_Path ();
        }
        else if (sector == DestinationSector)
        {
            Hande_Path_Found ();
        }
        else
        {
            CPathfindPortal *portal = NULL;
            while (portal = sector->Get_Next_Portal (portal))
            {
                Process_Portal (portal);
            }
        }
    }
}

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

Расслабься чувак! Избегаем “роботизированных” путей

Когда мы используем секторно-портальную систему, решенный путь представляет собой упорядоченную последовательность порталов. Этот путь будет следовать установленному порядку: идете к порталу AB, поворачиваетесь лицом к порталу BT, идете к порталу BT, поворачиваетесь к порталу ТУ, идете к нему, и так далее. Если ваш AI не робот, желательно, чтобы юнит вел себя как можно более жизненно, а прохождение кратчайшего пути до каждого портала не способствует жизненности.

Для того чтобы наш путь казался немного более естественным, мы будем использовать сплайны. С точки зрения непрофессионала, сплайны — изогнутые линии, которые следуют множеству точек. Различные типы сплайнов следуют своим точкам разными способами. Некоторые сплайны проходят через свои контрольные точки, другие сплайны действуют как магниты и либо притягиваются, либо отталкиваются от своих контрольных точек. Чтобы увидеть все преимущества сплайнинга пути, рассмотрим следующую схему:

Сплайнинг делает кривую пути более естественной.

Выглядит здорово, не правда ли? К сожалению, есть одна проблема. Поскольку сплайн ничего не знает о секторах и порталах, которые определяют «безопасный» участок для ходьбы юнита, вполне вероятно, что кривая сплайна покинет эти объемы, вызвав столкновения юнита с углами, дверными проемами, мусорными баками или даже его падение с края утеса!

К счастью, мы можем воспользоваться математическим свойством кривых Безье (тип сплайна): если контрольные точки кривой Безье лежат внутри объема, то и сама кривая будет лежать внутри объема. Кривая Безье – сплайн третьего порядка, заданный начальной точкой, конечной точкой и последовательностью контрольных точек. Контрольные точки действуют как магниты, «оттаскивая» изгиб от отрезка линии, определенного начальной и конечной точками.

Учитывая это, наш “живой” алгоритм постобработки будет работать следующим образом:

Построим кривую Безье, используя точки конечного пути. Составим список секторов и порталов, которые AI будет проходить на своем пути. Каждую контрольную точку на кривой Безье “прикрепим” к объемам сектора. Чтобы “прикрепить” контрольную точку, создадим линию от контрольной точки до соответствующей точки на не-сплайновом пути. Проверим этот отрезок, чтобы понять проходит ли он через сторону какого-либо бокса сектора в списке. Если проходит, проверьте, не является ли площадь пересечения порталом. Если точка пересекает стенку сектора, и она не проходит через портал, “прикрепите” контрольную точку к стенке сектора; в противном случае оставьте точку в покое – она будет действительной.

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

Этот алгоритм позволит AI следовать естественно изогнутому пути, не покидая “безопасных” pathfind-секторов.

Использование Innate Waypaths

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

Innate waypaths — это еще одно мощное решение, которое хорошо интегрируется с нашей системой поиска пути. Waypath — это созданные вручную последовательности направляющих точек, которые формируют путь. Waypath может быть жестким или сплайновым. Каждая направляющая точка на waypath может кодировать специфическую информацию — здесь пригнуться, там ускориться, замедлиться или даже перейти к следующей точке. Чтобы интегрировать эту информацию в наш решатель пути, рассмотрим следующий алгоритм.

Запустите обычную pathfind-заливку для создания секторов и порталов. Для каждого innate waypath создайте “сектор-пустышку” (сектор без размера или расположения) и добавьте его в систему. Для каждой направляющей точки в waypath, найдите pathfind-сектор который её пересекает. Создайте на месте направляющей точки двусторонний портал с pathfind-сектора в “сектор-пустышку”. Добавьте новый портал в оба сектора – pathfind-сектор и waypath “сектор-пустышку”.

Во время выполнения решения пути, эвристика алгоритма должна быть с уклоном в сторону waypath-секторов (умножьте затраты использования waypath-сектора на 0,75). В результате AI будет стремиться следовать innate waypaths.

Учитывая эту систему, для того, чтобы автомобиль AI ехал по правой стороне дороги, дизайнер уровней будет просто рисовать односторонний, предназначенный только для транспортных средств, innate waypath вдоль каждой стороны дороги.

Innate waypaths могут быть использованы для того, чтобы транспортное средство двигалось по правой стороне дороги.

Следуй за лидером

Игроки умнее AI: люди обладают логикой и могут совмещать абстрактные понятия. Способность логически мыслить позволяет игрокам совершать действия, на которые AI не способен, но если нам повезет, возможно, он сможет их повторить. Например, во время перестрелки на втором этаже здания, игрок осознает – ему не отбиться. В отчаянии, он могучим прыжком выскакивает из окна на улицу. Что сделает AI? Пока мы не предложим ему альтернативы, AI поступит следующим образом: найдет путь вниз по лестнице, откроет входную дверь и тупо осмотрит улицу, ища игрока, которого уже и след простыл. Было бы гораздо веселее, если бы AI просто выпрыгнул из окна вслед за игроком, не так ли?

Существует множество различных способов решения данной проблемы, давайте выберем самый простой. Мы знаем, откуда игрок прыгнул и где он приземлился. Если обе точки находятся внутри данных поиска пути, почему бы не добавить временный односторонний портал “прыжка” между этими двумя секторами? Все, что нам требуется сделать, это закодировать немного информации о прыжке (ориентация, скорость и время). В зависимости от системы физики, этого может быть вполне достаточно для AI, чтобы повторить могучий прыжок игрока. Мы можем даже сохранить алгоритм FIFO «ведро» для этих временных порталов, чтобы другие AI могли последовать за первым.

Транспортные средства

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

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

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

Будьте внимательны, располагая порталы. Не забудьте о радиусе поворота автомобиля.

Путь сгенерирован, но, возможно, движение транспортных средств по нему будет проблематичным. Это потому, что ориентация очень важна при работе с транспортными средствами; наша секторно-портальная система не полностью справляется с этим. Рассмотрим следующую схему:

Ориентация важна при прохождении пути. Оказавшись в секторе B, автомобиль не сможет повернуть в сектор C.

В секторно-портальной системе автомобиль будет следовать кратчайшим путем от входа в сектор A до сектора B. Автомобиль будет ориентироваться таким образом, что не сможет сделать поворот в портал сектора С. Однако, если транспортное средство въедет по дуге в сектор A, оно сможет попасть в сектора B и C. К сожалению, мы не сможем узнать необходимо ли это, пока не изучим путь.

Простым решением указанной выше проблемы, хорошо работающим с системой, которую мы описываем, является сплайнинг пути. Тем не менее, ни один из классических «правильных» сплайнов не будет работать в данной ситуации, и это хорошо — мы создадим нашу собственную кривую.

Наша цель — создать непрерывную кривую линию, которая поможет транспортному средству объехать углы по дуге, учитывая его ограниченный радиус поворота. Такой путь может быть создан с использованием прямой линии и окружности поворота автомобиля. В отличие от «правильных» сплайнов, этот путь не является непрерывным в математическом смысле, но состоит из трех различных непрерывных частей, которые, при размещении концом к концу, образуют непрерывный путь. Эти три части: кривая выхода из предыдущей точки, прямая линия от кривой выхода до кривой входа в следующую точку, и кривая входа в следующую точку. Примечание: начальная и конечная точки всего лишь содержат две части (для начальной точки не существует предыдущей части, так же как для конечной точки не существует следующей части). Рассмотрим следующую схему:

Кривая движения транспортного средства состоит из трех отдельных частей: кривой выхода, прямой линии и кривой входа.

Чтобы построить эту кривую, наложите окружность поворота транспортного средства на каждый узел пути. Будем считать, что оптимальный центр этой кривой поворота будет лежать в точке на полпути между углами, образованными (prev_node — curr_node) и (next_node — curr_node) векторами. Это приведёт  к тому, что текущая узловая точка будет лежать на периметре дуги поворота.

Для каждой окружности поворота на пути, найдите внутренние и внешние точки касания. Внутренняя точка касания — ближайшая точка касания от предыдущей точки до кривой поворота. Внешняя точка касания -  ближайшая точка касания. Ячейка А связана с B и C, ячейка C соединяется с А и D, D с С и В, а В связана с ячейками D и A. Здесь мы можем объединить все четыре ячейки в один сектор и отказаться от первоначальных ячеек. Обобщая, мы можем объединить в сектор любой прямоугольной набор смежных, соединенных между собой ячеек. В конечном счете, мы хотим сжать все ячейки в сектора. Тогда сектор становится основным типом данных, используемых во время выполнения решения пути.от следующей точки кривой поворота. Теперь просто соедините точки. Путь выглядит следующим образом: прямая линия от начальной точки до внутренней точки касания на кривой поворота следующего узла пути; кривая поворота внешней точки касания; прямая линия от этой точки до внутренней точки касания кривой поворота следующего узла пути и так далее.

После своего завершения, этот алгоритм дает непрерывную кривую, которая следует за ограничениями поворота транспортного средства, двигающегося по пути.

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

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

Заключение

Пользуясь простым алгоритмом заливки, мы можем решить труднейшую задачу автоматической генерации связных данных через сложный “суп их полигонов”. С помощью нескольких приемов и дополнений мы можем легко использовать двери, лестницы и лифты; применять сплайн к решённому пути для придания ему естественности; динамически изменять pathfind-данные, чтобы позволить AI повторить действия игрока; использовать innate waypaths, чтобы решить проблему специфического поведения AI; и распределять выполнение решения пути в течение нескольких кадров, чтобы сбалансировать нагрузку на процессор.

Отдельное спасибо Eric Cosky за оригинальную концепцию алгоритма заливки. Блестящая идея, которая доказывает ценность мозгового штурма с другом перед погружением в решение сложной проблемы. Спасибо Colin Mclaughlan за предложенную концепцию динамического временного портала “прыжка”.

Заполнен: ОбщееТуториалы
Присвоен тэг:

avatar

Об Авторе ()

Пишу музыку, делаю сайты и перевожу статьи :) e-mail: v-vasiley@rambler.ru

Комментирование закрыто.

Наверх