網格圖中的碰撞檢測？

Question

有一個網格地圖（瓷磚地圖）。在所有的瓷磚中，有些是免費的（空的），有些則是障礙。 現在，如果我隨機選擇清空瓷磚（瓷磚A和瓷磚B）並在它們上繪製一條線段。 什麼是最快的算法來判斷這條線段是否對任何障礙物無碰撞？ （下圖：紅色瓦片障礙，LINE_2是無碰撞，LINE_1不是）

目前，我在做什麼是做一個體素遍歷從一個到乙和檢查遍歷瓷磚是否它是否包含障礙物？

但是否有更好的解決辦法？

Answer 1

我相信，算法的速度取決於場的大小和障礙物的數量。如果場地充滿障礙，你的方式非常出色。

另一種方法是找到光線與瓷磚兩側的交點。

我覺得這種方式是優秀的，如果你有幾個磚和很多的自由空間。

UPD：該方法應通過所有集合的「背面」瓷磚的排除計算來優化。這會減少計算量並加速日常工作。

最後，我相信你可以在你的代碼中使用這兩種算法。您可以通過近似地圖的「密度」來選擇一種方法。