Drench oyununda tahtayi boyama algoritmasi

Python
1

Merhaba;

Su oyunun aynisini pyglet ile yapmaya calisiyorum. Elimde 12x12 bir tahta var, 6 renkten olusan Rectangle objeleriyle dolu. Oyuncu her hamlesinde 6 renkten birini seciyor. 0,0 noktasini secili renge boyaniyor, 0,0 noktasina bitisik diger noktalar da 0,0 ile ayni renkteyse onlar da boyaniyor. Oyuncu en fazla 30 hamlede tahtayi tek bir renk yapmaya calisiyor. Yukarida verdigim linkte bitmis ornegi var.

Anlatacagim konuyla alakali olan paint fonksiyonum soyle:

def paint(self, pos, color):
        """
        Pos: (x, y): Current position to start painting.
        """

        main_block = self.board[pos[0]][pos[1]]
        old_color = main_block.color
        main_block.color = color

        def check(target_pos):
            try:
                target = self.board[target_pos[0]][target_pos[1]]
            except IndexError:
                pass
            else:
                if tuple(target.color) == tuple(main_block.color) or tuple(target.color) == tuple(old_color):
                    self.paint(target_pos, main_block.color)

        # Right
        check((pos[0], pos[1]+1))

        # Down
        check((pos[0]-1, pos[1]))

Kodun tamami: dpaste: Drench Clone

Problem

Problem performans. Ilk hamlelerde sorun yok, 9-10. hamlelere gelindiginde yavaslama oldukca farkediliyor, ve tahta boyandikca yavaslama da artiyor. Ki fonksiyon su anda sadece asagiyi ve sagi tariyor, 4 yone taramam gerektigini varsayarsak asiri performanssiz oluyor. Yavasligin sebebi ne? Yukaridaki fonksiyonun alternatifi ama daha hizlisini nasil yaparim?

2 Beğeni
2

Yavaşlığın asıl sebebi aynı koordinatları birden fazla defa kontrol etmeniz. Bunu düzeltmek kolay:

    def __init__(self):
        super().__init__(SIZE[0], SIZE[1], TITLE)
        self.batch = pyglet.graphics.Batch()
        self.board = self._create_board()
        self.visited = set()


    def paint_util(self, pos, color):
        """
        Pos: (x, y): Current position to start painting.
        """
        if pos in self.visited:
            return
        self.visited.add(pos)
        
        main_block = self.board[pos[0]][pos[1]]
        old_color = main_block.color
        main_block.color = color

        def check(target_pos):
            try:
                target = self.board[target_pos[0]][target_pos[1]]
            except IndexError:
                pass
            else:
                if target.color == main_block.color or target.color == old_color:
                    self.paint_util(target_pos, main_block.color)

        # Right
        check((pos[0], pos[1]+1))

        # Down
        check((pos[0]-1, pos[1]))

    def paint(self, pos, color):
        self.visited.clear()
        self.paint_util(pos, color)

Algoritma da daha iyi bir hale getirilebilir ama. Aklıma en dıştaki karelerin koordinatını saklayıp sadece onların çevresini kontrol etmek geliyor. İçte kalan karelerin de koordinatları saklanır ve sadece renkleri değiştirilir.

2 Beğeni