python - Pygame 中的 2D 光线转换和矩形碰撞(视线，障碍物)

Question

新程序员在我的腰带下使用了三个月的 Python(只有几周的 pygame)......
我正在设计一个 2-D、自上而下的游戏，并且一直在尝试设置障碍来打破 sprite LOS。我目前的尝试是让每个 Sprite 向可视范围内的每个其他 Sprite 转换一条光线，如果光线与 LOS 阻止程序的矩形碰撞，则停止，并仅将可见 Sprite 添加到列表中。
到目前为止， Sprite 总是隔着墙看到彼此。我认为这是一个迭代/缩进/太多循环问题。我尝试过 bool 类型的中断并将代码放在一个带有返回的函数中(在代码中的几个不同点)，但它没有帮助——怪物总是直奔玩家直到他们撞到墙上。
图片 :X-Ray Vision
谷歌研究和试错已经几天了，但没有快乐。任何在正确方向上的解决或插入都非常感谢!
相关代码如下。
墙类
实现

    wall = GraphBoxSprite('wall', (WIDTH // 2 - 25, HEIGHT // 2 - 10), 50, 20, BLACK, False, walls, obstacles, losBlockers, allSprites)

代码

class GraphBoxSprite(pygame.sprite.Sprite):
    # Creates a sprite the size and shape of supplied graph size
    def __init__(self, ID, position, squareWidth, squareHeight, colour, transparent=False, *groups):
        super().__init__(*groups)
        self.ID = ID
        self.position = position
        self.image = pygame.Surface((squareWidth, squareHeight)) # Blank surface
        self.rect = self.image.get_rect(topleft=position)
        self.image.fill(colour)
        if transparent is True:
            self.image.set_colorkey(colour) # Transparent background

生物类
实现

    character = CreatureSprite('character', (WIDTH // 2, HEIGHT // 2 - 50), MEDIUM, QUICK, QUIET, BLUE_LINE, CANDLELIGHT, None, None, characters, allCreatures, allSprites)

代码

class CreatureSprite(pygame.sprite.Sprite):
    # Creates a sprite to order
    def __init__(self, ID, position, size, speed, noiseLevel=None, colour=GREY, lightRadius=None, infravision=None, image=None, *groups):
        super().__init__(*groups)
        self.image = pygame.Surface(size) # Blank surface for image
        self.image.fill(WHITE)
        self.image.set_colorkey(WHITE) # Transparent background
        self.rect = self.image.get_rect(topleft=position)

        self.ID = ID
        self.size = size
        self.colour = colour
        self.lightRadius = lightRadius

        self.losLength = 600 # view distance
        self.losWidth = 150 # degrees

        self.position = Vector2(position)
        self.speed = int(speed / (GRID_SCALE * 10))
        self.velocity = Vector2(0, 0)

        self.destination = Vector2(position)
        self.destinationRadius = 40
        self.heading = self.destination - self.position

        
    def update(self, walls, dungeonDressings, obstacles, losBlockers, monsters, characters, allCreatures, dungeonLights, creatureLights, allLights, allSprites):
        # Draw the creature
        pygame.draw.circle(self.image, self.colour, (self.size[0] // 2, self.size[1] // 2), self.size[0] // 2)
        pygame.draw.line(self.image, WHITE, (self.size[0] // 2, self.size[1] // 2), (self.size[0]  // 2, self.size[1] - 20), 1)


        # Draw light over darkness and colour over light
        if self.lightRadius:
            spritePosition = (int(self.position[0]), int(self.position[1])) # syntactic sugar
            pygame.draw.circle(DARKNESS, (COLOURKEY), spritePosition, self.lightRadius * GRID_SCALE)
            pygame.draw.circle(LIGHTNESS, (GOLDENROD), spritePosition, self.lightRadius * GRID_SCALE)


        # Movement
        self.position += self.velocity  # Update the position vector first
        self.rect.center = self.position  # Update the rect afterwards

        # This vector points to the destination
        self.heading = self.destination - self.position
        distance = self.heading.length()

        # Normalize heading for scale to desired length/speed below
        if self.heading: # Cannot normalize a zero vector
            self.heading.normalize_ip()
            
            # Sprite rotation to heading
            #self.image = pygame.transform.rotate(self.image, self.heading) --- won't accept Vector2, only real number ---

            # Slow down when approaching destination
            if distance > self.destinationRadius:
                self.velocity = self.heading * self.speed
            elif distance <= 15:
                for sprite in allSprites:
                    if sprite in allCreatures or sprite in obstacles: # Creatures maintain personal space
                        self.velocity = Vector2(0, 0)
            else:
                self.velocity = self.heading * (distance / self.destinationRadius * self.speed)


        # Line of Sight
        targets = []
        visible = []
        seen = []

        for target in allSprites:
            if target != self:
                targets.append(target.ID)
                lineOfSight = target.position - self.position
                lineOfSightDist = lineOfSight.length()
                
                if lineOfSightDist < self.losLength: # Target in range
                    #if self.heading < self.losWidth: # Target in field of view --- need to convert to comparable format ---
                    x = self.position[0]
                    y = self.position[1]

                    for i in range(int(lineOfSightDist)): # Try to reach target with a cast ray
                        x += lineOfSight[0]
                        y += lineOfSight[1]
                        
                        for sprite in allSprites:
                            if sprite.rect.collidepoint(int(round(x)), int(round(y))):
                                if sprite in losBlockers: # Stop ray
                                    seen.append(sprite)
                                    visible.append(target.ID)
                                    break
                                else:
                                    seen.append(sprite)
                                    visible.append(target.ID)
                                    break

        print('{} sees {} out of {} in range'.format(self.ID, visible, targets))
        

        # Creature AI
        if self.ID == 'monster':
            if seen:
                for sprite in seen:
                    if sprite.ID == 'character':
                        self.destination = sprite.position


        # When sprites collide
        for sprite in allSprites:
            if self.rect.colliderect(sprite):
                if self in allCreatures and sprite in obstacles:
                    self.velocity = Vector2(0, 0)


    def changeColour(self, colour):
        self.colour = colour

完整代码

import os, sys, ctypes, random, math, copy, time, pickle, shelve, pprint, pygame # Inbuilt functions
import charReference, equipment # Reference material
from pygame.locals import *
from pygame.math import Vector2

pygame.init() 
pygame.display.set_caption('LOOT OR DIE!')

directory = 'C:\\Users\\user\\OneDrive\\LootOrDie\\'

pygame.font.init()


# Main fonts
font             = pygame.font.Font(directory + 'fonts\\Cour.ttf', 18)
fontB            = pygame.font.Font(directory + 'fonts\\Courbd.ttf', 18)
fontI            = pygame.font.Font(directory + 'fonts\\Couri.ttf', 18)
fontBI           = pygame.font.Font(directory + 'fonts\\Courbi.ttf', 18)
smallFont        = pygame.font.Font(directory + 'fonts\\Cour.ttf', 16)
smallFontB       = pygame.font.Font(directory + 'fonts\\Courbd.ttf', 16)
smallFontI       = pygame.font.Font(directory + 'fonts\\Couri.ttf', 16)
smallFontBI      = pygame.font.Font(directory + 'fonts\\Courbi.ttf', 16)
bigFont          = pygame.font.Font(directory + 'fonts\\Cour.ttf', 24)
bigFontB         = pygame.font.Font(directory + 'fonts\\Courbd.ttf', 24)
bigFontI         = pygame.font.Font(directory + 'fonts\\Couri.ttf', 24)
bigFontBI        = pygame.font.Font(directory + 'fonts\\Courbi.ttf', 24)


# Colours
COLOURKEY    = (127,  33,  33) # Transparent colour key

BLACK        = (  0,   0,   0)
WHITE        = (255, 255, 255)
DARKGREY     = ( 64,  64,  64)
GREY         = (128, 128, 128)
LIGHTGREY    = (200, 200, 200)

PINK_LINE    = (238, 106, 167)
RED          = (179,   0,   0)
BLOOD        = (138,   3,   3)
ORANGE       = (255, 185,   0)

GOLD         = (100,  84,   0)
GOLDENROD    = (212, 175,  55)
GREEN        = (  0, 130,   0)
FOREST_GREEN = ( 11, 102,  35)

BLUE_LINE    = (100, 149, 237)
BLUE_INK     = (  0,   0, 128)
DARK_BLUE    = (  0,  60, 120)



""" Define Screen """
# Prevent screen stretching
preventStretch = True
if preventStretch is True:
    user32 = ctypes.windll.user32
    user32.SetProcessDPIAware()


SCREEN_SIZE = WIDTH, HEIGHT = (1440, 900)
SCREEN = pygame.display.set_mode(SCREEN_SIZE, pygame.RESIZABLE) # FULLSCREEN

LEFT_MARGIN = 40
TOP_MARGIN = 26
LINE_HEIGHT = 22

COL1 = LEFT_MARGIN 
COL2 = int(SCREEN.get_width() / 4 + (LEFT_MARGIN * 2))
COL3 = int(((SCREEN.get_width() / 4) + (LEFT_MARGIN * 2)) * 2)
COL4 = int(((SCREEN.get_width() / 4) + (LEFT_MARGIN * 2)) * 3)


# Timing and FPS
clock = pygame.time.Clock()
FPS = 60

# Double mouse-click half second delay
doubleClickClock = pygame.time.Clock()
DOUBLE_MOUSE_CLICK_TIME = 500 



""" Define Buttons """
MENU_BUTTON_WIDTH = 150
MENU_BUTTON_HEIGHT = 30

LINE_BUTTON_WIDTH = int(SCREEN.get_width() / 4 - (LEFT_MARGIN * 2))
LINE_BUTTON_HEIGHT = LINE_HEIGHT - 2

EQUIP_BUTTON_WIDTH = int(SCREEN.get_width() / 2 - (LEFT_MARGIN * 2))
BODY_BUTTON_WIDTH = 255

# TextLine Buttons
col_1_textLines = []
col_2_textLines = []
col_3_textLines = []

lineNo = 0
for line in range(40): # The maximum number of lines per screen
    line = COL1, TOP_MARGIN + LINE_HEIGHT * lineNo
    col_1_textLines.append(line)
    lineNo += 1

col_2_textLines = []
lineNo = 0
for line in range(40):
    line = COL2, TOP_MARGIN + LINE_HEIGHT * lineNo
    col_2_textLines.append(line)
    lineNo += 1

col_2_textLines = []
lineNo = 0
for line in range(40):
    line = COL2, TOP_MARGIN + LINE_HEIGHT * lineNo
    col_2_textLines.append(line)
    lineNo += 1



""" Dungeon Settings """
# Graph paper coordinates
GRID_SCALE    = 5 # feet per square
SQUARE_WIDTH  = 20
SQUARE_HEIGHT = 20
GRID_MARGIN   = 1 # between squares

# Creature Sizes
TINY   = (5, 5)
SMALL  = (10, 10)
MEDIUM = (15, 15)
LARGE  = (20, 20)
HUGE   = (40, 40)

# Creature Speeds and Noise Levels
""" Run is * 10 """
STATIONARY = SILENT      = 0
SHAMBOLIC  = STEALTHY    = 15
SLUGGISH   = QUIET       = 30
SLOW       = NOISY       = 60
PLODDING   = LOUD        = 90
QUICK      = CACOPHONOUS = 120

# Light Source Radii
CANDLELIGHT       = 10
SMALL_ITEMLIGHT   = 10
MEDIUM_ITEMLIGHT  = 15
LONG_ITEMLIGHT    = 20
LANTERNLIGHT      = 30
TORCHLIGHT        = 40

# Cloak screen in darkness
DARKNESS = pygame.Surface(SCREEN_SIZE)
DARKNESS.set_colorkey(COLOURKEY)

# Mask for light colour
LIGHTNESS = pygame.Surface(SCREEN_SIZE)
LIGHTNESS.set_colorkey(COLOURKEY)


def dungeon():
    # Window for testing
    windowSize = windowWidth, windowHeight = WIDTH, HEIGHT
    window = pygame.Surface(windowSize)

    """ Sprite Groups """
    # Dungeon
    walls = pygame.sprite.Group()
    dungeonDressings = pygame.sprite.Group()
    obstacles = pygame.sprite.Group() # Anything that blocks movement
    losBlockers = pygame.sprite.Group() # Anything that blocks line of sight (LOS)

    # Creatures
    characters = pygame.sprite.Group()
    monsters = pygame.sprite.Group()
    allCreatures = pygame.sprite.Group()

    # Lights
    dungeonLights = pygame.sprite.Group()
    creatureLights = pygame.sprite.Group()
    allLights = pygame.sprite.Group()

    # Everything
    allSprites = pygame.sprite.Group()


    """ Sprites """
    # Character sprites
    character = CreatureSprite('character', (WIDTH // 2, HEIGHT // 2 - 50), MEDIUM, QUICK, QUIET, BLUE_LINE, CANDLELIGHT, None, None, characters, allCreatures, allSprites)

    # Enemy sprites
    for monster in range(1):
        orc = CreatureSprite('monster', (WIDTH // 2, HEIGHT // 2 + 50), MEDIUM, PLODDING, NOISY, BLOOD, TORCHLIGHT, None, None, monsters, allCreatures, allSprites)

    # The Wall
    wall = GraphBoxSprite('wall', (WIDTH // 2 - 25, HEIGHT // 2 - 10), 50, 20, BLACK, False, walls, obstacles, losBlockers, allSprites)


    selectedObject = None
    destinationPoint = None


    while True: # Main Loop
        clock.tick(FPS) # Set framerate

        # Capture mouse coordinates on screen and in window
        mousePos = x, y = pygame.mouse.get_pos() 
        mouseWindowPos = (x - int(WIDTH / 2 - windowWidth / 2), y - int(HEIGHT / 2 - windowHeight / 2))

        for event in pygame.event.get():
            if event.type == QUIT:
                pygame.quit()
                sys.exit()

            if event.type == KEYDOWN:
                if event.key == K_ESCAPE:
                    if selectedObject:
                        if selectedObject in characters:
                            selectedObject.changeColour(BLUE_LINE)
                        elif selectedObject in monsters:
                            selectedObject.changeColour(BLOOD)
                        selectedObject = None
                    else:
                        quitGame()

            # Set destination with mouse-click
            if event.type == MOUSEBUTTONDOWN:
                # Check for double click event
                doubleClick = False
                if doubleClickClock.tick() < DOUBLE_MOUSE_CLICK_TIME:
                    doubleClick = True

                if event.button == 1:
                    if selectedObject: # Single-click to de-select sprite
                        if selectedObject in characters:
                            selectedObject.changeColour(BLUE_LINE)
                        elif selectedObject in monsters:
                            selectedObject.changeColour(BLOOD)
                        selectedObject = None

                    elif not selectedObject: # Single-click to select new sprite
                        for sprite in allCreatures:
                            if sprite.rect.collidepoint(mouseWindowPos):
                                selectedObject = sprite
                                selectedObject.changeColour(GOLDENROD)

                elif event.button == 3:
                    if selectedObject: # Send selected sprite to destination
                        selectedObject.destination = mouseWindowPos


        # Arrange dark and light sources
        DARKNESS.fill(0)
        LIGHTNESS.fill(COLOURKEY)

        # Draw squares on coloured background to mimic graph paper
        window.fill(BLUE_LINE)
        for column in range(SQUARE_WIDTH + GRID_MARGIN, windowWidth, SQUARE_WIDTH + GRID_MARGIN):
            for row in range(SQUARE_HEIGHT + GRID_MARGIN, windowHeight, SQUARE_HEIGHT + GRID_MARGIN):
                pygame.draw.rect(window, WHITE, [column, row, SQUARE_WIDTH, SQUARE_HEIGHT])

        # Update Sprites
        allSprites.update(window, walls, dungeonDressings, obstacles, losBlockers, monsters, characters, allCreatures, dungeonLights, creatureLights, allLights, allSprites)

        # Draw items
        walls.draw(window)
        allCreatures.draw(window)

        # Draw screen overlaid with darkness overlaid by lit areas
        SCREEN.blit(window, (WIDTH // 2 - windowWidth // 2, HEIGHT // 2 - windowHeight // 2))

        # Make LIGHTNESS surface partially transparent
        LIGHTNESS.set_alpha(75)
        SCREEN.blit(LIGHTNESS, (0, 0))
        SCREEN.blit(DARKNESS, (0, 0))
        pygame.display.update()



class GraphBoxSprite(pygame.sprite.Sprite):
    # Creates a sprite the size and shape of supplied graph size
    def __init__(self, ID, position, squareWidth, squareHeight, colour, transparent=False, *groups):
        super().__init__(*groups)
        self.ID = ID
        self.position = position
        self.image = pygame.Surface((squareWidth, squareHeight)) # Blank surface
        self.rect = self.image.get_rect(topleft=position)
        self.image.fill(colour)
        if transparent is True:
            self.image.set_colorkey(colour) # Transparent background



class CreatureSprite(pygame.sprite.Sprite):
    # Creates a sprite to order
    def __init__(self, ID, position, size, speed, noiseLevel=None, colour=GREY, lightRadius=None, infravision=None, image=None, *groups):
        super().__init__(*groups)
        self.image = pygame.Surface(size) # Blank surface for image
        self.image.fill(WHITE)
        self.image.set_colorkey(WHITE) # Transparent background
        self.rect = self.image.get_rect(topleft=position)

        self.ID = ID
        self.size = size
        self.colour = colour
        self.lightRadius = lightRadius

        self.losLength = 600 # view distance
        self.losWidth = 150 # degrees

        self.position = Vector2(position)
        self.speed = int(speed / (GRID_SCALE * 10))
        self.velocity = Vector2(0, 0)

        self.destination = Vector2(position)
        self.destinationRadius = 40
        self.heading = self.destination - self.position

        
    def update(self, walls, dungeonDressings, obstacles, losBlockers, monsters, characters, allCreatures, dungeonLights, creatureLights, allLights, allSprites):
        # Draw the creature
        pygame.draw.circle(self.image, self.colour, (self.size[0] // 2, self.size[1] // 2), self.size[0] // 2)
        pygame.draw.line(self.image, WHITE, (self.size[0] // 2, self.size[1] // 2), (self.size[0]  // 2, self.size[1] - 20), 1)


        # Draw light over darkness and colour over light
        if self.lightRadius:
            spritePosition = (int(self.position[0]), int(self.position[1])) # syntactic sugar
            pygame.draw.circle(DARKNESS, (COLOURKEY), spritePosition, self.lightRadius * GRID_SCALE)
            pygame.draw.circle(LIGHTNESS, (GOLDENROD), spritePosition, self.lightRadius * GRID_SCALE)


        # Movement
        self.position += self.velocity  # Update the position vector first
        self.rect.center = self.position  # Update the rect afterwards

        # This vector points to the destination
        self.heading = self.destination - self.position
        distance = self.heading.length()

        # Normalize heading for scale to desired length/speed below
        if self.heading: # Cannot normalize a zero vector
            self.heading.normalize_ip()
            
            # Sprite rotation to heading
            #self.image = pygame.transform.rotate(self.image, self.heading) --- won't accept Vector2, only real number ---

            # Slow down when approaching destination
            if distance > self.destinationRadius:
                self.velocity = self.heading * self.speed
            elif distance <= 15:
                for sprite in allSprites:
                    if sprite in allCreatures or sprite in obstacles: # Creatures maintain personal space
                        self.velocity = Vector2(0, 0)
            else:
                self.velocity = self.heading * (distance / self.destinationRadius * self.speed)


        # Line of Sight
        targets = []
        visible = []
        seen = []

        for target in allSprites:
            if target != self:
                targets.append(target.ID)
                lineOfSight = target.position - self.position
                lineOfSightDist = lineOfSight.length()
                
                if lineOfSightDist < self.losLength: # Target in range
                    #if self.heading < self.losWidth: # Target in field of view --- need to convert to comparable format ---
                    x = self.position[0]
                    y = self.position[1]

                    for i in range(int(lineOfSightDist)): # Try to reach target with a cast ray
                        x += lineOfSight[0]
                        y += lineOfSight[1]
                        
                        for sprite in allSprites:
                            if sprite.rect.collidepoint(int(round(x)), int(round(y))):
                                if sprite in losBlockers: # Stop ray
                                    seen.append(sprite)
                                    visible.append(target.ID)
                                    break
                                else:
                                    seen.append(sprite)
                                    visible.append(target.ID)
                                    break

        print('{} sees {} out of {} in range'.format(self.ID, visible, targets))
        

        # Creature AI
        if self.ID == 'monster':
            if seen:
                for sprite in seen:
                    if sprite.ID == 'character':
                        self.destination = sprite.position


        # When sprites collide
        for sprite in allSprites:
            if self.rect.colliderect(sprite):
                if self in allCreatures and sprite in obstacles:
                    self.velocity = Vector2(0, 0)


    def changeColour(self, colour):
        self.colour = colour



def quitGame():
    pygame.quit()
    sys.exit()



def waitForKeyPress():
    # Pause program until a key is pressed
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
                sys.exit()

            if event.type == pygame.KEYDOWN or event.type == pygame.MOUSEBUTTONDOWN:
                return



""" Start Game """
if __name__ == '__main__':
    dungeon()

Answer 1

我无法仅从静态代码的一部分中看出为什么您的程序不起作用，似乎应该如此。
但是，我可以提供我自己的解决方案:
对于每个 NPC/对手:

计算每个 NPC 之间的线和播放器。这里我们只使用 Sprite 矩形的中心，因为它很容易。如果您愿意，可以将其视为“射线”。

确定是否有任何 Wall/Blocker 对象位于这条线/射线上。

如果是这样，视线被破坏了，我们可以停止检查。

所以视线就是简单的(Player-x, Player-y)到(NPC-x, NPC-y)，定义一条线。
每个 Wall 对象都是四条线(形成一个矩形)，因此我们检查 Player-NPC 线与每条矩形边线的交点。这简化了对一些没有三角函数或平方根的线性几何的检查。也没有必要沿着视线“走”来检查遮挡，一旦在线上发现任何东西，NPC 就看不到玩家。
注意:根据设计，我们不会检查 NPC 是否遮挡了其他 NPC 的视野。

引用代码:

import pygame
import random

WINDOW_WIDTH = 800
WINDOW_HEIGHT= 600
SURFACE = pygame.HWSURFACE|pygame.DOUBLEBUF|pygame.RESIZABLE

#define colour
WHITE = ( 200, 200, 200)
GREY  = ( 50, 50, 50)
BLACK = (0,0,0)
RED   = ( 200, 0, 0 )
GREEN = (0,255,0)
TAN   = (240,171,15)
YELLOW= (255,255,0)


def lineRectIntersectionPoints( line, rect ):
    """ Get the list of points where the line and rect
        intersect,  The result may be zero, one or two points.

        BUG: This function fails when the line and the side
             of the rectangle overlap """

    def linesAreParallel( x1,y1, x2,y2, x3,y3, x4,y4 ):
        """ Return True if the given lines (x1,y1)-(x2,y2) and
            (x3,y3)-(x4,y4) are parallel """
        return (((x1-x2)*(y3-y4)) - ((y1-y2)*(x3-x4)) == 0)

    def intersectionPoint( x1,y1, x2,y2, x3,y3, x4,y4 ):
        """ Return the point where the lines through (x1,y1)-(x2,y2)
            and (x3,y3)-(x4,y4) cross.  This may not be on-screen  """
        #Use determinant method, as per
        #Ref: https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
        Px = ((((x1*y2)-(y1*x2))*(x3 - x4)) - ((x1-x2)*((x3*y4)-(y3*x4)))) / (((x1-x2)*(y3-y4)) - ((y1-y2)*(x3-x4)))
        Py = ((((x1*y2)-(y1*x2))*(y3 - y4)) - ((y1-y2)*((x3*y4)-(y3*x4)))) / (((x1-x2)*(y3-y4)) - ((y1-y2)*(x3-x4)))
        return Px,Py

    ### Begin the intersection tests
    result = []
    line_x1, line_y1, line_x2, line_y2 = line   # split into components
    pos_x, pos_y, width, height = rect

    ### Convert the rectangle into 4 lines
    rect_lines = [ ( pos_x, pos_y, pos_x+width, pos_y ), ( pos_x, pos_y+height, pos_x+width, pos_y+height ),  # top & bottom
                   ( pos_x, pos_y, pos_x, pos_y+height ), ( pos_x+width, pos_y, pos_x+width, pos_y+height ) ] # left & right

    ### intersect each rect-side with the line
    for r in rect_lines:
        rx1,ry1,rx2,ry2 = r
        if ( not linesAreParallel( line_x1,line_y1, line_x2,line_y2, rx1,ry1, rx2,ry2 ) ):    # not parallel
            pX, pY = intersectionPoint( line_x1,line_y1, line_x2,line_y2, rx1,ry1, rx2,ry2 )  # so intersecting somewhere
            pX = round( pX )
            pY = round( pY )
            # Lines intersect, but is on the rectangle, and between the line end-points?
            if ( rect.collidepoint( pX, pY )   and
                 pX >= min( line_x1, line_x2 ) and pX <= max( line_x1, line_x2 ) and
                 pY >= min( line_y1, line_y2 ) and pY <= max( line_y1, line_y2 ) ):
                pygame.draw.circle( window, WHITE, ( pX, pY ), 4 )
                result.append( ( pX, pY ) )                                     # keep it
                if ( len( result ) == 2 ):
                    break   # Once we've found 2 intersection points, that's it
    return result



class Wall( pygame.sprite.Sprite):
    """ Rectangular objects that blocks line-of-sight """
    def __init__( self, x, y, width, height ):
        pygame.sprite.Sprite.__init__( self )
        self.image = pygame.Surface( ( width, height ) )
        self.rect  = self.image.get_rect();
        self.rect.topleft = ( x, y )
        self.image.fill( TAN )

    def getRect( self ):
        return self.rect
        

class Being( pygame.sprite.Sprite):
    """ Some kind of creature with miraculous 360 degree vision """
    def __init__( self, x, y, colour=YELLOW, size=48 ):
        pygame.sprite.Sprite.__init__( self )
        self.colour= colour
        self.image = pygame.Surface( ( size, size ), pygame.SRCALPHA )
        self.rect  = self.image.get_rect();
        self.rect.center = ( x, y )
        self.size  = size
        self.seen  = False
        self.update()

    def update( self ):
        """ If we've been seen, go red with embrassment """
        if ( self.seen ):
            colour = RED
        else:
            colour = self.colour
        pygame.draw.circle( self.image, colour, ( self.size//2, self.size//2 ), self.size//2 )

    def setSeen( self, seen=True ):
        self.seen = seen

    def getCentre( self ):
        return self.rect.center

    def getRect( self ):
        return self.rect




### initialisation
pygame.init()
pygame.mixer.init()
window = pygame.display.set_mode( ( WINDOW_WIDTH, WINDOW_HEIGHT ), SURFACE )
pygame.display.set_caption("Line of Sight")

# Occluders
wall_sprites = pygame.sprite.Group()
central_block = Wall( WINDOW_WIDTH//3, WINDOW_HEIGHT//2, WINDOW_WIDTH//3, 20 )  # top middle (random)
wall_sprites.add( central_block )

# NPCs
npc_sprites = pygame.sprite.Group()
for i in range( 3 ):
    npc_sprites.add( Being( random.randint( 50, WINDOW_WIDTH-50 ), 50, GREEN ) )

# Player
player_sprite = pygame.sprite.GroupSingle()
player = Being( WINDOW_WIDTH//2, 3*WINDOW_HEIGHT//4 )  # bottom middle
player_sprite.add ( player )


### Main Loop
clock = pygame.time.Clock()
done = False
while not done:

    # Handle user-input
    for event in pygame.event.get():
        if ( event.type == pygame.QUIT ):
            done = True
        elif ( event.type == pygame.MOUSEBUTTONUP ):
            # On mouse-click
            pass

    # Movement keys
    keys = pygame.key.get_pressed()
    if ( keys[pygame.K_LEFT] ):
        player.rect.x -= 1
    if ( keys[pygame.K_RIGHT] ):
        player.rect.x += 1
    if ( keys[pygame.K_UP] ):
        player.rect.y -= 1
    if ( keys[pygame.K_DOWN] ):
        player.rect.y += 1


    # Update the window, but not more than 60fps
    window.fill( BLACK )

    # Check to see if the Player can see any NPCs
    player_centre = player.getCentre()
    for npc in npc_sprites:
        npc_centre = npc.getCentre()
        # Does the line <player> to <npc> intersect any obstacles?
        line_of_sight = [ player_centre[0], player_centre[1], npc_centre[0], npc_centre[1] ]
        found = True
        for wall in wall_sprites:
            # is anyting blocking the line-of-sight?
            intersection_points = lineRectIntersectionPoints( line_of_sight, wall.getRect() )
            if ( len( intersection_points ) > 0 ):
                found = False
                break # seen already
        # Highlight anyone found
        npc.setSeen( found )
        if ( found ):
            pygame.draw.line( window, WHITE, player_centre, npc_centre )
        else:
            pygame.draw.line( window, GREY, player_centre, npc_centre )
                
    # draw the sprites
    wall_sprites.draw( window )
    npc_sprites.update()
    npc_sprites.draw( window )
    player_sprite.draw( window )

    pygame.display.flip()
    clock.tick_busy_loop(60)


pygame.quit()