В рамках написание своего квеста наткнулся на замечательную статью по игровой механике в адвенчурах, ее и предлагаю вашему вниманию.
Как написать адвенчуру
Эта статья расскажет вам о том, как происходит разработка адвенчур. Большинство изложенных идей абстрактны, но в местах, где представлен код или обсуждаются детали реализации, используется движок из моей книги “C# Game programming”. Весь код доступен онлайн, под лицензий MIT. Подходы, обсуждаемые в данной статье, широко применимы не только для адвенчур. К примеру, идея навигационных мешей, разработанная однажды, используется в таких играх, как Baulder's Gate, Planescape Torment и т.д. Лишь с небольшим изменением навигационные меши могут быть использованы и в 3D играх. Система взаимодействия с инвентарем и система диалогов могут быть модифицированы для большинства игр с элементами РПГ.
Что такое адвенчуры?
Адвченчуры были популярным жанром в начале девяностых и с недавних пор начали набирать популярность. Наиболее известный квест, вероятно, – серия “Остров обезьян”, где вы играете за честолюбивого пирата.
Пользовательский интерфейс адвенчур может меняться от игры к игре, но на картинке выше показывает интерфейс “Острова обезьян”. Игроку доступна игровая сцена, а персонаж находится где-то в пределах экрана. По-умолчанию, при клике по сцене, персонаж будет стремиться попасть в указанное место. При перемещении мыши по игровому экрану, вещи, с которыми можно контактировать, будут подсвечиваться. К примеру, на верхней картинке вы можете подвигать курсов вдоль замка на клетке темницы. Персонаж имеет несколько путей взаимодействия с предметами и в игре “Остров Обезьян” они перечислены на нижней половине экрана.
Выберите “Посмотреть на”, нажмите “Открыть” и Гайбраш шепотом скажет свое впечатление о замке (ни один из персонажей в игре не комментирует то, что Гайбраш разговаривает с предметами, что ж, я предполагаю, они думают, что он сумасшедший :D).
Следующее – это инвентарь, который показывает, какие предметы есть у персонажа в данный момент. Гайбраш может взаимодействовать с вещами в инвентаре, так же как и с предметами на игровой сцене.
Сейчас, надеюсь, вы получили базовое представлен о пользовательском интерфейсе и взаимодействии с игровым миром. Это действительно не очень сложно. Естественно, квесты определяются не только интерфейсами. В основном этот тип игр имеет сильный сюжет, в процессе которой игрок должен преодолевать различные проблемы и решать хитроумные головоломки. Большинство квестов позволяют игроку общаться с другими игровыми персонажами, используя систему диалогов. Эти персонажи так же известны как NPC (не игровые персонажи, non playing characters).
Как можно разбить адвенчуру на подсистемы?
Адвенчура является давно устоявшимся жанром, а это значит, что игру легко можно разбить на подсистемы, которые в дальнейшем будут запрограммированы.
Ядро системы состоит из серии уровней. Если один из уровней находится выше другого, то это означает, что нижний используется как подуровень системы. Это хорошее решение для создания изолированной и чистой архитектуры. Движок уже делает много за нас: загрузку и рисование спрайтов, рендеринг и анимацию объектов, текст может быть отрисован с выравниванием и различными шрифтами, – эти части для игры уже сделаны!
Наиболее сложная часть программы – система навигации и большая часть статьи будет посвящена ей.
Навигация
Навигационная система перемещает персонажа с текущего места на точку, по которой был сделан клик. Существует очень много путей реализации подобного механизма, но не существует единственно верного. В некоторых квестах используется вид от первого лица и поэтому смещение в сторону является проблемой (взгляните на ShadowGate и Myst).
В большинстве своем, квесты отображают персонажа на игровом пространстве и иногда важно, где герой находится, для решения определенного вида задач.
Навигация в играх в целом состоит из поиска пути. Если вы хотите поискать больше информации по этой теме, чем в этой статье, то это подходящее ключевое слово. Путь представляют собой линию, по которой игровой персонаж должен следовать для достижения желаемой позиции без прохождений сквозь стены, столы, маленьких собак и т.д. Путь ищется между точками текущего местоположения и позицией, где только что произошел клик. Лучше всего, если построенный путь является кратчайшим или наиболее точно приближается к кратчайшему – вы не захотите, чтобы игровой персонаж блуждал по всему экрану, когда вы просите его пройти пять метров влево.
Алгоритмы поиска пути строятся на графах, которые описывают пространство перемещения игрового персонажа. Граф – это термин их области теории алгоритмов (не переживайте, определение очень простое), который строится из набора вершин и связей между ними.
Выше приведенный граф показывает только путь между “Дороги из вне” в магазин через узел “Дверь магазина”. Это предотвращает сумасшедшее блуждание персонажа по всему экрану. Вы можете заметить несколько вещей в системе:
— Не кажется ли, что у персонажа слишком мало свободы, а что если он захочет остановится в середине магазина? Граф не позволит ему сделать это.
Это абсолютно верный вопрос и решить его мы сможем с помощью навигационной системы, которая ассоциирует зону допустимого движения с узлами графа.
Как же строится граф?
Мы сделаем его из навмеша, который мы рассмотрим чуть позже.
Поиск кратчайшего пути в графе
Наиболее общий алгоритм нахождения кратчайшего пути в графе это алгоритм A* (A звезда). Это метод производит поиск по графу в попытке найти кратчайший путь к выбранному узлу. Этот алгоритм широко используется в играх. Лучший ресурс по A* это страница A* Амита. По-сути, я думаю, он проделал отличную работу, объясняя этот метод, и я не собираюсь даже пытаться сделать лучше. Почитайте эту страницу! :D
Эта версия A* доступна на моем репозитории в google code. Конечно, очень базовая и простая, но она работает и находит кратчайшие пути. Вот ссылка на реализацию. (Программа вылетит, если путь между двумя вершинами не может быть найден – конечно, я устраню это в ближайшем будущем :D)
A* начитает работу со стартового узла и дальше проходит по всем его соседям, и вычисляет некоторое значение веса для ближайших вершин. Далее алгоритм применяется рекурсивно для всех соседей с наибольшим весом. Вес обычно определяется функцией, которая задает расстояние от узла до цели. Алгоритм останавливается, когда находит целевой узел или определяет, что пути не существует. Это лишь краткое изложение, для лучшего понимания зайдите на сайт Амита.
С A* за поясом мы можем находить кратчайшие пути на графе, но до сих пор мы его не построили.
Использование алгоритма навмеш
НавМеш, как вы уже могли предположить, это сокращение от термина навигационный меш (сетка) и, если по-простому, это всего лишь набор полигонов, которые описывают область, по которой персонаж может передвигаться. Этот меш будет изображен на фоне рисунка с использование специально разработанного инструмента.
На верхней картинке синие полигоны представляют собой пространство, по которому игрок может перемещаться. Розовые точки – это связи между полигонами, которые показывают в каком месте игрок может переходить с одного полигона на другой. Граф будет создан из тестовых розовый связующих точек и центров всех полигонов. Стартовая и конечные точки графа могут быть установлены где угодно внутри синего полигона.
Путь будем строить с позиции игрока, в точку клика мышки. Это значит, что заданная точка (x, y) навигационного меша должна уметь определять в каком полигоне она находится.
Polygon FindPolygonPointIsIn(Point point)
{
foreach(Polygon polygon in _polygons)
{
if ( polygon.IntersectsWith(p) )
{
return polygon;
}
}
return null;
}
Вышеуказанный код может выполнить трюк с нахождением полигона, но до сих пор остается вопрос о том, как проверить, находиться ли точка внутри полигона или вне его. В этом примере все полигоны в навигационном меше являются выпуклыми и это жестким образом задано на сетки, которая строится в редакторе. Выпуклые полигоны помогают делать тестовые пересечения проще и с созданными навмешами значительно проще работать.
Определение вогнутого многоугольника крайне простое. Если одна из вершин находится внутри полигона, то он является вогнутым. В Китае и Японии канжи используются для представления идеи – посмотрите на две следующих канжи;
Попытайтесь определить, какая из фигур выпуклая и какая вогнутая – круто, да?
Далее представлен листинг программы, определяющий, является ли полигон выпуклым. В данном случае полигон всего лишь класс (List _vertices) с набором точек.
bool IsConcave()
{
int positive = 0;
int negative = 0;
int length = _vertices.Count;
for (int i = 0; i < length; i++)
{
Point p0 = _vertices[i];
Point p1 = _vertices[(i + 1) % length];
Point p2 = _vertices[(i + 2) % length];
// Subtract to get vectors
Point v0 = new Point(p0.X - p1.X, p0.Y - p1.Y);
Point v1 = new Point(p1.X - p2.X, p1.Y - p2.Y);
float cross = (v0.X * v1.Y) - (v0.Y * v1.X);
if (cross < 0)
{
negative++;
}
else
{
positive++;
}
}
return (negative != 0 && positive != 0);
}
Следующая листинг нужен нам для проверки на пересечения.
///
/// Определяет, находится ли выбранная точка внутри полигона.
/// Взято с <a href="http://local.wasp.uwa.edu.au/%7Epbourke/geometry/insidepoly/">http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/</a>
///
///
X координата точки
///
Y координата точки
/// Находится ли точка в полигоне?
public bool Intersects(float x, float y)
{
bool intersects = false;
for (int i = 0, j = _vertices.Count - 1; i < _vertices.Count; j = i++)
{
if ((((_vertices[i].Y <= y) && (y < _vertices[j].Y)) ||
((_vertices[j].Y <= y) && (y < _vertices[i].Y))) &&
(x < (_vertices[j].X - _vertices[i].X) * (y - _vertices[i].Y) / (_vertices[j].Y - _vertices[i].Y) + _vertices[i].X))
intersects = !intersects;
}
return intersects;
}
На данный момент мы можем определить, находится ли точка внутри полигона и, как следствие, можем проверить, попадают ли клики мыши в зону, доступную для перемещения персонажа. В случае, если на пути достижение нет пересекающихся полигонов, то мы не сможем попасть в выбранную точку и клик будет проигнорирован.
Последний шаг на этапе — это взять начальные и конечные позиции персонажа, центры полигонов, соединить узловые точки и построить граф, на котором можно запустить алгоритм A*.
Результаом работы алгоритма будет список точек, вдоль которых сможет перемещаться персонаж. Ниже приведен псевдокод алгоритма передвижения персонажа по пути.
- Получить позицию персонажа -> pc_position
- Получить позицию текущей точки на пути->target
- Получить направление pc_position к target -> direction
- Добавить направление *walkspeed к pc_postion
- Проверить, находится ли PC рядом с текущим положением на пути
- Если верно, сдвинуть текущую точку по пути
- Если текущая точка на пути является конечной, то прекратить движение персонажа
Актуальный код я использую, в функции UpdatePath.
Анимация
Последний шаг – это отрендерить спрайт персонажа и провести анимацию в соответствии с направления движения. Реализованный код уже обеспечивает перемещение персонажа по направлению выбранного вектора, осталось лишь сопоставить это направление с прорисовкой анимации.
Это пример арта, который я нашел на kafkaskoffee.com (я удалил зеленый бордюр в используемой версии):
Итак, у нас есть три позиции в состоянии покоя и три варианта анимации. Движение в направлениии “влево”, “вправо”, “вверх” и “вниз” может быть реализовано программно, путем обычных трансформаций.
Для сопоставления вектора движения одной из этих анимаций я сделал следующие преобразования. Были введены четыре вектора для каждого из направлений: (-1, 0), (1, 0), (0, 1), (0, -1). Далее, я вычислял скалярное произведение и смотрел, какой из векторов направлений ближе к вектору движения, как результат, выбирал нужную анимацию.
private Direction VectorToDirection(Vector direction)
{
Vector up = new Vector(0, 1, 0);
Vector down = new Vector(0, -1, 0);
Vector left = new Vector(-1, 0, 0);
Vector right = new Vector(1, 0, 0);
double upDiff = Math.Acos(direction.DotProduct(up));
double downDiff = Math.Acos(direction.DotProduct(down));
double leftDiff = Math.Acos(direction.DotProduct(left));
double rightDiff = Math.Acos(direction.DotProduct(right));
double smallest = Math.Min(Math.Min(upDiff, downDiff), Math.Min(leftDiff, rightDiff));
// yes there's a precidence if they're the same value, it doesn't matter
if (smallest == upDiff)
{
return Direction.Up;
}
else if (smallest == downDiff)
{
return Direction.Down;
}
else if (smallest == leftDiff)
{
return Direction.Left;
}
else
{
return Direction.Right;
}
}
Я уверен, что можно найти лучший способ, но данный вариант гарантировано работает. Алгоритм заканчивает работу, когда персонаж достигает точки клика и в качестве последнего состояния будет выбран вариант спрайта на основе конечного направляющего вектора.
Соберем все вместе
Автор: Silf
