C＃：2D子平鋪線相交

Question

我有一些問題讓我的遊戲運行算法，並希望有人在這裏可以幫助我。谷歌似乎不是一個很好的幫助，因爲大多數解決方案只適用於全瓷磚。在遊戲中，單位可以佔據瓦片內的不同位置，即它們可以位於瓦片（2/3）的左上角，中心，右下角......位置，即（2.2/3.1）， （2.5/3.5），（2.8/3.9）。

如果他們從位置（2.2/3.1）移動到（5.7/4.1），我需要檢查路徑中是否存在障礙物。

我的當前的算法是：

1. 從（2.2/3.1）
2. 開始計算移動的角度（即70度）
3. 移動0.1步驟在該方向
4. 檢查哪個瓦片我是上（地板（PX）/地板（PY））
5. 重複從2

這個算法可行，但對我而言，它看起來效率並不高，因爲障礙只能是一個完整的瓦片，而不是瓦片的一部分（單元不會相互碰撞）。如果我增加步長，我開始錯過只是稍微穿過的貼圖（即，你只穿過最左下角）。即使步長爲0.1，仍然有可能錯過障礙。

我試圖找到一個解決方案採取子地圖（所有瓷磚與角落（樓（start.X）/樓（start.Y））和（ceil（start.X）/ ceil（start.Y ）），遍歷每個瓦片，並在數學上檢查它是否越過。可悲的是，我似乎缺乏這項檢查所需的數學知識。

我最後的想法是將瓦片的所有4個邊界作爲一條線並做一條線-intersection但似乎比我原來的做法更慢。

任何提示？

感謝。

Answer 1

而不是通過沿線逐步追蹤路徑 - 您想要跳到下一個可能的拼貼（邊框）。這可以相當簡單地計算。我將使用上面的示例數字。

1. 計算線等式（Y = + .286x 2.471）
2. 您正在啓動上瓦片2,3和朝向瓷磚5,4移動。因此，計算x到3時的y值（立即向右的邊界）。它是3.329。
3. 然後計算y到4時的x值（上面緊鄰的瓦片的邊界）。它是5.346。
4. 從2,3開始，右移到3,3.329。上漲到5.346.4。你在右邊相交（在x上移動2 - > 3不會移動y上的圖塊）。直到你在x中的第5塊上，你纔會相交。
5. 在4中計算的平鋪成爲您的新比較（3,3）。從步驟2開始重複。

此過程只會導致每個瓷磚移動一次計算（無論您的精度或瓷磚的大小）並且確切無誤。請注意，計算的值可以存儲並重復使用，而不是盲目計算兩個交叉點。在上面我們知道（步驟4），直到x = 5，我們不會向上移動一個瓦片。所以整個路徑可以不經過另一次計算而推斷（2,3→3,3→4,3→5,3→5,4）。

也可以預先計算所有過渡，而不是逐步完成它們，儘管如果您始終需要整個路徑（因爲您希望在找到障礙時停止處理，那麼這樣做只會有所幫助）。

兩個注意事項。要小心跡象和線路的走向 - 許多錯誤發生在不注意負斜率的情況下。另外，使用實際的線索幾乎不會對角線（兩個邊界一次），但你應該知道它（在代碼中處理它）以防萬一。

這個方法有一個名字，但我記不起它的頂部。我相信它可能來自Game Programming Gems系列，但也許別人可以提供更好的參考。