Поиск эффективной стратегии в играх жанров Tower Defence и R oguelike

1.

Поиск эффективной стратегии в
играх жанров Tower Defence и R
oguelike

2.

Tower defence
Игры жанра tower defence - - это стратегические
игры, в которых внимание сфокусировано на доб
ыче ресурсов и размещении юнитов.

3.

В простейший форме в tower defence игрок заним
ается покупкой и установкой башен, которые авто
матически атакуют врагов, называемых крипами
либо мобами.

4.

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

5.

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

6.

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

7.

Алгоритм А*
--находит кратчайший путь между двумя вершина
ми графа. Для этого на каждом шаге алгоритма в
ыбирается вершина с наименьшим значением нек
оторой функции f и поиск продолжается из нее.

8.

Функция f - - это сумма функций g и h. Где g предс
тавляет собой точную оценку длины кратчайшего
пути до данной вершины из стартовой, а h предст
авляет собой приближенную оценку длины кратча
йшего пути из данной вершины в конечную.

9.

В качестве функции h в данном случае выгодно бр
ать евклидово расстояние либо манхэттенское рас
стояние.

10.

Roguelike
-- ролевые приключенческие игры, основными ос
обенностями которых являются необратимая сме
рть персонажа и пошаговый геймплей.

11.

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

12.

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

13.

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

14.

Вместо дерева решений удобным и весьма эффек
тивным вариантом оказывается создание эксперт
ной системы.

15.

Экспертная система
-- это программная попытка сымитировать процес
с принятия решений специалиста-человека при по
мощи правил вида "если X - > то Y, в противном сл
учае - > Z".

16.

Rog-o-Matic
Первой и очень успешной попыткой создать эксп
ертную систему для игры в rogue является програ
мма Rog-o-Matic.

17.

Так как в rogue отсутствует графика и вся информа
ция о состоянии игры передаётся при помощи си
мволов ASCII, то Rog-o-Matic может считывать эту
информацию с экрана точно так же, как и игрок-ч
еловек.

18.

Некоторые правила Rog-o-Matic
Система разделена на "экспертов" по различным
игровым ситуациям. Таким как бегство от опаснос
тей, выбор подходящей экипировки, сражения с
врагами, разведка карты и т.д.

19.

Пусть на определенных уровнях L1, L2,...Ln игры эк
ипировка из материалов X1, X2,... Xm подвергаетс
я разрушению. Пусть каждой экипировке присвое
но некоторое значение ценности W1, W2,.. Wk.

20.

Тогда можно вывести следующее правило:
если персонаж находится на некотором уровне, н
е входящем в множество L, то надеть первую по ц
енности экипировку;
в противном же случае если материал первой по с
тоимости экипировки принадлежит множеству X,
то попытаться по такому же правилу. надеть следу
ющую экипировку.

21.

Пусть существует некоторая функция F со множест
вом значений [0;1], которая возвращает вероятно
сть победы в текущем сражении.

22.

Тогда можно составить следующее правило:
Если F меньше некоторого значения eps и в графе
карты игрового окружения существует цикл или су
ществует путь на уровень выше, то войти в режим
бегства;

23.

в противном случае, если в инвентаре имеется ср
едство пространственного перемещения, то испо
льзовать это средство;
в противном случае продолжать сражение.