スネークゲームの経路探索アルゴリズム - MugiChaスネークゲーム、ある領域内に蛇と餌があって、蛇は上下左右に移動でき、餌を食べると長さが1ずつ長くなっていく。蛇が壁にぶつかったり、自分自身にぶつかったら終了。 餌はここでは、蛇が餌を食べる度に、空いた空間のどこかに等確率で出現するとする。 このゲームを自動で行うようなアルゴリズムを考えていたのだが、意外に難しい。 まず前提として、最終的に詰まるまでの長さを最大化することを目的とし、餌の位置は、出現するまでは全くわからないものとする。 一番初めはbkzenさんのこれ。 これはよくわからないアルゴリズムを使っているが、割合はやく詰まってしまう。それも非常に哀れな詰み方で・・ これを改良して自分がつくったのがこれ。 A*を用いている。これで寿命は少し延びたが、餌を食べた時点で蛇の頭がある空間と次の餌のある空間が連結でない場合、経路を作れず詰む。これを防ぐために、できるだけ壁伝いに行くとか実装して
