2

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()
Improve this question

1 Answer 1

Reset to default
1

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()
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

can you please tell me the name of this algorithm so that i can learn more about it. thanks for the help.
@shyckh As far as I know the algorithm has no specific name, but it is based on the Dot product. Ssee also Given a line in 3D space, how do I find the angle from it to a point? respectively Line–line intersection.
and intersection point data is stored in intersectingPoints = []?
Yes, intersectingPoints is the list of intersection points
One more question! Is it necessary to use surface screen.blit in order to get mouse control or whats the use of blitting?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.