pythonpygameset-intersectionline-intersection

Finding every point of intersection of multiple lines using pygame in python for creation of game board


I need to find every point of intersection of lines in my code. At these points, I want to put my game pieces. The logic of the game is like that of tic tac toe in which if a player places 3 same color marbles in a row he/she can grab a piece of the other player which are not arranged in a sequence.

My code so far:

import pygame
 
# Define some colors
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
 
# This sets the WIDTH and HEIGHT of each grid location
WIDTH = 20
HEIGHT = 20
 
# This sets the margin between each cell
MARGIN = 5
 
# Create a 2 dimensional array. A two dimensional
# array is simply a list of lists.
grid = []
for row in range(19):
    # Add an empty array that will hold each cell
    # in this row
    grid.append([])
    for column in range(19):
        grid[row].append(0)  # Append a cell
 
# Set row 1, cell 5 to one. (Remember rows and
# column numbers start at zero.)
grid[1][5] = 1
 
pygame.init()
WINDOW_SIZE = [800, 600]
screen = pygame.display.set_mode(WINDOW_SIZE)
pygame.display.set_caption("Array Backed Grid")
done = False
clock = pygame.time.Clock()
while not done:
    # Set the screen background
    screen.fill(BLACK)
 
    # Draw the grid
    for row in range(19):
        for column in range(19):
            color = WHITE
            if grid[row][column] == 1:
                color = GREEN
                board_lines = [
                                ( 13,15,462,15 ), ( 13,469,462,469 ), #lin1 and line2,outer rect
                                ( 62,86,409,86 ), ( 62,389,409,389 ), #line3 and l4,mid reect
                                ( 114,186,360,186 ), ( 114,318,360,318 ), #line5,l6,internl rect
                                ( 13,15,13,469 ), ( 462,12,462,469 ), #line9,l10,left and right sides
                                ( 62,86,62,389 ), ( 409,85,409,389 ), #l7,l8left and right sides
                                ( 114,186,114,316), ( 360,187,360,318 ), #l11,lin12left and right sides
                                ( 237,15,237,186 ), ( 237,469,237,320 ), #upper V.line,lowerV
                                ( 13,242,113,242 ), ( 360,242,462,242 ) #rIGHT LEFT hoRIZONTAL LINE
                                 ] 
                                
                for line in board_lines:
                    line_from = ( line[0], line[1] )
                    line_to   = ( line[2], line[3] )
                    pygame.draw.line( screen, RED, line_from, line_to, 3)

    # Limit to 60 frames per second
    clock.tick(60)
    pygame.display.flip()
 
pygame.quit()

Solution

  • The following function computes the intersection of 2 lines which are given by the points (P0, P1) and (Q0, Q1):

    def lineLineIntersect(P0, P1, Q0, Q1):  
        d = (P1[0]-P0[0]) * (Q1[1]-Q0[1]) + (P1[1]-P0[1]) * (Q0[0]-Q1[0]) 
        if d == 0:
            return None
        t = ((Q0[0]-P0[0]) * (Q1[1]-Q0[1]) + (Q0[1]-P0[1]) * (Q0[0]-Q1[0])) / d
        u = ((Q0[0]-P0[0]) * (P1[1]-P0[1]) + (Q0[1]-P0[1]) * (P0[0]-P1[0])) / d
        if 0 <= t <= 1 and 0 <= u <= 1:
            return round(P1[0] * t + P0[0] * (1-t)), round(P1[1] * t + P0[1] * (1-t))
        return None
    

    The algorithm is explained in detail, in the answer to Problem with calculating line intersections:

    P     ... point on the 1. line
    R     ... normalized direction of the 1. line
    
    Q     ... point on the 2. line
    S     ... normalized direction of the 2. line
    
    alpha ... angle between Q-P and R
    beta  ... angle between R and S
    
    gamma  =  180° - alpha - beta
    
    h  =  | Q - P | * sin(alpha)
    u  =  h / sin(beta)
    
    t  = | Q - P | * sin(gamma) / sin(beta)
    
    t  =  dot(Q-P, (S.y, -S.x)) / dot(R, (S.y, -S.x))  =  determinant(mat2(Q-P, S)) / determinant(mat2(R, S))
    u  =  dot(Q-P, (R.y, -R.x)) / dot(R, (S.y, -S.x))  =  determinant(mat2(Q-P, R)) / determinant(mat2(R, S))
    
    X  =  P + R * t  =  Q + S * u
    

    You've to evaluate if a line segment intersects any other line segments. Iterate through the lines in nested loops and find the intersection of a line with any other line except itself, by using the function lineLineIntersect:

    intersectionPoints = []
    for i, line1 in enumerate(board_lines):
        for line2 in board_lines[i:]:
            isectP = lineLineIntersect(line1[:2], line1[2:], line2[:2], line2[2:])
            if isectP:
                intersectionPoints.append(isectP)
    

    Draw circles at the intersection points:

    for isectP in intersectionPoints:
        pygame.draw.circle(screen, GREEN, isectP, 5)
    

    See the example:

    import pygame
    import math
    
    def lineLineIntersect(P0, P1, Q0, Q1):  
        d = (P1[0]-P0[0]) * (Q1[1]-Q0[1]) + (P1[1]-P0[1]) * (Q0[0]-Q1[0]) 
        if d == 0:
            return None
        t = ((Q0[0]-P0[0]) * (Q1[1]-Q0[1]) + (Q0[1]-P0[1]) * (Q0[0]-Q1[0])) / d
        u = ((Q0[0]-P0[0]) * (P1[1]-P0[1]) + (Q0[1]-P0[1]) * (P0[0]-P1[0])) / d
        if 0 <= t <= 1 and 0 <= u <= 1:
            return round(P1[0] * t + P0[0] * (1-t)), round(P1[1] * t + P0[1] * (1-t))
        return None
    
    board_lines = [
        ( 13,15,462,15 ), ( 13,469,462,469 ), #lin1 and line2,outer rect
        ( 62,86,409,86 ), ( 62,389,409,389 ), #line3 and l4,mid reect
        ( 114,186,360,186 ), ( 114,318,360,318 ), #line5,l6,internl rect
        ( 13,15,13,469 ), ( 462,12,462,469 ), #line9,l10,left and right sides
        ( 62,86,62,389 ), ( 409,85,409,389 ), #l7,l8left and right sides
        ( 114,186,114,316), ( 360,187,360,318 ), #l11,lin12left and right sides
        ( 237,15,237,186 ), ( 237,469,237,320 ), #upper V.line,lowerV
        ( 13,242,113,242 ), ( 360,242,462,242 ) #rIGHT LEFT hoRIZONTAL LINE
    ] 
    
    pygame.init() 
    
    intersectionPoints = []
    for i, line1 in enumerate(board_lines):
        for line2 in board_lines[i:]:
            isectP = lineLineIntersect(line1[:2], line1[2:], line2[:2], line2[2:])
            if isectP:
                intersectionPoints.append(isectP)
     
    # Define some colors
    BLACK = (0, 0, 0)
    WHITE = (255, 255, 255)
    GREEN = (0, 255, 0)
    RED = (255, 0, 0)
     
    # This sets the WIDTH and HEIGHT of each grid location
    WIDTH = 20
    HEIGHT = 20
     
    # This sets the margin between each cell
    MARGIN = 5
     
    # Create a 2 dimensional array. A two dimensional
    # array is simply a list of lists.
    grid = []
    for row in range(19):
        # Add an empty array that will hold each cell
        # in this row
        grid.append([])
        for column in range(19):
            grid[row].append(0)  # Append a cell
     
    # Set row 1, cell 5 to one. (Remember rows and
    # column numbers start at zero.)
    grid[1][5] = 1
     
    WINDOW_SIZE = [800, 600]
    screen = pygame.display.set_mode(WINDOW_SIZE)
    pygame.display.set_caption("Array Backed Grid")
    done = False
    clock = pygame.time.Clock()
    while not done:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                done = True
    
        # Set the screen background
        screen.fill(BLACK)
     
        # Draw the grid
        for row in range(19):
            for column in range(19):
                color = WHITE
                if grid[row][column] == 1:
                    color = GREEN
                    
        for line in board_lines:
            pygame.draw.line(screen, RED, line[:2], line[2:], 3)
    
        for isectP in intersectionPoints:
            pygame.draw.circle(screen, GREEN, isectP, 5)
    
        # Limit to 60 frames per second
        clock.tick(60)
        pygame.display.flip()
     
    pygame.quit()