AI для компьютерной игры

[Euler7]

Доброго времени суток. У меня такая задачка- есть игра, в ней на двухмерной карте катаются танчики с разными характеристиками и убивают друг-друга. Нужно написать "игроков" для этой игры. Игрок- это отдельный поток, который по специальному протоколу получает сведения об изменениях в игре. Кроме того, эти игроки могут быть ещё и союзниками, что тоже хорошо бы использовать(т.е. совершать совместные манёвры). К сожалению не смог найти тематической литературы в рунете, подскажите пожалуйста что-нибудь.

[Yuri Gendelman]

Единственная книга на русском, которую я знаю, да и то переводная:
Алекс Дж. Шампандар. "Искусственный интеллект в компьютерных играх: как обучить виртуальные персонажи реагировать на внешние воздействия". Вильямс. 2007

[Euler7]

Yuri Gendelman в сообщении #678814 писал(а):

Единственная книга на русском, которую я знаю, да и то переводная:
Алекс Дж. Шампандар. "Искусственный интеллект в компьютерных играх: как обучить виртуальные персонажи реагировать на внешние воздействия". Вильямс. 2007

Спасибо, именно её сейчас и читаю.

[Euler7]

Боле конкретная задача- нужно добраться до определённой точки. Целевая точка задана координатами, в общем случае бот знает только часть карты:

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

[mustitz]

Выбираем белую точку, ближайшую к красной. Если тупик, то тут мы сделать ничего не можем. И идем к ней.

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

[Euler7]

mustitz в сообщении #678918 писал(а):

Выбираем белую точку, ближайшую к красной. Если тупик, то тут мы сделать ничего не можем. И идем к ней.

Увы:

так мы упрёмся в стену о которой заранее знаем.

[Yuri Gendelman]

Сайт: Искусственный интеллект в играх

mustitz в сообщении #678918 писал(а):

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

По-моему это хорошее предложение.

[Euler7]

Yuri Gendelman в сообщении #678948 писал(а):

Сайт: Искусственный интеллект в играх

Спасибо, сейчас изучим.

Yuri Gendelman в сообщении #678948 писал(а):

По-моему это хорошее предложение.

У меня карта и так дискретна :) . Плюс эта тема раскрыта в книге Шампандара из первого поста.
Если мы начинаем в точке A и идём в точку B то, нужно найти точку(C), на границе области видимости, для которой сумма $(A\to C)+\sqrt{(C_x-B_x)^2+(C_y-B_y)^2}$, где $A\to C$ - путь между точками(его мы можем вычислить, т.к. он пролегает по видимой области). Мне непонятно как это сделать без просчёта всей карты.

[worm2]

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

[Euler7]

worm2 в сообщении #679161 писал(а):

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

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

[mustitz]

Euler7 в сообщении #678960 писал(а):

Если мы начинаем в точке A и идём в точку B то, нужно найти точку(C), на границе области видимости, для которой сумма $(A\to C)+\sqrt{(C_x-B_x)^2+(C_y-B_y)^2}$, где $A\to C$ - путь между точками(его мы можем вычислить, т.к. он пролегает по видимой области). Мне непонятно как это сделать без просчёта всей карты.

Что именно непонятно? $\sqrt{(C_x-B_x)^2+(C_y-B_y)^2}$ считается тривиально. $A\to C$ считается для видимой карты. Если вычислений много, можно строить специальные индексы, как я описывал. Непонятно, что непонятно.

[Euler7]

mustitz в сообщении #679907 писал(а):

Что именно непонятно? $\sqrt{(C_x-B_x)^2+(C_y-B_y)^2}$ считается тривиально. $A\to C$ считается для видимой карты. Если вычислений много, можно строить специальные индексы, как я описывал. Непонятно, что непонятно.

Вычислений слишком много, при таком подходе приходится всю видимую карту просматривать. Объединить несколько клеток в одну, конечно, вариант, но Mysterious Light предложил более простой и очевидный(теперь очевидный ) выход:

Mysterious Light писал(а):

Только что я подумал, что исходное условие ($(A\to C)+|B-C|=\mathrm{min}$) определяет кратчайший путь, как если бы вся неизвестная область была свободной от препятствий.
Иными словами, бот начинает свой маршрут так, как если бы в неизвестной облости можно двигаться свободно.
Такой маршрут можно проложить с помощью А*.
Точка С есть первая серая точка такого маршрута.
Собственно, перерасчёт маршрута должно произойти во время поступления новой информации. Как минимум, при подходе к С часть области раскроется.

[Corwin]

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

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

Нужно найти все "особые точки".

Перебираем все препятствия-многоугольники.
Для каждого многоугольника перебираем все выпуклые углы (<180).
Для каждого выпуклого угла будет две особые точки (для угла 90 они сольются в одну).
Это такие точки, из которых можно двигаться по прямой так, что одна из вершин танка-квадрата будет касаться одной из сторон угла.
Например, для угла с вершиной (x0, y0) особыми точками будут точки вида (x0 +- a/2, y0 +- a/2), где a - размер танка.

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

Особые точки будут узлами нашего графа.
Так же узлами будет текущее положение и точка назначения.
Если от одной особой точки можно, двигаясь по прямой, добраться до другой особой точки, то значит эти узлы соединены ребром. Вес ребра - это длина соответствующего отрезка. (Длину лучше считать приближенно, не используя квадратный корень и даже умножение).

Нужно найти кратчайший путь на этом графе (например, используя алгоритм Дейкстры).

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

[B@R5uk]

Надо заметить, что все предложенные решения -- это математические решения задачи оптимального передвижения, а не построение AI.

[Corwin]

По АИ сложно что-то говорить, так как неизвестен даже набор возможных действий.

Я вижу тут два основных варианта:
1. Приоритетная модель
2. Полевая модель

1. Приоритетная модель

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

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


2. Полевая модель

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

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