Point
■広大な銀河を舞台にしたMMOスペース・アドベンチャー・ゲーム『Elite:Dangerous』で、銀河を股にかけたレースの最高記録が達成された
■このレースは太陽系Solから22000万光年離れたコロニア星系までの飛行時間を競うもので、新記録は1時間38分11秒となった
■このニュースの一番の驚きは、この記録を作ったのがテキサス大学の教授で、グラフ理論を使ったルート検索プログラムを自作することで最短ルートを見つけ出したということ
ゲームにもかかわらずマップ内で遭難者が出たことでも有名な、『Elite:Dangerous』(E:D)で、またも次元を超えたニュースが話題になっています。
今回報道されているのは、太陽系Solからコロニア星系までの22000万光年の飛行時間を競うレースで、最速宇宙記録が塗り替えられたというものです。
これまで最短だった「CMDR St4r Fox」（CMDRはゲーム世界の宇宙船乗りたちの呼称、コマンダーと読む）の記録1時間50分32秒を約12分更新して、1時間38分11秒のワールドレコードを達成したのです。
「ゲームでしょ？ それの何がすごいの？」とツッコミたくなる気持ちもわかりますが、このニュースで注目を集めているのは、この記録を作った人物が現職のテキサス大学コンピュータサイエンスの教授で、専門分野の知識をフル稼働させて、レースの最短ルートを計算したということです。
大学教授が本気出してゲームやってみた、というこのニュースは科学的にも興味深く、教授の所属するテキサス大学ダラス校が自ら公式サイトでこのニュースを報告しています。
https://www.utdallas.edu/magazine/11465/professor-wins-spaceflight-simulation-game-world-record/
大人気ない？ 科学的テクニックを使ってゲーム記録更新
記録を作ったのはテキサス大学ダラス校の教授、Kevin Hamlen博士と、副操縦士を努めた彼の6歳の息子Will君のコンビです。
ゲーム内の宇宙で最短で移動するなんて、目的地まで真っ直ぐ飛べば良いんじゃないの？ とゲームを知らない人間は安易に考えてしまいそうですが、「E:D」は非常にシビアに作られているゲームです。
ゲーム内におけるワープ航法「Frame Shift Drive（FSD）」を利用するには、途中の経路に障害物がなく、1回のワープで飛行できる距離は燃料に依存するなど、色々と利用に制約があります。
そのため、数々の設定可能なワープポイントを経由し、燃料の補給も適切に行いながら、着実に目的地へ近づいていくという作業が必要になるのです。
こうした形式で、目的地への最短ルートを計算する方法はグラフ理論の最短経路問題として考えることができます。
グラフというのは、頂点とそれを結ぶ経路（パス）で構成された図形のことで、グラフ理論の最短経路問題は、それぞれの経路に距離や移動時間、移動に要する燃料などで重み付けをして、最小コストの移動経路を発見するという離散数学の問題です。
グラフ理論は交通網、分子構造、コンピューターネットワークなどのモデル化や解析に使われる理論で、まさにHamlen氏の教えるコンピュータサイエンスにも関わっている問題でした。
このことに気づいたHamlen博士は、ゲーム内の星図データをダウンロードし、グラフ理論を用いてルート計算するアルゴリズムの開発に乗り出したのです。
「E:D」は天の川銀河の全てをゲームマップとしており、観測で確認されている領域は再現されています。まだ未観測の領域については、独自の設定で作られています。
Hamlen博士は、130万以上の天体を含む星図をデスクトップPCで経路計算するために、様々の技術的なアプローチを試みたといいます。
ヒープデータ構造、距離空間、高速データバッファリングするメモリマップファイルや最新のIntelプロセッサのベクトル演算など、多くのアルゴリズムとプログラミングのトリックを利用し、4時間近くを掛けてコードを書くことで、20,000光年のルート検索を約1分でこなすルート計算環境を整えたのです。
