桃太郎電鉄のお助け機能「いけますよ!」の実装に関する考察
遊びの中の一機能を解析してみよう
今日は少し、わたしの専門を活かして、ゲームの仕組みに密着した話をしようと思います。
みなさんは、「桃太郎電鉄」で遊んだことがあるでしょうか?
すごろくを拡張したようなゲームで、日本(やその他地域)を模したマップを移動して、停まった鉄道駅周辺の物件を買い、資産をもっとも大きくしたプレイヤーが優勝というルールのゲームです。
モノポリーにも近い印象ですが、こちらは実在する物件のリサーチや新キャラクターのデザインを行い、膨大なグラフィック・イベント・新要素を毎作品用意している、よりビデオゲームらしいコンテンツです。
頭を使うパーティゲームの定番であり、ポテチの大袋などを囲んで遊んだ経験のある方は多いのではないでしょうか。
新旧お助け機能「いけるかな?」と「いけますよ!」
先述したとおり、桃鉄は「すごろく」のバリエーションであり、マスを駅に見立てて日本地図のようなマップの上で遊びます。
必然、道は一本道ではなく、駅の間に張り巡らされた鉄道網を、どちらに行くか自由に選択しながら進むことになります。
その際、停まった駅によって起こるイベントが異なるほか、「目的地」と呼ばれる、到着すると高額の補助金がもらえるマスが存在するため、
「出目が確定した後、特定のマスへ行けるかどうか」調べることがが非常に重要なゲームです。
そこで、桃鉄には古くから「いけるかな?」というお助け機能が搭載されています。
- 行きたいマスを選択すると、秘書がそのマスに行けるかどうかを教えてくれる
- そのマスに行くための経路を検索し、自動的に移動してくれる(プレイヤーが希望した場合)
この機能の初出は1992年に発売のSFC「スーパー桃太郎電鉄II」です。
進めるマス数が「1~6」だけならこの機能も不要なのでしょうが、桃太郎電鉄には同時に複数のサイコロを振ることができる機会があり、その数は最高で8つ(出目の最高は48)。
プレイ中に頻出する出目は20程度までではありますが、ループ(線路を辿って一周できるようなところ、桃鉄ファンの用語)の活用も考慮しなくてはならないため、人が自力で割り出すのは結構時間のかかる作業ですし、ルートの見落としも考えられます。
およそ14年間、「いけるかな?」機能はたいへん便利な機能としてユーザーに活用され続けてきました。
ところが、この機能には「質問をしないと答えが返ってこない」という欠点があり、しばらくの年月を経て、より便利な機能へ改善されました。
改善版である「いけますよ!」機能が搭載されたのは、2006年発売のPS2・Wii・Xbox「桃太郎電鉄16」においてです。
上記の画像を再生するとお分かりのように、出目の確定後に行けるマスが「光って」見え、秘書に質問をすることなく行けるマスが一目瞭然になりました。
この機能の搭載までずいぶん期間があった理由として、技術的に困難であったためか、ユーザーからのフィードバックが少なかったためかは定かでありません。
なお、技術的に困難だった要素としては、さくまあきら氏のホームページ「さくまにあ」の以下のページでいくらか語られています。
http://sakumania.com/momo/momoken-8/01.05.html
- 貧乏神がつかないルートが存在するかどうかの判定
- うんち(駅を通れなくする障害物)が大量に置かれたときの検索
「いけますよ!」はどうやって実装したのか
「いけますよ!」は、プレイヤーが虫メガネ(マップ全体を見渡す機能)を使ったときに計算が終わっていなければなりません。
出目の確定後、虫眼鏡を起動するまでの時間は最短で0.1秒程度でしょうから、高速な計算が必要となります。
(事前に出目が決まっている擬似乱数を使っているため、その限りではないかもしれませんが)
十分に高速な計算ができるよう、実装については気を遣わなくてはなりません。
ちょっと調べてみましたが、「いけますよ!」の実装方法に関する文献は見当たらなかったため、どうやって実装しているかを考察してみることにしました。
考察を始める前に、桃太郎電鉄の電車の移動に関する規則をおさらいしておきましょう。
移動規則
- サイコロを振って、出た目の数だけ移動することができる
- 同時に複数のサイコロを振るときは、出た目の合計だけ移動することができる
- 隣り合う駅に移動するとき、移動可能なマス数をひとつ消費する
- ピッタリ到達できるマスにしか移動できず、移動数の破棄はできない
- 線路を辿って一周することはできるが、折り返しはできない
準備 - 駅の位置関係をコンピュータに入力しておく
簡単な例として、以下のようなマップを考えてみましょう。
丸が駅、丸と丸とつなぐ線が線路を表します。
ゲーム内では駅に名前が付いていますが、ここでは「0、1、2、3、…」と数字を付けて識別できるようにしてあります。(スタート地点が0)
数字に特に意味はなく、一つ一つの駅を識別するための番号だと思ってください。
いまわれわれの目には駅どうしの隣接関係が見えていますが、コンピュータは直接この絵を見て内容を理解することはできません。
そこで、コンピュータに駅どうしの位置関係を覚えてもらうために、「隣接リスト」というものを作ります。
左側の表の各行を見ると、ある駅に隣り合った駅のリストになっています。
たとえば一行目は、出発地である駅「0」に隣接するのは、「1」と「3」であることを示しています。
二行目は、「1」に隣接するのは「0」と「2」と「23」であることを示しています。
いずれも、右側のマップの絵と合致していますね。
このように、駅の隣接関係を入力するだけでも、マップの全貌を表現することができます。
このやり方は、数字の列を書くだけでマップの構造を表現できますので、コンピュータにとって記憶可能なものだということは何となく分かっていただけるでしょうか。
このリストによって、駅の位置関係をコンピュータに理解してもらうことができるようになります。
(言い換えると、マップの構造をコンピュータに入力できるようになります。)
実装 - 移動数を一つずつ大きくして考える(動的計画法)
いよいよ、移動可能なマスを実際に求める手続き、すなわち実装について考察していきます。
ここでは上記の画像において、出目が「10」のときに到達可能な全ての駅を求める問題を解くことができそうな、一つのアイディアを紹介します。
Step1 - 「1」で移動できる駅を求める
いきなり「10」ピッタリで移動できる駅をすべて求めるのは難しいので、まず「1」ピッタリで移動できる駅を求めることから始めます。
(つまり、出発地に隣接する駅をすべて求めます。)
コンピュータは出発地である「駅0」に隣接する駅を隣接リストからチェックし、「駅1」と「駅3」が該当することが分かります。
よって、この2つの駅を覚えておきます。(図表においては赤く塗ること表現。)
Step2 - 「2」で移動できる駅を求める
先ほど、「1」ピッタリで移動できる駅をすべて求めました。
これを使って、「2」ピッタリで移動できる駅を求めることができそうです。
先ほどは出発地に隣接する駅を隣接リストからチェックしましたが、今度は「1」ピッタリで移動できる駅である、「駅1」と「駅3」に隣接する駅をすべてチェックします。
すると、「駅0」「駅2」「駅4」「駅5」「駅23」が該当することが分かります。
これで「2」ピッタリで移動できる駅が求まる…かと思いきや、結果がちょっと変なことにお気づきでしょうか。
実は、赤く塗られた「駅0」というのは移動数「2」で到達可能な駅ではありません。
駅0は出発地でした。実は、移動数「2」で駅0に到達できるというのは、折り返しが可能な場合の話なのです。
先述した、電車の移動に関する規則を思い出してみましょう。
サイコロを振って、出た目の数だけ移動することができる
同時に複数のサイコロを振るときは、出た目の合計だけ移動することができる
隣り合う駅に移動するとき、移動可能なマス数をひとつ消費する
ピッタリ到達できるマスにしか移動できず、移動数の破棄はできない
- 線路を辿って一周することはできるが、折り返しはできない
今進めているこの手続きを「10」まで続けていくと、「折り返しが可能な場合に」、移動数「10」ピッタリで移動可能な駅をすべて求めることができます。
これはこれで別の問題に応用できそうですが、いま欲しい結果とは違いますから、少し方法を修正する必要がありそうです。
改良 - 「来た方向」を記憶させてみる
もう一度、「1」ピッタリで移動できる駅を求めた段階に巻き戻してみましょう。
上の画像は、先ほどとちょっとだけ変わっています。
どこが変わったかというと、隣接リストの「駅1」と「駅3」の行で、「駅0」のところが緑色で塗られていますね。
これは何を表しているかというと、「それぞれの駅に移動数1で行く場合、どの駅の方向から到達することができるか」を表しています。
そして、「来た方向には次のステップで行くことができない」ように実装すれば、「折り返しができない」ルールを反映することができます。
このアイディアにのっとって、移動数「2」で到達可能な駅を求めてみましょう。
上記画像の赤く塗られた駅を、どのように求めたか説明します。
移動数「1」で到達可能な「駅1」と「駅3」に隣接する駅のうち、緑色で塗られた「来た方向」に該当しないものをすべて求めました。
すると、「駅2」「駅4」「駅5」「駅23」が該当することが分かると思います。
移動数「2」ピッタリで到達可能な駅が正しく求まっていますね。
続いて、移動数「3」ピッタリで到達可能な駅を求めてみましょう。
このときに重要なのは、移動数「2」で駅「2」に到達する方向は2通りあったという点です。
駅「2」には駅「1」と駅「3」どちらからも到達できましたから、駅「2」からその次に行くことのできる駅は隣接するすべての駅になります。
一般に、「2つ以上の方向から到達できる駅ならば、次のステップでは隣接するすべての駅に行くことができる」という規則が成り立ちます。
「来た方向(緑色)以外の駅にしか行けない」という風に実装すると間違った結果になりますので、この点について注意が必要です。
移動数「4」ピッタリで移動可能な駅です。この要領で計算を繰り返せば…
移動数「10」ピッタリで移動可能な駅をすべて求めることができます。
実は、「駅0」「駅16」「駅17」を除く全ての駅にピッタリ停まる事ができることが分かりました。
「桃鉄」未経験者やビギナーの方は、こんなに多くの駅にピッタリ到達できることに驚かれるのではないでしょうか。
計算速度について
上記の小さなマップであれば、出目が1000でも一瞬で計算が終わります。
計算時間は駅数と線路数に依存しますが、「一つの駅に接続する線路は4本まで」という桃鉄のマップの性質を使えば、
駅数が倍になれば計算時間もおよそ倍で抑えられるし、出目が倍になれば計算時間もおよそ倍で抑えられる、ということが言えそうです。
(専門的には、駅数を|V|、出目をWとしたとき、時間複雑度は|V|Wのオーダであるといいます。)
もっと大きなマップや、同じ駅数でも計算にもっとも時間のかかるケースについても実験してみたいですが、今日のところはひとまずここまでにさせて頂きます。
ダウンロードリンク
実際に、csv形式の隣接リストを読み込んで、結果をコマンドプロンプトに出力するプログラムをC++で書きました。
・隣接リストサンプルのダウンロードはこちら(Dropboxにアクセス)
・プログラムのダウンロードはこちら(Dropboxにアクセス)
ソースコードとcsvファイルをダウンロードし、同一フォルダ内に置いてコンパイル・実行すればすぐ結果を見ることができます。
csvファイルの隣接リストを書き換えれば好きなマップに関する結果を見ることができますので、暇つぶしにどうぞ。(ちょっと入力が面倒ですが)
隣接リストは必ず「0」を出発地に設定し、SIZEの横の数字を全駅数にアジャストしてください。
おまけ - 「アルゴリズム」と「グラフ理論」について
今回話した内容は、出発地と出目に対して到達可能なマスをすべて求める計算方法に関するものでしたが、専門用語を使うと「アルゴリズム」というものを作ったことになります。
アルゴリズムとは、入力(ここではマップと出発地と出目)に対し、正しい出力(ここでは到達可能なマスの集合)を返すまでの手続きのことです。
アルゴリズムを先に考えておくと、プログラムを書くときに楽になりますし、「どのぐらい速いか・メモリを必要としないか」を事前に見積もることができます。
そして、駅の位置関係について簡単な図で表し、対応する隣接リストを作りましたが、これは「グラフ理論」と呼ばれる分野の考え方を応用しました。
ここで言うグラフというのは、算数や数学の授業で見たり書いたりするグラフや、棒グラフ・円グラフといった統計情報を整理するグラフのことではなく、
ものとものの隣接関係をコンピュータに覚えさせ、いろいろな計算をするために使われる枠組み(データ構造)のことをいいます。
専門的には、図の中にあった丸は「頂点」、線は「枝」とよばれます。
この枠組みは、交通網や鉄道網における効率の良い経路の検索や、社会のネットワークにおけるクラスターの分析に実際に使われていて、
最適経路を検索するナビゲーションアプリや、知り合いかもしれないユーザーのレコメンド(おすすめ)に活用されています。
分析対象 | 頂点にあたるもの | 枝にあたるもの |
---|---|---|
鉄道網 | 駅 | 線路 |
交通網 | 交差点 | 道路 |
SNSのクラスタ | ユーザー | 友達関係 |
そして、今回は「頂点」を駅、「枝」を線路だと考えることで、桃太郎電鉄の「いけますよ!」機能について考察することができたわけですね。
備考 - アルゴリズムに関する権利
アルゴリズムを知的財産として保護する権利には「著作権」と「特許権」がありますが、
前者はアイデアそのものを保護する権利ではないこと、後者は特許として認められたものについてのみ保護する権利であることを加味し、今回この記事を公開することを判断しました。
なお、当該のアルゴリズムについて特許が取られていないこともざっと確認しましたが、独力の調査ですので保証はできません。
この記事で公開したアイデアを用いる際は、くれぐれも自己責任でよろしくお願いいたします。