Optimisation de Shadow Casting Python

Question

J'ai travaillé sur une Shadow Caster pour un petit RPG que je fais. Le problème que j'ai, c'est que lorsque je l'utilise dans mon jeu, il est bien moyen de ralentir et d'induire un retard horrible.

S'il vous plaît ne soyez pas trop effrayé par la longueur de la poste. C'est assez simple mais pour que vous puissiez exécuter le code, j'ai inclus tous les algorithmes de Bresenham.

Le principe est le suivant: - créer une surface noire - définir une source de lumière avec une position et un rayon. - obtenir tous les points sur la circonférence du cercle défini par cette position et ce rayon en utilisant l'algorithme du cercle de Bresenham. - pour chaque point de la circonférence, tracez une ligne à partir de la position de la source lumineuse en utilisant l'algorithme de ligne de Bresenham. - puis passez en revue les points de la ligne et vérifiez s'ils entrent en collision avec tous les obstacles affichés à l'écran. - S'il n'y a pas de collision, dessinez un cercle BLANC centré sur ce point avec un rayon de 10 pixels environ. - S'il y a collision, passez au point suivant le long de la circonférence du cercle. - enfin, la surface est rincée avec tous les cercles blancs sur une surface qui a une valeur de transparence de 100 pour la couleur noire et une transparence complète pour la couleur BLANC.

Jusqu'à présent, j'ai essayé les suivantes: Ce qui a réduit le lag: - limiter la liste des obstacles à ceux affichés sur l'écran - prendre en compte les bords de l'écran comme des obstacles pour réduire l'itération de la zone non visible. - itérer seulement sur tous les 3 points autour du cercle et 12 points le long des lignes. Ce qui n'a rien changé: - en utilisant des ellipses allant de la source lumineuse au bord de la plage ou de l'obstacle au lieu de beaucoup de cercles le long de la ligne. Le problème était que je devais redessiner la surface pour chaque ellipse, puis faire pivoter le tout.

Si vous avez des suggestions sur la façon de rendre cela plus efficace, je serais heureux d'ici alors.

Ligne de 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 

Cercle 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 

Mes classes pour les sources de lumière, les obstacles et masque ombre:

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

Les fonctions de génération d'ombre qui me permet de sortir de la ligne et de la boucle d'obstacles sans utiliser d'exception n dans ma apply_shadows méthode de la classe 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 

Et enfin la boucle principale exemple pygame pour exécuter tous les ci-dessus:

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

Voici le code du début à la fin pour un facile copier coller:

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

Votre problème de latence semble provenir de la méthode Night_Mask.apply_shadows(self, obstacles).Cela semble être dû à la quantité pure d'itérations que la boucle for imbriquée doit traverser.

Réduire la valeur de range_ dans le constructeur de Light_Source(x, y, range_) réduit le retard en réduisant les itérations des méthodes susmentionnées, mais l'effet visuel est pire. J'ai trouvé que le fps a commencé à vraiment tomber pour moi après avoir réglé la variable passé ~ 65-70.

Il existe une bibliothèque graphique Pygame, qui gère très bien les ombres.

Lien vers la page: http://pygame.org/project-Pygame+Advanced+Graphics+Library-660-4586.html Téléchargement direct pour la version 8.1.1 à partir du site: link

Ceci est la description de la bibliothèque du site:

Ceci est une bibliothèque tous les graphiques but pour créer facilement des effets complexes rapidement et avec un minimum de code. Exécutez les exemples très bien commentés, chacun moins d'une page (sans compter les commentaires), et apprenez comment faire des effets compliqués comme les ombres et l'anti-crénelage.

Voici une image de la page montrant un exemple d'ombres.

J'ai téléchargé et testé la bibliothèque, et cela fonctionne très bien. Je l'ai testé sur Pygame1.9.2a0 pour python 3.4

Je crois que c'est la solution la plus facile pour votre problème, et devrait également vous aider avec de futurs projets. J'espère que ça aide.