Home>C/C++でいろいろ作ろう

桃太郎電鉄 いけるかな？ シミュレータ

家庭用ゲーム「桃太郎電鉄（略して桃鉄）」でサイコロを振って大きな目が出た場合、 指定の駅に虫眼鏡を合わせると、その駅に行けるかどうかが分かりますよね。
その仕組みを考えてみることにしました。

これは数学でいうと「グラフ理論」に近いのでしょうか。（私はそんな詳しくありません）
グラフ理論（Wikipedia）
桃鉄では駅から駅までの長さは１マスなので、エッジ（辺）の長さは考える必要はなく、単純に考えられそうです。

以下のような駅の構成を考えます。


例えば、現在地点が「大阪」で目的地が「三重」だとします。
サイコロを振って２が出た場合、三重に到着するかどうかをチェックします。
人間が見れば「大阪」→「奈良」→「三重」だと分かって一目ですが、コンピュータは探索していく必要があります。
探索方法は、一番簡単なのが全経路探索していく方法です。
時間がかかりそうに思えますが、桃鉄のような少ない情報量では時間はかからずに一瞬です。例えサイコロの目が1000でも。

全経路を求めるのは、分岐図を書いてみれば分かりやすいです。


文章で書くと以下のような手順です。長いので途中省略してます。
  1. 現在地は大阪です。
  2. 大阪に繋がっている駅は、「兵庫」「京都」「奈良」「和歌山」「ハワイ」の５つです。
  3. まずは兵庫に行ってみます。１マス消費しました。
  4. その兵庫に繋がっている駅は、「大阪」「京都」です。
  5. 大阪は今来た道なので戻れません。
  6. 次は京都に行きます。これで２マス消費しました。
  7. 京都は目的地ではないので、バックします。兵庫に戻ってきました。
  8. 兵庫に繋がっている駅は全て調べたので、バックします。大阪に戻ってきました。
  9. 次は京都に行ってみます。１マス消費しました。
  10. その京都に繋がっている駅は、「大阪」「兵庫」「滋賀」「奈良」です。
  11. 大阪は今来た道なので戻れません。
  12. 次は兵庫に行きます。これで２マス消費しました。
  13. 兵庫は目的地ではないので、バックします。京都に戻ってきました。
  14. 次は滋賀に行きます。これで２マス消費しました。
  15. 滋賀は目的地ではないので、バックします。京都に戻ってきました。
  16. ･･･（省略）
  17. 三重は目的地なので到着しました。
プログラム化する事を考えると、再帰を用いると組みやすそうです。
再帰（Wikipedia）

再帰の問題としてスタックの浪費があります。
サイコロの目が100程度までならいいものの、１万とか１０万になるとスタックオーバーフローを起こしてプログラムが停止してしまう恐れがあります。
桃鉄ならサイコロが100を超えることはないため、再帰を用いても大丈夫そうですが、一応再帰を使わないほうも作ることにします。
しかし、再帰を使わないのは非常にプログラムが複雑になります。（私が下手なだけかもしれませんが）

＜プログラム＞
・main.cpp (見やすくしたもの)
・実行ファイル

再帰を用いたのが
Game::Process

再帰を用いないのが
Game::Process2

という関数です。再帰のほうは30行、再帰使わないほうは110行いってます。
再帰のほうはサイコロの目が5000でオーバーフロー起こしました。

↓実行画面（現在地 三重、目的地 ハワイ）

最短距離は３マスだということが分かる。
サイコロを振って10が出たときの経路を出力。到着できることが分かる。

↓実行画面（現在地 大阪、目的地 滋賀）

最短距離は２マスだということが分かる。
サイコロを振って1が出たときは到着できないことが分かる。