概要
FF11のマップ、多すぎて覚えられない！
移動手段も経験も豊富なベテラン冒険者の方々にはきっとなんの障害にもならないのであろうが、初心者には
「白魔道士の限界突破のために『偉大な白魔道士の証』を取りに行きたいけど、テリガン岬？ソ・ジヤ？ってどこだよ！」
とか
「闇の王を倒しにズヴァール城？たしかザルカバード？ってことは更に隣は……どこだっけ？」
みたいな感じで本筋ではない、その場所への行き方という壁がそびえ立っている。
ウィキもFF11 DBも非常に内容が充実しておりこの上ない情報源ではあるのだが、流石にピンポイントにウィンダスからボスディン氷河に行きたい！みたいな疑問には答えてくれない。
結局地図を辿っていくしかないのだが、土地勘のない場所はデータベースのマップを追うのも難しい。
どうにかならないものかと思っていたところ、丁度仕事で化合物のグラフ構造表現の話をしていたのを思い出した。
マップって正にノードとエッジで表せそうだよね！という考えから、PythonのNetworkxというパッケージを使ってFF11のマップ移動をグラフ構造の最短経路問題として解いてみるというお話です。
似たようなことやっている人はもういそうだけど、勉強がてらということで。
結論
- ちゃんとFF11のマップはグラフ構造で表現できる
- とりあえずどのマップを辿れば目的地に行き着くかは探索できるようになった
- 本当は移動距離の情報をエッジに埋め込めればよいのだが、うまいデータの形が思いつかず断念
グラフにしてもさっぱりわけがわからない。が、nx.shortest_path(graph, source='ジュノ', target='ズヴァール城')で探索すれば、
['ジュノ', 'バタリア丘陵', 'ボスディン氷河', 'ザルカバード', 'ズヴァール城']
とかnx.shortest_path(graph, source='ジュノ', target='テリガン岬')とやれば
['ジュノ', 'バタリア丘陵', 'ジャグナー森林', 'ラテーヌ高原', 'バルクルム砂丘', 'グスタフの洞門', 'テリガン岬']
みたいな結果が得られるものができた。素晴らしい！
データの入力がきつすぎた。ひたすらFF11DBの地図を見ながら繋がっているマップを入力し、計2時間かかった。マップ多すぎ！
このデータ使ってElastic BeanstalkでWebアプリとか作ったらいい自由研究になりそう。……だけど今更利用者がいない気がする。
コード
GitHub - bobfromjapan/FF11_route_finder
Githubにも置いておいたので、なんかミスがあったらPR投げてください。
こんな感じのYamlファイルとしてそれぞれのエリアから行き先を記載していき、これをパースしてあるエリア→目的地というノード-エッジ-ノードをひたすら作って行く感じ。
あと、飛空艇や船のノードの重みを増やしておくことで、グラフで表示するとき重要都市を真ん中あたりに持ってこようというちょっとした工夫もしている。
areas: - name: サンドリア survival_guide: True home_point: True distination: - name: 東ロンフォール weight: 1 transportation: walk - name: 西ロンフォール weight: 1 transportation: walk - name: ドラギーユ城 weight: 1 transportation: walk - name: ジュノ weight: 100 transportation: airship - name: バストゥーク survival_guide: True home_point: True distination: - name: ツェールン鉱山 weight: 1 transportation: walk - name: 北グスタベルグ weight: 1 transportation: walk - name: 大工房 weight: 1 transportation: walk - name: ジュノ weight: 100 transportation: airship - name: ウィンダス survival_guide: True home_point: True distination: - name: 東サルタバルタ weight: 1 transportation: walk - name: 西サルタバルタ weight: 1 transportation: walk - name: 天の塔 weight: 1 transportation: walk - name: ジュノ weight: 100 transportation: airship
Pythonコードは適当だけどこんな感じ。
工夫としては日本語で書いたyamlを読むためにcodecsを使ってファイルオープンしたこと、パースしたyamlを上手いことfor文で回してエッジを追加したことでしょうか。
import networkx as nx import codecs import matplotlib.pyplot as plt import yaml walk_only = True graph = nx.DiGraph() with codecs.open("areas.yaml", "r", 'utf-8') as yml: net = yaml.load(yml, Loader=yaml.SafeLoader) for i in net['areas']: for j in i['distination']: if walk_only: if j['transportation']=="walk": graph.add_edges_from([(i['name'], j['name'], {"transportation" : j['transportation'], "weight":j['weight']})]) else: graph.add_edges_from([(i['name'], j['name'], {"transportation" : j['transportation'], "weight":j['weight']})]) # pos = nx.spring_layout(graph, k=1.2) # nx.draw_networkx_nodes(graph, pos, alpha=0.6, node_size=500) # nx.draw_networkx_labels(graph, pos, font_size=4, font_family="MS Gothic") # nx.draw_networkx_edges(graph, pos, alpha=0.4) # plt.show() print(nx.shortest_path(graph, source='ウィンダス', target='ムバルポロス新市街'))
一番下のSourceとTargetを書き換えれば、任意のルートの探索ができる。
また、walk_onlyをFalseにすれば、汽船や飛空艇を使ったルートも探索できるはず。
例えばwalk_only=Trueで source='ウィンダス', target='ムバルポロス新市街' なら
['ウィンダス', '東サルタバルタ', 'タロンギ大峡谷', 'メリファト山地', 'ソロムグ原野', 'ジュノ', 'バタリア丘陵', 'ジャグナー森林', 'ラテーヌ高原', 'バルクルム砂丘', 'コンシュタット高地', '北グスタベルグ', 'ムバルポロス旧市街', '2716号採石場', 'ムバルポロス新市街']
てな感じ。ちなみにムバルポロスとか行ったことないのでこの道が正しいのかわからない笑。
また、walk_only=Falseにすればウィンダス→ジュノ間とジュノ→グスタベルグを飛空艇でショートカットしてくれるので、
['ウィンダス', 'ジュノ', 'バストゥーク', '北グスタベルグ', 'ムバルポロス旧市街', '2716号採石場', 'ムバルポロス新市街']
となるよう。まあなんとなくあってそうな感じですね！めでたしめでたし。
