Olá pessoal!
Esta é a primeira parte de uma série de posts sobre Algoritmos Genéticos (GA).
Atualmente existe bastante material sobre GA espalhado pela rede, porém
boa parte deste material é teórico ou muito especializado, o que acaba frustrando quem
deseja aprender mais sobre o assunto.
Também vejo muitos iniciantes encontrando dificuldades para implementar uma versão do Tetris. Já vi de tudo: peças sumindo do nada, blocos sendo abduzidos, etc...
Por essas e outras decide juntar os dois assuntos de maneira prática: implementando uma
A.I. que jogue Tetris decentemente.
A definição de decentemente varia, porém vamos
tomar como base o seguinte: a A.I. deve jogar de maneira parecida com a humana, aplicando as estratégias
básicas do game (que logo serão discutidas).
Introdução
O objetivo é simples: implementar um agente Tetris, que faça o maior número possível de linhas. Fatores como tempo e velocidade das peças serão desprezados, vamos assumir que o agente seja rápido o suficiente mover a peça na posição desejada.
Neste post iremos implementar o cliente Tetris: as classes TetrisPiece e TetrisBoard darão conta da lógica do game. A classe GamePanel implementa a GUI e aceita input do teclado, assim poderemos testar o game e ter certeza de que tudo funciona perfeitamente.
No próximo post iremos implementar a estrutura do agente Tetris, definindo as classes
TetrisAgent, TetrisMove, MoveSearcher, BoardEvaluator e AIGame.
Mãos à obra!
Classe TetrisPiece
Toda peça possui um tipo, rotação e posição. A variável blockSize, apesar de não ser necessária, especifica o tamanho dos blocos que formam a peça, e consequentemente define a unidade de deslocamento. Essa variável em geral é hard-coded como 1, mas ao definir um valor teremos a flexibilidade de construir a GUI especificando o número de linhas, colunas, e o blockSize, assim o tamanho do Panel será calculado automaticamente.
A constante de classe PIECE_SIZE = 5 nos permite fazer uso de simetria. Cada peça possui um bloco pivô de rotação, e ao definir PIECE_SIZE = 5 ao invés de PIECE_SIZE = 4, esse pivô é fixado (o bloco central de um quadrado de 25 blocos), o que facilitará o posicionamento das peças no início do game.
A constante de classe BLOCKS_PIECE = 4 nos diz quantos blocos serão efetivamente desenhados por peça, ou seja, Tetris = 4 blocos, Pentris = 5 blocos, etc. A array TRANSLATIONS será usada no posicionamento inicial, e indica o offset (medido em blockSize) necessário para centralizar a peça.
A array PIECES define a estrutura de cada peça, assim como COLORS define a cor. As variáveis TRANSLATIONS e PIECES usarão kind e rotation como índices de acesso. É possível calcular a rotação algebricamente, mas devemos lembrar que estes métodos serão chamados milhares de vezes por segundo. Ao usar valores hard-coded a estrutura das peças é calculada uma única vez, assim que a classe é carregada.
Quais são os métodos da classe? Além dos métodos que possibilitem movimento e rotação, um objeto TetrisPiece deve ser capaz de desenhar a si mesmo, dado um contexto gráfico. O método mais interessante da classe, boardIndexes, nos diz quais os índices (linha, coluna) ocupados por determinada peça, dado a rotação e a posição. Normalmente, esse método não precisaria de argumentos, afinal rotação e posição são variáveis de instância. Porém, acompanhe o raciocínio abaixo:
Ao mover ou rotacionar uma peça, podemos facilmente calcular a nova rotação ou posição, e chamar boardIndexes passando estes valores, obtendo assim os novos índices ocupados. Caso estes índices estejam livres o movimento é possível, e as variáveis de instância rotação e posição são atualizadas. Caso contrário, a colisão é detectada e a peça não se move.
A lógica para lidar com o movimento e colisão das peças será implementada na classe TetrisBoard. Objetos da classe TetrisPiece sabem se mover, mas a decisão de mover cabe a outro objeto. Segue a classe TetrisPiece:
import java.awt.*; public class TetrisPiece { int rotation; int kind; int blockSize = 20; Point position = new Point(0,0); //upper left static final int PIECE_SIZE = 5; static final int BLOCKS_PIECE = 4; static final Color[] COLORS = { new Color(255, 255, 0), //yellow new Color(0, 180, 0), //green new Color(255, 0, 0), //red new Color(255, 127, 0), //orange new Color(255, 0, 255), //purple new Color(0, 0, 255), //blue new Color(0, 255, 255) //cyan }; static final int [][][] TRANSLATIONS = { /* T */ { {-2, -3}, {-2, -3}, {-2, -3}, {-2, -2} }, /* I */ { {-2, -2}, {-2, -4}, {-2, -2}, {-2, -3} }, /* S */ { {-2, -3}, {-2, -3}, {-2, -3}, {-2, -2} }, /* Z */ { {-2, -3}, {-2, -3}, {-2, -3}, {-2, -2} }, /* O */ { {-2, -3}, {-2, -3}, {-2, -3}, {-2, -3} }, /* J */ { {-2, -3}, {-2, -2}, {-2, -3}, {-2, -3} }, /* L */ { {-2, -3}, {-2, -3}, {-2, -3}, {-2, -2} } }; static final int[][][][] PIECES = { //TPiece { { {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 1, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 1, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0} } }, //IPiece { { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 1, 1, 1, 1}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {1, 1, 1, 1, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0} } }, //SPiece { { {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 1, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 1, 1, 0}, {0, 1, 1, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 1, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 1, 1, 0}, {0, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0} } }, //ZPiece { { {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 1, 1, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 1, 1, 0, 0}, {0, 0, 1, 1, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 1, 1, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 1, 1, 0, 0}, {0, 0, 1, 1, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0} } }, //OPiece { { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}, {0, 0, 0, 0, 0} } }, //JPiece { { {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 1, 1, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 1, 1, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 0} } }, //LPiece { { {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 1, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 1, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0} } } }; public void draw(Graphics g) { g.setColor(COLORS[this.kind]); for (int i = 0; i < PIECE_SIZE; i++) { for (int j = 0; j < PIECE_SIZE; j++) { if (PIECES[kind][rotation][i][j] == 1) { g.fillRect(position.x + j * blockSize, position.y + i * blockSize, blockSize, blockSize); } } } } public void moveLeft() { position.x -= blockSize; } public void moveRight() { position.x += blockSize; } public void moveDown() { position.y += blockSize; } public void rotateCW() { rotation++; if (rotation > 3) rotation = 0; } public void rotateCCW() { rotation--; if (rotation < 0) rotation = 3; } public Point[] boardIndexes(Point pos, int rot) { Point[] indexes = new Point[BLOCKS_PIECE]; int n = 0; for (int i = 0; i < PIECE_SIZE; i++) { for (int j = 0; j < PIECE_SIZE; j++) { if (PIECES[kind][rot][i][j] == 1) { int col = j + pos.x/blockSize; int row = i + pos.y/blockSize; indexes[n] = new Point(col, row); n++; } } } return indexes; } public TetrisPiece clonePiece() { TetrisPiece p = new TetrisPiece(); p.kind = this.kind; p.rotation = this.rotation; p.position = new Point(this.position.x, this.position.y); p.blockSize = this.blockSize; return p; } } //fim da classe TetrisPiece /* classe auxiliar */ class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } public Point(){} }
Classe TetrisBoard
Essa classe representa a grade onde as peças se movem, e a estrura é bem simples: no construtor são passados o número de linhas rows e colunas cols, usados para inicializar a array board. Reparem que board consiste de rows + 1 linhas e cols + 2 colunas, onde a linha extra será usada para detectar colisão com o fundo da grade, e as duas colunas extras serão usadas para detectar colisão com as laterais. Obviamente apenas a parte interna da grade será desenhada (rows linhas x cols colunas).
O método removePiece remove uma peça da grade, obtendo os índices ocupados por essa peça (através do método boardIndexes do objeto TetrisPiece) e zerando os mesmos. Este método não é utilizado na lógica do game, mas será útil ao implementarmos a AI.
Agora a parte mais interessante: colisões. O método isColliding recebe uma array de índices e verifica se ao menos um desses índices está ocupado, o que resultaria em colisão. Aqui devemos ter cuidado com duas coisas: índices de array negativos (causa RuntimeException) e um bug em potencial: peças ficando presas nas bordas superiores da grade. Os 2 primeiros if's, dão conta disso.
Os próximos métodos são do tipo canMoveX e canRotateX. Ao receber input de movimento (do usuário ou da AI), estes métodos serão chamados para decidir se o movimento é possível, como discutido no tópico anterior. Os métodos willFitNext e pieceLandOffScreen detectam duas situações distintas de game-over: No primeiro caso, a próxima peça não possui espaço, no segundo, a última peça encaixada ficou parcialmente fora da grade.
Finalmente, updateBoard atualiza a grade, recebendo uma peça como argumento e atualizando os índices da board (novamente tomando cuidado com índices negativos). Os dois métodos restantes são triviais e cuidam da remoção de linhas completas.
Agora falta apenas uma GUI simples, habilitar input do teclado e colocar os objetos pra conversar em um loop principal. Segue a classe TetrisBoard:
public class TetrisBoard { int rows; int cols; int[][] board; public TetrisBoard(int rows, int cols) { this.rows = rows; this.cols = cols; board = new int[rows + 1][cols + 2]; for (int i = 0; i < rows + 1; i++) { board[i][0] = 1; board[i][cols + 1] = 1; } for (int j = 0; j < cols + 2; j++) board[rows][j] = 1; } public void removePiece(TetrisPiece piece) { Point[] indexes = piece.boardIndexes(piece.position, piece.rotation); for (Point p:indexes) { int row = p.y; if (row < 0) continue; int col = p.x + 1; board[row][col] = 0; } } public void resetBoard() { for (int i = 0; i < board.length - 1; i++) { for (int j = 1; j < board[i].length - 1; j++) { board[i][j] = 0; } } } public void printBoard() { for (int i = 0; i < board.length - 1; i++) { for (int j = 1; j < board[i].length - 1; j++) { System.out.print(board[i][j] + " "); } System.out.println(); } System.out.println(); } private boolean isColliding(Point[] indexes) { boolean collide = false; for (Point p:indexes) { int row = p.y; int col = p.x + 1; if (col < 1 || col > cols) { collide = true; break; } if (row < 0) continue; if (board[row][col] > 0) { collide = true; break; } } return collide; } public boolean canMoveLeft(TetrisPiece piece) { Point pos = new Point(piece.position.x - piece.blockSize, piece.position.y); Point[] indexes = piece.boardIndexes(pos, piece.rotation); return ! isColliding(indexes); } public boolean canMoveRight(TetrisPiece piece) { Point pos = new Point(piece.position.x + piece.blockSize, piece.position.y); Point[] indexes = piece.boardIndexes(pos, piece.rotation); return ! isColliding(indexes); } public boolean canMoveDown(TetrisPiece piece) { Point pos = new Point(piece.position.x, piece.position.y + piece.blockSize); Point[] indexes = piece.boardIndexes(pos, piece.rotation); return ! isColliding(indexes); } public boolean canRotateCW(TetrisPiece piece) { int rot = piece.rotation; rot++; if (rot > 3) rot = 0; Point[] indexes = piece.boardIndexes(piece.position, rot); return ! isColliding(indexes); } public boolean canRotateCCW(TetrisPiece piece) { int rot = piece.rotation; rot--; if (rot < 0) rot = 3; Point[] indexes = piece.boardIndexes(piece.position, rot); return ! isColliding(indexes); } public boolean willFitNext(TetrisPiece piece) { Point[] indexes = piece.boardIndexes(piece.position, piece.rotation); return !isColliding(indexes); } public boolean pieceLandOffScreen(TetrisPiece piece) { Point[] indexes = piece.boardIndexes(piece.position, piece.rotation); boolean offscreen = false; for (Point p:indexes) { if (p.y < 0) { offscreen = true; break; } } return offscreen; } public void updateBoard(TetrisPiece piece) { Point[] indexes = piece.boardIndexes(piece.position, piece.rotation); for (Point p:indexes) { int row = p.y; if (row < 0) continue; int col = p.x + 1; board[row][col] = piece.kind + 1; } } public int checkCompleteRows() { int completeRows = 0; for(int y = 0; y < rows; y++) { boolean ok = true; for(int x = 1; (x < cols + 1) && ok; x++) if(board[y][x] == 0) ok = false; if(ok) { completeRows++; deleteRow(y); } } return completeRows; } public void deleteRow(int r) { for (int i = r; i > 0; i--) { for (int j = 1; j < cols + 1 ; j++) { board[i][j] = board[i - 1][j]; } } for (int j = 1; j < cols + 1 ; j++) { board[0][j] = 0; } } } //fim da classe TetrisBoard
Classe GamePanel
As classes TetrisPiece e TetrisBoard implementam objetos totalmente independentes, o que nos permite usar um esquema de composição que seja mais vantajoso de acordo com a aplicação. No nosso caso, cada agente irá evoluir com uma sequência de n jogos diferentes, onde cada jogo será executado em uma Thread própria. Essa parte é crucial, e será explicada em detalhes mais adiante, o que nos interessa agora é definir GamePanel de forma que seja possível executar vários games em paralelo, ou seja, implementando a interface Runnable.
As variáveis board, fallingPiece e gameOver mantem o estado atual do game, e são resetadas em startNewGame. O construtor base recebe o número de linhas, colunas e o tamanho de cada bloco, inicializa algumas variáveis e habilita input do teclado. O segundo construtor nos permite semear o gerador aleatório, ou seja, ao se passar o mesmo seed, a sequência de peças se repetirá.
Usaremos classes interessantes da api java.util.concurrent, que facilitam muito o trabalho com Threads. A classe ScheduledThreadPoolExecutor nos permite alocar um pool de Threads, que irão executar run a cada intervalo de tempo especificado.
O método run implementa a lógica do game: em caso de game over o método retorna e a Thread é interrompida, caso contrário, a peça continua a cair. Quando a peça repousa, board é atualizada, possíveis linhas completas são verificadas, e addNewPiece é chamado. O método addNewPiece simplesmente checa as duas condições de game over, e atualiza fallingPiece.
Ao final do loop, repaint irá invocar paintComponent, que por sua vez invoca renderGame, que é responsável por desenhar a peça atual e o restante dos blocos. Segue a classe GamePanel:
import javax.swing.*; import java.awt.*; import java.awt.event.*; import java.util.concurrent.ScheduledThreadPoolExecutor; import java.util.concurrent.TimeUnit; import java.util.Random; public class GamePanel extends JPanel implements Runnable { TetrisBoard board; int blockSize; TetrisPiece fallingPiece; boolean gameOver; Random random; ScheduledThreadPoolExecutor animator; int cols; int rows; public GamePanel(int rows, int cols, int blockSize, int seed) { this(rows, cols, blockSize); random = new Random(seed); } public GamePanel(int rows, int cols, int blockSize) { this.blockSize = blockSize; this.setPreferredSize(new Dimension(cols * blockSize, rows * blockSize)); setDoubleBuffered(true); random = new Random(); board = new TetrisBoard(rows, cols); this.cols = cols; this.rows = rows; setFocusable(true); requestFocus(); addKeyWatcher(); } public void startNewGame() { gameOver = false; board.resetBoard(); fallingPiece = randomPiece(); long delayToStart = 100L; long step = 1000L/4; animator = null; animator = new ScheduledThreadPoolExecutor(1); animator.scheduleAtFixedRate(this, delayToStart, step, TimeUnit.MILLISECONDS); } public void run() { if (gameOver) { animator.shutdown(); return; } if (board.canMoveDown(fallingPiece)) { fallingPiece.moveDown(); } else { board.updateBoard(fallingPiece); int cleared = board.checkCompleteRows(); addNewPiece(); } repaint(); } public void paintComponent(Graphics g) { super.paintComponent(g); renderGame(g); } private void renderGame(Graphics g) { if (fallingPiece != null) fallingPiece.draw(g); for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { int block = board.board[i][j + 1]; if (block != 0) { g.setColor(TetrisPiece.COLORS[block - 1]); g.fillRect(j * blockSize, i * blockSize, blockSize, blockSize); } } } } protected void addNewPiece() { if (board.pieceLandOffScreen(fallingPiece)) { gameOver = true; fallingPiece = null; return; } TetrisPiece next = randomPiece(); if (board.willFitNext(next)) { fallingPiece = next; } else { fallingPiece = null; gameOver = true; } } protected TetrisPiece randomPiece() { int kind = random.nextInt(7); int rot = random.nextInt(4); TetrisPiece piece = new TetrisPiece(); piece.blockSize = this.blockSize; piece.kind = kind; piece.rotation = rot; int x = blockSize * (cols/2 + TetrisPiece.TRANSLATIONS[kind][rot][0]); int y = blockSize * TetrisPiece.TRANSLATIONS[kind][rot][1]; piece.position = new Point(x, y); return piece; } private void addKeyWatcher() { addKeyListener( new KeyAdapter() { public void keyPressed(KeyEvent e) { if (gameOver) { return; } int key = e.getKeyCode(); if (key == KeyEvent.VK_SPACE) { } else if (key == KeyEvent.VK_LEFT) { if (board.canMoveLeft(fallingPiece)) fallingPiece.moveLeft(); } else if (key == KeyEvent.VK_RIGHT) { if (board.canMoveRight(fallingPiece)) fallingPiece.moveRight(); } else if (key == KeyEvent.VK_UP || key == KeyEvent.VK_NUMPAD3) { if (board.canRotateCW(fallingPiece)) fallingPiece.rotateCW(); } else if (key == KeyEvent.VK_DOWN || key == KeyEvent.VK_NUMPAD1) { if (board.canRotateCCW(fallingPiece)) fallingPiece.rotateCCW(); } repaint(); } }); } // fim de addKeyWatcher() }
Testando o cliente
Agora, a parte mais fácil: juntar tudo em um método main e testar nosso cliente Tetris. A idéia aqui é verificar se tudo funciona como devia, e não implementar um game completo. Por exemplo, na classe TetrisPanel, a velocidade foi fixada com long step = 1000L/4, ou seja, a cada 0.25 segundos o loop será executado. Na parte visual, desenhamos a peça como um bloco contínuo, mas é fácil desenhar as bordas utilizando drawRect em conjunto com fillRect, sem esquecer de setar as cores de fill e stroke.
Use as setas do teclado para mover e rotacionar as peças, e não se esqueça de testar valores diferentes para rows, cols e blockSize.
Vale lembrar que o JPanel se ajustará com largura = cols * blockSize e altura = rows * blockSize, independentemente do tamanho do seu monitor! Segue a classe TestTetris:
import javax.swing.*; import java.awt.*; public class TestTetris { public static void main(String[] args) { JFrame f = new JFrame("Tetris - GA"); int rows = 20; int cols = 10; int blockSize = 30; GamePanel gamePanel = new GamePanel(rows, cols, blockSize); gamePanel.setBackground(Color.gray) ; gamePanel.setBorder(BorderFactory.createLineBorder(Color.white)); f.add(gamePanel); f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); f.pack(); f.setVisible(true); f.setResizable(false); gamePanel.startNewGame(); } }
No próximo post iremos começar a parte que realmente interessa, AI. Fique ligado!
Nenhum comentário:
Postar um comentário