Intersection between two segments algorithm misses out intersections

Question

I am currently looking into making a simple shadow casting algorithm for a small 2D game. As much as possible I would like to give it a try myself before using optimised libraries.

I feel like I am almost there but for some reason the method I use to detect the intersection between the ray from my line source and a segment (either side of an obstacle or screen edge) doesn't seem to capture all the collisions.

I narrowed the error down to this function but I can't find the error in it. I've been through it many times and still can't figure out why it is not always working. All my rays are extending out of the screen so I should at least detect a collision with the screen edges. I also checked that the algorithm was looping through all the rays and segments.

This is the method to check collisions:

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

And here is a screen shot showing that some rays are not colliding with the blue obstacle or the wall when they clearly should:

Answer 1

Your function is defective - pieces like X1 +=0.1 cause weird behavior (it is clear near ends of vertical segments). Use some robust implementation like this simple one
(Alexander Hristov. Java but easy understandable).

/**
 * 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;
}

Another very long discussion at SO.

Note that there are special (more effective) methods intended to find intersection of line with edges of axis-aligned box (Line clipping). I'd recommend Liang-Barski one.