我目前正在研究一个简单的阴影投射算法为一个小的二维游戏。在使用优化的库之前，我想尽可能自己尝试一下。
我觉得我就快到了，但是由于某种原因，我用来检测线源光线和一段光线（障碍物的两边或屏幕边缘）之间的交叉点的方法似乎并不能捕捉到所有的碰撞。
我把错误缩小到这个函数，但找不到错误。我已经经历过很多次了，仍然不明白为什么它不总是起作用。我所有的光线都从屏幕向外延伸，所以我至少应该检测到与屏幕边缘的碰撞我还检查了算法是否在所有光线和片段中循环。
这是检查碰撞的方法：
def check_col(self, ray, source):
'''
segment1 = (self.start,self.end)
segment2 = (source.pos,ray.far_pt)'''
X1,Y1 = self.start #start pt of segment 1
X2,Y2 = self.end #end pt of segment 1
X3,Y3 = source.pos #start pt of segment 2
X4,Y4 = ray.far_pt #end pt of segment 2
'''we are looking to express the segments as:
A*x + b = y '''
'''ensuring mutual abscisse exists'''
if (max(X1,X2) < min(X3,X4)) or (min(X1,X2) > max(X3,X4))\
or (max(Y1,Y2) < min(Y3,Y4)) or (min(Y1,Y2) > max(Y3,Y4)):
return False,0 #no mutual abscisse, 0 added to return a tulpe
'''ensures no division by 0
when calculating the segment
slopes A1 and A2'''
if float(X1-X2) == 0:
X1 +=0.1 #add a small increment to avoid difference to be null
if float(X3-X4) == 0:
X3 += 0.1 #add a small increment to avoid difference to be null
'''calculating segment slopes'''
A1 = (Y1-Y2)/float(X1-X2) # Pay attention to not dividing by zero
A2 = (Y3-Y4)/float(X3-X4) # Pay attention to not dividing by zero
b1 = Y1-A1*X1# = Y2-A1*X2
b2 = Y3-A2*X3# = Y4-A2*X4
'''if slopes are the same, offsets one slightly
to avoid dividing by 0 later on'''
if (A1 == A2):
A1 += 0.0001
'''finding out intersect between the two segments at (Xa,Ya)'''
#A1 * Xa + b1 = A2 * Xa + b2
Xa = int((b2 - b1) / (A1 - A2))# Once again, pay attention to not dividing by zero
Ya = int(A1 * Xa + b1)
#Ya = int(A2 * Xa + b2)
col_pt = (Xa,Ya)
'''make sure intersection is within bounds'''
if max(min(X1,X2),min(X3,X4)) <= Xa <= min(max(X1,X2),max(X3,X4)):
'''calculates distance between the light source and the collision point'''
dist = sqrt((source.pos[0]-col_pt[0])**2+(source.pos[1]-col_pt[1])**2)
return True,col_pt,dist
else:
return False,0 #0 added to return a tulpe
这是一张屏幕截图，显示一些光线没有与蓝色障碍物或墙壁碰撞，而它们显然应该：
最佳答案
你的功能是有缺陷的-像X1 +=0.1这样的碎片会导致奇怪的行为（在垂直段的末端很明显）。使用一些健壮的实现，比如this simple one
（亚历山大·赫里斯托夫。Java，但很容易理解）。
/**
* Computes the intersection between two segments.
* @param x1 Starting point of Segment 1
* @param y1 Starting point of Segment 1
* @param x2 Ending point of Segment 1
* @param y2 Ending point of Segment 1
* @param x3 Starting point of Segment 2
* @param y3 Starting point of Segment 2
* @param x4 Ending point of Segment 2
* @param y4 Ending point of Segment 2
* @return Point where the segments intersect, or null if they don't
*/
public Point intersection(
int x1,int y1,int x2,int y2,
int x3, int y3, int x4,int y4
) {
int d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
if (d == 0) return null;
int xi = ((x3-x4)*(x1*y2-y1*x2)-(x1-x2)*(x3*y4-y3*x4))/d;
int yi = ((y3-y4)*(x1*y2-y1*x2)-(y1-y2)*(x3*y4-y3*x4))/d;
Point p = new Point(xi,yi);
if (xi < Math.min(x1,x2) || xi > Math.max(x1,x2)) return null;
if (xi < Math.min(x3,x4) || xi > Math.max(x3,x4)) return null;
return p;
}
另一个very long discussion在so。
注意，有一些特殊的（更有效的）方法来寻找直线与轴对齐框的边的交集（Line clipping）。我推荐Liang-Barski one。
关于python - 两段之间的交集算法错过了交集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37918677/