그림자 캐스팅 파이썬의 최적화

Question

나는 작은 RPG를위한 그림자 캐스터 작업을하고 있습니다.

내가 가지고있는 문제는 내가 게임에서 사용하면 속도를 늦추고 끔찍한 지연을 유발한다는 것입니다.

게시물의 길이가 너무 두려워하지 마세요. 그것은 매우 간단하지만 당신이 모든 브레 센함의 알고리즘을 포함하는 코드를 실행할 수 있습니다.

원칙은 다음과 같습니다. - 검은 색 표면을 만듭니다. - 위치와 반지름이있는 광원을 정의하십시오. - Bresenham의 Circle Algorithm을 사용하여이 위치와 반지름으로 정의 된 원의 둘레에있는 모든 점을 얻습니다. - Bresenham 's Line Algorithm을 사용하여 원주를 따라 각 점에 대해 광원의 위치에서 선형을 그립니다. - 라인의 포인트를 반복하고 화면에 표시된 모든 장애물과 충돌하는지 확인하십시오. - 충돌이없는 경우 그 지점을 중심으로 10 픽셀 정도의 반경을 갖는 흰색 원이 그려집니다. - 충돌이있는 경우 원 원주를 따라 다음 포인트로 이동합니다. - 마지막으로 서페이스의 모든 흰색 원을 사용하여 서페이스를 blit합니다.이 서클에는 검정색의 투명도 값이 100이고 흰색 색의 투명도 값이 있습니다.

지금까지 내가 시도한 다음과 지연 감소했다 : 을 - 장애물이 보이지 않는 영역의 반복을 줄이기 위해 화면의 가장자리를 고려 - 화면 에 표시되는 것들과 장애물의 목록을 제한합니다. - 원을 중심으로 한 3 포인트와 선을 따라 12 포인트를 반복합니다. 아무 것도 변경하지 않았습니다 : - 광원을 따라 선을 따라 많은 원 대신 범위 또는 가장자리의 가장자리로가는 타원을 사용합니다. 문제는 각 타원에 대해 서페이스를 다시 그려야하고 전체를 많이 회전해야한다는 것입니다.

이 방법을 더 효율적으로 만드는 방법에 대한 제안 사항이 있으면 여기까지 기뻐할 것입니다.

Bresenham의 라인 너 한테 :

def get_line(start, end): 
    """Bresenham's Line Algorithm 
    Produces a list of tuples from start and end 

    >>> points1 = get_line((0, 0), (3, 4)) 
    >>> points2 = get_line((3, 4), (0, 0)) 
    >>> assert(set(points1) == set(points2)) 
    >>> print points1 
    [(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)] 
    >>> print points2 
    [(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)] 
    """ 
    # Setup initial conditions 
    x1, y1 = start 
    x2, y2 = end 
    dx = x2 - x1 
    dy = y2 - y1 

    # Determine how steep the line is 
    is_steep = abs(dy) > abs(dx) 

    # Rotate line 
    if is_steep: 
     x1, y1 = y1, x1 
     x2, y2 = y2, x2 

    # Swap start and end points if necessary and store swap state 
    swapped = False 
    if x1 > x2: 
     x1, x2 = x2, x1 
     y1, y2 = y2, y1 
     swapped = True 

    # Recalculate differentials 
    dx = x2 - x1 
    dy = y2 - y1 

    # Calculate error 
    error = int(dx/2.0) 
    ystep = 1 if y1 < y2 else -1 

    # Iterate over bounding box generating points between start and end 
    y = y1 
    points = [] 
    for x in range(x1, x2 + 1): 
     coord = (y, x) if is_steep else (x, y) 
     points.append(coord) 
     error -= abs(dy) 
     if error < 0: 
      y += ystep 
      error += dx 

    # Reverse the list if the coordinates were swapped 
    if swapped: 
     points.reverse() 
    return points 

Bresenham의 서클 너 한테 : 광원, 장애물과 그림자 마스크

def get_circle((dx,dy),radius): 
    "Bresenham complete circle algorithm in Python" 
    # init vars 
    switch = 3 - (2 * radius) 
    points = set() 
    x = 0 
    y = radius 
    # first quarter/octant starts clockwise at 12 o'clock 
    while x <= y: 
     # first quarter first octant 
     points.add((x,-y)) 
     # first quarter 2nd octant 
     points.add((y,-x)) 
     # second quarter 3rd octant 
     points.add((y,x)) 
     # second quarter 4.octant 
     points.add((x,y)) 
     # third quarter 5.octant 
     points.add((-x,y))   
     # third quarter 6.octant 
     points.add((-y,x)) 
     # fourth quarter 7.octant 
     points.add((-y,-x)) 
     # fourth quarter 8.octant 
     points.add((-x,-y)) 
     if switch < 0: 
      switch = switch + (4 * x) + 6 
     else: 
      switch = switch + (4 * (x - y)) + 10 
      y = y - 1 
     x = x + 1 
    offset_points = set() 
    for pt in points: 
     offset_points.add((pt[0]+dx,pt[1]+dy)) 

    return offset_points 

def shadow_gen(shadow_surf,source,cir_pt,obstacles): 
    line_points = get_line(source.pos,cir_pt) 
    for line_pt in line_points[0::12]: 
     for obs in obstacles: 
      pygame.draw.circle(shadow_surf, WHITE, line_pt, 20, 0) #radius to 5px and 0 to fill the circle 
      if obs.rect.collidepoint(line_pt) or pygame.Rect(0,0,500,500).collidepoint(line_pt) == False: 
       return 

내 클래스 :

class Obstacle(object): 
    def __init__(self,x,y): 
     self.surf = pygame.Surface((150,150)) 
     self.rect = pygame.Rect((x,y),(150,150)) 
     self.surf.fill(pygame.color.Color('blue')) 

class Light_Source(object): 
    def __init__(self,x,y,range_): 
     self.range = range_ 
     self.pos = (x,y) 


class Night_Mask(object): 
    def __init__(self): 
     self.surf = pygame.Surface((500,500)) #Screenwidth and height 
     self.alpha = 100 
     self.light_sources = [] 

     '''setting initial alpha and colorkey''' 
     self.surf.set_colorkey(WHITE) 
     self.surf.set_alpha(self.alpha) 


    def apply_shadows(self, obstacles): 
     shadow_surf = pygame.Surface((500,500)) 
     for source in self.light_sources: 
      circle_pts = list(get_circle(source.pos,source.range)) 
      for cir_pt in circle_pts[0::3]: 
       shadow_gen(shadow_surf,source,cir_pt,obstacles) 
     self.surf.blit(shadow_surf, (0, 0)) 

그림자 생성 기능을하는 exceptio를 사용하지 않고도 회선과 장애 루프를 모두 벗어날 수 있습니다. n은 Night_Mask 클래스의 내 apply_shadows 방법에 :

def shadow_gen(shadow_surf,source,cir_pt,obstacles): 
    line_points = get_line(source.pos,cir_pt) 
    for line_pt in line_points[0::12]: 
     for obs in obstacles: 
      pygame.draw.circle(shadow_surf, WHITE, line_pt, 20, 0) #radius to 5px and 0 to fill the circle 
      if obs.rect.collidepoint(line_pt) or pygame.Rect(0,0,500,500).collidepoint(line_pt) == False: 
       return 

마지막 주 파이 게임 예를 들어 루프

은 위의 모든 실행 : 여기

pygame.init() 
screen = pygame.display.set_mode((500, 500)) 

bg = pygame.Surface((500,500)) 
bg.fill(pygame.color.Color('yellow')) 

ob_a = Obstacle(75,80) 
ls = Light_Source(75,75,300) 
night_m = Night_Mask() 
night_m.light_sources.extend([ls]) 

while True: 
    screen.fill(pygame.color.Color('black')) 
    for event in pygame.event.get(): 
     if event.type == pygame.QUIT: 
      pygame.quit() 
      sys.exit() 

    ls.pos = pygame.mouse.get_pos() 

    night_m.apply_shadows([ob_a]) 

    screen.blit(bg, (0, 0)) 
    screen.blit(ob_a.surf,ob_a.rect) 
    screen.blit(night_m.surf, (0, 0)) 

    pygame.display.flip() 

쉬운을 위해 처음부터 끝까지 전체 코드입니다 복사 붙여 넣기 :

import pygame 
import sys 

WHITE = (255,255,255) 
'''FUNCTIONS''' 
def get_line(start, end): 
    """Bresenham's Line Algorithm 
    Produces a list of tuples from start and end 

    >>> points1 = get_line((0, 0), (3, 4)) 
    >>> points2 = get_line((3, 4), (0, 0)) 
    >>> assert(set(points1) == set(points2)) 
    >>> print points1 
    [(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)] 
    >>> print points2 
    [(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)] 
    """ 
    # Setup initial conditions 
    x1, y1 = start 
    x2, y2 = end 
    dx = x2 - x1 
    dy = y2 - y1 

    # Determine how steep the line is 
    is_steep = abs(dy) > abs(dx) 

    # Rotate line 
    if is_steep: 
     x1, y1 = y1, x1 
     x2, y2 = y2, x2 

    # Swap start and end points if necessary and store swap state 
    swapped = False 
    if x1 > x2: 
     x1, x2 = x2, x1 
     y1, y2 = y2, y1 
     swapped = True 

    # Recalculate differentials 
    dx = x2 - x1 
    dy = y2 - y1 

    # Calculate error 
    error = int(dx/2.0) 
    ystep = 1 if y1 < y2 else -1 

    # Iterate over bounding box generating points between start and end 
    y = y1 
    points = [] 
    for x in range(x1, x2 + 1): 
     coord = (y, x) if is_steep else (x, y) 
     points.append(coord) 
     error -= abs(dy) 
     if error < 0: 
      y += ystep 
      error += dx 

    # Reverse the list if the coordinates were swapped 
    if swapped: 
     points.reverse() 
    return points 

def get_circle((dx,dy),radius): 
    "Bresenham complete circle algorithm in Python" 
    # init vars 
    switch = 3 - (2 * radius) 
    points = set() 
    x = 0 
    y = radius 
    # first quarter/octant starts clockwise at 12 o'clock 
    while x <= y: 
     # first quarter first octant 
     points.add((x,-y)) 
     # first quarter 2nd octant 
     points.add((y,-x)) 
     # second quarter 3rd octant 
     points.add((y,x)) 
     # second quarter 4.octant 
     points.add((x,y)) 
     # third quarter 5.octant 
     points.add((-x,y))   
     # third quarter 6.octant 
     points.add((-y,x)) 
     # fourth quarter 7.octant 
     points.add((-y,-x)) 
     # fourth quarter 8.octant 
     points.add((-x,-y)) 
     if switch < 0: 
      switch = switch + (4 * x) + 6 
     else: 
      switch = switch + (4 * (x - y)) + 10 
      y = y - 1 
     x = x + 1 
    offset_points = set() 
    for pt in points: 
     offset_points.add((pt[0]+dx,pt[1]+dy)) 

    return offset_points 

def shadow_gen(shadow_surf,source,cir_pt,obstacles): 
    line_points = get_line(source.pos,cir_pt) 
    for line_pt in line_points[0::12]: 
     for obs in obstacles: 
      pygame.draw.circle(shadow_surf, WHITE, line_pt, 20, 0) #radius to 5px and 0 to fill the circle 
      if obs.rect.collidepoint(line_pt) or pygame.Rect(0,0,500,500).collidepoint(line_pt) == False: 
       return 

'''CLASSES'''     
class Obstacle(object): 
    def __init__(self,x,y): 
     self.surf = pygame.Surface((150,150)) 
     self.rect = pygame.Rect((x,y),(150,150)) 
     self.surf.fill(pygame.color.Color('blue')) 

class Light_Source(object): 
    def __init__(self,x,y,range_): 
     self.range = range_ 
     self.pos = (x,y) 


class Night_Mask(object): 
    def __init__(self): 
     self.surf = pygame.Surface((500,500)) #Screenwidth and height 
     self.alpha = 100 
     self.light_sources = [] 


     '''setting initial alpha and colorkey''' 
     self.surf.set_colorkey(WHITE) 
     self.surf.set_alpha(self.alpha) 


    def apply_shadows(self, obstacles): 
     shadow_surf = pygame.Surface((500,500)) 
     for source in self.light_sources: 
      circle_pts = list(get_circle(source.pos,source.range)) 
      for cir_pt in circle_pts[0::3]: 
       shadow_gen(shadow_surf,source,cir_pt,obstacles) 
     self.surf.blit(shadow_surf, (0, 0)) 


'''MAIN GAME''' 
pygame.init() 
screen = pygame.display.set_mode((500, 500)) 

bg = pygame.Surface((500,500)) 
bg.fill(pygame.color.Color('yellow')) 

ob_a = Obstacle(75,80) 
ls = Light_Source(75,75,300) 
night_m = Night_Mask() 
night_m.light_sources.extend([ls]) 

while True: 
    screen.fill(pygame.color.Color('black')) 
    for event in pygame.event.get(): 
     if event.type == pygame.QUIT: 
      pygame.quit() 
      sys.exit() 

    ls.pos = pygame.mouse.get_pos() 

    night_m.apply_shadows([ob_a]) 

    screen.blit(bg, (0, 0)) 
    screen.blit(ob_a.surf,ob_a.rect) 
    screen.blit(night_m.surf, (0, 0)) 

    pygame.display.flip() 

Answer 1

귀하의 지연 문제가 나타납니다 메소드 Night_Mask.apply_shadows(self, obstacles)에서 오는합니다.이는 중첩 된 for 루프가 수행해야하는 순수한 양의 반복 때문인 것으로 보입니다.

Light_Source(x, y, range_)의 생성자에서 range_의 값을 줄이면 앞에서 설명한 방법을 반복하여 지연을 줄일 수 있지만 시각적 효과는 더 나쁩니다. 나는 ~ 65-70 지나서 가변을 설정 한 후에 fps가 정말로 나를 위해 떨어지는 것을 발견했다.

그림자를 잘 처리하는 Pygame 그래픽 라이브러리가 있습니다. 페이지에

링크 : 사이트에서 버전 8.1.1에 대한 http://pygame.org/project-Pygame+Advanced+Graphics+Library-660-4586.html 직접 다운로드 :

이 모든 용도의 그래픽 라이브러리는 다음과 같습니다 link

이 사이트에서 라이브러리의 설명입니다 복잡한 효과를 손쉽게 신속하게 작성하고 최소한의 코드로 작성합니다. 아주 잘 주석 처리 된 예제를 실행하십시오. 주석은 제외하고 페이지가 아닌 페이지를 실행하고 그림자 및 앤티 앨리어싱과 같은 복잡한 효과를 만드는 방법을 배웁니다.

다음은 그림자 예제를 보여주는 페이지의 이미지입니다.

라이브러리를 다운로드하고 테스트 한 결과 매우 효과적이었습니다. Python 3.4에 대한 Pygame1.9.2a0에서 테스트했습니다.

나는 이것이 당신의 문제에 대한 가장 쉬운 해결책이라고 생각하며, 미래의 프로젝트에도 도움이 될 것입니다. 이게 도움이 되길 바란다.