我知道我的問題似乎很模糊，但我想不出一個更好的方式來說明，所以我會先解釋我正在嘗試做什麼。圍繞2D地圖的AI導航 - 避開障礙
我目前正在開發一個項目，我已經獲得一張地圖，並且正在編寫一個應該能夠在地圖上導航的「小動物」;生物有其他各種功能，但這些與當前問題無關。整個程序和解決方案都是用C＃編寫的。我可以控制小動物的速度，並通過返回其當前的X和Y位置來檢索它在地圖上的當前位置，我還可以在它與阻止它的地形碰撞時設置它的方向。
我唯一的問題是，我想不出一種方法來智能地導航我的方式圍繞地圖;到目前爲止，我一直以它在與地形碰撞時生物體面臨的方向爲基礎，而這絕不是繞地圖移動的好方法！
我不是一個遊戲程序員，這是一個軟件任務，所以我不知道人工智能技術。
下面是什麼樣的地圖和小動物看起來像一個圖像的鏈接：
我絕不找任何人都可以給我一個完整的解決方案，只是一個推入一般在地圖導航方向。
我會使用一種以目標爲導向的方法。你的問題指出的目標是探索地圖並避開障礙，所以這就是我們的目標。但我們如何探索整個地圖？我們探索什麼是未開發的。
從一開始，您只有一個未開發區域，即您所在的廣場。地圖的其餘部分標記爲未探索。您選擇一個未開發的位置，並將其作爲探索它的目標。但你如何到達那裏？你創建一個子目標來探索它旁邊的位置。你如何做到這一點 - 探索旁邊的廣場，等等，直到你的原始目標被分解爲一系列探索，從你當前的廣場開始，並導航到目標廣場。
當你遇到障礙物並發現地圖的特徵時，一些子目標可能需要更改。例如。當你撞牆時，探索這個廣場的子目標必須被清理，並且你創建了一個新計劃來尋找替代路線。這被稱爲回溯。
這基本上是高層次的描述。我希望它有幫助！
我不會這樣做 - 你想選擇一個附近的目標。我會讓目標去探索最近未知的廣場。 – 2010-05-04 04:51:18
A *搜索
看看在A*尋路算法。它基本上是這種東西的標準方法。
阿米特帕特爾的寫在pathfinding for games有一個相當不錯的介紹A *以及算法的流行變種。
動態A *
比方說，你可以搜索不提前知道地形，而是被發現的代理探討其環境。如果您的代理遇到一個以前未知的障礙，你可以只更新代理的地形地圖，然後重新運行A *尋找新的路徑目標障礙物周圍的路由。
雖然可行的解決方案，每次發現新障礙從頭重新運行規劃算法導致大量的冗餘計算。例如，一旦你在障礙物附近，最有效的途徑可能就是在你發現障礙物之前遵循你打算採取的最有效途徑。通過重新運行A *，您需要重新計算以前路徑的這一部分。
您可以通過使用Dynamic A* (D*)避免這種情況。由於它跟蹤以前計算的路徑，當代理髮現新的障礙物時，系統只需計算障礙物周圍區域的新路線。之後，它可以重複使用現有的路徑。
這是聚焦D *的紙，而不是D *。但是，這些都被D * -Lite所取代。有關更多信息，請參見[here]（http://cstheory.stackexchange.com/a/11866/8532），以及可能適用於OP問題的其他算法。 – 2012-07-13 19:56:21
如果您有環境的唯一知識是你的小動物和它的速度，你能做的最好的位置是牆下面的算法我想。如果你可以檢測到你的環境中的其他一些東西，你有更多的選擇。
一些比較流行的算法類型的...
勢場是奇怪的說每道障礙或牆壁都有「排斥力」的時候艾爾擁有「吸引力」。力的強度取決於與物體的距離和物體的「嚴重性」。 （熔岩坑是更嚴重的比路坎坷穿越）構建的力場天真的算法歸結爲以下阻力最小的路徑之後。更好的版本可以檢測當地的最小值和最大值，並逃離這些井。
Critter
-----\ /-------\
\/ \
\/ \
Local Minima Trap \
\
\
Goal
我似乎遲到了派對。如果你的小動物有GPS和完整的地圖，正確的做法肯定是A *，如果地圖足夠小，如果你不想編碼A *（A *有好幾個角落案例需要處理）。
但是，另一個問題是如果你的小動物只知道目標的方向，只能在本地觀察它是什麼？如果你的小動物不知道完整的地圖怎麼辦？
在這種情況下，你會想實現導航的「bug算法」。鏈接：http://www.cs.cmu.edu/~./motionplanning/lecture/Chap2-Bug-Alg_howie.pdf
這是一個可愛的算法，適用於所有未知的地圖，你會有一個爆炸編碼，我敢肯定。
你說你可以「設置它的方向，當它與阻止它的地形碰撞。」你只能在與某物碰撞時設定方向嗎？或者，您可以在地圖周圍導航時隨意更改方向嗎？ – dmcer 2010-05-02 04:41:14
我可以隨意改變方向！ – 2010-05-05 12:55:55
地圖是否提前完全知道？或者，您是否需要通過與小動物探索地形來發現障礙和獎勵？ – dmcer 2010-05-07 07:29:46