我已經(jīng)為一個項(xiàng)目編寫了 A* 算法。這個項(xiàng)目的要求之一是隨機(jī)生成50個迷宮。我有點(diǎn)卡住了，因?yàn)檫@與正常的迷宮世代不同。在迷宮世代中，你有阻塞和暢通的墻壁，而在我的情況下，我需要有阻塞和暢通的瓷磚。它也不可能是完美的（應(yīng)該有多個路徑）。我真的無法在網(wǎng)上找到適合這種情況的算法或描述。實(shí)現(xiàn)這一目標(biāo)的最佳方法是什么？如果可能的話，我還想指定一個起點(diǎn)+終點(diǎn)，如果不是那么只是一個起點(diǎn)。謝謝！這是我手動生成的示例迷宮（規(guī)模較?。?
2 回答
尚方寶劍之說
TA貢獻(xiàn)1788條經(jīng)驗(yàn) 獲得超4個贊
您可以使用 union-find 數(shù)據(jù)結(jié)構(gòu)來執(zhí)行此操作，類似于使用 Kruskal 算法生成迷宮：
選擇起點(diǎn)和終點(diǎn)
將除開始和結(jié)束之外的每個單元格標(biāo)記為阻塞，并將每個單元格放在自己的集合中
隨機(jī)解鎖單元格。當(dāng)您取消阻止一個單元格時，將其集合與其連接的任何未阻止單元格的集合合并。
當(dāng)開始單元格的集合與結(jié)束單元格的集合合并時停止。
現(xiàn)在將有一條從開始到結(jié)束的路徑。如果你想確保迷宮更開放一點(diǎn)，你可以保持隨機(jī)解鎖單元格，直到至少 70% 被解鎖。
結(jié)果看起來不會很像傳統(tǒng)的迷宮，但它可能對 A* 測試有好處。
添加回答
舉報
0/150
提交
取消