Q&A
一度通ったかどうか関係なしに分岐点では完全にランダムに道を選択すればいいのでは？
迷路を探索するプログラムを作っています。
組んだプログラムのルールとして、自分の周囲８コマを探知し、その中で未だ踏んだことのない道をランダムに選択する、という風にルールを設定しました。一度踏んだ道は通れないように組んであります。
サンプルプログラムを見ていただくとわかるのですが、このルールだと赤いゴールにたどり着かずに自滅することがかなりの確率で起こり得ます。
プログラムの方で、「自滅しないように判断しつつ道を選択する」という組み方は可能でしょうか？
かなり難しそうですが・・・・。
こうした問題に詳しい方、あるいはそうでない方も、ご興味、あるいはご助言お持ちの方の回答お待ちしております。
サンプルプログラム
回答ありがとうございます。
それだと、あまりにもアホな動きに見えるような気がして・・・・。
ある程度、進んでます！みたいな意志がキャラに感じられるようにしたいのです。
あ、すみません。回答の意図がよく読めてませんでした・・・。
やりたいこと，というか条件を明確にしてください．
> 二度同じ道を通ってもいいのであれば…
という回答が付いていますが，そもそも「一度踏んだ道は通れない」が絶対的なルール（この話の前提条件）なのであればそのような話をしても無駄ですし．
探索者にどこまで情報を与えても良いのかという話も必要です．
迷路全体の全てのデータを知っている前提としてよいのか否かでアルゴリズムは全然変わるでしょうし，
情報が制限されているとしても
・迷路全体のサイズやその中での自身の現在座標を知ることはできるのか？
・ゴールがどこにあるのか？を最初から知らされているのか？
等々でやれることが変わるでしょう．
「自滅」＝「行き止まりにたどり着く」であれば，
曲がり角に実際に行き着くよりも前にその曲がった先が行き止まりだと知っているならば，「そっちに行かない」ということはできるでしょうけども，
少なくとも曲がり角に行ってみるまでその先を知り得ないならば，原理的に「自滅」を回避するように道を選択するなんてことはできないのではありませんか？
回答ありがとうございます。
回答してくださった通り、この問題を考えるにあたって、もっとも「生産的」、かつ「興味をそそられる」設定について考える必要性がありますね。
僕としてはターン毎に一ます動ける、ターン毎に知り得るのは自分の周囲８マスの情報、という設定が最初に浮かんだものです。なので、「戻る」操作を許す必要性がありそうです。
この問題においては、どのような設定で考えてゆくのが適切か、ということがまず興味の対象となりそうです。
回答3件
0
二度同じ道を通ってもいいのであれば、探知範囲に入ったマスで一度も踏んでいないものを覚えておいて、行き詰ったらそのマスまで戻るようにしたらどうでしょう
投稿2021/12/02 12:04
総合スコア2047
回答ありがとうございます。
とても面白いですね。
二次元配列にデータを格納すれば、簡単に行き詰まったマスを記憶することができますものね。
そのデータを元に、与えられたマップの地形を測定することもできそうだ・・・・。
0
ベストアンサー
探索者がどれだけの情報を利用できるのか次第でやれることが変わるでしょう．
少なくとも
【自身が過去に通ったマスとそれらに隣接するマスの情報を収集/蓄積できる】
ならば，
その収集した情報から判断できる範囲で「明らかに自滅に向かう方向へ歩を進めること」を回避することくらいはできるでしょう．
例えば，下図で黄色の軌跡をたどって現在Aの場所にいるとしましょう．
収集できているデータは以下のような感じです．
- 黄色マスに隣接する範囲の情報だけは得られています．
青は既知の壁であり，白は既知の通れる場所です．
- 灰色マスには何があるかわかりません．
（迷路サイズや自身の正確な座標もわからない場合は，灰色の空間が外側にどこまで広がっているかもわかりません．）
この状態で，現在位置Aから左側に進むと「自滅となる可能性が高そう」くらいは判断が付きそうです．
（ゴールの位置情報が与えられていない場合，ここで左に進むというのは，「真ん中ら辺にある灰色の３マスの中にゴールがある可能性に賭ける」ということになる）
すなわち，
「既知の壁と自身の過去の軌跡で囲まれる閉空間にはなるべく立ち入らない方がよいかもな」という戦略が立ちます．
「閉空間内に未知のマスがあっても，その空間が狭いほど避けておこう」とか．
「俺は実際に進んでみる前に，まずは各方向に進んでみた場合をシミュレーションしてみて，今知っている地図の範囲で，未知の外周に到達できる経路を選ぶぜ！」
とか何とかいう話を実装したとするならば，
「左ではなくて右の方に進めば未知の広い世界が広がっているかもしれないのでそちらを優先的に選ぶ」という判断めいたことを行う形になるでしょう．
投稿2021/12/03 05:01
編集2021/12/03 05:03総合スコア11658
まぁ，このくらいしか情報が無いなら，まさに「一寸先は闇」なので，どう頑張っても「即自滅」が高確率であり得るけど．
隣接マスだけでなく「視界の範囲」の情報は収集できるだとか何とか，情報獲得条件を緩和していけばいくほど，「つまらない自滅」が減り，「それっぽく」なっていくんじゃないかな．
0
経路探索における、最短距離を割り出すという要件でよろしければ、
ダイクストラ法というものがあります。
ゴールを先に保持し、ある地点が、ゴールからどれくらいの距離であるかなどによって、最短経路を辿る方法です。
経路探索の一つの方法なので、他にも適したものがあるかもしれませんが、
ひとまず、ご自身で調べてみてはいかがでしょうか。
投稿2021/12/02 11:41
総合スコア9528
回答ありがとうございます。
調べてみたいと思います。
最短経路のような一択（？）ではなく、ウヨウヨと迷い、結構無駄な動きをしながら、しかし、自滅はしない、というある程度ランダムネスが保持される動きを求めています。
それではそのように質問文を編集して下さい。
私はそこまで詳しくないので、
（以前経路探索アルゴリズムを自作しようとしていろいろ調べた）
他に回答がつくことを祈っております。
例えば、一個先ではなく、二個先まで探索範囲を広げ、
自滅してしまう道は選ばないようにする、
とやってはいかがでしょうか。
もしくは、最短ルートをまず割り出し、そのルートに色をつけて、ランダムに動いてると見せかける、とか。
あなたの回答
tips
プレビュー
