дистанция ai morrowind что это

Morrowind дистанция ai что это

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

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

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

Текущая скорость NPC (и игрока) рассчитывается исходя из многих переметров fActors (скорость, атлетика и др.) и выбирается из промежутка между fMinWalkSpeed и fMaxWalkSpeed. Эти два значения задают диапазон скорости ходьбы персонажа.

плавании (быстрое плавание).

Также обнаружено, что навык Бездоспешный не работает вовсе, ПОКА не будет надет хотя бы один доспех. ( Форум.инф. / The other Felix )

Все эффекты ‘Усталости’ в игре – Для различных действий, тем не менее не все из них работают в игре (мне не удалось создать заклинание на уменьшение усталости). Названия говорят сами за себя, но серьезно они не тестировались.

«1068» устанавливает число зарядов, которое будет иметь предмет, зачарованный на одноразовое использование. Формула такова: BaseSpellEffectCost x iMagicItemChargeOnce. Линейная. Таким образом, предмет с зачарованием на один раз будет иметь как раз то число зарядов, чтобы выдать нужный эффект.

(заряды рассчитываются для достижения X «использований», где Х – данное значение).

Значение умножается на стоимость заклинания на ловушке, а затем добавляется к шансу на разоружение. Т.к. ее значение равно нулю, то стоимость заклинания не влияет на шанс снятия ловушки.

Управление с помощью скриптов

Кроме того, есть команды AI, которые можно ввести только при помощи скрипта или диалога. Большая их часть требует версии игры 1.2 или выше (Трибунал или БладМун).

Команда ForceSneak переводит актера в режим скрытности, все движения будут выполняться, как будто он крадется. ClearForceSneak завершает режим ForceSneak.

Все эти функции управляют движением указанного NPC. ForceRun заставляет актера всегда бежать при движении, ForceJump заставляет актера постоянно прыгать, ForceMoveJump заставляет актера постоянно прыгать при движении. Функции ClearXXX используются для сброса этих режимов. Каждый NPC может быть только в одном из этих режимов одновременно. Приоритет для этих режимов:

Morrowind дистанция ai что это

Уже пару лет как, всё стало гораздо проще.

В свойствах ярлыка лаунчера морровинда, просто морровинда и МГЕ сделайте запуск от имени администратора. После чего запустите лаунчер и смените разрешение экрана в игре. выключите лаунчер. запускайте МГЕ

Вроде все. Экспериментируйте))

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

а) Вот что вам будет доступно после установки MGE на Морровинд:

в)Сам MGE можно скачать с ссылка на МГЕ 3.8.0.

д) Что нужно перед установкой?

е) Что нужно после установки?

ё)Как включить удаленный ландшафт (Distant Land)?

ж) Настройка полноэкранных шейдеров:

з) Дополнительные клавиши управления.

л)Ещё чуть-чуть и получим Обливион.

я) Вам не нравится, что даже в плохую погоду виден весь ландшафт, на всю его дальность?

м) Depth of Field (DOF) и AtmosphericScattering

н) Советую также поставить утилиту TalkyMorrowind.

Тема про TalkyMorrowind: Автоматическая озвучка диалогов.

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

Настройка AI с помощью скриптов

Для активации различных объектов используются скриптовые команды AiActivate «Object ID». Но надо учесть, что эта функция глючная и не очень хорошо работает. AI-пакеты типа «Follow» заставляют один персонаж следовать за другим неотрывно. Но можно с помощью скриптовых команд заставить NPC или монстра следовать за игроком, либо заставить несколько NPC или монстров построиться в своеобразный караван. Для этого используются команды типа:

Пример такого скрипта, в котором гуар будет следовать за NPC до тех пор, пока не будет дана другая команда.

Вот мы и рассмотрели настройки AI неписей, в том числе и скриптовые. Считаю важным заметить, что они подходят и для зверушек. Только у них нет disp’ов, т.е., значения отношения к вам (помните Ползуна из Кальдеры?). Грамотно настроенный NPC будет вести себя реалистично и украсит любое ваше произведение. Действуйте!

Как настроить искусственный интеллект NPC и Creature

Введение

Path Grid

Также, если говорить о перемещениях NPC, нельзя не сказать о путях их перемещений, так называемых Path Grid (Сетка путей). Если в редакторе вы нажмёте на кнопку с изображением «Красных и синих точек, связанных жёлтыми палочками» в любой стандартной локации вы увидите эти самые точки и палочки.

Итак, зачем они нужны? Геймер всегда видит, где есть проход, как обойти препятствие и тому подобные навигационные действия. Для компьютера же это очень сложная задача. В реальной жизни, задача ориентирования и распознавания является одной из наиболее трудоёмких в кибернетике. В игре это намного легче, но тоже доставляет неудобства. Все вы видели, как во время боя, неписи застревают в камнях, статуях и пр. Если вы тестировали только что созданные локации с неписями, то замечали, что те норовят потоптаться по кроватям, залезть на стол или учудить подобные безобразия. Это из-за неверной расстановки тех самых точек.

Как оно работает? Вы видите точки и линии. Эти точки являются как бы железнодорожными станциями, а линии – путями. В нормальном (небоевом) состоянии, непись будет ходить точно между точками и только по путям. В состоянии блуждания (Wander) он идёт к какой-либо случайной точке, находящейся в пределах [Distance] от начальной точки. Если эта точка окажется для него недостижимой, он будет вечно крутиться по локации, пока её не достигнет или пока плейер не уйдёт другую локацию. По этому надо внимательно следить за расположением этих точек. Когда NPC дойдёт до этой точки, он переходит к следующей операции (движению idle, следующему переходу и т.д.). Короче, если вы хотите, чтоб неписи вменяемо передвигались, правильно расставляйте пафгриды.

Вот, кажется и всё, что можно извлечь из непися. Что-то новое можно поставить через скрипты, что-то через диалоги, но самое лёгкое было описано выше. Надеюсь, моя статья вам поможет.

При написании статьи использованы материалы из MSfD8 GhanBuriGhan’а с переводом Gwathlobal’а (Для MPT).

Кнопка AI

На первой закладке Package можно настроить перемещения непися в пространстве.

Wander

Idle chance – шанс в процентах, что непись совершит какую-то анимацию. Приведём список этих анимаций:

Человек женщина – как и выше, кроме:

Хаджит женщина – как Человек мужчина, кроме:

Также эти параметры можно настроить через скрипт или результирующую команду в диалоге. Она должна выглядеть так:

где 1-е число соответствует Distance, затем Duration, time и все idle.

Итак, если вы сделаете режим Wander с параметрами 512, 5, 0, 0, 20, 0, 0, 10, 30, 0, 0, 0, то ваш непись будет регулярно прогуливаться по локации на расстояние не более 512 ед. от своего первоначального положения, изредка останавливаясь(idle), почёсываясь(idle4) и поправляя одежду на плече (idle5). В общем, он будет вести себя живенько. Большинство стандартных неписей ведёт себя похожим образом и, если ваш подопытный ничем не выделяется из их числа, то можно вообще оставить стандартные настройки. А вот если нет. Вот, например, паромщик из моего плага WindyBoat, который стоит на корпусе лодки, не должен никуда ходить или он свалится. Поэтому я поставил Distance на 0. Если вы делаете какого-нибудь божка или короля, то будет не совсем разумно позволять ему почёсываться. Тогда ставим вероятность выпадения соответствующего idle на 0.

В меню Add package также можно выбрать и другие действия.

Travel

Travel заставляет непися идти в назначенную точку. Нажав на кнопку View location, вы можете визуально её определить по красному кресту. Этот крест вы можете спокойно двигать мышкой. Если вы поставите несколько travel’ов, то можете сделать маршрут и заставить непися «патрулировать территорию», бегая между этими точками. Можно также задать это строкой: AITravel [координата х] [координата у] [координата z]

Escorte

Escorte заставляет вести куда-то выбранного актора (плейера, непися, кричера). Он идёт впереди и, если ведомый отстаёт, будет ждать его. Помните белого гуара? Когда вы с ним встречаетесь, он ласково смотрит вам в глаза, разворачивается и уходит. Если вы не идёте за ним, он останавливается и ждёт. Это очень удобно применять, чтобы довести плейера до квестовой точки, как, например труп, вещи, дом, в конце концов. Только есть один нюанс. Актор остановится не только, если плеер отстанет, но и если будет опережать его. Можно также задать это строкой:

Follow

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

Если указать нулевые координаты, то цель будет следовать за актором до поступления новых инструкций. Так, например, если вы укажете в результате диалога строку AiFollow, «Player», 0,0,0,0, то заставите непися следовать за плейером и охранять его. Для того, чтобы отменить это действие, то есть попросить непися “подождать здесь”, надо установить команду AIWander, например

Activate

Activate, который, по идее, должен заставлять непися активировать какой-то объект не работает.

Поле Fight

Поле Fight отвечает за агрессивность персонажа. Коротко говоря, если эта величина более 50, то он на вас нападёт, а если не коротко, то вот выдержка из MSfD8:

Flee влияет на желание непися смотаться от вас при драке. Если 100 –мотает, не дожидаясь столкновения, если 0 – не бежит никогда. Но результат не всегда такой, так как актер учитывает другие факторы, такие как количество повреждений, которые он может получить, или другая стратегия, которую они могут использовать, например магию и дальний бой.

Alarm

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

Hello

Hello – расстояние, на котором непись с вами поздоровается. Для получения реального расстояния умножайте на 7.

Services

Morrowind:Работа с NPC и AI

Ниже идут стандартные характеристики от силы и ловкости до стамины и магии.

Ниже идут скиллы персонажа.

Переходим на правую сторону окна.

Настройки AI на вкладке «Services»

Мы только что рассмотрели вкладку Packages, а есть еще и Services.

В ней указаны услуги непися, которые разделены на три блока:

С заклинаниями дела обстоят примерно также. Просто теперь надо тащить из вкладки Spellmaking (что в том же Object Window) во вкладку Spells, что находится за Items. Разумеется, поместить заклинание для обучения можно только в инвентарь.

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

Настройки AI на вкладке «Packages»

Здесь выставляются проценты: от 0 до 100. Теперь подробнее о каждом параметре:

Fight

Alarm

Hello

Над этими четырьмя параметрами есть два окошка:

А вот на этих AI пакетах (левое окошко) нужно остановиться и рассмотреть их более подробно.
Итак.

Всего есть пять типов пакетов:

Рассмотрим их более подробно.

Wander

Travel

Follow

Escort

Activate

Необходимо упомянуть, что если бы пакеты, управляющие движениями и поведением NPC, возможно было бы только раз и навсегда жестко задавать в КС, то было бы просто неинтересно. Но разработчики предусмотрели возможность управлять ими из скриптов командами Get/Mod/Set[Fight/Flee/Alarm/Hello] и PlayGroup.

Источник

Дистанция ai morrowind что это

Разработчик: Bethesda Softworks
Издатель: Ubi Soft Entertainment
Локализатор в России: Акелла
Издатель в России: 1С
Дата Выхода: 2002 год

Решил ещё разочек пройти морр.
Проблема: катастрофически маленький фпс.
На улице в Балморе 15 фпс в среднем. В зданиях нормально, 30-35 фпс.
Система для этой игры не слабая, вроде не должно быть таких тормозов. Celeron 2.8 GHz, 1 Gb RAM, GeForce 6600GT 128 mb. Дистанция обзора ниже половины, дистанция AI 25%.

__________________
Небо над портом было цвета экрана телевизора, включенного на мертвый канал.

Я человек современный, и меня тянет к саморазрушению.

Тогда вопрос: на каком конфиге игра идет нормально? (40-50 fps)

Есть ещё второй комп, чуть получше, Pentium 4 3.0 GHz, 1,5 Gb RAM, GF6600 128 mb.
Попробую сегодня на нём.

Источник

Проект «Морровинд»

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

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

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

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

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

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

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

Вы можете понять, какие интересные способы перемещения могут возникать при сочетании этих средств. Например, вы можете скастовать 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?)

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

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

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

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

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

(Интересно, что здесь есть три проблемы с «аргонианским парнем» (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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нам снова нужно зайти в Гильдию Садрит Моры и телепортироваться, на этот раз в Вивек. Затем мы ещё раз кастуем 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 3×3, то мы сможем вычислить настоящие внутриигровые координаты, и наоборот. Третий компонент вектора, равный 1 — это грязный хак, позволяющий нам закодировать переносы (движение), потому что в противном случае вектор (0, 0) на карте соответствовал бы вектору (0, 0) в игре. Подробнее об этом можно прочитать в Википедии.

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

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

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

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

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

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

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

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

Часть 5

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

Только я забыл, что работаю в Python и что мне придётся пройтись для каждой точки карты примерно по 2400 возможным маршрутам через внешние точки. А всего есть 1650×1900 = около 3 миллионов точек. Разумеется, можно подойти с умом и воспользоваться разными оптимизациями (например собрать достаточно близкие друг к другу внешние точки и обрабатывать их как одну, или воспользоваться неравенством треугольников (о чём я говорил в предыдущей части), или рассматривать блоки 2×2 карты, а не каждый пиксель, или использовать все 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).

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

Источник