AI в играх. Дискретизированное пространство


Notice: Функция get_currentuserinfo с версии 4.5.0 считается устаревшей! Используйте wp_get_current_user(). in /hlds/web/u138079p19/code4life.ru/htdocs/wp-includes/functions.php on line 3840

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

Примечание: статья не претендует на научную точность … говорю как сам пониманию.

Вообще, это все взято из дискретной математике, а именно из теории графов. Для изучения этого не будем окунаться в математику, достаточно хотя бы понять суть, и уяснить очень базовые понятия. Сам я не специалист в области математике, но построить АИ сетку смог и научил НПС по ней ходить, конечно не без помощи интернетов))

Итак, все пространство, которое будет доступно для живности в игре, должно быть описано математически, то есть это пространство должно быть интерпретировано (просчитано) как граф:

AI в играх. Дискретизированное пространство
граф состоящий из вершин (круги с буквами внутри) и ребер ( вершины связанные линией)

Самое главное на этом этапе — это разобраться с терминологией.

Дискертизированное пространство — это пространство описанное графом, который состоит из вершин и соединяющих их ребер. По такому графу можно строить пути.

Граф — объект состоящий из множества вершин которые могу быть соединены ребрами. Картинка выше это граф.

Вершина — ключевой элемент графа, составная часть графа. На картинке выше это круги.

Ребро — соединение между вершинами. На картинке выше это линии соединяющие круги, следует обратить внимание что соединения AB BD DC CA одного цвета, а AD BC другого, это значит что между ними разная связь.

А как же этот граф будет выглядеть в игровом пространстве? Очень просто:

AI в играх. Дискретизированное пространство
Квадраты со стрелками это вершины, а стрелки это ребра, указывающие на связи между вершинами, а все в целом это граф! В данном случае не показаны диагональные связи.

Все просто, верно?

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

Связный граф — это граф в котором для каждой u, v вершины есть путь из u в v.

Ориентированный граф — это граф в котором ребра имеют направления, то есть ребра ориентированы.

Смешанный граф — это граф в котором есть ориентированные и неориентированные ребра.

Планарный граф — это граф, все вершины которого, располагаются на одной плоскости, и ребра не пересекаются.

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

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

Это тема уже другой статьи, однако могу сказать что алгоритм A* с этим справляется как надо, причем без каких либо объяснений ему что есть и другие этажи. Но путь ищется в этом случае дольше (ну как дольше, все зависит от ситуации, к примеру может быть дольше на 0.5 млсек), то есть алгоритм ищет сначала можно ли дойти до вершины по прямой и только потом анализирует то что ведет на верх.


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

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

Также беспокоил вопрос перемещения по этой сетке. Здесь все тоже оказалось предельно просто (перемещаемся из центра в центр при наличии сетки), самое главное чтобы эта сетка была))

Поделиться:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*