基於X範圍查找網格中的有效節點

我在基於中心點和最大範圍的網格中查找N個位置時遇到問題。基於X範圍查找網格中的有效節點

我有這個網格，網格中的每個座標都可以是關閉或打開的，我打算使用一個打開的座標找到所有打開的座標，第一個有效的座標和之間的步距是等於或低於最大步行距離。

起初我嘗試了一個使用A *的解決方案，在那裏我會選擇範圍內的每個座標，檢查它們是否有效，如果它們是我會從它們調用A *到中心位置並計算步數，如果它們高於我的最大範圍，我會從列表中刪除座標。當然，對於高於3的範圍或者具有不止幾個座標的網格，這確實是緩慢的。然後我試着遞歸地搜索座標，從中心座標開始，擴展並遞歸地檢查座標有效性。該解決方案證明是最有效的，除了在我的代碼中，每個函數調用都是重新檢查已經檢查過的座標並返回重複的值。我想我可以在函數調用之間共享'checked'列表，但是這只是打破了我的代碼，因爲調用正在檢查一個座標並關閉它，即使它仍然有子節點但技術上不在它們中心的範圍內但在第一中心的範圍內），它會關閉它們並給出一些奇怪的結果。

最後，我的問題是，我該怎麼做？我的方法錯了嗎？有沒有更好的方法來做到這一點？

謝謝。

來源

2011-11-04 Luke B.

我實現了一次類似的東西。你提出的簡單的遞歸解決方案適用於小步行範圍，但執行時間失控的更大的值...

我改進了這一點，實現了Dijkstra算法的變體，它保留了訪問節點列表說過。但是，如果N是你的步行距離（維基百科上的gif可能會幫助你理解我的意思），那麼不要像對待A *一樣對每個座標進行全路徑搜索，而要執行算法的前N次迭代。您訪問的節點列表將成爲您要查找的可到達磁貼。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

來源

2011-11-04 22:34:06 wutz

工作正常！正確實施它有點痛苦，但最終是最好的解決方案。謝謝：） –

基於X範圍查找網格中的有效節點

回答

相關問題