シャドーキャストPythonの最適化

Question

私は小さなRPGのためにシャドーキャスターに取り組んでいます。

私が抱える問題は、ゲームで使用すると、遅くて恐ろしい遅れを誘発する方法です。

投稿の長さがあまりにも驚かないようにしてください。それはかなり簡単ですが、私はすべてのBresenhamのアルゴリズムも含めたコードを実行することができます。

原則は次のとおりです。 - 黒い表面を作る - 位置と半径を持つ光源を定義します。 - BresenhamのCircle Algorithmを使用して、この位置と半径で定義される円周上のすべての点を取得します。 - 周囲に沿った各点について、Bresenhamの線アルゴリズムを使用して光源の位置から線を描画します。 - 次に、線のポイントを繰り返して、画面に表示されているすべての障害物と衝突するかどうかを確認します。 - 衝突がない場合は、その点を中心に半径10ピクセル程度のWHITE円が描画されます。 - 円周に沿って次の点に衝突がある場合。 - 最終的に、サーフェス上のすべての白丸でサーフェスをblitします。サーフェスの透明度値は、黒色で100、白色で完全透明です。

これまでのところ、私は次のことを試みた：ラグを減少させた ： - 画面 に表示されたものに障害物リストを制限する - 障害物が地域見えないの繰り返しを減らすためとして、画面の端を考えます。 - 円の周りに3点、線に沿って12点だけ繰り返します。 何も変更されていないもの： - 光源に沿って、線に沿って多くの円ではなく、範囲または障害物の端に向かう楕円を使用する。問題は、楕円ごとにサーフェスを再描画して、ロット全体を回転させなければならないことでした。

これをより効率的にする方法についてご意見がありましたら、ここまでお気軽にご連絡ください。

ブレゼンハムのラインアルゴ：

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 

私のクラス：

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を使わずに線と障害の両方のループから抜け出すことができますNight_Maskクラスの私のapply_shadows方法において、n：

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

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のためにPygame1.9.2a0をテストしました。

これはあなたの問題の最も簡単な修正であると信じており、今後のプロジェクトでも役立ちます。私はこれが役立つことを願っています