粘菌が迷路を最短ルートで解く

物理化学の視点から、迷路ゲームへの応用を考えるヒントが浮かび上がって………来る人もいるだろうか。（記事そのものは古めです）

粘菌が迷路を最短ルートで解く能力があることを世界で初めて発見
http://www.riken.go.jp/r-world/info/release/press/2000/000926/

面白い。

考えてみれば、生物として当然の行動であるとも感じるが。

迷路の最短経路探索のアルゴリズムは、昔からゲーム雑誌やアルゴリズム本に数多く載せられてきた題材の一つだったが、菌が迷路を解くなどという話は初耳だ。

出口にはエサを。基本といえば基本ですな。

最後に得られる“何か”があることを知っているからこそ、迷路ゲームを遊ぶモチベーションを保てるケースは数多くある。最短経路を追い求める気持ちに共感する人は多いかも(?)。

人間も、粘菌の遠い親戚ってことでしょうか。

……三十分ほどで一個アイデアを思いついてしまった………。こんなコトやってる暇はないはずなんだが………。

面白い記事を見つけてしまったことがいいやら悪いやら。

思いついたアイデアは以下の通り。

スタート地点から、ただ一つのゴール地点を目指す迷路を自動生成する場合の話だ。*1

プレイヤーに、最短経路とそうでない経路をある程度区別する方法を、何らかの形でヒントとして伝えておかないと、誤った経路への進入を繰り返してしまいプレイヤーの探索が「泥沼化」する恐れがある。

粘菌の行動は、それを防ぐ一つのヒントになる。

まず、粘菌の行動について簡略化して述べると、以下の通りになる。

入口と出口にのみエサを与えられた粘菌は、迷路中に張り巡らせた己の体から、徐々に最短経路とは無関係の経路に存在する枝を短く収束させていき、最終的に一本の最短経路のみを残し、効率的に食事を取ろうとする性質を持っている。

このロジックは、たとえダンジョン進入直後は最短経路が分からなくても、探索を続けていくに従い（すなわち、時間が経過するに従い、または踏破ブロック数が増えるに従い）、徐々に最短経路が明らかになっていく仕組みに応用できる。

最短経路ではない枝の先から、少しずつ「この経路は誤っているよ」とプレイヤーに伝えてあげる頻度を増やしてあげればいいのだ。

具体的な方法の一つとして、以下がある。

この方法ならば、プレイヤーが数本の誤った経路に進入することがあっても、多少間違いを繰り返したところで、最短経路が明らかになってくるため、それ以降は間違いづらくなる。

つまり、最短経路を見つけられず進入経路を間違いすぎて、迷路を「全制圧」しなけれならない事態を回避することができる。

*1:例の、マップ自動生成型の宝探しゲームでは一本経路型と呼んでいたが、けっきょくどのフロアも全探索しなければならないゲームだったので、有効に活用できなかった