探索/填充網格地圖的算法

Question

我正在一個發生在網格地圖上的小遊戲。我想編寫一個能夠儘可能多地利用可用空間來探索網格地圖的AI。

從任何給定的位置有四種可能的移動（北，南，東，西），但其中一些可能被牆堵塞。另外，一旦我訪問了一個單元，我不想再次訪問它。更重要的是，我想避免陷入困境：如果朝着一個方向前進，意味着我將陷入死衚衕，我寧願不填寫那部分網格。

你能幫我指點一下我該怎麼做？

Answer 1

這blog post應該可以幫助你開始。