桃太郎電鉄の「いけるかな」を実現する高速なアルゴリズムの実装と考察 - Qiita

この記事は「データ構造とアルゴリズム Advent Calendar 2020」16日目の記事です。 15日目の記事はyurahunaさんの「木分解上の動的計画法」で、 17日目の記事はtsukasa__diaryさんの「Lawler の K-Best 列挙アルゴリズム」です。 この記事内で使用しているプログラムやそのテストプログラムは全て以下のGitHubリポジトリで閲覧可能です。プログラムの詳細に興味がある方はこちらをご覧ください（ついでにStarを押していってくれると喜びます🙂）。 Github: ashiba/Imprementation_of_IKERUKANA: Momotaro Dentetsu is a game. 変更履歴 2020/12/21に「最終的に貧乏神が付かない移動方法 ～貧乏神持ちの場合～」, 「最終的に貧乏神が付かない移動方法 ～貧乏神がついていない場合～

[chikuwabus]

貧乏神の仕様上、確実に判別するには「自分についてから別のプレーヤーになすりつける/さらになすりつけられる」パターンも考慮が必要だから更に重くならない？（コード読めてないので考慮されてたら申し訳ない）

[kako-jun]

目的地にいけるのを見逃しちゃうのもゲーム性だと思うから「いけるかな」がいらない（古典派）

[kotas]

コード軽く読むと、なすりつけ/つけられも適切に計算してるのがわかる／メモ化も「貧乏神がついたプレイヤーID」がキーに含まれてるので問題ないはず

[gabill]

ユーザーに「ボンビー憑くなら諦めるか」「ボンビーを擦りつけられるなら誰に憑けるか」の選択をさせるとテンポが悪くなるからバッサリ切ったと予想。

[Chishow]

仮設１じゃないかなぁ　意外とゲームアプリ開発者はアルゴリズムに詳しくなかったりする　前作のソースを引き継いで担当者が居なくてブラックボックス化してて手が出せないとかもあり得るな

[kastro-iyan]

スーファミ版の桃鉄DXをよくやってたけどあの頃からいけるかな機能付いてたもんなぁ。当時は結構な時間かかって処理してたけどSwitch版なら早いのかな

[daichirata]

複数人につけられる状況で誰につけるかとか、誰にも付けずにいくかとか、UI的な仕様考えるの確かにめんどそうではある

[harist]

仮説2かなぁ。あのサクサク順番が回るテンポ感を重視したんじゃないかな。通信対戦も可能とする中で少しでも処理時間がかかるものは入れられない気はする

[tatsuya_memo]

検証後の文章で「計算だけで 1時間ぐらい かかるそうです！」に触れない優しさ。

[kenzy_n]

いけるかも

[call_me_nots]

“桃鉄のマスの最大次数は4であるという性質を使うと、サイコロの出目をD,桃鉄の盤面のサイズをMとしたとき、アルゴリズムの計算量は盤面が(2*D+1)^2/2+1より十分に大きい場合にO(D^3)”

[altar]

貧乏神プレイヤーを状態パラメータに含む動的計画法、人間の思考様式にかなり近い感覚で理解できる話のはずなんだけど、複数回の貧乏神のやりとりが考慮されてなさそうって考える人も少なからずいるものだなあ。

[buhoho]

アルゴリズムできる人尊敬する

[jhoshina]

こういうの真面目に考えられる人はえらい

[mochige]

例えば出目をいくらか使って手動で貧乏神なすりつけを確定させたあと、そこから再度いけるかな使用、とかも出来るんで、いけるかな上の貧乏神判定機能はそもそも重要度が低いんじゃないかと思う

[knok]

昔のゲームプログラマーはリソース少ない環境でのプログラミングが普通だったから割とアルゴリズムに強かった。今はそうじゃない人が多いかもしれない(ゲームに限らず)

[yubessy]

こういうの大好きです

[hanyA]

今作は”定番”がキーワードで、遊んでて目立つような大きな変更とかは無いけれど、とにかくテンポとか快適さとかがすごく進化してて地味にすごいと感じる。「いけるかな」もテンポ考えたら必要十分なんですよね。

[aroechan]

タイトルと概要的にこの人が開発陣として実装したのかと思ったら全然違かった

[katariya0116]

１フレーム16.66msが許容範囲の中でこのmsだとカクつきがめっちゃ出るね……。（ちなみに16.66msは描画とかその他演出の計算も含んでの値）カクつくくらいな数字モリモリにして無理！っていうのが桃鉄らしい

[morita_non]

ゴールに着いたら貧乏神は外れるからそもそもあまり考慮する必要ないんでは。／ゴール以外に行く場合の話もあるのか…

[dekijp]

そもそも、貧乏神のマスを複数回通る場合について考慮してますか？

[wataken44]

テンポやゲーム性のために乗せなかったんだとは思うが、実装自体はまあなんとでもなるよね（最悪、「今貧乏神がいるマス」除外する実装だっていいわけだし）

[gorilla213]

中々マニアックですが面白かったです！C++扱われてるだけあって、計算方法にお詳しいようで勉強になりました。 ただ、C++分かんないんでコードは全く分かりませんでしたが・・・

[taguch1]

いいね。

[NOV1975]

証拠なしに仮説を述べて良いなら僕は「あの文言自体が演出」だと思うけどな

[Yuny]

さくまあきらさんへの最高のファンレターに思えた。プレイヤーの喜怒哀楽のウラで、難しいことしてるんだねぇ。

[YukeSkywalker]

いけるやん！

[ledsun]

（貧乏神を考慮しなければ）事前計算した全マスx出目のマップを持つと、1000x50で5万レコードぐらい？容量の面でDSでは厳しくてもPS2なら行けそう。

[spark7]

桃鉄よく知らんけどでかい目についてはあらかじめ駅間のコストと経路を計算してテーブルで持っておいたらダメなのかね

[sisopt]

ゲーム業界にいたけど、ブコメにある”テンポが悪くなる“説を支持。あと必須じゃないボーナス的なこの機能を付けてそこまでやっても面白さが増えるわけじゃなく労力にも複雑にすることにも見合わないからと予想

[neetia]

今いるノードとその直前までいたノードでn^2分領域使うと思ったけど、各ノードの接続しているノードを別でmap管理してソートしておけば最大次数4なので定数倍で済むの賢い。計算量もメモリ消費量もかなり削減できる。

[studio3104]

これまさに子とプレイしながら考えてたｗ 熟読します。

[Iridium]

AtCoderはこういう問題を解決するのに役立つのか。ちょっとやってみたいけど、自分レベルで歯が立つモノなのかどうか

[tattyu]

PS2位までだと1個の関数がブロックしてメモリ使い放題な作りでは厳しい。PS2は32MB、DSは後期で16MBしかない。CPUよりもメモリ予算の問題。switch世代であれば動く。今回出来てないのは現場のレベルが低いは十分ありえる。

[napsucks]

graphillionにぶっこむのじゃ駄目なのかな。