経路アルゴリズムを検討した話 その２
2013 年 12 月 9 日 by 山平前回はゲームのためのアルゴリズムを探して迷子になってしまいました。
目的は実装なのであまり迷子になってばかりもいられません。
しかたがないので自分で作ってしまうことにします。
アルゴリズム検討
ゲームで使うもの、という前提のため、
- 現実的な回数で経路が導き出せればよい
- 少なくとも成功率6割は欲しい
- 3×3～6×6ぐらいの大きさでよい
- なるべくランダムな経路にしたい
- 最低限のルール、あとは乱数に
という方針で作ります。
ここで言う「最低限のルール」とは、「窪地の問題」です。
- 窪地が１つある場合、そこはゴールにしなければならない
- 2つ以上の窪地ができてしまった場合、一筆で全マスを埋められないことが確定する
作成途中の経路をスキャンして窪地を全て探すのは大変なので、「窪地候補を優先的に埋める」方針にします。
少し改良
取り急ぎ作ってみたものを動かして眺めてみます。
jQueryを使ってでNxMのマスを逐一埋めていく様は見ていて飽きません。
ですが、失敗と判断しているものの、スタート地点から再開すればまだチャンスがあるのに…ともどかしい気持ちになります。
そこで、
- これ以上先に進めない場合、スタート地点から再開可能なら現在地をスタート地点に、元のスタート地点を現在地に変更して再開する
というルールを追加しました。
思ったより効果が出ていない気もしますが、今回はここまでです。
タグ: アルゴリズム
