Trovare ogni punto di intersezione di più linee utilizzando pygame in python per la creazione del tabellone di gioco

Aug 21 2020

Devo trovare ogni punto di intersezione delle linee nel mio codice. A questi punti, voglio mettere i miei pezzi di gioco. La logica del gioco è come quella del tris in cui se un giocatore piazza 3 biglie dello stesso colore in fila può afferrare un pezzo dell'altro giocatore che non sono disposte in sequenza.

Il mio codice finora:

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()

Risposte

1 Rabbid76 Aug 21 2020 at 20:08

La seguente funzione calcola l'intersezione di 2 linee che sono date dai punti ( P0, P1) e ( 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

L'algoritmo è spiegato in dettaglio, nella risposta a Problema con il calcolo delle intersezioni di linee :

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

Devi valutare se un segmento di linea interseca altri segmenti di linea. Scorri le linee in cicli annidati e trova l'intersezione di una linea con qualsiasi altra linea tranne se stessa, utilizzando la funzione 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)

Disegna cerchi nei punti di intersezione:

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

Guarda l'esempio:

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()