與方形網格的最佳線交點

Question

我有用於查找陰影/光線的光線投射算法。

雖然光線在像素座標中，但地圖本身是一個正方形的恆定大小的網格。網格單元可以通過，也可以不通過（方形牆）。典型的許多二維遊戲。

我有光線投射代碼，將光線向前推進，並在光線在牆內時標記。發生這種情況時，光線通常位於細胞內部，而不在邊緣。在那一點上，我有來自光源的起始x/y對，光線經過的角度和牆內的x/y對。

我想找到與牆壁第一接觸點，所以在本質上，我需要「備份」的路線。使用光線來自的角度，我可能只需要測試一個方形的區域來找到相交點。

如果我有一個固定的TILE_WIDTH和TILE_HEIGHT（在這種情況下，他們是平等的太）;是否有任何更優化的具體方法來找到該線段交點的位置？也就是說，它利用了關係，而且我必須比一般算法更簡單和/或更快。

Answer 1

Woo和Amanatides的算法爲Fast Voxel Traversal。它計算光線與矩形網格邊緣的交點。