python - Overlap between mask and fired beams in Pygame [AI car model vision]

Question

I try to implement beam collision detection with a predefined track mask in Pygame. My final goal is to give an AI car model vision to see a track it's riding on:

This is my current code where I fire beams to mask and try to find an overlap:

import math
import sys

import pygame as pg

RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLUE = (0, 0, 255)

pg.init()
beam_surface = pg.Surface((500, 500), pg.SRCALPHA)


def draw_beam(surface, angle, pos):
    # compute beam final point
    x_dest = 250 + 500 * math.cos(math.radians(angle))
    y_dest = 250 + 500 * math.sin(math.radians(angle))

    beam_surface.fill((0, 0, 0, 0))

    # draw a single beam to the beam surface based on computed final point
    pg.draw.line(beam_surface, BLUE, (250, 250), (x_dest, y_dest))
    beam_mask = pg.mask.from_surface(beam_surface)

    # find overlap between "global mask" and current beam mask
    hit = mask.overlap(beam_mask, (pos[0] - 250, pos[1] - 250))
    if hit is not None:
        pg.draw.line(surface, BLUE, mouse_pos, hit)
        pg.draw.circle(surface, GREEN, hit, 3)


surface = pg.display.set_mode((500, 500))
mask_surface = pg.image.load("../assets/mask.png")
mask = pg.mask.from_surface(mask_surface)
clock = pg.time.Clock()

while True:
    for e in pg.event.get():
        if e.type == pg.QUIT:
            pg.quit()
            sys.exit()

    mouse_pos = pg.mouse.get_pos()

    surface.fill((0, 0, 0))
    surface.blit(mask_surface, mask_surface.get_rect())

    for angle in range(0, 120, 30):
        draw_beam(surface, angle, mouse_pos)

    pg.display.update()
    clock.tick(30)

Let's describe what happens in the code snippet. One by one, I draw beams to beam_surface, make masks from them, and find overlap with background mask defined by one rectangle and a circle (black color in gifs). If there is a "hit point" (overlap point between both masks), I draw it with a line connecting hit point and mouse position.

It works fine for angles <0,90>:

But it's not working for angles in range <90,360>:

Pygame's overlap() documentation tells this:

Starting at the top left corner it checks bits 0 to W - 1 of the first row ((0, 0) to (W - 1, 0)) then continues to the next row ((0, 1) to (W - 1, 1)). Once this entire column block is checked, it continues to the next one (W to 2 * W - 1).

This means that this approach will work only if the beam hits the mask approximately from the top left corner. Do you have any advice on how to make it work for all of the situations? Is this generally a good approach to solve this problem?

Answer 1

Your approach works fine, if the x and y component of the ray axis points in the positive direction, but it fails if it points in the negative direction. As you pointed out, that is caused by the way pygame.mask.Mask.overlap works:

Starting at the top left corner it checks bits 0 to W - 1 of the first row ((0, 0) to (W - 1, 0)) then continues to the next row ((0, 1) to (W - 1, 1)). Once this entire column block is checked, it continues to the next one (W to 2 * W - 1).

To make the algorithm work, you have to ensure that the rays point always in the positive direction. Hence if the ray points in the negative x direction, then flip the mask and the ray vertical and if the ray points in the negative y direction than flip the ray horizontal.

Use pygame.transform.flip() top create 4 masks. Not flipped, flipped horizontal, flipped vertical and flipped vertical and horizontal:

mask = pg.mask.from_surface(mask_surface)
mask_fx = pg.mask.from_surface(pg.transform.flip(mask_surface, True, False))
mask_fy = pg.mask.from_surface(pg.transform.flip(mask_surface, False, True))
mask_fx_fy = pg.mask.from_surface(pg.transform.flip(mask_surface, True, True))
flipped_masks = [[mask, mask_fy], [mask_fx, mask_fx_fy]]

Determine if the direction of the ray:

c = math.cos(math.radians(angle))
s = math.sin(math.radians(angle))

Get the flipped mask dependent on the direction of the ray:

flip_x = c < 0
flip_y = s < 0
filpped_mask = flipped_masks[flip_x][flip_y]

Compute the flipped target point:

x_dest = 250 + 500 * abs(c)
y_dest = 250 + 500 * abs(s)

Compute the flipped offset:

offset_x = 250 - pos[0] if flip_x else pos[0] - 250
offset_y = 250 - pos[1] if flip_y else pos[1] - 250

Get the nearest intersection point of the flipped ray and mask and unflip the intersection point:

hit = filpped_mask.overlap(beam_mask, (offset_x, offset_y))
if hit is not None and (hit[0] != pos[0] or hit[1] != pos[1]):
    hx = 500 - hit[0] if flip_x else hit[0]
    hy = 500 - hit[1] if flip_y else hit[1]
    hit_pos = (hx, hy)

    pg.draw.line(surface, BLUE, mouse_pos, hit_pos)
    pg.draw.circle(surface, GREEN, hit_pos, 3)

See the example: repl.it/@Rabbid76/PyGame-PyGame-SurfaceLineMaskIntersect-2

import math
import sys
import pygame as pg

RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLUE = (0, 0, 255)

pg.init()
beam_surface = pg.Surface((500, 500), pg.SRCALPHA)


def draw_beam(surface, angle, pos):
    c = math.cos(math.radians(angle))
    s = math.sin(math.radians(angle))

    flip_x = c < 0
    flip_y = s < 0
    filpped_mask = flipped_masks[flip_x][flip_y]
    
    # compute beam final point
    x_dest = 250 + 500 * abs(c)
    y_dest = 250 + 500 * abs(s)

    beam_surface.fill((0, 0, 0, 0))

    # draw a single beam to the beam surface based on computed final point
    pg.draw.line(beam_surface, BLUE, (250, 250), (x_dest, y_dest))
    beam_mask = pg.mask.from_surface(beam_surface)

    # find overlap between "global mask" and current beam mask
    offset_x = 250 - pos[0] if flip_x else pos[0] - 250
    offset_y = 250 - pos[1] if flip_y else pos[1] - 250
    hit = filpped_mask.overlap(beam_mask, (offset_x, offset_y))
    if hit is not None and (hit[0] != pos[0] or hit[1] != pos[1]):
        hx = 499 - hit[0] if flip_x else hit[0]
        hy = 499 - hit[1] if flip_y else hit[1]
        hit_pos = (hx, hy)

        pg.draw.line(surface, BLUE, pos, hit_pos)
        pg.draw.circle(surface, GREEN, hit_pos, 3)
        #pg.draw.circle(surface, (255, 255, 0), mouse_pos, 3)


surface = pg.display.set_mode((500, 500))
#mask_surface = pg.image.load("../assets/mask.png")
mask_surface = pg.Surface((500, 500), pg.SRCALPHA)
mask_surface.fill((255, 0, 0))
pg.draw.circle(mask_surface, (0, 0, 0, 0), (250, 250), 100)
pg.draw.rect(mask_surface, (0, 0, 0, 0), (170, 170, 160, 160))

mask = pg.mask.from_surface(mask_surface)
mask_fx = pg.mask.from_surface(pg.transform.flip(mask_surface, True, False))
mask_fy = pg.mask.from_surface(pg.transform.flip(mask_surface, False, True))
mask_fx_fy = pg.mask.from_surface(pg.transform.flip(mask_surface, True, True))
flipped_masks = [[mask, mask_fy], [mask_fx, mask_fx_fy]]

clock = pg.time.Clock()

while True:
    for e in pg.event.get():
        if e.type == pg.QUIT:
            pg.quit()
            sys.exit()

    mouse_pos = pg.mouse.get_pos()

    surface.fill((0, 0, 0))
    surface.blit(mask_surface, mask_surface.get_rect())

    for angle in range(0, 359, 30):
        draw_beam(surface, angle, mouse_pos)

    pg.display.update()
    clock.tick(30)

---

Not,the algorithm can be further improved. The ray is always drawn on the bottom right quadrant of the beam_surface. Hence the other 3 quadrants are no longer needed and the size of beam_surface can be reduced to 250x250. The start of the ray is at (0, 0) rather than (250, 250) and the computation of the offsets hast to be slightly adapted:

beam_surface = pg.Surface((250, 250), pg.SRCALPHA)

def draw_beam(surface, angle, pos):
    c = math.cos(math.radians(angle))
    s = math.sin(math.radians(angle))

    flip_x = c < 0
    flip_y = s < 0
    filpped_mask = flipped_masks[flip_x][flip_y]
    
    # compute beam final point
    x_dest = 500 * abs(c)
    y_dest = 500 * abs(s)

    beam_surface.fill((0, 0, 0, 0))

    # draw a single beam to the beam surface based on computed final point
    pg.draw.line(beam_surface, BLUE, (0, 0), (x_dest, y_dest))
    beam_mask = pg.mask.from_surface(beam_surface)

    # find overlap between "global mask" and current beam mask
    offset_x = 499-pos[0] if flip_x else pos[0]
    offset_y = 499-pos[1] if flip_y else pos[1]
    hit = filpped_mask.overlap(beam_mask, (offset_x, offset_y))
    if hit is not None and (hit[0] != pos[0] or hit[1] != pos[1]):
        hx = 499 - hit[0] if flip_x else hit[0]
        hy = 499 - hit[1] if flip_y else hit[1]
        hit_pos = (hx, hy)

        pg.draw.line(surface, BLUE, pos, hit_pos)
        pg.draw.circle(surface, GREEN, hit_pos, 3)