問題歷史/原點

最近我偶然發現Twitch.TV上的 Channels 來自執行經典游戲速度的玩家 . 其中一人打了The Legend of Zelda - A Link to the Past . 我看到了很多低效的動作，我開始懷疑 - 鑒于世界 Map 數據 - 是否有可能編寫一個執行完美速度的機器人 . 一個經常出現的子問題是找到一個平面中兩點之間的最短路徑，我認為這是一個非常有趣的問題，我開始對此進行更多的研究 .

類似的Stackoverflow問題已經發布

... 和更多

其中答案總是為Superproblem(如下所述)提供不同的解決方案，例如使用基于網格的方法，而不是我感興趣的實際子問題(如下所述) .

Superproblem解決方案描述

給定平面中的兩個點 X=(x1,x2) 和 Y=(y1,y2) - 如果平面包含路徑可能無法通過的障礙物/區域，那么從 X 到 Y 的最短路徑是多少？

Differently/ More visually 從Link的當前位置到 Map 上的第二個紅點的最短路徑是什么，因為他無法爬過墻壁或穿過灌木叢？

為此，構造了一個帶有 V= {X,Y} U {"Corner-Points of obstacles}" 的所謂的Visibility Graph . 當且僅當可以從 P 到 Q 繪制直線而不穿過任何障礙物時，邊緣插入點 P and Q 之間 . 每個邊緣由它連接的點之間的Eucledian Distance加權 .

在上面的示例中，可見性圖表看起來像這樣 . 為了便于閱讀，我省略了一些邊緣和重量 . 陰影區域顯示障礙 .

然后，可以使用可見性圖上的開發者最喜歡的最短路徑算法來計算最短路徑 .

子問題描述

讓我們首先將障礙定義為不可通過的地形的連續區域 . 如何找到所有障礙物的最小數量的所需角落(以及角落的坐標)來構建執行最短路徑計算所需的最小可能性圖表？

對于矩形障礙物，很容易找到角落，因為草圖中只有很少的鋒利邊緣......

...或應用于游戲內場景

然而，一旦障礙物具有對角線“前線”，由于誘導的拼圖模式(無論角度)，獲得角落變得非常重要 . 下面的屏幕截圖說明了這個問題：左側圖像顯示哪個坐標點應該被識別為角點，而右側圖片顯示由于“豎鋸” - 對角線圖案而插入附加點的位置 .

現在的問題是：如何從可能非常大的可見性圖中排除/防止這些不必要的角點(被插入)？

總結

以上是生活随笔為你收集整理的java棋盘最短路径障碍物_（Eucledian最短路径）检测平面中障碍物的角落的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。