Как написать адвенчуру?

http://www.godpatterns.com/2010/08/how-to-make-adventure-game.html
  • Перевод
В рамках написание своего квеста наткнулся на замечательную статью по игровой механике в адвенчурах, ее и предлагаю вашему вниманию.

Как написать адвенчуру


image
Эта статья расскажет вам о том, как происходит разработка адвенчур. Большинство изложенных идей абстрактны, но в местах, где представлен код или обсуждаются детали реализации, используется движок из моей книги “C# Game programming”. Весь код доступен онлайн, под лицензий MIT. Подходы, обсуждаемые в данной статье, широко применимы не только для адвенчур. К примеру, идея навигационных мешей, разработанная однажды, используется в таких играх, как Baulder's Gate, Planescape Torment и т.д. Лишь с небольшим изменением навигационные меши могут быть использованы и в 3D играх. Система взаимодействия с инвентарем и система диалогов могут быть модифицированы для большинства игр с элементами РПГ.

Что такое адвенчуры?


Адвченчуры были популярным жанром в начале девяностых и с недавних пор начали набирать популярность. Наиболее известный квест, вероятно, – серия “Остров обезьян”, где вы играете за честолюбивого пирата.
image
Пользовательский интерфейс адвенчур может меняться от игры к игре, но на картинке выше показывает интерфейс “Острова обезьян”. Игроку доступна игровая сцена, а персонаж находится где-то в пределах экрана. По-умолчанию, при клике по сцене, персонаж будет стремиться попасть в указанное место. При перемещении мыши по игровому экрану, вещи, с которыми можно контактировать, будут подсвечиваться. К примеру, на верхней картинке вы можете подвигать курсов вдоль замка на клетке темницы. Персонаж имеет несколько путей взаимодействия с предметами и в игре “Остров Обезьян” они перечислены на нижней половине экрана.

Выберите “Посмотреть на”, нажмите “Открыть” и Гайбраш шепотом скажет свое впечатление о замке (ни один из персонажей в игре не комментирует то, что Гайбраш разговаривает с предметами, что ж, я предполагаю, они думают, что он сумасшедший :D).

Следующее – это инвентарь, который показывает, какие предметы есть у персонажа в данный момент. Гайбраш может взаимодействовать с вещами в инвентаре, так же как и с предметами на игровой сцене.

Сейчас, надеюсь, вы получили базовое представлен о пользовательском интерфейсе и взаимодействии с игровым миром. Это действительно не очень сложно. Естественно, квесты определяются не только интерфейсами. В основном этот тип игр имеет сильный сюжет, в процессе которой игрок должен преодолевать различные проблемы и решать хитроумные головоломки. Большинство квестов позволяют игроку общаться с другими игровыми персонажами, используя систему диалогов. Эти персонажи так же известны как NPC (не игровые персонажи, non playing characters).

Как можно разбить адвенчуру на подсистемы?


Адвенчура является давно устоявшимся жанром, а это значит, что игру легко можно разбить на подсистемы, которые в дальнейшем будут запрограммированы.
image
Ядро системы состоит из серии уровней. Если один из уровней находится выше другого, то это означает, что нижний используется как подуровень системы. Это хорошее решение для создания изолированной и чистой архитектуры. Движок уже делает много за нас: загрузку и рисование спрайтов, рендеринг и анимацию объектов, текст может быть отрисован с выравниванием и различными шрифтами, – эти части для игры уже сделаны!

Наиболее сложная часть программы – система навигации и большая часть статьи будет посвящена ей.

Навигация


Навигационная система перемещает персонажа с текущего места на точку, по которой был сделан клик. Существует очень много путей реализации подобного механизма, но не существует единственно верного. В некоторых квестах используется вид от первого лица и поэтому смещение в сторону является проблемой (взгляните на ShadowGate и Myst).
image
В большинстве своем, квесты отображают персонажа на игровом пространстве и иногда важно, где герой находится, для решения определенного вида задач.
image
Навигация в играх в целом состоит из поиска пути. Если вы хотите поискать больше информации по этой теме, чем в этой статье, то это подходящее ключевое слово. Путь представляют собой линию, по которой игровой персонаж должен следовать для достижения желаемой позиции без прохождений сквозь стены, столы, маленьких собак и т.д. Путь ищется между точками текущего местоположения и позицией, где только что произошел клик. Лучше всего, если построенный путь является кратчайшим или наиболее точно приближается к кратчайшему – вы не захотите, чтобы игровой персонаж блуждал по всему экрану, когда вы просите его пройти пять метров влево.

Алгоритмы поиска пути строятся на графах, которые описывают пространство перемещения игрового персонажа. Граф – это термин их области теории алгоритмов (не переживайте, определение очень простое), который строится из набора вершин и связей между ними.
image
Выше приведенный граф показывает только путь между “Дороги из вне” в магазин через узел “Дверь магазина”. Это предотвращает сумасшедшее блуждание персонажа по всему экрану. Вы можете заметить несколько вещей в системе:
— Не кажется ли, что у персонажа слишком мало свободы, а что если он захочет остановится в середине магазина? Граф не позволит ему сделать это.

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

Как же строится граф?

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

Поиск кратчайшего пути в графе
Наиболее общий алгоритм нахождения кратчайшего пути в графе это алгоритм A* (A звезда). Это метод производит поиск по графу в попытке найти кратчайший путь к выбранному узлу. Этот алгоритм широко используется в играх. Лучший ресурс по A* это страница A* Амита. По-сути, я думаю, он проделал отличную работу, объясняя этот метод, и я не собираюсь даже пытаться сделать лучше. Почитайте эту страницу! :D
image
Эта версия A* доступна на моем репозитории в google code. Конечно, очень базовая и простая, но она работает и находит кратчайшие пути. Вот ссылка на реализацию. (Программа вылетит, если путь между двумя вершинами не может быть найден – конечно, я устраню это в ближайшем будущем :D)

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

С A* за поясом мы можем находить кратчайшие пути на графе, но до сих пор мы его не построили.

Использование алгоритма навмеш


НавМеш, как вы уже могли предположить, это сокращение от термина навигационный меш (сетка) и, если по-простому, это всего лишь набор полигонов, которые описывают область, по которой персонаж может передвигаться. Этот меш будет изображен на фоне рисунка с использование специально разработанного инструмента.
image
На верхней картинке синие полигоны представляют собой пространство, по которому игрок может перемещаться. Розовые точки – это связи между полигонами, которые показывают в каком месте игрок может переходить с одного полигона на другой. Граф будет создан из тестовых розовый связующих точек и центров всех полигонов. Стартовая и конечные точки графа могут быть установлены где угодно внутри синего полигона.

Путь будем строить с позиции игрока, в точку клика мышки. Это значит, что заданная точка (x, y) навигационного меша должна уметь определять в каком полигоне она находится.
Polygon FindPolygonPointIsIn(Point point)
{
    foreach(Polygon polygon in _polygons)
    {
        if ( polygon.IntersectsWith(p) )
        {
            return polygon; 
        }
    }
    return null;
}


Вышеуказанный код может выполнить трюк с нахождением полигона, но до сих пор остается вопрос о том, как проверить, находиться ли точка внутри полигона или вне его. В этом примере все полигоны в навигационном меше являются выпуклыми и это жестким образом задано на сетки, которая строится в редакторе. Выпуклые полигоны помогают делать тестовые пересечения проще и с созданными навмешами значительно проще работать.
image
Определение вогнутого многоугольника крайне простое. Если одна из вершин находится внутри полигона, то он является вогнутым. В Китае и Японии канжи используются для представления идеи – посмотрите на две следующих канжи;
Попытайтесь определить, какая из фигур выпуклая и какая вогнутая – круто, да?
image
Далее представлен листинг программы, определяющий, является ли полигон выпуклым. В данном случае полигон всего лишь класс (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*.
image
Результаом работы алгоритма будет список точек, вдоль которых сможет перемещаться персонаж. Ниже приведен псевдокод алгоритма передвижения персонажа по пути.

  1. Получить позицию персонажа -> pc_position
  2. Получить позицию текущей точки на пути->target
  3. Получить направление pc_position к target -> direction
  4. Добавить направление *walkspeed к pc_postion
  5. Проверить, находится ли PC рядом с текущим положением на пути
  6. Если верно, сдвинуть текущую точку по пути
  7. Если текущая точка на пути является конечной, то прекратить движение персонажа


Актуальный код я использую, в функции UpdatePath.

Анимация


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

Это пример арта, который я нашел на kafkaskoffee.com (я удалил зеленый бордюр в используемой версии):
image
image
image
image
Итак, у нас есть три позиции в состоянии покоя и три варианта анимации. Движение в направлениии “влево”, “вправо”, “вверх” и “вниз” может быть реализовано программно, путем обычных трансформаций.

Для сопоставления вектора движения одной из этих анимаций я сделал следующие преобразования. Были введены четыре вектора для каждого из направлений: (-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;
    }
}


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

Соберем все вместе




P.S автор одобрил перевод и сказал, что фигуры действительно обе вогнутые, но перевод одной из канжи — это выпуклая, второй вогнутая
image

Luxoft

120,85

Bright minds! Sharp Solutions!

Поделиться публикацией

Похожие публикации

Комментарии 23
    +2
    Спасибо, было инетерсно прочитать, особенно со знакомыми с детства картинками :)

      +9
      Название обманчиво — код для подобного класса игр занимает от силы 10% (а в статье рассмотрен только граф навигации для point&click версии), остальное — это арт и его нудная подгонка-набор с настройкой механики взаимодействия со всем этим игрока :)
        +1
        Не всегда верно, движки для многих классических игр (Syberia, RunAway и т.д.) разрабатывались с нуля, а это уже приличный пласт работы. А игры, сделанные, с применением существующих бесплатных движков (к примеру, www.adventuremaker.com/), обычно большой популярности не набирают. К сожалению, не имею информации о платных решениях.
          +2
          То, что их писали с нуля, не меняет цифр. Для Сибири, пожалуй, влияние арта даже больше — кода в подобных штуках реально мало и он унифицирован для навешивания на объекты по разным сценам. Основная проблема — сборка игровых сцен (расстановка объектов, задников, навешивание логики поведения из репозитория логических блоков) и настройка графа взаимодействия (тот же граф сюжета, блокировки веток развития в зависимости от поведения, инвентаря и т.п.).
          З.Ы. Вот еще неплохой движок: dead-code.org/
      +3
      А мне одному кажется, что на самом деле оба канжи–иероглифа вогнутые?
        +7
        Мне тоже так кажется.

        Если я правильно помню, то выпуклая фигура — та, у которой каждое ребро делит плоскость на две полуплоскоти так, что фигура целиком остается в одной из них.
          0
          Думаю, вы правы. Уточню у автора, что он имел ввиду, возможно перевод не до конца корректен, спасибо за замечание.
            0
            Боюсь показаться вульгарным, но я тут вижу намек на гениталии. А в геометрическом смысле обе фигуры невыпуклые.
        +2
        Плюсанул статью как только наткнулся на скрин из Monkey Island.

        You fight like a dairy farmer!
          +2
          Day of the Tentacle, на мой взгляд, тоже очень ничего =)
            –5
            Интересно, я один подумал про хентай? %)
              0
              Видимо, да
                +3
                На самом деле нет. Щас все дети, которые не видели 486x, не знают великого Фиолетового и не знают, как можно телепортироваться, перешивать флаг америки и прятать зубы за решетку. В том числе они не понимают, что руки, выросшие благодаря радиоактивным отходам, могут помочь в завоевании мира. Особенно если ты — щупальце.
            0
            Я просто оставлю это здесь: www.adventuregamestudio.co.uk/
              0
              Ну раз гулять, так гулять, добавлю еше http://alpacaengine.com/, отличная вещь для прототипирования
              0
              Какую нафиг «адвенчуру»? Загляните в англо-русский словарь, что ли.
                0
                При прочтении заголовка, лично меня, вывернуло. Вверните обратно хотя бы… :)
                  0
                  я отдаю себе отчет, что adventure, переводится, как приключение, но, как и квест (quest), это уже устоявшиеся понятия, поэтому нет дословного перевода
                    +1
                    Вообще-то мне, как спектрумисту, странно, что адвенчурой называют игры, которые, скорее, правильней было бы назвать квестами (характерные черты: вид от 3его лица, чаще 2D, перемещение между экранами и т.д.). Наиболее яркий представитель — Dizzy.
                    А адвенчурами я называю игры, которые управляются командами (the Gremlins) или списком команд (Star Inheritance). Наиболее близкий жанр — т.н. Interactive Fiction, но зачастую игры этого жанра упрощены (например, отсутствует инвентарь).
                      0
                      Я, кстати, тоже именно про IF подумал по заголовку, особенно в связи с «написать». Adventure — исторически первая игра этого жанра, отсюда и ассоциация.

                      На мой опыт, IF обеспечивает самую неиллюзорную глубину погружения, которую не испытаешь ни в одном квесте с более «традиционным» интерфейсом.
                    0
                    Товарищи из Sierra Online (вернее, того, к кому перешли ее авторские права) уже выехали за Вами, ибо Space Quest, King's Quest, Police Quest, Quest For Glory – зарегистрированные торговые марки сиерры, и называть адвенчуры квестами – исключительно ее прерогатива. Именно поэтому ни одна адвенчура от Lucas Arts не называется квестом. ru.wikipedia.org/wiki/Квест#Происхождение_названия
                  +1
                  А почему нужно всё изобретать с нуля, а не использовать SCUMMVM?
                    +1
                    Или вообще Z-Machine.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое