そもそもどういうのを作ったのか
こんなのを作ってました。よくあるセリフをクリックしていくと途中で分岐が現れてその選んだ分岐の結果によってGood EndだとかBad Endだとか変わるやつです。
ハマった部分はここですねぇ
大学の実習の講義の一環でWEBサービスを立ち上げてそこにノベルゲームを実装してました。
何がハマったのか
先ほども説明したようにこのゲーム、分岐があるんですね。つまりこのような問題があります。
- 分岐があり、なおかつ選択した分岐によって画面に表示されるセリフの量が変化する
- 何%進んだが現在時点で表示させるので、セリフの総数が確定しない状態で進捗状況を表示させないといけない
めちゃくちゃ省略して簡易的な図で表すとこんな感じになります。
解決策としてかんがえたこと
色々考えました。
考えたこととしては
- 100 / 総セリフ数 で一つのセリフをクリックしたらどれだけ進むかを決める
- ゴリ押しで特定のセリフにいったら進捗をプラスしていい感じに最後になったら100%になるように手動で調整する
こんな感じです。
ただ...
1→セリフの総数が確定していない都合上不可能
2→現実的ではあるものの、新しくセリフや分岐が追加された時にバグり散らかす可能性があり拡張性に欠ける
といった問題がありました...
発見した解決策
色々な方法を考えていたところ、1つのことを思い出しました。
大学で木構造やその探索について学ぶ講義があったんですよね。
それを踏まえて先ほどの図をみてみると...
回転させて少し図を付け加えてもっとわかりやすくしてみると...
はい、多分木の構造になっているんですよね
この多分木を「行きがけ順」で探索を行なっていきます。
具体的には...
手順を説明していきます。
- まず「根」となるノードに100という値を付与します
- 次にその根から分岐している「葉」の部分(葉が一つのセリフとなる)と分岐の集合という2種類に分け、 100 / (葉の数 + 1) ←1が分岐の集合 といった計算をし、その出た値を葉と葉ではないノードで均等に分割していきます
- 次は葉ではないノードを訪れ、さらにその子ノードを先ほどでた値を分岐分の数で割る...ということはせず分岐先にそれぞれ先ほど出た値をそのまま付与させます(理由としてはユーザは数ある分岐の一つしか訪れず、分けると結果的に100%にならないからです)
- あとは2の手順を繰り返します
言葉だけだと分かりにくいと思うので図で説明するとこんな感じです。
黒が根ノードと分岐、赤がセリフ、緑が分岐をまとめているノードになっています。
注意点としてはユーザは必ず緑のノードを訪れる前にその緑のノードに対する兄弟ノードを全て訪れます。
何がハマったか(その2)
このアルゴリズムを思いつくまでにかなり時間がかかりましたが、コードを書くのも苦労しました。
こういう探索系は再帰をほぼ必ずと言っていいほど書かないといけないと思うんですが、僕再帰を書くのがとても苦手なのでかなり頑張りました。おかげて再帰は鍛えられました。
これがコードです。今見返すとと少し冗長な部分がありますね...(三項演算子で事足りる部分があったりだとか)
感想
なんとなく受けてた大学の講義ってひょんなところで役に立つんだなぁと思いました。長年の伏線を回収した感じがします。