algorithm - レベル解決と経路探索

Question

最近、Just A Trim Pleaseという小さなフラッシュ ゲームをプレイしましたが、コンセプト全体がとても気に入りました。

ゲームの基本的な目的は、各マスを 1 回通過して芝生全体を刈ることです。芝刈り機はタイルの上からスタートし、そこからあらゆる方向に移動できます (壁に遮られている場合を除く)。草のタイルの上を複数回走ると劣化し、レベルが下がります。上下左右にしか移動できません。ただし、ゲームを終了すると、さらにタイルが追加されます。

• 一度しか刈れないタイル（草）。
• 劣化する前に2 回乗り越えることができるタイル(背の高い草)。
• 好きなだけ上がれるタイプ（コンクリート）。
• 越えられないタイル（壁）。

私の言いたいことが分からない場合は、ゲームをプレイすれば理解できます。

私は、最初の種類のタイル (基本的にはナイツ ツアー問題のバリエーション) だけでパズルを解くことができるブルート フォース アルゴリズムをコード化することができました。ただし、これは最適ではなく、一度しか実行できないタイルのパズルでのみ機能します。余分なタイルをどのように処理するかについて、私は完全に迷っています。

開始点とタイル マップが与えられた場合、レベルを解決するパスを見つける方法またはアルゴリズムはありますか (解決できる場合)? 私は効率を気にしません。これは私が念頭に置いていた質問です。それを解決するためにどのように行かなければならないのか、私は興味があります。

私はコードを探しているのではなく、単なるガイドライン、または可能であれば手順のプレーンテキストの説明を探しています。ただし、疑似コードがある場合は、共有してください。:)

(また、これが経路探索と関係があるかどうかは完全にはわかりませんが、それが私の最善の推測です。)

Answer 1

問題は有限なので、確かにアルゴリズムがあります。

非決定論的アルゴリズムは、正しい動きを推測し、それらが機能することを確認することで、問題を簡単に解決できます。このアルゴリズムは、バックトラッキング検索などを使用して決定できます。

余分なタイル (背の高い草とコンクリート) を標準の草に減らしたい場合は、次のようにします。

• コンクリートのすべての連続ブロックは、最初に 1 つのグラフ頂点に縮小され、次に頂点が削除されます。これは、コンクリート ブロック領域が実際には他のタイルに到達するために移動する方法にすぎないためです。
• 背の高い草タイルはすべて、元の隣接タイルに接続されているが互いに接続されていない 2 つの頂点に置き換えられます。

例: G = 草、T = 背の高い草、C = コンクリート

G G T
G C T
C C G

グラフとして考えてみましょう:

次に、コンクリート ブロックを変形させます。最初にそれらを 1 つに縮小します (すべて接続されているため)。

次に頂点を削除し、それを「介して」接続します。

次に、背の高い草のタイルを展開し、コピーをオリジナルと同じノードに接続します。

次に、T、T' を G に置き換えます。これで、長方形のグリッドではなく、草のノードのみを含むグラフができました。

変換された問題は、元の問題が解ける場合にのみ解くことができ、変換された問題の解を元の問題の解に変換できます。