# メギド72のルート探索をしてみた話
この記事は，[みす51代 Advent Calender 2019](https://adventar.org/calendars/3868)の16日目の記事です．

2018年は[派手に業をぶちまけさせていただきました](https://hackmd.io/@aak1GejfT-KyRQnF82xx8Q/S1FUIqfxN?type=view)，zuzuです．
2019年もバ美肉ブームは健在ということで．興味のある方はぜひ読んでください❤️

うってかわって，今年はとても健全なんですね．
皆さんは**メギド72**というゲーム，ご存知でしょうか？

…………エ？！…………知らないッ？！
2019年日本ゲーム大賞優秀賞をスマホゲームとして唯一受賞したゲームなんだぜ！！！！！

メギド72がなんたるかを知って欲しいので，解説をはじめるね！

## メギド72とは
設定がモリモリ盛りだくさんだから，とても説明しきれない！（初手敗北）
> 絶望を希望に変えるRPG．
72柱の悪魔を育成して世界を救う，本格戦略バトルゲーム
([公式ホームページ](https://megido72-portal.com/)より)

ひらたく言えば，ヴァイガルド（人間界）を守るため，仲間のメギド（悪魔）たちと共に，メギドラル（悪魔界）と戦う世界線のお話なんですね．

戦闘画面をみていただけば，だいたいの雰囲気はつかめるだろうか……．
<div align="center">
<img src=https://i.imgur.com/JzTUwD4.jpg>
</div>
<br/>

可愛らしい見た目をした小さき存在が，なにやらデカい怪物と戦っていますね……
真ん中にある飴のような物体・フォトンを敵と交互に取り合って，戦闘を進めます．

このゲームの楽しいところは
1. 　頭をひねらないと敵が倒せない，とても戦略的なゲーム性
2. 　考察要素がてんこ盛りのストーリー
3. 　絶対にすべての性癖を網羅してやるという気概を感じるキャラクター
4. 　ぬるぬる動く3Dモデリング（どうなってんの？！）
5. 　etc

……あげるとキリがない！
で，わたしが１番楽しんでいるのは，**キャラの育成**です！！(あげてないじゃん)

メギドの皆さんは，それぞれ色々な贈り物を欲しがるんですね．
たとえば，最近ちまちま育ててる，音楽大好きベバルさんの欲しい物リストがこちら．
<br/>
ハニーケーキにカエルドーナツ……甘いものが好きなのか？！可愛いな！！
ドラムメジャーらしい衣装に帽子も欲しがっています．可愛いですね．
ハーモニカももしかしたら吹いているのかもしれません．可愛い．
可愛いものものに混ざる魔槍……こう見えて戦闘力もあるのか……ギャップ……可愛い……

進化したら，次はなにを欲しがるんだろうと思うと，はやく進化させてあげたくてたまらなくなりますね．可愛いので．

これらのブツを贈るには，マップを探索して，素材を集め制作する必要があります．
おっ，ちょっとタイトルの香りがしてきましたね．
そうなんです，このゲーム，探索も重要なんです．

## マップ探索のお話
メギドのクエストは，まずマップを探索して，ボス戦を目指します．

<br/>
ツボからは進化素材アイテムを錬成できる素材が落ちがちなので，絶対に回収したい．
ザコ敵は，アイテムを落とすこともあるが，時短したい．できるだけ避けたい．

**……これ最適経路を出せるんじゃね……？**

※ 右下のボタンにあるように，ルート探索のボタンを押せばパッとルートを提案してくれる機能があります．こんな感じ．
<br/>
今回はすべてのツボを通ってくれていますが，たまに宝箱を捨て，敵を選ぶルートを提案してくることがあり，これはルート検索の挑戦しがいがあるなとなりました．

## 最短ルート探索をしてみよう！
本日16日にこのネタを思いついたために，初歩的な内容になっています．南無．
初手敗北宣言が2度目ですね．計画的に過ごしてえ．

宝箱を網羅し，時短できる敵をできる限り避けるルートを提案するのが最終目標ですが，まずは最短経路を提案してみましょう．

マップは最大で，５x５の25マスとなっています（たぶん）．

ルールとして，
* スタート地点を０
* ゴール地点を72
* それのマスは１から連番で数字をふる

こととします．

### 方針
できる限り少ないステップ数でゴールにたどり着くルートを提案したいので，幅優先探索でいこうと思います．

### 入力
マップを見て，これグラフでゎ！？となったので，勉強のためにマップをグラフとみなします．（ょゎょゎ並感なので叩かないで……アドバイスはくれ……）

入力がありえんめんどいですね．
１マスに対して，
* 道が繋がっているマス
* （宝物の数）

を入力していきます．めんどい！

Start(neighbor):
1
1(treasure):
0
1(neighbor):
0 2 4

この要領で，力尽くで入力していきます．めんどい！
最後まで入力できたら，経路グラフができあがっているわけです！ガハハ！（ミスるわ，そんなん）

### 幅優先探索
スタート地点から，ゴール地点への最短ルートを探索します．

スタート地点から，各マスまで最短ルートで向かう際に経由する，直前のマスをリストに記録していきます．

def bfs(graph, N):
    # 上で作ったグラフ
    vertex_list = graph.vertex_dict
    
    # 各マスまでの最短ステップ数
    step_list = [-1] * N
    step_list[0] = 0
    
    # 各マスまで最短ステップで行くとき，直前に経由したマス
    pre_list = [-1] * N
    
    # １回通ったマスを記録（宝箱マスの場合，訪問後は宝箱を０に更新したい
    visited_list = [0]
    
    # 探索用キュー
    queue  = deque([0])
    
    while queue:
        v = queue.popleft()
        step = step_list[v]
        visited_list.append(v)
        for w in vertex_list[v].neighbor:
            if step_list[w] > -1:
                continue
            if w not in visited_list:
                visited_list.append(w)
                pre_list[w] = v
            step_list[w] = step + 1
            
            queue.append(w)
    return pre_list

直前に通ったマスを記録してくれたリストがかえってくるようになりました．

[-1, 0, 1, 4, 1, 2, 3, 4, 5, 8]

よかった．
これをゴールからスタート地点までたどることで，ルートを提案してくれます．

GOAL <- 8 <- 5 <- 2 <- 1 <- START

なるほどね．
宝箱は全然とれていないですが，これが最短ルートなんですね．ははん．

## まとめ
改善点はいっぱいありますね．
* 宝箱を網羅 or できる限り多く宝箱を取得してのゴール
* ザコ敵を避ける
* 探知力（宝箱を発見できる最大移動回数）の反映

う〜ん，改善に挑戦したいです．
半日にしては頑張れたと思います．
<br/>
話は変わるのですが，FGOはWスカディ狂スロパーティーで脳死周回が完全に可能になってしまったせいで，本当につまらないですね．なんとかして欲しいです．
環境が改善するまでは，メギドを効率よく育成するためにパーティーを練る，ぬくぬくライフを楽しもうと思います．
<br/>
明日は4nzuくんです！
みすの人が3年後くらいに気にしてくれればいいDTMの細かい話……３年後には全人類DTMをしているかもしれないので，お役立ち情報確実ですね．