Планирование спидрана Morrowind с помощью имитации отжига

Ну ты и соня, тебя даже вчерашний шторм не разбудил. Говорят, мы уже приплыли в Морровинд. Нас выпустят и позволят нам сделать спидран, это точно!

Введение

Существует знаменитый спидран основного квеста Morrowind, в котором, по сути, игрок перемещается к месту конца игры, использует несколько свитков и заклинаний, а затем убивает босса.

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

• В Morrowind есть 10 фракций, в которые можно вступить (Гильдии магов/воров/бойцов, Имперский культ, Имперский легион, Храм Трибунала и Великие Дома: Хлаалу, Редоран, Телванни). Во время прохождения игрок может стать членом только одного Великого Дома, но всё равно остаётся 8 фракций.
• Транспортная система. Это вопрос не только быстрого перемещения в нужные места, которые использовал игрок в Skyrim или Oblivion. Это ещё и путешествия с использованием различных средств передвижения, в том числе лодок, караванов и заклинаний телепортации, которые я исследовал ранее. Очень активно применяется ходьба, и чрезвычайно важно управлять квестовыми линиями фракций, чтобы избежать ненужных путешествий в различные города.
• Существует множество способов стать главой фракции. В квестовых линиях фракций используется система повышения в звании, при которой новые квестовые линии открываются, когда персонаж получает повышение ранга во фракции. Повышение зависит не только от очков репутации (которые даются за выполнение квестов), но и от навыков и атрибутов игрока.
• Задачи некоторых квестов можно завершить заранее или выполнить иным способом. Например, если дающий квест персонаж хочет, чтобы игрок кого-то убил, то этого кого-то часто могут убить ещё до того, как начнётся квест, и в таком случае выдающий квест персонаж всё равно даст игроку награду. Однако иногда это не срабатывает и игроку оказываются недоступными очки репутации, необходимые для открытия дальнейших квестовых линий. Аналогично, в большинстве квестов типа «принеси предмет» выдающий квест сообщает, где игрок может получить предмет, но его не волнует, был ли он куплен в ближайшем магазине несколько минут назад.

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

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

Примечание о требованиях к навыкам и системе уровней Morrowind

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

В отличие от Skyrim и Oblivion, повышение во фракциях Morrowind требует наличия у игрока определённых навыков с определённым уровнем. В Morrowind 27 навыков и у каждой фракции есть 6 так называемых «предпочтительных навыков». Чтобы стать главой фракции, игрок должен иметь очень высокий уровень одного из этих навыков (примерно 80-90 из 100) и двух из них — на среднем уровне (примерно 30-35).

Кроме того, у персонажей Morrowind есть 7 атрибутов, каждый из которых «управляет» несколькими навыками. Также атрибуты влияют на повышение ранга во фракциях.

Это печальные для нас новости, потому что в спидране у нас не будет достаточно времени на развитие навыков персонажа. Однако хорошие новости заключаются в том, что по Морровинду разбросаны учителя навыков, способные за определённую оплату мгновенно повысить эти навыки. Печальные новости — эти учителя не смогут поднять навыки выше, чем управляющие ими атрибуты. Для увеличения атрибутов требуется повышение уровней, а эта задача в Morrowind является очень долгой историей. О стратегии повышения уровней я расскажу позже.

Различные маршруты для отдельной фракции

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

Вот пример одной из таких электронных таблиц:


Из этой таблицы уже понятна сложность фракций Morrowind. Существует два предполагаемых способа достичь вершины Гильдии магов: получить достаточно репутации и навыков, чтобы стать Мастером Волшебником, завершить все квесты Эдвинны Эльберт и вызвать Архимага на дуэль, или завершить все квесты Сцинка-в-Тени-Дерева и получить письмо от руководства, сообщающее об отстранении нынешнего Архимага. Позже я нашёл ещё один способ — достичь ранга Волшебника (на один ранг ниже Мастера Волшебника), а затем поговорить с Архимагом о дуэли, что оказывается быстрее.

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

Генерирование всех возможных маршрутов для прохождения фракции

… оказалось сложной задачей. Первой попыткой стало кодирование каждого квеста в файл YAML как множества предпосылок и требуемых для выполнения предметов/действий. Вот пример:

  edwinna_2:
    giver: edwinna elbert
    prerequisites:
      rank: Conjurer
      quest: Chimarvamidium 2
    quests:
      - Dwemer Tube:
          rep: 5
          completion:
            items: misc_dwrv_artifact60
      - Nchuleftingth:
          rep: 10
          completion:
            go_person: anes vendu
      ...

Так кодируется начало расширенной квестовой линии Эдвинны Эльберт — двемерская трубка из Аркнгтунч-Штурдумц, которая требует от игрока стать Вызывающим (Conjurer) в Гильдии и завершить предыдущий квест Эдвинны. Для выполнения этого квеста игрок должен иметь в инвентаре трубку (я использовал внутриигровой ID предмета). Выполнение квеста даёт игроку 5 очков репутации фракции.

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

Учитывая всё это, мы можем сгенерировать множество всех возможных способов прохождения гильдии с помощью поиска в ширину (breadth-first search):

• множество всех последовательностей прохождения гильдии S = пусто
• выполнить:
  
  • для каждой последовательности в S:
    
    • если она уже завершает гильдию, то игнорировать
    • в противном случае получить все возможные следующие квесты, которые можно выполнить в этой последовательности:
      
      • где соблюдены предпосылки квеста (например, выполнен предыдущий/необходимый квест в квестовой линии)
      • где достаточно репутации для начала новой квестовой линии
    • добавить каждый из этих возможных квестов в последовательность, чтобы создать несколько новых последовательностей
    • заменить текущую последовательность сгенерированными новыми
• продолжать, пока S не перестанет изменяться

Комбинаторные взрывы, комбинаторные взрывы повсюду

Что могло пойти не так? Ну, во-первых, тут есть проблема с порядком. Если игрок жонглирует двумя параллельными квестовыми линиями от разных выдающих квесты персонажей, то учитывается каждое их возможное пересечение, что приводит к комбинаторному взрыву. Во-вторых, генерируются и маршруты, которые совершенно точно хуже существующих маршрутов. Например, если прохождение определённой гильдии требует от нас выполнения только квестов A, B, D и E, то нет смысла генерировать маршрут A, B, C, D, E: выполнение D в любом случае потребует дополнительного времени.

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

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

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

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

Попытка 2: граф зависимостей отдельных квестов

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

Краткий обзор самых быстрых маршрутов для конкретной фракции

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

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

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

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

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

Квестовая линия Имперского легиона выполняется в единственном городе и требует от игрока посещения места, которое он и так посещает в квестовой линии Эдвинны Эльберт в Гильдии магов. Кроме того, один квест даёт дополнительную репутацию у Храма, что позволяет пропустить один его квест.

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

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

Граф зависимостей квестов

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

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

Например:

# Соединённая квестовая линия Ажиры
mg_ajira_1:
  giver: ajira
# Квесты Эдвинны до экспедиции в Нчулефтингт, все выполняются за один раз (двемерская трубка, украденная
# у Ворара Хеласа в Балморе, затем Кимервамидиум, Сцинк и Хулин)
mg_edwinna_1:  # также даёт амулеты Almsivi/Divine
  giver: edwinna elbert
  prerequisites:
    - mg_ajira_1
mg_edwinna_2:
  giver: edwinna elbert
  prerequisites:
    - mg_edwinna_1
    - mg_edwinna_nchuleftingth
    - mg_edwinna_scarab_plans
    - mg_edwinna_airship_plans
# локации мест, необходимых для выполнения квестов Эдвинны
mg_edwinna_nchuleftingth:
  giver: anes vendu # можно обнаружить его тело до начала квеста
mg_edwinna_scarab_plans:
  giver: Khargol gro-Boguk # орк в Свободной башне с другой копией чертежей
mg_edwinna_airship_plans:
  giver: lugrub gro-ogdum # расположен рядом с орком в Яичной шахте Гнисиса, которая также является частью квеста Имперского легиона
mg_master:
  giver: trebonius artorius
  prerequisites:
    - mg_edwinna_2

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

Когда частью квеста является общение с кем-нибудь, я кодировал это как несколько узлов, зависящих друг от друга:

fg_eydis_1_start: # вступление в Гильдию бойцов и начало первого квеста
  giver: eydis fire-eye
fg_eydis_1_do:
  giver: drarayne thelas # выполнение первого квеста
  prerequisites:
    - fg_eydis_1_start
fg_eydis_1_end: # сдача квеста
  giver: eydis fire-eye
  prerequisites:
    - fg_eydis_1_do

Вот как выглядит окончательный граф зависимостей квестов:

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

Однако здесь по-прежнему есть проблема: существует множество возможных топологических сортировок заданного графа и их вычисление является #P-полной задачей.

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

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

Генерирование матрицы времени перемещений

Здесь мы поговорим о двух графах: первый — это описанный выше граф зависимостей квестов, а второй — граф перемещений, который я сгенерировал в одной из предыдущих статей.

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

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

Однако здесь есть проблема: в графе перемещений содержится около 6500 вершин и 16000 рёбер телепортации (то есть перемещения общественным транспортом или при помощи заклинаний Almsivi/Divine Intervention: в это число не входят рёбра физических перемещений между точками в одной ячейке). На выполнение алгоритма Дейкстры для одной исходной точки потребовалось около 10 минут, поэтому на генерирование матрицы времени перемещений я бы потратил примерно день.

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

def coalesce_cells(vertices, edges):
    # Заменяет все вершины в графе в одной ячейке единственной ячейкой (усреднённым местоположением)
    vertices_map = defaultdict(list)

    for v in vertices:
        vertices_map[v.cell].append(v)

    # Вычисление усреднённой вершины для каждой ячейки    
    average_vertices = {}
    for cell, vs in vertices_map.items():
        coords = tuple(sum(v.coords[i] for v in vs) / float(len(vs)) for i in range(3))
        average_vertices[cell] = Location(coords=coords, cell_id=vs[0].cell_id, cell=vs[0].cell)

    new_vertices = set([average_vertices[v.cell] for v in vertices])

    # Группировка рёбер по усреднённым вершинам, к которым они принадлежат
    grouped_edges = defaultdict(lambda: defaultdict(list))
    for v1 in edges:
        av1 = average_vertices[v1.cell]
        for v2 in edges[v1]:
            av2 = average_vertices[v2.cell]
            # Вычисление затрат на новые рёбра
            grouped_edges[av1][av2].append((edges[v1][v2][0], get_distance(av1.coords, v1.coords) / WALKING_SPEED + edges[v1][v2][1] + get_distance(v2.coords, av2.coords) / WALKING_SPEED))

    new_edges = defaultdict(dict)
    for av1 in grouped_edges:
        for av2 in grouped_edges[av1]:
            # Заменяем все возможные рёбра между двумя новыми вершинами самым дешёвым
            new_edges[av1][av2] = min(grouped_edges[av1][av2], key=lambda md: md[1])

    return new_vertices, new_edges

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

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

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

Имитация отжига (генетический алгоритм?)

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

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

В результате я использовал следующий алгоритм:

• Начнём с пула маршрутов-кандидатов: возьмём простую топологическую сортировку и повторим это 20000 раз
• Продолжаем, пока не надоедает, затем прекращаем оптимизацию:
  
  • сортируем маршруты по их общему времени, сохраняя лучшую 1000 маршрутов
  • для каждого оставшегося маршрута:
    
    • генерируем из него 20 маршрутов-кандидатов:
      
      • выбираем случайную точку маршрута и перемещаем её на случайное количество шагов вверх или вниз
      • проверяем, удовлетворяется ли требования графа зависимостей, если нет, то повторяем снова
      • выполняем такие перестановки 30 раз
  • в пуле теперь снова 20000 маршрутов, повторяем

Разумеется, с константами можно поэкспериментировать, а условие прекращения можно определить лучше. Кто-то называет это генетическим алгоритмом (в котором мы симулируем эволюцию и случайные мутации в генетическом пуле), другие — имитацией отжига (в котором величина случайных перемещений со временем уменьшается, пока мы не приходим к пулу решений). «Генетический алгоритм» звучит интереснее, поэтому я упомянул его в этом параграфе.

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


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

В целом, в некоторых моментах оптимизатор меня приятно удивил.


Я написал удобную программу, которая берёт узлы графов и разворачивает их в план перемещения с использованием заклинаний Almsivi/Divine Intervention и общественного транспорта. Например, в этом фрагменте планировщик маршрута совершенно правильно настроил прогресс в квестовой линии фракции, благодаря чему все шесть заданий в отдалённом юго-западном углу карты можно выполнить за один заход (строки 592-618).

Однако у этого маршрута есть некоторые проблемы:

• В нём не учитываются применения заклинаний Mark/Recall. Эти заклинания очень мощны: Recall телепортирует игрока в точку, в которой последний раз было произнесено заклинание Mark.
• Он не учитывает обучение навыкам для перехода между квестами фракций.

Обучение навыкам

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

Значения атрибутов можно повышать только при повышении уровня. В качестве основных навыков у персонажа игрока есть 5 из 27 навыков (которые позволяют ему повышать их уровень быстрее и дают бонус +25 к этим навыкам в начале игры) и 5 побочных навыков (которые тоже позволяют быстрее повышать их уровень, хотя и не так быстро, как у основных, а также дают бонус +10 к этим навыкам). Персонаж повышает уровень, когда наберёт 10 очков основного или побочного навыка.

И здесь всё начинает становиться странным. При повышении уровня игрок выбирает 3 атрибута, уровень которых он хочет повысить. Величина повышения зависит от навыков, которым обучался игрок. Например, если он получил 10 очков в Алхимии (управляемой Интеллектом), то если при повышении уровня выбирается Интеллект, он увеличится не на 1, а на 5 очков. Однако если игрок поднял уровень, обучившись 1 очку в Длинных клинках (управляемых Силой) и 9 очкам в Алхимии, то он получит множитель 4x к Интеллекту и 1x к Силе.

Также игрок может обучаться навыкам, не являющимся основными или побочными, чтобы получить достаточно очков на увеличение множителя атрибута. Допустим, игрок также обучается 1 очку в Безопасности (управляемой Интеллектом), которая не является его основным или побочным навыком. Она не будет учитываться в 10 очках, необходимых для повышения уровня, но учитывается в вычислениях множителя атрибутов. Поэтому игрок сможет увеличить свой Интеллект на 5.

Поэтому мне нужно было тактически выбрать основные/побочные навыки моего персонажа, а также его расу (которая даёт бонусы определённым навыкам и атрибутам), чтобы быстро достичь требований каждой фракции.

Обзор фракций и требуемых уровней навыков

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

• Гильдия магов: Изменение, Разрушение, Алхимия, Зачарование, Иллюзия, Мистицизм. Один навык не менее 70, два не менее 25, Интеллект и Сила воли не менее 33.
• Гильдия бойцов: Секиры, Длинные клинки, Дробящее оружие, Тяжёлые доспехи, Кузнец, Защита; 70/25/25, Сила и Выносливость 33.
• Гильдия воров: Меткость, Короткие клинки, Лёгкие доспехи, Акробатика, Скрытность, Безопасность; 80/30/30, Ловкость и Привлекательность 34.
• Храм Трибунала: Алхимия, Дробящее оружие, Колдовство, Мистицизм, Восстановление, Бездоспешный бой; 80/30/30, Интеллект и Привлекательность 34.
• Мораг Тонг: Акробатика, Иллюзия, Меткость, Лёгкие доспехи, Короткие клинки, Скрытность; 80/30/30. Скорость и Ловкость 34.
• Имперский культ: Красноречие, Бездоспешный бой, Восстановление, Мистицизм, Зачарование, Дробящее оружие; 90/35/35. Привлекательность и Сила воли 35.
• Имперский легион: Атлетика, Древковое оружие, Длинные клинки, Дробящее оружие, Тяжёлые доспехи, Защита; 70/25/25. Выносливость и Привлекательность 33.
• Дом Хлаалу: Красноречие, Торговля, Меткость, Короткие клинки, Лёгкие доспехи, Безопасность; 70/25/25. Скорость и Ловкость 33.

Планирование персонажа

С учётом всего этого я решил выбрать в качестве высокоуровневых навыков Алхимию, Дробящее оружие и Меткость. Алхимии (основной навык для Гильдии магов) можно быстро научиться созданием зелий. Дробящее оружие является общим навыком для 4 фракций (Гильдии бойцов, Храма, Имперского культа и Имперского легиона) и должно повышаться до 90. Меткость связана с другими 3 фракциями (Гильдией воров, Мораг Тонг и Домом Хлаалу) и повышается до 80.

Прочие навыки нужно выбирать частично затем, чтобы покрыть оставшиеся, более слабые требования, а частично потому, что обучение им увеличивает Силу или Ловкость до 90 или до 80 (в противном случае невозможно будет обучиться Дробящему оружию или Меткости). Поэтому я решил прокачивать персонажа, начинающего с высокой Силы и с бонусом к Дробящему оружию, а также обучаться Длинным клинкам для увеличения Силы (и для соответствия требований вторичных навыков для Гильдии бойцов/Имперского легиона).

Для Ловкости я буду обучаться Защите, Лёгким доспехам и Скрытности. Все они управляются Ловкостью и обучение им до требуемых уровней приведёт к том, что Ловкость повысится настолько, что позволит мне обучиться Меткости до 80.

Зачарование и Мистицизм соответствуют вторичным требованиям Храма, Гильдии магов и Имперского легиона.

Вот окончательная схема персонажа. Она начинает со следующими основными и побочными навыками:

• Основные:
  
  • Алхимия: 35. Чтобы поднять её до 70 с помощью создания зелий (основной навык для Гильдии магов, вторичный навык для Храма).
  • Дробящее оружие: 40. Чтобы поднять его до 90 (основной навык для Гильдии бойцов, Имперского легиона, Имперского культа и Храма).
  • Меткость: 30. Чтобы поднять её до 80 (основной навык Гильдии воров, Мораг Тонг и Дома Хлаалу).
  • Мистицизм: 35, не нужно обучаться (вторичный навык для Гильдии магов, Храма и Имперского культа).
  • Зачарование: 35, не нужно обучаться (вторичный навык для Гильдии магов и Имперского культа).
• Побочные:
  
  • Длинные клинки: 25. Чтобы поднять до 45 для получения дополнительных очков Силы (вторичный навык для Гильдии бойцов и Имперского легиона).
  • Скрытность: 15. Чтобы поднять до 30 (вторичный навык для Гильдии воров и Мораг Тонг)
  • Защита: 15. Чтобы поднять до 30 (вторичный навык для Гильдии бойцов и Имперского легиона).
  • Красноречие: 15. Чтобы поднять до 25 для дополнительных пяти очков Привлекательности (вторичный навык для Дома Хлаалу).
  • Лёгкие доспехи: 15. Чтобы поднять до 30 (вторичный навык для Гильдии воров, Мораг Тонг и Дома Хлаалу).

Кодирование обучения в графе зависимостей квестов

Я решил не загружать данные учителей Morrowind для встраивания их в планировщик маршрутов. Вместо этого я нашёл лучших учителей Дробящего оружия и Меткости (потому что это единственные навыки, позволяющие игроку достичь требуемого уровня), а также вторых по качеству учителей и попытался вычислить людей, с которыми персонаж игрока всё равно встретится на своём пути. Так выявились забавные совпадения, например, Алвелег, которого нужно убить как часть квеста Гильдии бойцов, но который также может обучить игрока Защите, Скрытности и Меткости до довольно высоких уровней.

Затем я добавил несколько дополнительных узлов в граф зависимостей, чтобы отразить новые сеансы обучения:

# Узлы обучения
training_alveleg:
  # мы убиваем его как часть квеста Гильдии бойцов и он обучает Меткости (45), Скрытности (42) и Защите (38)
  description: Train Block x10 (up to 25), Sneak x15 (up to 30), Marksman x15 (up to 45), should get Agi 60
  giver: alveleg
training_bolnor:
  description: Train Light Armor x15 (up to 30), Marksman x5 (up to 50), should get Agility 70
  giver: bolnor andrani
  prerequisites:
    - training_alveleg
training_eydis:
  description: Train Long Blade x20 (up to 40), Blunt x30 (up to 70), Strength 85
  giver: eydis fire-eye
training_ernse:
  description: Train Blunt x20 (up to 90)
  giver: ernse llervu
  prerequisites:
    - training_eydis
training_missun:
  description: Train Marksman x30 (up to 80)
  giver: missun akin
  prerequisites:
    - training_bolnor
training_falvel:
  description: Train Mercantile x10 (should get Personality 35)
  giver: falvel arenim

Затем они должны стать предпосылками для некоторых более поздних квестов в квестовых линиях фракций:

tt_tharer_1:
  description: Get and hand in all Tharer Rotheloth quests
  giver: tharer rotheloth
  prerequisites:
    - tt_7graces_vivec
    - tt_7graces_gnisis
    - tt_7graces_kummu
    - tt_7graces_gg
    - tt_cure_lette
    - tt_mount_kand
    - tt_mawia
    - tt_kill_raxle_berne
    - training_eydis # Curate (50 blunt) to hand in Galom Daeus quest

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

Заключение

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