スマートフォン向けRPG「Fate/Grand Order」のユーザーが使える、欲しいアイテムの個数を入力すると最適なクエストの周回数を求めるサイトを作りました。

欲しい素材の数を入力すると、どのフリクエを何周するのが最も効率的か教えてくれるサイトを作りました

周回するクエストに迷ったら使ってみてください#FGO https://t.co/JXzZ8fmHmX
— あんてな (@antenna_games) July 18, 2021

サイト

フロントエンド

API

スクレイピング

サービスの内容

入力フォームから最小化する対象、集めたいアイテムの数、対象に含めるクエストを入力します。
送信すると最適なクエストの周回数がわかります。

作った目的

フォロワーさんがこんなサイトが欲しい！とツイートしていたのをきっかけにモデル化・実装してみたら割と簡単にできたので、色んな人が簡単に使えるようにWebサイトとして公開してみようと思いました。

ビジネスロジック

クエスト$q$、アイテム$i$に対して、ドロップ率を$p_{qi}$、欲しいアイテムの個数を$n_i$とすると、合計が最小となるクエスト周回数$x_q$は次の線形計画問題を解くことで求められます。

最小化:

\quad\sum_{q}x_q

制約条件:

\sum_{q} p_{qi} x_q \ge n_{i} \quad ( \forall i)\\
x_{q} \ge 0 \quad( \forall q)

これをPythonの線形計画APIであるPuLPでモデル化します。まず、ドロップ率が次のような表で与えられているとします。

quest_name	item_name	drop_rate
モントゴメリー	証	0.627
モントゴメリー	塵	0.154
シャーロット	証	0.481
シャーロット	塵	0.642
……	……	……

このとき、塵と証を100個ずつ集めるのに最適な周回数を求めるコードは次のようになります。

import csv
import pulp
import itertools
import operator

item_counts = {'塵': 100, '証': 100}

with open('drop_rates.csv', 'r', newline='', encoding='utf-8') as f:
    reader = csv.DictReader(f)
    rows = [row for row in reader if row['item_name'] in item_counts]

quests = set(row['quest_name'] for row in rows)
ig = operator.itemgetter('item_name')
groups = itertools.groupby(sorted(rows, key=ig), key=ig)

#問題の作成
problem = pulp.LpProblem(sense=pulp.LpMinimize)

#変数の作成
laps = pulp.LpVariable.dicts('lap', quests, lowBound=0)

#目的関数の設定
problem += pulp.lpSum(laps.values())

#制約条件の設定
for item, rows in groups:
    problem += pulp.lpSum(float(row['drop_rate']) * laps[row['quest_name']] for row in rows) >= item_counts[item]

#求解
problem.solve()

for quest, lap in laps.items():
    if pulp.value(lap) > 0:
        print(quest, round(pulp.value(lap)))

これを実行すると次のような結果が得られます。

シャーロット 144
モントゴメリー 49

このように、PuLPでは問題を直感的にモデル化して簡単に解くことができます。

アーキテクチャ

スクレイピング

クエスト周回数の算出には各クエストのアイテムのドロップ率が必要となります。このデータは自前ではなく、FGOアイテム効率劇場という有志の方による統計データを利用しています。Googleスプレッドシートとして公開されているので、定期的に実行されるLambda関数からGoogle Sheets APIでドロップ率表を取得して、データを整理した後S3に保存しています。

API

アイテム数からクエスト周回数を計算するLambda関数です。API Gatawayから呼び出されると、PuLPを使って線形計画問題をモデル化して解きます。

Lambda関数の構築にはAWS SAMを使用しています。YAMLを書くだけでデバッグ・デプロイやポリシー設定をやってくれるので便利です。

フロントエンド

Next.js+TypeScriptで構築してVercelでホスティングしています。複雑なデータから静的・動的に生成する必要があり、SSG・SSR・CSRを使い分けられるNext.jsはとても便利でした。

スタイルには手軽に使えるNo-Class CSSフレームワークのMVP.cssとNext.jsに組み込まれているCSS in JSであるstyled-jsxを組み合わせています。

工夫した点

サーバーレス構成

最初はDjangoででも作って、自前の最低スペックのVPSにでも置いておこうかと思ったのですが、友人の助言でLambdaベースとしました。公開したら思ったより伸びて、APIコールが最大500回/時くらいになったのでサーバーレス構成の恩恵を感じました。

メンテナンスフリー

クエストやアイテムはストーリーが進むごとに追加されますが、効率劇場からスクレイピングしたデータを元にバックエンド・フロントエンドともに自動的に生成されるので、効率劇場の形式が変わらなければ開発者側で対応することなく新クエストや新アイテムに対応できます。

レスポンシブデザイン

スマートフォン向けゲームのユーザー向けということでモバイル端末からのアクセスが多いことが予想されたので、モバイル対応を意識しました。レスポンシブ化自体は簡単にできるのですが、画面に含める情報を必要十分に抑えたり、それぞれのコンポーネントを折りたためるようにしてページ内の移動をしやすくしたり、ラジオボタンやチェックボックスを一回り大きくしてタッチしやすくしたり、といったところに気を付けました。

Twitter共有

FGOはTwitterコミュニティが活発なので、結果をTwitterに共有できるようにTweet Web Intentを付けてみたのですが、ユースケースが可視化されて結構参考になりました。

引っかかった点

フロントエンドとバックエンドのすり合わせ

フロントエンドをTypeScript、バックエンドをPythonで作っていますが、データやAPIの設計はきちんとすべきだと感じました。キャメルケースとスネークケースが入り混じったり、Pythonでは多用しがちな動的キーの辞書がTypeScriptだと扱いづらかったり……。

AWSの環境変数がVercelで予約されている

フロントエンドのSSGのときにgetStaticPropsでS3バケットからアイテムやクエストのリストを取得しているのですが、AWSのAPIを叩くときには認証情報が必要です。Node.jsでは環境変数を使って認証するのが一番手っ取り早く、Vercelにもセキュアに環境変数を設定する機能があるので安心していたのですが、認証に使うAWS_ACESS_KEY_IDやAWS_SECRET_ACESS_KEYはVercelでは予約済みのため使えませんでした。認証情報をファイルとして置いておく方法もあるのですが、GitHubの公開リポジトリにリンクする形でデプロイしているので、S3の読み取り権限しか付与していないとはいえ認証情報を公開するわけにもいかないのでこの方法も使えませんでした。

最終的に環境変数名を衝突しないように変更して、プログラム側で読み取ってAWS SDKに直接渡すようにしましたが、これがベストプラクティスなのかはよくわかりません。

react-checkbox-treeが再現性なくクラッシュする

周回対象に含めるクエストを選択するためにreact-checkbox-treeを使用していました。

ツリー構造はセクション>エリア>クエストの3層になっています。ここで、S3にあるオブジェクトはクエストごとにセクションとエリアが書かれたフラットな表で、ツリー構造を作るときにセクション名やエリア名をキーにしてグループ化を行っていたのですが、キーとなるセクション名やエリア名に元のオブジェクトにはない文字コードが混入することがありました。こうなると同一のIDの枝が2つ生える事態となり、react-checkbox-treeがクラッシュしてしまいます。それだけならまだましなのですが、React16からコンポーネントがエラーを起こすとツリー全体がアンマウントされる仕様になっていたため、一部のユーザーの画面にはエラーメッセージが表示されるだけという事態になっていました。

一部のコンポーネントのエラーがDOM全体を巻き添えにする仕様についてはerror boundaryを設定して回避します。また、この問題に対する解決策として、グルーピングにセクション名やエリア名の代わりにIDを使用するようにしました。

まとめ

FGOの欲しい素材からクエスト周回数を求めるサイトを作りました。AWSもReactも初めて触りましたが、AWS SAMとNext.jsが面倒な設定などはすべてやってくれるので割とすんなり作ることができました。