2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 AI для компьютерной игры
Сообщение01.02.2013, 03:00 


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

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение01.02.2013, 15:27 
Заслуженный участник


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

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение01.02.2013, 17:24 


30/03/12
130
Yuri Gendelman в сообщении #678814 писал(а):
Единственная книга на русском, которую я знаю, да и то переводная:
Алекс Дж. Шампандар. "Искусственный интеллект в компьютерных играх: как обучить виртуальные персонажи реагировать на внешние воздействия". Вильямс. 2007

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

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение01.02.2013, 19:10 


30/03/12
130
Боле конкретная задача- нужно добраться до определённой точки. Целевая точка задана координатами, в общем случае бот знает только часть карты:
Изображение
бот начинает путь в зелёной точке, ему нужно добраться до красной, по белому цвету можно перемещаться, по чёрному нельзя, а про серую пока ничего не известно. Как в такой ситуации действовать? Алгоритмы на графах напрямую не применить, а идти напрямик с обходом препятствий в ряде случаев глупо(можно угодить в тупик, который бот разведал ранее).

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение01.02.2013, 19:59 


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

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

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение01.02.2013, 20:05 


30/03/12
130
mustitz в сообщении #678918 писал(а):
Выбираем белую точку, ближайшую к красной. Если тупик, то тут мы сделать ничего не можем. И идем к ней.

Увы:
Изображение
так мы упрёмся в стену о которой заранее знаем.

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение01.02.2013, 20:43 
Заслуженный участник


15/05/05
3445
USA
Сайт: Искусственный интеллект в играх

mustitz в сообщении #678918 писал(а):
Попутно можно построить граф связности точек, например, с шагом 20 пикселей. Соответственно из каждой вершины у нас максимум 8 направлений + расстояние. Потом оптимизируем этот путь.
По-моему это хорошее предложение.

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение01.02.2013, 20:56 


30/03/12
130
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$ - путь между точками(его мы можем вычислить, т.к. он пролегает по видимой области). Мне непонятно как это сделать без просчёта всей карты.

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение02.02.2013, 14:07 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение02.02.2013, 15:41 


30/03/12
130
worm2 в сообщении #679161 писал(а):
Можно попробовать перейти на уровень выше. Почему бы не позволить ботам видеть всю карту целиком? Станет ли пользователю менее интересно играть от того, что боты поумнеют? По-моему, чаще интерес к игре пропадает от того, что боты слишком глупы.

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

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение04.02.2013, 15:46 


10/04/12
704
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$ считается для видимой карты. Если вычислений много, можно строить специальные индексы, как я описывал. Непонятно, что непонятно.

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение06.02.2013, 22:52 


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

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

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение11.04.2013, 16:13 


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

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение12.04.2013, 08:51 
Аватара пользователя


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

 Профиль  
                  
 
 Re: AI для компьютерной игры
Сообщение12.04.2013, 10:57 


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

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

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

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

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


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group