Оптимизация Shadow Casting Python

Я работаю над создателем тени для небольшой RPG, которую я делаю.Оптимизация Shadow Casting Python

У меня есть проблема в том, что когда я использую его в своей игре, это просто способ замедлить работу и вызвать ужасное отставание.

Пожалуйста, не пугайтесь длины сообщения. Это довольно просто, но чтобы вы могли запускать код, я включил все алгоритмы Брешенема.

Принцип заключается в следующем: - сделать черную поверхность - определить источник света с положением и радиусом. - получить все точки на окружности круга, определяемые этим положением и радиусом, используя алгоритм Крузеса Брешенема. - для каждой точки вдоль окружности нарисуйте линь из положения источника света с помощью линейного алгоритма Брешенема. - затем перебирайте точки линии и проверяйте, сталкиваются ли они с каждым препятствием, отображаемым на экране. - Если нет столкновения, нарисуйте круг WHITE с центром в этой точке с радиусом 10 пикселей или около того. - Если есть столкновение, переходите к следующей точке вдоль окружности круга. - наконец, размыл поверхность со всеми белыми кругами на поверхности, которая имеет значение прозрачности 100 для черного цвета и полную прозрачность для цвета WHITE.

До сих пор я попытался следующее: Что же сократить отставание: - ограничить список препятствий для тех, отображаемых на экране - рассмотреть края экрана, как препятствия для уменьшения итерации площади не видна. - повторять только каждые 3 точки вокруг круга и 12 точек вдоль линий. Что ничего не изменило: - используя эллипсы, идущие от источника света к краю диапазона или препятствия, а не много кругов вдоль линии. Проблема заключалась в том, что мне приходилось перерисовывать поверхность для каждого эллипса, а затем вращать всю партию.

Если у вас есть предложения по тому, как сделать это более эффективным, я был бы счастлив здесь.

Bresenham по линии Algo:

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 в круг Algo:

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

теневой функции поколения, которые позволяет мне вырваться из петли линии и препятствия без использования исключения п в моем методе apply_shadows класса Night_Mask:

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 цикл запустить все выше:

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

источник

2016-06-18 Sorade

Ваш вопрос лаг будет приходить от метода Night_Mask.apply_shadows(self, obstacles).По-видимому, это связано с чистым количеством итераций, которые необходимо пройти вложенному циклу.

Уменьшение значения range_ в конструкторе Light_Source(x, y, range_) уменьшает отставание, уменьшая вышеупомянутые методы итераций, но визуальный эффект хуже. Я обнаружил, что fps начали действительно бросаться за мной после установки переменной ~ 65-70.

Существует графическая библиотека Pygame, которая отлично обрабатывает тени.

Ссылка на страницу: http://pygame.org/project-Pygame+Advanced+Graphics+Library-660-4586.html Прямая загрузка для версии 8.1.1 с сайта: link

Это описание библиотеки с сайта:

Это все графики назначения библиотеки для быстрого создания сложных эффектов быстро и с минимальным кодом. Запустите очень хорошо прокомментированные примеры, каждая из которых меньше, чем страница (не считая комментариев), и узнайте, как создавать сложные эффекты, такие как тени и сглаживание.

Вот изображение со страницы, где показан пример теней.

Я скачал и протестировал библиотеку, и она работает очень хорошо. Я тестировал на Pygame1.9.2a0 для python 3.4

Я считаю, что это самое легкое исправление вашей проблемы, а также должно помочь вам в будущих проектах. Надеюсь, это поможет.

источник

2016-06-20 07:21:56 Flutterguy135

Спасибо за совет. Мне удалось заставить его работать в конце, но он все же намного менее эффективен, чем эта библиотека, которую вы рекомендуете. Поэтому я буду использовать его вместо: D – Sorade

Я счастлив, что смогу помочь. – Flutterguy135

ответ

Смежные вопросы