開發前遊戲 - 一個現實的尋路算法

Question

我正在做一個遊戲，我遇到了難以實現的代碼。我的遊戲是一個有很多追逐你的敵人的瓷磚平臺遊戲。基本上，在理論上，我希望我的敵人能夠以每幀/秒/ 2秒的速度找到我的玩家的現實路徑和最短路徑。我原本以A星爲解決方案，但它將敵人引向違背重力的路徑，這並不好。另外，多個敵人會每秒使用它來獲取最新路徑，然後走過它的前幾個區塊。所以他們會每秒拋棄其餘的路徑，並且只是跟着它的前幾個區塊。我知道這似乎很多，如果他們不止一個敵人，但是我不知道任何其他方式來實現我想要的，每秒鐘都會計算出一條新路徑。 這是我想要的圖片： 說明：綠色圖是玩家，紅色是敵人。灰色的瓷磚是規則的，開放的，沒有瓷磚，棕色瓷磚是你可以站立的瓷磚。最後，突出顯示的黃色方塊表示我希望我的敵人能夠找到的路徑，以便切實地找到玩家。所以問題是：我可以使用什麼樣的現實路徑尋找算法來獲取？保持速度快嗎？

編輯* 我更新了圖片，以表示它們可能是最複雜的地圖。這張地圖代表了我的遊戲玩家實際看到的內容，他們只是使用WASD並可以四處移動，並且他們看到自己在這個2D平臺前視圖中移動。他們將是不同類型的敵人，所有敵人都有不同的速度和跳躍高度。但是所有人都將有足夠的跳躍高度和速度來在這張地圖上跳躍，並通過它進行機動。這些地圖是通過簡單地讀取其中包含關卡數據的XML文件生成的。然後解析數據，並根據XML所說的內容，將不同類型的圖塊放置在圖塊控股精靈中。 EX（XML節點：（type =「reg」graphic =「grass2」x =「5」y =「7」），所以x和y乘以常數gridSize（像30或其他），並放置它們敵人從他們附屬的AI類中獲得逐幀指令，這個類負責產生這條路，並將第一個方向返回給敵人，這應該每隔一秒左右發生一次，以便敵人如果你瞭解我的概念，請告訴我，你有一些想法/想法，或者甚至是我正在尋找的答案。 另外：這個遊戲中的物理是獨立於尋路，他們工作得很好，使用AABB vs AABB概念（玩家和敵人也是AABB）。

Answer 1

在這裏使用A *的技巧是如何將拼貼鏈接在一起形成可用路徑。第一紅色玩家需要跨越的差距。到下一個平臺（左邊的棕色瓷磚）的「連接」實際上是一個跳躍動作，而不是一個移動動作。另外，由您決定節點如何連接在一起;從棕色瓷磚上的灰色瓷磚移動到灰色瓷磚時，我會添加一個沉重的懲罰，對於初學者來說，沒有任何東西在下面（沒有阻止打開快捷方式的跳躍）。

我個人認爲有兩條路線：快速預測玩家可以跳多遠以及跳躍的位置，並調整算法如何確定節點鄰接或接受路徑，並確定路徑的哪些部分「掛起「在空中（緊接着下面沒有棕色的瓦片）並且讓敵人」跳躍「到路線的下一部分。訣竅在於，當敵人可能穿過棕色瓷磚時，即使在路徑中也不是拋物線。

我不熟悉任何一種解決方案;只是我想過的東西。

Answer 2

您需要向我們提供您要自動創建或手動創建的最複雜的地圖，玩家和敵人行爲（包括跳躍和跨越速度）的情況，以便我們提供相關建議。給定的地圖非常簡單，將地圖放在一個二維數組中，然後將初始玩家位置作爲該地圖的一個元素，然後首先測試同一行上的較低數字列是否被棕色佔據重複直到虛假然後同行更高的列等移動敵人。

更新：從我的閱讀階段一代 - 它有時你創造 - 不是半隨機的。

我的建議是敵人用自己的AI創建自己的克隆，但不可見，每個克隆開始向不同的方向跳/向左/右/跳對角線向右/向左，每次成功創建一個新的克隆 - 基本上是遺傳算法。從地圖上看，敵人似乎永遠不需要評估一條路徑，而只有一條路徑不能接近玩家的初始位置，而另一條路徑不會接近玩家的初始位置。