爲推箱子游戲隨機生成級別？

Question

我正在做一個推箱子風格的遊戲（即它不是完全一樣，推箱子，所以我不能用現有的水平），並希望在其上創建隨機水平，使玩家可以繼續玩它，總是有水平試試。有沒有什麼方法可以使計算機自動或半自動地爲我生成關卡（通過半，我的意思是我可以給它初始地圖，但可能沒有包裝箱的位置）？

我有一個想法是隨機生成的地圖，將箱子在他們整理的狀態（即：在十字），然後隨機移動的箱子，好像他們是由遊戲角色拉動。這保證了這個關卡應該是可以解決的。然而，主要問題是如何知道這個級別是否簡單/困難和有趣/無聊？例如，推箱子是NP-hard，所以我不能實際問機器然後檢查是否有簡單的解決方案。

我知道這將是很難創建隨機的水平，將與人類專家競爭，但我只是在尋找的東西，是體面的。

編輯：順便說一下，我會更感興趣，如產生小而有趣的推箱子樣的水平5x5級而不是50x50級。這可能使事情在計算上更可行。

Answer 1

這個網站有一些推箱子級發電機：http://www.erimsever.com/sokoban7.htm

你可能會發現，看他們是如何工作的。