Вам нужно сыграть в Morrowind.

(Предупреждение: ниже идут несколько абзацев похвал Морровинду, так что вы можете спокойно пропустить их и переходить к самой сути поста.)

В начале Morrowind вы обычный обалдуй, только что сошедший с тюремного корабля с 87 золотыми в кармане (в этом мире одна буханка хлеба стоит 1 золотой, то есть это примерно 35 фунтов — именно столько вам придётся заплатить за 87 упаковок нарезанного белого хлеба в Tesco). Вашим первым заданием будет получение посылки от человека в другом городе, и вы можете или проехаться на силт страйдере (огромном насекомом с длинными ногами, которым, вероятно, управляет вечно пьяный жуткий водитель — почти как в лондонских автобусах) или прогуляться туда пешком по дикой местности, сражаясь с ордами хищных птиц-переростков железным кинжалом, который вы стянули из бюро переписей. Только ваш кинжал всегда промахивается, потому что, видите ли, создатели боевой системы Morrowind вдохновлялись настольными ролевыми играми, а аниматорам платили не так много, поэтому даже если ваше оружие очевидно вонзается в мясистое тело того, в кого вы, игрок, целитесь, нет никаких гарантий, что вы на самом деле попали.

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

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

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

Всё как в реальной жизни.

(Здесь похвалы игре заканчиваются.)

Недавно я решил заново сыграть в Morrowind и посередине процесса зарабатывания высокого ранга мне немного надоели постоянные квесты «принеси предмет», которые приходится выполнять, чтобы получить повышение в некоторых гильдиях. Поэтому я задумался о создании планировщика маршрутов. Это нетривиальная задача, потому что количество вариантов действий в Morrowind очень велико:

• Ходьба (или левитация, потому что уважающий себя игрок уже зачаровал какой-нибудь предмет постоянным эффектом левитации)
• Поездка на силт-страйдере (или лодке) — но стоит учесть, что вы не можете мгновенно попасть в нужный город и вам придётся менять транспорт в одной из плохих частей города. На это тратится внутриигровое время, но мы будем считать, что перемещение происходит мгновенно, как это и воспринимается игроком.
• Телепорт Гильдии магов — тоже мгновенный. Вам нужно поговорить с магами, но на самом деле они хорошие ребята.
• Divine/Almsivi Intervention — здесь всё становится интереснее. Divine Intervention (Божественное вмешательство) телепортирует нам к ближайшему Имперскому форту (Морровинд является частью Империи, хотя всё ещё и не смирился с этой мыслью), а Almsivi Intervention (вмешательство Альмсиви) телепортирует нас к ближайшему Храму Трибунала (который является официальной религией Морровинда и существовал задолго до Империи).
• Mark/Recall — два заклинания, одно размещает метку, а второе телепортирует вас к этой метке.
• Пропильоны (Propylon Indices) — давным давно кто-то решил построить на острове в круг кучу красивых крепостей. Хорошие новости: существует комната телепортации, соединяющая их все по кругу. Плохие новости: вам потребуется метка пропильона для каждой из этих крепостей, а их часто сложно найти. Кроме того, эти крепости переполнены кучей разных тварей, и обычно рядом с ними находиться не очень приятно. Пока я исключу их из своего анализа.

В связи с появлением акул на Кольцевой линии ожидаются незначительные задержки движения.

Вы можете понять, какие интересные способы перемещения могут возникать при сочетании этих средств. Например, вы можете скастовать Almsivi Intervention, чтобы телепортироваться к ближайшему Храму, а затем Divine Intervention для телепортации в Имперский форт, а затем воспользоваться телепортом Гильдии и сразу же скастовать ещё одно Almsivi для попадания ещё в один город.

Но разумеется, было бы скучно, если бы я просто потратил некоторое время на чтение этих карт перемещений Morrowind, создание графа и выполнение для него алгоритма Дейкстры. Во-первых, не получился бы такой хороший пост. Во-вторых, это не помогло бы нам, если мы оказались бы где-то в пустоши (видите эту область в середине, окружённого Falasmaryon, Valenvaryon, Rotheran, Indoranyon, Falensarano, Ald'Ruhn и Maar Gan? Да, ходить туда не стоит).

Наконец, существует несколько довольно больших фанатских дополнений к Morrowind, в том числе Tamriel Rebuilt, потому что я вам солгал, и на самом деле этот остров называется не Морровинд, а Вварденфелл, а Морровинд — это провинция, частью которого является Вварденфелл. Авторы Tamriel Rebuilt попытались воссоздать всю эту провинцию (да, весь Морровинд не вошёл в игру с названием Morrowind. Более того, Тамриэль — это вся Империя, частью которой является Морровинд, и да, Tamriel Rebuilt просто пытается воссоздать Морровинд. В игре под названием Morrowind).

Всё это я сказал для того, чтобы убедить вас, что хорошей идеей будет найти систематический способ выдирания этих данных из файлов игры, чтобы упростить нашу жизнь. Представьте, что мы можем узнать, если сделаем это! Демографию! Тепловые карты населения! Графы! Мы даже можем составить графики цен и времени перемещения!

В следующей части проекта «Морровинд» мы сразимся с запутанными двоичными форматами, странными допущениями, линейной алгеброй, языком Python и, возможно, узнаем больше о лоре Morrowind и его игровой механике.

Часть 2

Далее в проекте «Морровинд» мы начнём превращать ужасные двоичные файлы в прекрасные структуры данных в пространстве памяти интерпретатора Python. Технически они всё равно остаются двоичными данными, но давайте не будем углубляться так сильно. В противном случае мы осознаем, что все состоим из атомов и нас накроет экзистенциальный кризис, а в этом нет ничего хорошего.


Я… я даже не вижу кода. Я вижу только дерево, камень, болотный тростник...

Дамп данных

В играх серии Elder Scrolls, созданных Bethesda Softworks, в том числе в Morrowind и её последователях (Oblivion, Skyrim, кроме того, в них включают Fallout 3 и 4) базовые данные игры (то есть карты и локации разных объектов, но не текстуры/звуки/модели) хранятся в формате ESM (Elder Scrolls Master). Со времён Morrowind он эволюционировал, разработчики Bethesda добавляли в него всё больше и больше возможностей, но основная идея остаётся той же: эти файлы являются коллекцией записей различных типов.

Например у нас может быть запись NPC_, определяющая персонажа игры, в которой будут содержаться определения пола, расы, поведения ИИ персонажа и т.д. Также она может содержать ссылки на другие записи, например, на инвентарь персонажа, который ссылается на записи ARMO и WEAP. Записи CELL описывают внутриигровые ячейки (сами локации) и содержат ссылки на всё, что содержится в этой ячейке, например NPC_, ARMO, WEAP или CONT (контейнеры, например сундуки). Двоичный формат Morrowind очень хорошо описан здесь и каждый новый релиз игр Bethesda обещает игрокам множество интересных задач по реверс-инжинирингу небольших изменений в формате файлов игровых данных.

Bethesda придумала умную идею — сделать файлы сохранений игры наложением на файлы игровых данных в этом формате. Например, если вы убьёте кого-то в определённой локации (что довольно часто случается в играх серии Elder Scrolls), то в вашем файле сохранёнки будет содержаться переопределение записи CELL, в которой указан соответствующий убитый NPC. К сожалению, эта идея никак не отразилась на моём проекте, как и множество других умных идей, но тем не менее она интересна.

Однако есть и другие трудности: ячейки могут быть внешними или внутренними. Внешние ячейки имеют квадратную форму и соединены друг с другом ребро к ребру, создавая потрясающие просторы Морровинда. С внутренними ячейками другая история — каждая из них находится в собственной маленькой реальности и соединяется с другими ячейками дверьми, которые по сути используются здесь в качестве телепортов. Небольшой домик во внешней ячейке часто намного больше изнутри, поэтому мы не можем надёжно судить о том, где находится игрок, когда входит внутрь.

Поэтому если мы хотим воссоздать граф способов перемещений по Морровинду, то нам нужно рассматривать как ещё один способ перемещения двери.

Что касается заклинаний Almsivi/Divine Intervention, то в каждом Храме и Имперском форте есть специальный объект-маркер — с помощью него игра определяет, куда телепортировать игрока, кастующего определённое заклинание. Это тоже просто для внешних ячеек (потому что маркеры находятся внутри помещений), но усложняется в случае внутренних. Некоторые люди утверждают, что Morrowind использует последнюю внешнюю ячейку, в которой был игрок (что иногда приводит к патологическим случаям — допустим, мы используем телепорт Гильдии, телепортирующий нас из одного помещения в другое; тогда при касте заклинания Intervention нас переместит к маркеру, близкому к первой Гильдии, а не второй) и реализация движка Morrowind с открытым исходным кодом OpenMW пытается решить эту проблему, используя в качестве ссылки ближайшую к игроку ячейку. По каким-то причинам моя копия Morrowind ведёт себя правильно, поэтому я симулирую такое поведение.

Гораздо лучше то, что если NPC предлагает транспортные услуги (силт страйдер, лодка или телепорт Гильдии), то это будет закодировано в его записи.

В общем, похоже, нам нужно вытащить всё из записей CELL и NPC_, потому что в них содержится всё необходимое нам.

Вытягивание всего из записей CELL и NPC_

Хотя я и думал, что будет вполне возможно и интересно декодировать двоичные данные в соответствии с этой замечательной спецификацией, я решил сжульничать и воспользовался Morrowind Enchanted Editor — низкоуровневым редактором файлов ESM. В частности, я использовал функцию «Dump to Text File», которая превращает нечитаемый двоичный хаос в читаемый хаос ASCII.


Встречайте персонажа Todd's Super Tester Guy, предположительно созданного самим Тоддом Говардом.

С этим уже можно поработать: каждый элемент в записи находится на отдельной строке и имеет ключ в виде подзаписи (например, FNAM — полное имя, RNAM — название расы и т.д.). Для начала мы можем извлечь только записи NPC_ и CELL, а затем превратить данные в токены, преобразовав их в поток пар ключ-значение (то есть строка NPC_ NAME todd превратится в кортеж (NAME, todd), потому что мы уже знаем, что он относится к записи NPC_).

(Здесь я собирался показать и блок за блоком объяснить исходный код, но сегодня WordPress оказался настроен против меня. Обещаю, что потом опубликую его на GitHub. Ну серьёзно, кому пришло в голову преобразовывать > to > после цикла сохранения, а затем обратно в &gt?)

В результате мы получим нечто подобное:

In [6]: cells[:10]
Out[6]:
[('NAME', ''),
('DATA', '\x02\x00'),
('DATA', '23'),
('DATA', '7'),
('RGNN', "Azura's Coast Region"),
('NAME', ''),
('DATA', '\x02\x00'),
('DATA', '23'),
('DATA', '6'),
('RGNN', "Azura's Coast Region")]

npcs[:10]
Out[7]:
[('NAME', 'player'),
('FNAM', 'player'),
('RNAM', 'Dark Elf'),
('CNAM', 'Acrobat'),
('ANAM', ''),
('BNAM', 'b_n_dark elf_m_head_01'),
('KNAM', 'b_n_dark elf_m_hair_01'),
('NPDT', '1'),
('NPDT', ''),
('NPDT', '')]

Парсинг потока записей NPC_ в список NPC — не такая сложная задача. Я выяснил, что простейший способ — передать поток в конструктор класса и позволить ему считать оттуда всё необходимое для своей инициализации. Но не забывайте, что нам нужно остановить парсинг, когда мы увидим подзапись NAME следующего NPC, и если мы уже использовали его, то уже слишком поздно, поэтому нам нужно определить итератор, позволяющий смотреть на следующий элемент, не используя его.

Парсинг списка локаций, искомого нами Священного Грааля, тоже очень прост — всего лишь посмотрите на этот пример (это одно из мест, в которое нас может доставить Todd's Super Tester Guy):

NPC_    DODT    1822.641
NPC_    DODT    -231.5323
NPC_    DODT    -292.9501
NPC_    DODT    0
NPC_    DODT    0
NPC_    DODT    0.5
NPC_    DNAM    ToddTest

Мы в буквальном смысле получаем список из 6 чисел: координат x, y, z и угла (который нам не важен). Иногда, если мы находимся во внутренней ячейке, присутствует подзапись DNAM.

Добавим метод repr и мы сможем увидеть список NPC!

npcs[:10]
Out[15]:
[NPC (player, player, Dark Elf, Acrobat),
 NPC (todd, Todd's Super Tester Guy, Dark Elf, Guard),
 NPC (Imperial Guard, Guard, Imperial, Guard),
 NPC (agronian guy, Tarhiel, Wood Elf, Enchanter),
 NPC (murberius harmevus, Murberius Harmevus, Imperial, Warrior),
 NPC (madres navur, Madres Navur, Dark Elf, Acrobat),
 NPC (farusea salas, Farusea Salas, Dark Elf, Commoner),
 NPC (erval, Erval, Wood Elf, Commoner),
 NPC (Dralas Gilu, Dralas Gilu, Dark Elf, Rogue),
 NPC (uulernil, Uulernil, High Elf, Smith)]

npcs[1].inventory
Out[16]: 
[('steel battle axe', 1),
 ('glass war axe', 1),
 ('steel mace', 1),
 ('chitin guantlet - right', 1),
 ('chitin guantlet - left', 1),
 ('chitin boots', 1),
 ('chitin greaves', 1),
 ('chitin pauldron - right', 1),
 ('chitin pauldron - left', 1),
 ('chitin cuirass', 1)]

(Интересно, что здесь есть три проблемы с «аргонианским парнем» (agronian guy) по имени Tarhiel. Во-первых, название его расы правильно пишется Argonian. Во-вторых, он не аргонианец, а лесной эльф (Wood Elf). И наконец, у него есть психические проблемы, но также и способности.

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

Часть 3

Сегодня в проекте «Морровинд» мы возьмём десятилетия изучения процесса визуализации описаний 3D-сцен в прекрасные фотореалистичные миры, и выбросим их в мусорку.


Я наконец отказался от попыток нетривиального форматирования в WordPress. Надеюсь, он не испортит текст хотя бы на картинках.

Загрузка данных ячеек

При парсинге ячеек Morrowind существует несколько сложностей. Первая — как нам дать ячейкам уникальные имена. Это легко сделать в случае внутренних ячеек, потому что у них есть поле NAME, например, «Мастерская Дядюшки Сладкая Доля» (и это не шутка). Однако внешние ячейки могут быть примерно трёх разных типов. Первый — это города и примечательные ориентиры, наподобие показанных на картинке. У них есть RGNN, NAME и координаты расположения огромной внешней квадратной ячейки. Однако существует множество ячеек Вивека (потому что Вивек огромный), поэтому мы для их идентификации будем использовать и координаты области.

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

Наконец, существуют внешние ячейки без имени ячейки и области, но с координатами — в TES Construction Set они называются Wilderness [x, y], поэтому мы будем использовать такое же название.


Каждая из этих областей сама по себе является городом, и все они соединены мостами. Кроме того, они находятся на воде. Кто бы не хотел здесь жить?

Следующим этапом будет парсинг содержимого каждой ячейки, которое по сути является ID объекта и другими данными о текущем экземпляре ссылки (например, позиция, количество здоровья (для NPC) или возможные точки назначения (для дверей или NPC, предлагающих транспортные услуги)).

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

Стоит также упомянуть, что определения объектов могут появляться до или после того, как на них ссылаются, поэтому мы должны парсить файл в два прохода — сначала записывая только ID ссылок в виде строк, а затем привязывая их к объектам Python.

Фух, работа завершена!

In [1]: mages
Out[1]: Vivec, Guild of Mages

In [2]: mages.is_interior
Out[2]: True

In [3]: mages.destinations
Out[3]: [(Vivec, Foreign Quarter Plaza, (-826.792800, 357.833600, 309.695400))]

Я не добавлял в список точек назначения ячеек локации, в которые могут перенести игрока NPC из ячейки (например, в случае услуг телепортации) — в нём перечислены только места, в которые ведут двери в ячейке.


Полная версия находится тут, но аккуратно — она весит примерно в 10МБ.

Даже используя только эту информацию мы можем создать красивые графы. Например, я создал показанную выше картинку в GraphViz, в ней узлы являются ячейками и они соединяются рёбрами тогда, когда между ними есть дверь. Большая группа посередине — это Вивек. По картинке разбросаны группы поменьше, это не такие большие города (наподобие Балморы, Калдеры или Альд'Руна). Здесь также присутствуют звездоподобные формации — центром является ячейка с именем, а соединённые с ней ячейки будут внутренними, в которые можно проникнуть через неё — это более мелкие поселения.

Но мы стремились не к этому. Мы хотим знать, как добраться из точки A в точку B с помощью всего, что нам может предложить мир, а не только дверей. Давайте поговорим о том, как мы опишем настоящий граф перемещений.

Создание планировщика маршрутов

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

• Для каждого объекта, предлагающего «услуги» перемещения (NPC/двери) — местоположение объекта и точку перемещения.
• Расположение каждого маркера Divine/Almsivi Intervention.

Вот и всё. Описание нашего маршрута будет тогда примерно таким «Из начальной точки подойти к этой двери (точка 1), пройти через неё в другую ячейку (точка 2), подойти к NPC, предлагающему транспортные услуги (точка 3), переместиться в другой город (точка 4), подойти к точке назначения (точка 5)». Поэтому давайте посмотрим, как можно соединить узлы графа.

• Местоположение предлагающего «услуги» перемещения (дверь, телепорт/NPC-водитель силт страйдера) соединяется с точкой назначения ребром с длиной 0.
• Если два узла находятся в одной ячейке (или оба находятся во внешнем мире), то они соединяются ребром, длина которого пропорциональна расстоянию между ними (то есть мы игнорируем, например, горы во внешнем мире и непроходимые препятствие во внутренних ячейках).
• Каждый узел соединяется с ближайшим Храмом/Имперским фортом (с помощью прямого эвклидового расстояния в случае внешних ячеек или расстояния от ближайшей внешней ячейки в случае внутренних ячеек).

Пользуясь таким способом, я пришёл к графу перемещений, состоящему из 6424 вершин и 16065 рёбер только телепортации — в них включены двери/транспортные услуги/заклинания Intervention, но не прямые перемещения внутри ячеек, потому что в этом случае очень легко найти расстояние между любыми двумя точками на лету.

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

С такими вещами достаточно хорошо справляется алгоритм Дейкстры, находя кратчайшие пути из одной точки к всем точкам в O(|V|?) (где |V| — число узлов в графе). Его можно усовершествовать с помощью фибоначчиевой кучи для хранения неисследованных вершин и получения ближайших за O(1), что даёт нам временную сложность O(|E| + |V|log|V|). Я решил, что поиск по всего 6000 вершинам не займёт слишком много времени, поэтому не реализовал её, но возможно, сделаю это позже.

В качестве подопытной крысы в этом эксперименте я использовал Ариона — он становится основным квестодателем на поздних этапах квестовой линии Дома Телванни и живёт в довольно отдалённой башне в глухомани с почти полным отсутствием транспортных услуг. Поэтому хотя для попадания к нему можно использовать Mark/Recall, его квесты могут отправлять вас в разные точки игрового мира, попадание в которые быстро становится нетривиальной задачей.

Скормив этот граф алгоритму Дейкстры (что заняло примерно 10 минут, а это довольно долго), я получил два списка: в первом для каждой точки указывается вес самого дешёвого (в нашем случае быстрого) маршрута от Ариона до этой точки. Во втором для каждой точки указывается предыдущая точка на самом быстром маршруте. Благодаря этому мы можем быстро воссоздать оптимальный маршрут, следуя по этим ссылкам к интересующей нас точке.

Например, как нам добраться от Ариона до данмерской крепости Хлормарен на другом краю острова? Вот так:

target
Out[35]: (Hlormaren, Dome, (384.000000, -408.000000, 384.000000))
route = chain_prev(prev, target)
route
Out[37]: 
[(Tel Vos, Aryon's Chambers, (3905.517000, 2935.360000, 15752.000000)),
 (Wolverine Hall, [18,3], (148881.700000, 28453.790000, 1495.193000)),
 (Wolverine Hall, [18,3], (148880.000000, 28360.000000, 1464.000000)),
 (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-64.000000, -96.000000, 0.000000)),
 (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-320.000000, -224.000000, 32.000000)),
 (Sadrith Mora, Wolverine Hall, (2560.000000, 4064.000000, 14240.000000)),
 (Sadrith Mora, Wolverine Hall, (2560.000000, 3968.000000, 14528.000000)),
 (Sadrith Mora, Wolverine Hall: Mage's Guild, (448.000000, 192.000000, 160.000000)),
 (Sadrith Mora, Wolverine Hall: Mage's Guild, (-70.134480, 434.521700, 65.990490)),
 (Balmora, Guild of Mages, (-755.896600, -1002.733000, -644.627900)),
 (Balmora, [-3,-2], (-22130.610000, -8582.789000, 889.572800)),
 (Hlormaren, [-6,-1], (-43200.000000, -3448.000000, 3072.000000)),
 (Hlormaren, Dome, (320.000000, -256.000000, 402.000000)),
 (Hlormaren, Dome, (384.000000, -408.000000, 384.000000))]

Недостаток здесь заключается в том, что мы на самом деле не видим способа перемещения, необходимого для перехода между узлами, поэтому для расшифровки плана путешествия требуются знания об игре. По сути, нам нужно использовать заклинание Divine Intervention, чтобы попасть в форт Волверин Холл, затем войти Имперское святилище, бесцеремонно пройти через него во внутреннюю часть форта, войти в Гильдию мага, телепортироваться в Балмору и затем уйти/улететь оттуда в Хлормарен.

А как насчёт попадания в родовую гробницу Сарисов, которая расположена на отдалённом острове в юго-западном краю карты? Легче некуда.

[(Tel Vos, Aryon's Chambers, (3905.517000, 2935.360000, 15752.000000)),
 (Wolverine Hall, [18,3], (148881.700000, 28453.790000, 1495.193000)),
 (Wolverine Hall, [18,3], (148880.000000, 28360.000000, 1464.000000)),
 (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-64.000000, -96.000000, 0.000000)),
 (Sadrith Mora, Wolverine Hall: Imperial Shrine, (-320.000000, -224.000000, 32.000000)),
 (Sadrith Mora, Wolverine Hall, (2560.000000, 4064.000000, 14240.000000)),
 (Sadrith Mora, Wolverine Hall, (2560.000000, 3968.000000, 14528.000000)),
 (Sadrith Mora, Wolverine Hall: Mage's Guild, (448.000000, 192.000000, 160.000000)),
 (Sadrith Mora, Wolverine Hall: Mage's Guild, (-70.134480, 434.521700, 65.990490)),
 (Vivec, Guild of Mages, (3.520470, 1391.325000, -385.853300)),
 (Ebonheart, [1,-13], (8703.056000, -100602.000000, 1383.638000)),
 (Bitter Coast Region, [-5,-9], (-37659.390000, -69956.550000, 322.489000)),
 (Sarys Ancestral Tomb, (7028.375000, 4415.659000, 15001.790000))]

Нам снова нужно зайти в Гильдию Садрит Моры и телепортироваться, на этот раз в Вивек. Затем мы ещё раз кастуем Divine Intervention и оказываемся в Эбонхарте, который находится в одной поездке на лодке от острова с гробницей.

Далее в проекте «Морровинд» мы попытаемся сделать рекомендации планировщика чуть более понятными, расположив их на карте игры. Может быть, нанесём на карту и другие вещи. Возможно, в статье даже будет исходный код!

Часть 4

Снова приветствую вас в проекте «Морровинд», в котором мы будем использовать технологии, чтобы оказывать давление на людей в собственных политических интересах.

Этим субботним утром к моему дому подошла пара похмельных волшебников Телванни. Прошлым вечером они отправились в башню мастера Ариона пропустить по рюмочке, которая быстро превратилась в несколько рюмочек. Если вкратце, то Арион умудрился куда-то подеваться, и с тех пор его никто не видел. Более того, в ближайший понедельник будет заседание Совета, и отсутствие Ариона станет катастрофой.

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

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

Регенерация графа

Сначала мне пришлось изменить веса между рёбрами графа перемещений, потому что во по внутреннему времени игры перемещение на силт страйдере или лодке не является мгновенным. Но его всё равно можно вычислить из расстояния: скорость перемещения — это игровой параметр, по умолчанию равный 16000 единицам за игровой час. Например, расстояние от Сейды Нин до Балморы около 55000 единиц, поэтому если в начале игры вы решили потратить деньги на общественный транспорт, а не идти пешком, то вы добрались бы до Балморы и завершили свой первый квест меньше чем за 3,5 игровых часов.

Для определения времени передвижения пешком между локациями тоже потребовались исследования. Минимальная скорость ходьбы в игре — 100 игровых единиц в секунду реального мира, а игровое время по умолчанию течёт в 30 раз быстрее реального. То есть на прохождение 16000 единиц потребуется примерно 16000 / 100 * 30 / 3600 = 1 ч 20 мин игрового времени. Как видите, это не намного медленнее поездки на силт страйдере, и если вы увидите его, то поймёте, почему.

Очевидно, что если в имени класса NPC перемещения есть слова «Guild Guide», то перемещение с ним не занимает времени, потому что это магия.

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

Существует оптимизация, которую я не использовал: на самом деле нас интересуют только те точки графа, в которые мы можем попасть любым маршрутом, кроме как пешком. Рассмотрим такой случай: если кратчайший путь к точке создан из телепортации в какую-то точку A, а затем пешей прогулкой до точки B, а затем пешей прогулкой до точки C (всё это по прямой), то почему нельзя непосредственно пройти пешком из A в C (мы предполагаем здесь, что Арион может левитировать и перемещаться между точками по прямой, поэтому любые три точки во внешних ячейках следуют неравенству треугольников).

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

Быстрое, неполное и в основном ошибочное введение в линейную алгебру

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

Хорошие новости заключаются в том, что их можно представить как матричное произведение.

$$

Поэтому если у нас есть пара координат на карте и эта матрица M 3x3, то мы сможем вычислить настоящие внутриигровые координаты, и наоборот. Третий компонент вектора, равный 1 — это грязный хак, позволяющий нам закодировать переносы (движение), потому что в противном случае вектор (0, 0) на карте соответствовал бы вектору (0, 0) в игре. Подробнее об этом можно прочитать в Википедии.

Как нам найти такую матрицу? Ну, мы можем использовать её для преобразования нескольких векторов одновременно:

$$

И это можно переписать следующим образом (инвертировав матрицу вправо и умножив на неё всё уравнение):

$$

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

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

В результате я пришёл к такой матрице:

$$

Чтобы протестировать её, я нанёс три опорные точки, которые использовал для её вычисления (красные), а также исходное местоположение Ариона (синяя точка): внешняя дверь в его дом расположена в игровых координатах (85730.77, 117960.3, 5081.284), которые мы через матрицу привязываются к (1147.33, 555.21).


Отсюда я вижу твой дом!

В следующей части я расскажу вам, как мне удалось найти Ариона и спасти Совет Телванни от краха.

Часть 5

Хорошая визуализация того, где может находиться Арион, уже очень близка. Я выбрал самый глупый подход: пройти по всем пикселям карты, преобразовать каждый из них в точку игрового мира и найти время, которое бы потребовалось Ариону, чтобы туда добраться (с помощью способа, о котором я говорил выше: пройтись по всем точкам графа, в которые мы знаем кратчайшее время перемещения и найти ту, для которой общее время перемещения (кратчайшее время перемещения в эту точку + время на перемещение пешком из этой точки в точку назначения) наименьшее).

Только я забыл, что работаю в Python и что мне придётся пройтись для каждой точки карты примерно по 2400 возможным маршрутам через внешние точки. А всего есть 1650x1900 = около 3 миллионов точек. Разумеется, можно подойти с умом и воспользоваться разными оптимизациями (например собрать достаточно близкие друг к другу внешние точки и обрабатывать их как одну, или воспользоваться неравенством треугольников (о чём я говорил в предыдущей части), или рассматривать блоки 2x2 карты, а не каждый пиксель, или использовать все 4 ядра моего процессора вместо одного). Или я могу просто сфармить решение в программе на C++.

Поэтому я слил в файл дамп списка известных внешних координат и времени кратчайших маршрутов к ним, а также внутриигровые координаты трёх с лишним миллионов точек карты, которые меня интересовали. Программа брала их и выдавала для каждой рассматриваемой координаты кратчайшее время, которое потребовалось бы Ариону для добирания туда из своей башни. На самом деле для этого понадобилось 40 строк кода и 10 секунд вычислений. Довольно удивительно, как быстро можно решать задачи, если общаешься напрямую с железом.

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

Время картинок!

Это на самом деле имеет смысл. Вокруг дома Ариона есть двухчасовой круг (в северо-восточной части острова), из которого он может пройти пешком или телепортироваться в Волверин Холл с помощью Divine Intervention (на остров к востоку от Ввандерфелла). В Волверин Холле есть Гильдия магов, поэтому он мгновенно мог переместиться в один из четырёх основных городов (круг вдоль западного края острова). То есть есть довольно много мест, куда можно добраться за два часа!

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

За шесть часов он мог бы попасть в любую точку острова, а за восемь — достичь северных краёв Дагон Фела — небольшого острова к северу от Вварденфелла. Наконец, примерно через 11 часов он с большой вероятностью мог позавтракать вместе с Большеголовым в самом изолированном уголке Морровинда. Возможно, у него там было какое-то дело?

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

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

В следующей части проекта «Морровинд», мы поговорим о моём назначении на должность в Бюро национальной статистики Вварденфелла для анализа демографии острова.

Часть 6

Итак, Арион вернулся в свою башню, а всё население острова максимизировало эффективность своих путешествий. Настало время взяться за другую задачу и создать ещё немного красивых картинок. Следующий вопрос был простым: где же живут все эти люди и чем они занимаются?

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

Вооружившись этими инструментами, я прошёлся по всем NPC в мире, получил их внешнее местоположение и преобразовал его в координаты на карте. У меня была матрица размером с карту, в которой накапливались эти координаты: число для каждого пикселя было количеством NPC, внешние координаты которых соответствуют этому квадрату. Это значило, что у меня получится непропорционально большое количество людей, скапливающихся у дверей густонаселённых внутренних помещений, что было неоптимально, потому что это сложно увидеть на изображение (в конце концов, это всего лишь один пиксель). Кроме того, это плохо отражало внутриигровую реальность: прежде всего нас интересует население отдельных городов/областей, а люди всё равно не стоят на одном месте, а бродят по окрестностям.

Поэтому я применил к моей матрице гауссово размытие, то есть одному пикселю вместо 10 людей назначается примерно 2,2, для соседнего пикселя — 1,1, для пикселя в двух пикселях от исходного — 0,5, и так далее. Это похоже на то, что мы рубим людей на куски и бросаем эти части тел так, что из них собирается удобная куча, потому что примерно так мы и делаем.

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

$$

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

С учётом этого, давайте посмотрим, что у нас в результате получилось!


draw_npcs(filter_sigma=25, sigmoid_k=8, sigmoid_c=0.2, output='map_population.png')

В больших населённых пунктах мы получили тёмные пятна. Снизу вверх: Вивек (и рядом с ним Эбонхарт), затем Балмора (в юго-западной части острова), Садрит Мора (на самом востоке), Альд'Рун (к северу от Балморы) и Гнисис (к северо-востоку от Альд'Руна). Здесь есть также пятна и поменьше — это или небольшие поселения, или большие подземелья/крепости/святилища.

Что мы ещё можем с этим сделать? Как насчёт нанесения на карту всех тёмных эльфов? Да запросто, просто проходим не по всем NPC:


draw_npcs(filter_sigma=25, mark_npcs=[n for n in npcs if n.race == 'Dark Elf'], sigmoid_k=8, sigmoid_c=0.2, output='map_population_darkelf.png')

Да, это выглядит точно как тепловая карта населения. Может быть, проверим, где их слишком много или слишком мало? Мы можем разделить эти два слоя один на другой и получить долю тёмных эльфов во всём населении:

draw_npcs(relative=True, filter_sigma=50, mark_npcs=[n for n in npcs if n.race == 'Dark Elf'], sigmoid_k=4, sigmoid_c=0.5, output='map_population_darkelf_relative.png')

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

Что ещё мы можем сделать? В Морровинде есть рабство! Давайте выясним, где сконцентрированы все рабы:


draw_npcs(relative=True, filter_sigma=25, mark_npcs=[n for n in npcs if n.class_name == 'Slave'], sigmoid_k=8, sigmoid_c=0.2, output='map_population_slave_relative.png')

Нет пятен вокруг больших городов — это логично, потому что это не относительная доля. Вместо этого пятнами выделены случайные подземелья и плантации мира, на которых содержатся рабы, в том числе Яичная шахта Абебаал, Плантация Дрена, несколько рынков рабов, Ротеран или Хлормарен (интересно, что для последнего пятно (к западу от Балморы, за большой водой) находится на западе самой крепости, потому что рабы содержатся в канализации, выход из которой расположен где-то здесь).

Разумеется, мы ни за что бы не стали использовать этот инструмент в собственных корыстных целях:


draw_npcs(relative=True, filter_sigma=50, mark_npcs=[n for n in npcs if n.is_female], sigmoid_k=12, sigmoid_c=0.7, output='map_population_female_relative.png')

На острове очень мало мест, в которых чрезмерно много женщин (заметьте, что я установил центр сигмоидальной кривой на 70%). Одно из них — это город Тель Мора на северо-востоке. Так получилось потому, что правителю города «не нравится присутствие мужчин» и все жители этого города на самом деле являются женщинами. Ещё одно место — это Одирниран на юго-востоке, крепость Телванни, атакованная Домом Хлаалу. К северо-западу есть Ассу с двумя волшебницами, а к северу от него есть Тел Увирит — крепость, строящаяся для игрока как часть квестовой линии Телванни. В начале игры она отключена (и невидима), но программу. разумеется, это не волнует.

Заключение

Наконец-то я разбил использованный для получения всех графиков код на набор модулей и загрузил его на GitHub. Вам потребуется обычный научный стек инструментов Python (NumPy, SciPy, matplotlib, а также PIL) и компилятор C++. Я решил, что будет плохой идеей публиковать полученный мной дамп игровых данных, так что вам придётся делать его самостоятельно: вам потребуется оригинальный файл данных Morrowind.esm и Enchanted Editor (инструкции по созданию дампа изложены в README).

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