経路アルゴリズムを検討した話 その2

2013 年 12 月 9 日 by 山平

前回はゲームのためのアルゴリズムを探して迷子になってしまいました。

目的は実装なのであまり迷子になってばかりもいられません。
しかたがないので自分で作ってしまうことにします。

アルゴリズム検討

ゲームで使うもの、という前提のため、

  1. 現実的な回数で経路が導き出せればよい
    1. 少なくとも成功率6割は欲しい
    2. 3×3~6×6ぐらいの大きさでよい
  2. なるべくランダムな経路にしたい
    1. 最低限のルール、あとは乱数に

という方針で作ります。
ここで言う「最低限のルール」とは、「窪地の問題」です。

dig_sample

  • 窪地が1つある場合、そこはゴールにしなければならない
  • 2つ以上の窪地ができてしまった場合、一筆で全マスを埋められないことが確定する

作成途中の経路をスキャンして窪地を全て探すのは大変なので、「窪地候補を優先的に埋める」方針にします。

少し改良

取り急ぎ作ってみたものを動かして眺めてみます。
jQueryを使ってでNxMのマスを逐一埋めていく様は見ていて飽きません。

continuable_behind

ですが、失敗と判断しているものの、スタート地点から再開すればまだチャンスがあるのに…ともどかしい気持ちになります。
そこで、

  • これ以上先に進めない場合、スタート地点から再開可能なら現在地をスタート地点に、元のスタート地点を現在地に変更して再開する

というルールを追加しました。
思ったより効果が出ていない気もしますが、今回はここまでです。

タグ:

TrackBack