Morrowindをプレイする必要があります。

（警告：ここにMorrowindへの称賛のいくつかの段落があるので、それらを安全にスキップして投稿の本質に進むことができます。）

Morrowindの初めに、あなたはポケットに87個の金を入れて刑務所の船から降りたばかりの普通の衝撃を与えます（この世界では、パン1杯は金1個、約35ポンドです。。あなたの最初の仕事は、別の都市の人から荷物を受け取ることであり、シルト・ストライダー（長い脚を持つ巨大な昆虫、おそらくロンドンのバスのように永遠に酔った不気味な運転手によって運転される）に乗ることができます国勢調査局から引き抜いた鉄の短剣で生い茂った猛禽類の大群と戦う。 Morrowind戦闘システムの作成者はボードロールプレイングゲームに触発されており、アニメーターはあまりお金を払っていなかったので、あなたの短剣だけが常に見逃しているので、あなたの武器が明らかにあなたのプレーヤーの肉体に刺さっていても、実際にヒットすることを保証します。

そのため、数千回の猛烈なクリックによりマウスを数匹破壊すると、Morrowindを終了し、もっと面白いことに人生を費やすことになります。

または、プレイを続けて、疲労が誰かを叩く（そして誰かを叩く）チャンスにどのように影響するかを調べ、ゲームの仕組みを調べ、新しいマウスを購入し、バルモラに行き、私が持っている最も豊かな世界の1つに飛び込みますゲームで見られる。あなたは、組織化された宗教、外国人嫌悪、植民地主義、部族の伝説、予言、自由意志、そしてあなた自身の利益とあなたが属する組織の利益との間の優先順位の選択に関する質問を提起する物語を生きます。

そして、この研究の過程のどこかで、あなたはあなたのスロップ短剣の波がもはや通り過ぎないことに気付きます。実際、短剣はもはや傾斜していません。実際、あなたはもはや短剣を使用していませんが、恐らく性的に動機づけられ、非常に危険な生き物であるカップルに守られているダンジョンで素晴らしい剣を見つけました。あなたは神を殺し、神の魂を奪うことに決めました。荒れ地を長く歩き回るのではなく、どこかに行く必要がある場合は、唯一のお守りを使用して最寄りの寺院にテレポートし、バニーホップジャンプを行う（より速く移動することが判明したため）か、都市に浮上し、メイジズギルドに行き、テレポートを使用しますギルド、別のお守りを適用し、最終的に正しいポイントに到達します。麻薬中毒では、喜びのために都市全体をカットし、最後のセーブをロードします。グレートハウスの宝物を奪い、珍しい鎧や武器を盗んで遠くの島に行き、巨大なカニに売ります。あなたはそれが最良の価格を提供するためにそれを選んだと言いますが、実際には他の誰もがあなたを恐れています。

すべてが実生活のようです。

（ゲームの賞賛はここで終わります。）

最近、Morrowindを再プレイすることにしました。高いランクを獲得する途中で、ギルドで昇格するために完了する必要のある「アイテムを持ち込む」という絶え間ないクエストに少しうんざりしていました。そこで、ルートプランナーを作成することを考えました。 Morrowindのアクションオプションの数は非常に多いため、これは簡単なタスクではありません。

ウォーキング（または空中浮揚、自尊心のあるプレーヤーが永続的な空中浮揚効果を持つアイテムを既にエンチャントしているため）
シルトストライダー（またはボート）での旅行-ただし、必要な都市にすぐに行くことができず、都市の悪い部分の1つで交通手段を変更する必要があることを考慮する価値があります。これにはゲーム内の時間がかかりますが、プレイヤーが認識するように、動きは即座に発生すると想定します。
メイジギルドのテレポートも瞬時に行われます。マジシャンと話をする必要がありますが、実際には彼らは善人です。
神/アルムシヴィの介入-ここではすべてがより興味深いものになります。神の介入（神の介入）は私たちを最も近いインペリアルフォートにテレポートさせます（Morrowindは帝国の一部ですが、まだこの考えに一致していません）、そしてAlmsiviの介入（Almsiviの介入）は私たちを最も近い法廷の神殿（Morrowindの公式の宗教であり、存在しました帝国のずっと前に）。
マーク/リコール-2つの呪文、1つはマークを配置し、2つ目はこのマークにテレポートします。
Propylons（Propylon Indices）-昔、誰かが島に円を描くように美しい要塞をたくさん作ることを決めました。朗報：それらをすべて円でつなぐテレポーテーションルームがあります。悪いニュース：これらの要塞のそれぞれにプロピオンタグが必要になりますが、それらを見つけるのは難しい場合がよくあります。さらに、これらの要塞にはさまざまな生物が群がっており、通常、それらの近くにいるのはあまり快適ではありません。今のところ、それらを分析から除外します。

リングラインにサメが出現するため、わずかな遅延が予想されます。

これらのツールを組み合わせると、どのような面白い移動方法が発生するかを理解できます。たとえば、Almsivi Interventionをキャストして最も近い寺院にテレポートし、次にDivine InterventionでImperial Fortにテレポートし、ギルドテレポートを使用してすぐに別のAlmsiviをキャストして別の都市に入れることができます。

しかし、もちろん、これらのMorrowindディスプレイスメントマップを読み取り、グラフを作成し、Dijkstraのアルゴリズムを実行するのに少し時間を費やしただけでは退屈です。まず、このような良い投稿は機能しません。第二に、もし私たちが荒れ地のどこかにいたとしても助けにはなりません（中央のファラスマリオン、バレンバリオン、ロザラン、インドラニオン、ファレンサラノ、アルドルーン、マールガンに囲まれたこのエリアをご覧ください？）

最後に、私はあなたに嘘をついたので、 Tamriel Rebuiltを含むいくつかのかなり大きなファンがMorrowindに追加されました。実際、この島はMorrowindではなくVvardenfellと呼ばれ、MorrowindはVvardenfellが属する州です。 Tamriel Rebuiltの作者は、この州全体を再現しようとしました（はい、MorrowindはすべてMorrowindという名前でゲームに参加しませんでした。さらに、TamrielはMorrowindが属する帝国全体であり、はい、Tamriel RebuiltはMorrowindと呼ばれます。）

私たちの人生を簡素化するために、ゲームファイルからこのデータを抽出する体系的な方法を見つけることをお勧めします。これを行うと何がわかるか想像してみてください！人口統計！人口のヒートマップ！カウント！価格と動きのグラフも作成できます！

Morrowindプロジェクトの次の部分では、紛らわしいバイナリ形式、奇妙な仮定、線形代数、Python言語と戦い、おそらくMorraindの伝承とそのゲームの仕組みについてさらに学習します。

パート2

Morrowindプロジェクトの後半では、ひどいバイナリをPythonインタープリターのメモリ空間で美しいデータ構造に変換し始めます。技術的には、とにかくバイナリデータのままですが、それほど深くは行きません。そうでなければ、私たちはすべてが原子で構成され、実存的危機があり、それには何も良いものがないことを認識します。

私は...私もコードを見ません。 木材、石、湿地のonlyだけが見えます...

データダンプ

Morrowindとそのフォロワー（Oblivion、Skyrim、Fallout 3および4を含む）を含むBethesda Softworksによって作成されたElder Scrollsシリーズのゲームでは、ゲームの基本データ（つまり、テクスチャではなくマップと異なるオブジェクトの場所/サウンド/モデル）はESM形式（Elder Scrolls Master）で保存されます。 Morrowind以来進化してきたBethesda開発者は、ますます多くの機能を追加しましたが、基本的な考え方は変わりません。これらのファイルはさまざまなタイプのレコードのコレクションです。

たとえば、性別、人種、AIキャラクターの行動などの定義を含む、ゲームのキャラクターを識別するNPC_レコードがある場合があります。また、ARMOおよびWEAPエントリを参照するキャラクターのインベントリなど、他のエントリへのリンクを含めることもできます。 CELLレコードは、ゲーム内のセル（場所自体）を記述し、NPC_、ARMO、WEAP、CONT（チェストなどのコンテナー）など、このセルに含まれるすべてへのリンクを含みます。ここではMorrowindバイナリ形式について詳しく説明します。Bethesdaゲームの新しいリリースはすべて、ゲームデータファイルの形式の小さな変更をリバースエンジニアリングするための多くの興味深いタスクをプレイヤーに約束します。

Bethesdaは、この形式のゲームデータファイルにゲームセーブファイルオーバーレイを作成するというスマートなアイデアを思いつきました。たとえば、特定の場所（エルダースクロールシリーズのゲームでよく発生します）で誰かを殺した場合、保存されたファイルには、対応する殺されたNPCを示すCELLレコードのオーバーライドが含まれます。残念ながら、このアイデアは、他の多くの賢いアイデアのように、私のプロジェクトにはまったく影響しませんでしたが、それでも興味深いものです。

ただし、他にも問題があります。セルは外部でも内部でもかまいません。外側のセルは正方形で、端から端まで互いに接続されており、Morrowindの見事なオープンスペースを作り出しています。内部セルには別の話があります-それぞれが独自の小さな現実にあり、ドアによって他のセルに接続されています。ドアはここでは基本的にテレポートとして使用されます。外側のセルにある小さな家は内側からはるかに大きいことが多いため、プレイヤーが内側に入ったときの位置を確実に判断することはできません。

したがって、Morrowindを移動する方法のグラフを再作成する場合は、ドアを移動する別の方法としてそれを考慮する必要があります。

Almsivi / Divine Interventionスペルに関しては、すべてのテンプルとインペリアルフォートに特別なマーカーオブジェクトがあります。これにより、ゲームは特定のスペルをキャストするプレイヤーをテレポートする場所を決定します。これは、マーカーが屋内にあるため外部セルでも簡単ですが、内部セルの場合は複雑です。 Morrowindはプレイヤーが最後にいた外部セルを使用すると主張する人もいます（これは病理学的ケースにつながることがあります-たとえば、ギルドテレポートを使用して部屋から部屋へテレポートします。その後、介入呪文を唱えると、マーカーの近くに移動します最初のギルドであり、2番目のギルドではありません）、オープンソースのMorrowindエンジンであるOpenMWの実装では、プレーヤーに最も近いセルを参照として使用してこの問題を解決しようとしています。何らかの理由で、Morrowindのコピーが正しく動作しているため、この動作をシミュレートします。

NPCが輸送サービス（シルトストライダー、ボート、またはギルドテレポート）を提供している場合、これはそのレコードにエンコードされることがはるかに優れています。

一般に、必要なものがすべて含まれているため、CELLおよびNPC_レコードからすべてを取得する必要があるようです。

CELLおよびNPC_レコードからすべてを引き出す

このすばらしい仕様に従ってバイナリデータをデコードすることは完全に可能で興味深いと思いましたが、低レベルのESMファイルエディターであるMorrowind Enchanted Editorをごまかすことにしました。特に、「テキストファイルにダンプ」機能を使用しました。この機能は、読み取り不可能なバイナリカオスをASCII読み取り可能なカオスに変換します。

トッド・ハワード自身が作成したと思われるトッドのスーパーテスター・ガイに会いましょう。

すでにこれを使用できます。レコード内の各要素は個別の行にあり、サブレコードの形式のキーを持っています（たとえば、FNAM-フルネーム、RNAM-レースの名前など）。まず、NPC_およびCELLレコードのみを抽出し、データをトークンに変換し、それらをキーと値のペアのストリームに変換します（つまり、NPC_NAME todd文字列はタプル（NAME、todd）になります。エントリを参照NPC_）。

（ここでは、ソースコードをブロックごとに表示して説明していましたが、今日はWordPressが私に反することが判明しました。後でGitHubで公開することをお約束します。＆amp; 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リストに解析することは、それほど難しいタスクではありません。最も簡単な方法は、ストリームをクラスのコンストラクターに渡し、そこから初期化に必要なものをすべて読み取らせることです。ただし、次のNPCのNAMEサブネームが表示されたら解析を停止する必要があることを忘れないでください。すでに使用している場合はすでに遅すぎるため、使用せずに次の要素を参照できるイテレータを定義する必要があります。

聖杯を探している場所のリストを解析することも非常に簡単です-この例を見てください（これはトッドのスーパーテスターガイが私たちを提供できる場所の1つです）：

 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

文字通り、x、y、z座標および角度（これは重要ではありません）の6つの数字のリストを取得します。内部セルにいる場合、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)]

（興味深いことに、タルヒエルという名前の「アグロニア人」には3つの問題があります。最初に、彼の種族の名前はアルゴニア語と正しく綴られています。次に、彼はアルゴニア人ではなく、森のエルフです。彼には精神的な問題がありますが、能力もあります。

次に、CELLデータのデコードに進みます。CELLデータには、他の興味深いポイントがあります（たとえば、プレイヤーが知覚できるほとんどのデータが含まれているなど）。しかし、私たちはすでに基本と最も退屈なことについて話しましたので、より速く動き始めて、動きの本当のグラフを作成することに取り掛かりましょう！

パート3

今日、Morrowindプロジェクトでは、美しい写実的な世界で3Dシーンの説明を視覚化するプロセスを数十年かけて研究し、それらをゴミ箱に捨てます。

最後に、WordPressで重要なフォーマットを試してみました。 彼が少なくとも写真の中のテキストを台無しにしないことを願っています。

セルデータの読み込み

Morrowindセルの解析にはいくつかの課題があります。 1つ目は、セルに一意の名前を付ける方法です。内部セルの場合、「Uncle's Workshop Sweet Share」などのNAMEフィールドがあるため、これは簡単です（これは冗談ではありません）。ただし、外部セルには約3つの異なるタイプがあります。 1つ目は、写真のような都市と注目すべきランドマークです。 RGNN、NAME、および巨大な外側の正方形セルの位置座標があります。ただし、Vivekセルは多数あるため（Vivekは巨大であるため）、領域の座標を使用してそれらを識別します。

次に、荒地のセル、たとえば、アスカディアン諸島の地域の他の部分は、このメソッドとその外部座標を使用して呼び出されます。

最後に、セル名とエリアのない外部セルがありますが、座標があります-TES構築セットでは、それらはWilderness [x、y]と呼ばれるため、同じ名前を使用します。

これらの各エリアはそれ自体が都市であり、すべてブリッジで接続されています。 さらに、彼らは水の上にいます。 ここに住みたいとは思わないだろうか？

次のステップでは、各セルのコンテンツを解析します。これは、基本的にはオブジェクトのIDと、リンクの現在のインスタンスに関するその他のデータです（たとえば、位置、健康の量（NPCの場合）、または目的地（輸送サービスを提供するドアまたはNPCの場合））。

そして、はい、リンクも削除できる場合があります-しかし、単にリンクをデータファイルから削除するのではなく、単に削除済みとしてマークされます。おそらくこれは、それらを削除するにはファイル全体を書き直さなければならないためです（ファイル内のすべてのポインターを再カウントする必要があるため）-今日はこれはナンセンスですが、2002年にはおそらくあまりにも多くのリソースを必要とします。

オブジェクト定義は、参照される前または後に表示される可能性があるため、2つのパスでファイルを解析する必要があります。最初にリンク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プレーヤーをセルから転送できるセルの宛先ポイントのリストに場所を追加しませんでした（たとえば、テレポーテーションサービスの場合）-セル内のドアがつながる場所のみをリストします。

完全版はこちらですが、きちんと-約10MBの重さです。

この情報のみを使用しても、美しいグラフを作成できます。たとえば、GraphVizで上記の図を作成しました。この図では、ノードはセルであり、それらの間にドアがある場合、エッジで接続されています。中央の大きなグループはVivecです。小さなグループが写真の周りに散らばっていますが、これらはそのような大都市ではありません（バルモラ、カルデラ、アルドルナなど）。星のような形もここにあります-中心は名前のあるセルであり、それに接続されたセルは内部にあり、そこに貫通できます-これらは小さな集落です。

しかし、私たちはこのために努力しませんでした。私たちは、ドアだけでなく、世界が私たちに提供しなければならないすべての助けを借りて、ポイントAからポイントBに到達する方法を知りたいです。実際の変位グラフをどのように記述するかについて話しましょう。

ルートプランナーの作成

明らかに、ゲームには無数のポイントがありますが、それらすべてを考慮する必要はありません。出発地点、終了地点、およびルートが通過できるすべての重要なポイントのみを考慮する必要があります。したがって、この方法でグラフのノードを簡単に指定できます。

「移動サービス」（NPC /ドア）を提供するオブジェクトごとに、オブジェクトの位置と移動ポイント。
各神聖/ Almsivi介入マーカーの場所。

以上です。ルートの説明は次のようになります。「出発点から、このドアに移動し（ポイント1）、別のセルに移動し（ポイント2）、輸送サービスを提供するNPCに移動し（ポイント3）、別の都市に移動します（ポイント4 ）、目的地に接近します（ポイント5）。」したがって、グラフのノードを接続する方法を見てみましょう。

移動を提供する「サービス」の場所（ドア、テレポート/ NPCドライバーのシルトストライダー）は、長さ0のリブによって目的地に接続されます。
2つのノードが1つのセルにある場合（または両方が外部世界にある場合）、ノード間の距離に比例する長さのエッジで接続されます（つまり、外部世界の山や内部セルの貫通できない障害物は無視します）。
各ノードは、最も近いテンプル/インペリアルフォートに接続します（外部セルの場合は直接ユークリッド距離、内部セルの場合は最も近い外部セルからの距離を使用します）。

この方法を使用して、6424の頂点と16065のみのテレポーテーションエッジで構成される変位グラフに到達しました-ドア/輸送サービス/介入呪文が含まれていますが、セル内の直接的な動きは含まれていません。この場合、任意の2つの間の距離を見つけるのは非常に簡単ですその場でドット。

最短経路探索アルゴリズムの興味深い特徴の1つは、2つのノード間の最短経路（1つのペアの最短経路）を見つけることは、ノードからグラフのすべての点までの最短経路（最短の経路を見つける）一点からのパス）。直感的に、これは、1ペアのタスクの理想的なパスにグラフ内の任意のポイントを含めることができるために発生します。したがって、1つのソースからこのポイントまでの最短パスを計算します。

ダイクストラアルゴリズムは、O（| V |²）（| V |はグラフ内のノードの数）の1つのポイントからすべてのポイントへの最短パスを見つけることで、こうしたことを非常にうまく処理します。未探索の頂点を格納し、O（1）に最も近いフィボナッチヒープを使用して改善できます。これにより、O（| E | + | V | log | V |）の時間の複雑さがわかります。 6,000のピークのみの検索にあまり時間がかからないことを決定したため、実装しませんでしたが、後で実行する可能性があります。

この実験では、アリオンを実験用のネズミとして使用しました。彼はテルバンニ家のクエストラインの後半のメインクエストの提供者になり、輸送サービスがほとんどない荒野のやや離れた塔に住んでいます。そのため、Mark / Recallを使用して到達できますが、そのクエストはゲームワールドのさまざまなポイントにあなたを送ることができ、その中に入るとすぐに重要なタスクになります。

このグラフをダイクストラのアルゴリズムに供給した後（約10分かかり、非常に長い時間）、2つのリストを取得しました。各ポイントの最初のリストは、アリオンからこのポイントまでの最も安い（この場合は高速）ルートの重みを示します 2番目では、各ポイントについて、最速ルートの前のポイントが示されます。このおかげで、興味のあるポイントまでこれらのリンクをたどることにより、最適なルートをすばやく再作成できます。

たとえば、アリオンから島の反対側にあるクロマーマレンのダンマー要塞へはどうやって行くのでしょうか？このように：

 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))]

ここでの欠点は、ノード間の遷移に必要な移動方法が実際には表示されないことです。したがって、旅行計画を解読するには、ゲームの知識が必要です。基本的に、ディヴァインインターベンションスペルを使用して、ヴォルフォリンホール砦に到着し、その後インペリアルサンクチュアリに入り、それを要塞の内部に行き、メイジギルドに入り、バルモラにテレポートし、そこからクロルマレンに発着します。

地図の南西端にある離島にあるサリソフの部族の墓に入るのはどうですか？どこも簡単です。

 [(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))]

サドリス・モラ・ギルドに行き、今度はVivecにテレポートする必要があります。それから私たちは再び神の介入をキャストし、エボンハートで自分自身を見つけます。エボンハートは墓と同じ島からの同じ船旅にあります。

さらにMorrowindプロジェクトでは、プランナーの推奨事項をゲームマップに配置することで、もう少しわかりやすくするようにします。地図に他のものを載せるかもしれません。おそらくこの記事にはソースコードさえ含まれているでしょう！

パート4

Morrowindプロジェクトに再びようこそ。このプロジェクトでは、テクノロジーを使用して、政治的利益のために人々に圧力をかけます。

今週土曜日の朝、二人の二日酔い魔術師テルバンニが私の家に近づいた。昨夜、彼らはグラスをスキップするためにマスターアリオンの塔に行きました。グラスはすぐにグラスになりました。要するに、アリオンはなんとか逃げることができ、それ以来誰も彼を見ていません。さらに、来週の月曜日には理事会が開催され、アリオンの不在は災害となります。

ウィザードは、アリオンがエージェントの努力を集中し、会議の前に彼を見つける時間があるためにアリオンがいる場所を地図上に示すことができるかどうか私に尋ねました。

このブログについてどんな記事を書くことができるか想像して、私は同意しました。

カウント再生

ゲームの内部時間では、シルトストライダーまたはボートでの移動は瞬時ではないため、最初は変位グラフのエッジ間のウェイトを変更する必要がありました。ただし、距離から計算することもできます。移動速度はゲームパラメータであり、デフォルトは1時間あたり16,000ユニットです。たとえば、Seydi NingからBalmoraまでの距離は約55,000ユニットです。したがって、ゲームの開始時に歩行ではなく公共交通機関にお金を使うことにした場合、Balmoraに着いて3.5時間以内に最初のクエストを完了します。

場所間の歩行時間を決定するには、調査も必要でした。ゲームの最小歩行速度は実世界の1秒あたり100ゲーム単位であり、ゲーム時間はデフォルトで実際のゲーム時間の30倍速くなります。つまり、16,000ユニットの通過には約16000/100 * 30/3600 = 1時間20分の再生時間が必要になります。ご覧のように、これはシルトストライダーに乗るよりもそれほど遅くはありません。それを見れば、その理由を理解できます。

明らかに、NPCクラスの動きの名前に「ギルドガイド」という単語が含まれている場合、魔法であるため、それと一緒に移動するのに時間がかかりません。

グラフを再構築し、それに対して再びダイクストラアルゴリズムを実行することにより、アリオンがゲーム世界のどこにでも移動するのにかかる時間を、彼が最速ルートを使用したという事実を考慮して簡単に決定できます。最短の移動時間がわかっているグラフのすべてのポイントを通過する必要があり、合計移動時間（このポイントに移動する最短の時間+このポイントから目的のポイントまで歩く時間）が最小になるポイントを見つける必要があります。

私が使用したことのない最適化があります。実際、グラフ内のポイントは、徒歩以外のどのルートでも到達できるものにしか興味がありません。この場合を考えてみましょう：ポイントへの最短経路がテレポーテーションからポイントAに作成され、徒歩でポイントBに、そして徒歩でポイントCに（これはすべて直線で）作成された場合、AからC（ここでは、Arionは浮上して直線上のポイント間を移動できるため、外側のセルの3つのポイントは三角形の不等式に従うと仮定しています）。

しかし、もちろん、テルバンニの魔法使いにゲーム内座標のリストを与えるだけでは価値がありません。彼らにはカードが必要で、私は彼らにカードを渡します。奇妙なことに、アフィニティマップ。

線形代数の迅速で不完全な、ほとんど間違いのある導入

ここでの問題は、ゲームマップ上のピクセル座標のペアをゲームワールドの座標に変換する方法を見つけたいということです。幸いなことに、この変換には重要な特性があります。ゲームマップ上の任意の2点間の線は、世界自体にも直接接続されます。このような変換は、アフィン変換と呼ばれます。転送、回転、反射などの基本的な操作から作成できます。

良いニュースは、それらが行列積として表現できることです。

b e g i n p m a t r i x x_{G A M E} y_{G A M E} 1 e n d p m a t r i x = M b e g i n p m a t r i x x_{M A P} y_{M A P} 1 e n d p m a t r i x

$\ begin {pmatrix} x_ {GAME} \\ y_ {GAME} \\ 1 \ end {pmatrix} = M \ begin {pmatrix} x_ {MAP} \\ y_ {MAP} \\ 1 \ end {pmatrix}$

したがって、マップ上に座標のペアがあり、このマトリックスがM 3x3である場合、実際のゲーム内座標を計算でき、逆も同様です。ベクトルの3番目のコンポーネントは1で、ダーティハックです。これにより、マップ上のベクトル（0、0）がゲーム内のベクトル（0、0）に対応するため、転送（動き）をエンコードできます。詳細については、 Wikipediaをご覧ください。

このような行列をどのように見つけるのでしょうか？さて、これを使用して複数のベクトルを一度に変換できます。

b e g i n p m a t r i x x_{G A M E 、 1} ＆ x_{G A M E 、 2} ＆ x_{G A M E 、 3} y_{G A M E 、 1} ＆ y_{G A M E 、 2} ＆ y_{G A M E 、 3} 1 ＆ 1 ＆ 1 e n d p m a t r i x = M b e g i n p m a t r i x x_{M A P 、 1} ＆ x_{M A P 、 2} ＆ x_{M A P 、 3} y_{M A P 、 1} ＆ y_{M A P 、 2} ＆ y_{M A P 、 3} 1 ＆ 1 ＆ 1 e n d p m a t r i x

$\ begin {pmatrix} x_ {GAME、1}＆x_ {GAME、2}＆x_ {GAME、3} \\ y_ {GAME、1}＆y_ {GAME、2}＆y_ {GAME、3} \\ 1＆1＆1 \ end {pmatrix} = M \ begin {pmatrix} x_ {MAP、1}＆x_ {MAP、2}＆x_ {MAP、3} \\ y_ {MAP、1}＆y_ {MAP、 2}＆y_ {MAP、3} \\ 1＆1＆1 \ end {pmatrix}$

そして、これは次のように書き直すことができます（マトリックスを右に反転し、方程式全体にそれを掛けることにより）：

M = b e g i n p m a t r i x x_{G A M E 、 1} ＆ x_{G A M E 、 2} ＆ x_{G A M E 、 3} y_{G A M E 、 1} ＆ y_{G A M E 、 2} ＆ y_{G A M E 、 3} 1 ＆ 1 ＆ 1 e n d p m a t r i x b e g i n p m a t r i x x_{M A P 、 1} ＆ x_{M A P 、 2} ＆ x_{M A P 、 3} y_{M A P 、 1} ＆ y_{M A P 、 2} ＆ y_{M A P 、 3} 1 ＆ 1 ＆ 1 e n d {p m a t r i x}^{- 1}

$M = \ begin {pmatrix} x_ {GAME、1}＆x_ {GAME、2}＆x_ {GAME、3} \\ y_ {GAME、1}＆y_ {GAME、2}＆y_ {GAME、3} \\ 1＆1＆1 \ end {pmatrix} \ begin {pmatrix} x_ {MAP、1}＆x_ {MAP、2}＆x_ {MAP、3} \\ y_ {MAP、1}＆y_ {MAP、 2}＆y_ {MAP、3} \\ 1＆1＆1 \ end {pmatrix} ^ {-1}$

実際、ゲームワールドとマップで3組の座標を取得した場合、それらを使用して関係を再作成できます。さらに、この場合、マップ座標行列の行列式はゼロになり、逆行列を持たないため、これらの3つの点を同じ線上に置くことはできません。

したがって、3つのポイントのゲーム座標を選択しました。これらは非常に広く分布しており（エラーを最小限に抑えるため）、マップ上の対応するピクセル座標を決定しようとしました。

その結果、私はこのマトリックスに到達しました：

M = b e g i n p m a t r i x 185.38 ＆ - 0.43327 ＆ - 126720 1.2986 ＆ - 0.018372 ＆ 218470 0 ＆ 0 ＆ 1 e n d p m a t r i x

$M = \ begin {pmatrix} 185.38＆-0.43327＆-126720 \\ 1.2986＆-0.018372＆218470 \\ 0＆0＆1 \ end {pmatrix}$

それをテストするために、計算に使用した3つの基準点（赤）とアリオンの元の位置（青い点）をプロットしました。彼の家の外側のドアはゲーム座標（85730.77、117960.3、5081.284）にあります。（1147.33、555.21）に添付されます。

ここからあなたの家が見えます！

次のパートでは、どのようにしてアリオンを見つけ、テルバンニ評議会を崩壊から救ったかを説明します。

パート5

Arionがどこにあるかを視覚化することは、すでに非常に近いです。最も愚かなアプローチを選択しました：マップのすべてのピクセルを調べ、それぞれをゲームワールドのポイントに変換し、アリオンがそこに到達するのにかかる時間を見つけます（上記の方法を使用して、グラフのすべてのポイントを通過し、最短の移動時間を知っており、合計移動時間（このポイントまでの最短の移動時間+このポイントから目的地までの歩行時間）が最小になる時間を見つけます。

私がPythonで作業していること、そしてマップ上の各ポイントについて外部ポイントを通る約2400の可能なルートに行かなければならないことを忘れただけです。そして、合計で1650x1900 =約300万ポイントです。もちろん、賢明にアプローチしてさまざまな最適化を活用することができます（たとえば、互いに十分に近い外部ポイントを収集して1つとして処理するか、三角形の不等式を使用する（前の部分で述べたように）、またはすべてのピクセルではなく2x2カードのブロックを考慮する）、またはプロセッサの1つではなく4つのコアすべてを使用します）。または、C ++プログラムでソリューションをファーム化できます。

そのため、既知の外部座標のリストとそれらへの最短ルートの時間のダンプと、興味のある300万以上のマップポイントのゲーム内座標をファイルにダンプしました。プログラムはそれらを取り、アリオンが彼の塔からそこに着くまでにかかる最短時間を各座標に与えました。実際、これには40行のコードと10秒の計算が必要でした。鉄と直接通信する場合、問題をどれほど迅速に解決できるかは驚くべきことです。

次に、matplotlibの等高線グラフを使用して、結果のヒートマップを視覚化しました。元の解像度でマップにオーバーレイすることはできませんでしたが、ウィザードは依然として非常に感銘を受け、スタートアップの資金を探したいと思ったら連絡できると言いました。

!

実際には理にかなっています。アリオンの家の周りには2時間のサークルがあり（島の北東部）、そこから神の介入を使ってウルバンホールまで歩いたりテレポートしたりできます（ヴァンダーフェルの東の島へ）。ウルヴァリンホールにはメイジズギルドがあるため、4つの主要都市（島の西端に沿った円）の1つに即座に移動できます。つまり、2時間で行ける場所はかなりあります！

その後、彼はシルト・ストライダーまたはボートに乗ることができました。 4時間で、彼はかろうじてグニシス（島の北東の角）またはマールガーナ（主要な入植地の周りの4時間のサーキットの上部にある小さな弧）に到達することができました。もちろん、彼は出発点から4時間歩くことはできましたが、遠くに行くことはありませんでした。

6時間で島のどこにでも行くことができ、8時間でダゴンフェラの北端に到達することができました。これはヴヴァルデンフェルの北にある小さな島です。最後に、約11時間後、彼はMorrowindの最も孤立したコーナーでBolshegolovと朝食をとる可能性がありました。おそらく彼はそこでビジネスをしていたのでしょうか？

ウィザードは、アリオンを最後に見たのは午前2時頃だったので、この時までに彼はほぼ10時間欠席していたと言いました。幸いなことに、彼が最も効率的なルートを選択してタワーから可能な限り離れることができるかどうかを確認しようとしていたときに、隣のキャビネットから大きな音が聞こえました。そこから、眠っているが無傷のアリオンが落ちました。

結局、彼は私のアウトライングラフが大好きで、壁に掛けました。タワーマネージャーは、アリオンのクレイジーパーティー後に失われた人々を見つけるために、まだそれを使用していると言う人もいます。

Morrowindプロジェクトの次の部分では、Vvardenfell国家統計局への私の任命について話し、島の人口統計を分析します。

パート6

それで、アリオンは彼の塔に戻り、島の全人口が彼の旅行の有効性を最大にしました。次は、別のタスクを実行して、さらに美しい写真を作成します。次の質問は簡単でした。これらの人々はどこに住んでいて、何をしていますか？

ゲーム内の座標をマップ上の座標に変換し、人口のヒートマップのようなものを作成する、優れたマトリックスのフルパワーを使用してみましょう。パズルのすべてのピースをすでに持っているため、これは簡単です。すべてのNPCがどこにいて、何をしているのか、人種と性別を知っているからです。 NPCを使用する場合の唯一の問題は、セル内です。内部空間は完全に独立したミニワールドであることを覚えていますか？これは、2つのドアの座標を取得し、ドアに対するNPCオフセットを追加するだけでは、キャラクターの位置を単純に推測できないことを意味します。私たちは世界をレビューするだけなので、私はそのような正確さを気にしないことに決めました：NPCの外部の場所は単に最も近い外部のドアの場所であり、（外に出るために通過しなければならないセルの数によって）近くに到達することができます。

これらのツールを使用して、世界中のすべてのNPCを調べ、外部の場所を取得して、マップ上の座標に変換しました。これらの座標が蓄積されたマップのサイズのマトリックスがありました。各ピクセルの数は、外部座標がこの正方形に対応するNPCの数でした。これは、人口密度の高い屋内スペースのドアに不均衡な数の人々が集まることを意味しました。これは最適ではありませんでした。これは、画像で見るのが難しいためです（最終的には1ピクセルです）。さらに、これはゲーム内の現実をあまり反映していません。まず、個々の都市/地域の人口に関心がありますが、人々はまだ1つの場所に立っておらず、近所をさまよいます。

だから私は私のマトリックスに適用しましたガウスぼかし、つまり、10人の代わりに約2.2が割り当てられます。近隣のピクセルには約2.2-1.1、元のピクセルから2ピクセルのピクセルには-0.5などが割り当てられます。これは、人々を細かく切り刻み、身体のこれらの部分を投げて、そこから便利なヒープが組み立てられるようにするという事実に似ています。

これが終わったら、すべての値が0から1の範囲になるようにマトリックスを正規化し、matplotlibで利用可能な多くのカラーマップの 1つを適用し（bluesと呼ばれるマップが好き）、元のマップと混合しました。また、デフォルト値の外観が気に入らなかったため、入力値をカラーマップに転送する前に変換する機能を試しました- ロジスティック関数を選択しました：

f (t) = \frac{1}{1 + e^{- k (t - c)}}

$f(t) = \frac{1}{1 + e^{-k(t-c)}}$

ここでは方法論を使用していません：変数

は、曲線の勾配（カラーマップの左側から右側への値の移動速度と増加する明るさ）、および変数

k

$k$

は関数のセンタリングを変更するので、画像がよく見えるようになるまでそれらを試してみました。これを念頭に置いて、結果として得られたものを見てみましょう！

c

$c$

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

大規模な集落では、暗いスポットがありました。：ボトムアップからのVivek（と彼の隣にEbonheart）、その後、Balmora（島の南西部にある）、Sadrithモラ（東）、Ald'ruhn（Balmoraの北）とGnisis（ALDの北東"フリース）。ここには小さなスポットもあります-これらは小さな集落、または大きなダンジョン/要塞/聖域です。

他に何ができますか？マップ上にすべての暗いエルフをプロットしてみませんか？はい、簡単に、すべての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')

はい、それはまさに人口のヒートマップのように見えます。多すぎる、または少なすぎる場所を確認することはできますか？これらの2つのレイヤーを上下に分離して、人口全体で暗いエルフのシェアを得ることができます：

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')

この写真では、パラメーターをいじる必要がありました（ぼかし半径を大きくし、S字曲線の中心を0.5に移動しました）が、暗いエルフ（アボリジニMorrowind）は島の南西部ではあまり見られず（よりコスモポリタンで見知らぬ人に親切です）、東部地域やアシュランダーキャンプ（ほぼ完全に構成されています）でより多く見られます。

他に何ができますか？ Morrowindには奴隷制があります！すべての奴隷が集中している場所を見つけましょう：

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％に設定していることに注意してください）。そのうちの1つは、北東のテルモラ市です。それは都市の支配者が「男性の存在を好まない」ためであり、この都市のすべての住民は実際には女性です。別の場所は、南東のオディルニランで、フラール家に襲われたテルバンニ要塞です。北西にはAssuがあり、2つの魔術師がいます。そしてその北にはTel Uviritがあります-Telvanniクエストラインの一部としてプレイヤーのために建てられた要塞です。ゲームの開始時には、プログラムは無効になっています（そして表示されません）。もちろん、これは気にしません。

おわりに

最後に、すべてのグラフを一連のモジュールに入れるために使用したコードを壊し、それをGitHubにアップロードしました。Pythonツール（NumPy、SciPy、matplotlib、およびPIL）の定期的な科学スタックとC ++コンパイラが必要になります。受け取ったゲームデータダンプを公開するのは悪い考えだと判断したので、自分でそれを行う必要があります。元のMorrowind.esmデータファイルとEnchanted Editorが必要です（ダンプの作成手順はREADMEで説明されています）。

とは言っても、コードを再度実行すると、この投稿で使用したものに似た一連の画像が表示され、非常に満足していました。

Morrowindプロジェクト