ReTabNews

Bom dia/tarde/noite para os leitores! Nesta postagem, vou explicar a lógica que criei durante o desenvolvimento de um jogo de damas, espero que gostem!

Teoria

Entidades

Para o jogo funcionar, são necessário dessas 2 entidades:

Match - Armazena as informações relevantes da partida

export class Match { // entidade do TypeORM
  uuid: UUID;

  player1: User; // ManyToOne
  player2: User; // ManyToOne

  winner: 'player1' | 'player2';
  winnerStatus: 'checkmate' | 'resign' | 'timeout';

  turn: 'player1' | 'player2';

  dateInit: Date;
  dateEnd?: Date;
}

Piece - Representam cada peça do tabuleiro, sendo excluídas quando capturadas ou quando a partida é finalizada.

export class Piece {
  id: number;

  match: Match; // ManyToOne
  player: 'player1' | 'player2';

  x: number;
  y: number;

  isQueen?: boolean;
}

Como uma partida é iniciada

Quando um 2° jogador entra na fila de pareamento, os seguintes processos acontecem nessa ordem:

Os dois jogadores são retirados da sala queue.
Uma entidade Match é criada, juntamente com 12 Piece para cada jogador.
Os dois jogadores entram na sala correspondente à partida.
É enviada uma mensagem para os dois jogadores contendo todas as informações da partida.

Fluxo da Movimentação

Após a partida ser iniciada, o fluxo de movimentação ocorre da seguinte forma (desde que o jogador não desista ou não se desconecte):

O jogador clica em uma peça.
O frontend requisita ao backend os movimentos disponíveis para aquela peça.
O frontend recebe as informações e exibe os movimentos disponíveis como casas verdes.
O jogador clica na casa verde para onde deseja mover a peça.
O frontend envia o ID da peça junto com as coordenadas do movimento para o backend.
O backend executa a lógica/magia para validar o movimento, salva as alterações no banco de dados e envia informações úteis para ambos os jogadores, como:
- Um array de coordenadas que corresponde ao trajeto até a coordenadas enviadas.
- Se a peça que se moveu é ou se tornou uma dama.
- O ID das peças capturadas.
O backend também troca o turno para o outro jogador, faz uma contagem das peças e envia as informações para ambos os jogadores.
O backend verifica se os dois jogadores ainda têm peças na partida. Se alguém não tiver, a partida termina com essa pessoa como perdedora. As peças são deletadas do banco e o resultado é enviado para ambos os jogadores.

Vocabulário

Mais adiante, falarei sobre palavras em um contexto específico. Quando me referir a elas, terão os seguintes significados:

Square (quadrado) ou casa - Refere-se às casas do tabuleiro, representadas no código por esta interface:

interface Square {
  coord: Coord; // Coord = {x: number, y: number}
  piece?: Piece;
  side?: Square[][]; // side é um array de caminhos laterais, usado quando acontece captura em cadeia com curvas
}

Direção - Uma das quatro direções em que uma peça pode se mover. Uso um enum para representá-las, armazenando também os sinais (- ou +) de x e y correspondentes a cada direção.
```
const directions = {
  upRight: [1, 1], // [x, y]
  upLeft: [-1, 1],
  downRight: [1, -1],
  downLeft: [-1, -1],
} as const;
export type DMap = keyof typeof directions;
```

Caminhos ou path - Um array de casas que segue em uma das quatro direções.

Captura em cadeia com curvas - Refere-se a uma captura em série que muda de direção.

Não sou muito bom com nomes.

Código

Hora do código! Agora vou mostrar cada método que compõe a lógica/magia de movimentação, captura e promoção. Para não ficar tão seco, vou comentar nas linhas de código o que está acontecendo.

forEachSquare - Método que itera sobre as casas até os limites do tabuleiro ou até que o callback retorne um valor verdadeiro. Ele começa na coordenada especificada e segue na direção desejada.

private forEachSquare(startSquare: Coord, direction: DMap, cb: (coord: Coord) => boolean | void) {
    let i = 1;
    while (true) {
      const [sinalX, sinalY] = directions[direction]; // pega os sinais da direção
      const x = startSquare.x + (sinalX * i); // Dê olhada em vocabulário > direção, pode ajudar a entender essa parte.
      const y = startSquare.y + (sinalY * i); 

      if (x < 0 || x > 7 || y < 0 || y > 7) break; // verifica se as coordenadas ainda estão dentro dos limites do tabuleiro
      if (cb({ x, y })) break; // chama o callback; se ele retornar true, termina o loop
      i++; // incrementa a diferença
    }
  }

forEachSide - Lembra do "Captura em cadeia com curvas"? Ela acabou complicando pra caramba o código a partir daqui. Esse método itera as laterais de uma casa de acordo com a direção do caminho e será usado no próximo método.

 private forEachSide(dire: DMap, cb: (direLateral: DMap) => boolean | void) {
    const direR =  // monto a direção oposta da que estava indo. ex: upRight ⟷ downLeft
      (dire.includes('up') ? 'down' : 'up') + // obtém a direção vertical oposta
      (dire.includes('Right') ? 'Left' : 'Right'); // obtém a direção horizontal oposta

    const direKeys = Object.keys(directions) as DMap[]; // transformo as keys do enum em um array. ex: [upLeft, upRight, downLeft, downRight]
    const sides = direKeys.filter((d) => ![direR, dire].includes(d)); // filtro a direção que o caminho está indo e oposta, sobrando apenas os caminhos laterais

    for (const dire2 of sides) { // itero os caminhos laterais
      if (cb(dire2 as DMap)) break; // chamo o callback com cada caminho lateral
    }
  }

createPath - Esse método é responsável por formar o caminho que a peça pode se mover em determinada direção e finalizá-lo quando encontra uma regra que interrompe o movimento.

  private createPath(
  { isQueen, player, ...cord }: Omit<Piece, 'id' | 'match'>, // a peça que está sendo movida
  pieces: Piece[], // as peças no tabuleiro
  direction: DMap, // a direção do movimento
  isSide = false, // indica se o movimento é lateral, utilizado em chamadas recursivas
) {
  const path: Square[] = []; // armazena o caminho formado

  // itera sobre as casas na direção especificada
  this.forEachSquare(cord, direction, ({ x, y }) => {
    const pieceInSquare = pieces.find((p) => p.x === x && p.y === y); // encontra a peça na casa atual, se houver
    const squareCurrent = { coord: { x, y }, piece: pieceInSquare, side: [] }; // cria o objeto square para representar a casa atual
    const squarePrev = path.at(-1); // pega a última casa do caminho

    // Verifica se a peça na casa atual pertence ao mesmo jogador, interrompendo o caminho se for
    if (squareCurrent?.piece?.player === player) return true;

    // Regras para a primeira casa no caminho
    if (path.length === 0) {
      // Se for um caminho lateral e a primeira casa estiver vazia, interrompe o caminho
      if (isSide && !squareCurrent.piece) return true;

      // Se a primeira casa estiver vazia e não for um caminho lateral
      if (!squareCurrent.piece) {
        path.push(squareCurrent);
         // Se a peça for uma dama, adiciona a primeira casa ao caminho e continua verificando as próximas
         // Se a peça não for uma dama, adiciona a primeira casa ao caminho e encerra o caminho (peça comum pode andar apenas uma casa se não for uma captura em cadeia)
        return isQueen ? false : true;
      }
    }

    // Verifica se o caminho deve ser interrompido após a primeira casa
    if (path.length > 0) {
      // Se ambas as casas (anterior e atual) estiverem vazias 
      const isBothEmpty = !squarePrev?.piece && !squareCurrent.piece;
      // Se ambas as casas (anterior e atual) estiverem ocupadas
      const isBothOccupied = squarePrev?.piece && squareCurrent.piece;

      // Verifica se chegou ao fim de uma sequência de capturas (para evitar que a dama continue após uma captura)
      const isEndChain = isBothEmpty && path.find((p) => p.piece);

      if ((isBothEmpty && !isQueen) || isBothOccupied || isEndChain) return true;
    }

    // Adiciona a casa atual ao caminho
    path.push(squareCurrent);

    // Verifica se houve uma captura
    const isCaptured = squarePrev?.piece && !squareCurrent.piece;
    if (!isCaptured) return; // se não houver captura, continua a iteração

    // Chama o método forEachSide para explorar as capturas laterais
    this.forEachSide(direction, (dire2) => {
      const side = this.createPath({ player, x, y }, pieces, dire2, true); // chamada recursiva para capturas laterais
      if (side.length) squareCurrent.side.push(side); // se houver capturas laterais, adiciona ao square atual
    });
  });

  return path; // retorna o caminho formado
}

createPaths - Método que gera um array de todas as direções disponíveis para a peça. Utiliza o método anterior.

private createPaths(piece: Piece, pieces: Piece[]) {
  const mapDirections = Object.keys(directions) as DMap[]; 
  // Enquanto o player1 começa na parte inferior (Y:0,1,2), o player2 começa na parte superior (Y: 5, 6, 7).
  // Por isso é necessário inverter o array, pois o 'up' do player2 é na verdade o 'down'
  if (piece.player === 'player2') mapDirections.reverse(); 

  return mapDirections.map((direcao, i) => { 
    const path = this.createPath(piece, pieces, direcao as DMap);

    // É necessário identificar se é uma captura, pois apenas quando uma peça está capturando ou quando é uma dama que pode andar para trás.
    const isPieceCapture = path[0]?.piece && !path[1]?.piece;
    
    return i < 2 // se a peça estiver avançando para frente
        ? path // o caminho é válido, então é retornado
        : piece.isQueen || isPieceCapture  // se não, verificar se a peça é uma dama ou está capturando
            ? path  // se sim, o caminho ainda é válido, então é retornado
            : []; // se não, então não, o caminho não é válido e não é retornado
  });
}

Divisão

A partir daqui, os métodos são divididos entre aqueles específicos para mostrar as casas nas quais uma peça pode se mover e aqueles que realmente movem a peça.

Até chegar no método público que retorna as coordenadas disponíveis para movimento

flatPaths - Este método cria um array de coordenadas de casas disponiveis para se movimentar

private flatPaths(path: Square[], coords = []): Coord[] {
  for (const square of path) { 
    const { side, coord } = square;

    if (!square.piece) coords.push(coord); // se a casa não contiver uma peça, adiciono sua coordenada ao array
    if (side?.length) side.forEach((s) => this.flatPaths(s, coords)); // se houver algum caminho lateral, chamo flatPaths neles com o array atual como argumento
  }
  return coords;
}

getPaths - É o método publico que o resto da aplicação chama para pegar os movimentos disponíveis.

Realmente o nome não é muito bom, olhando agora deveria ser 'getMovements' ou algo assim

getPaths(piece: Piece, pieces: Piece[]) { 
 // Geramos os caminhos disponíveis com createPaths e, em seguida, usamos o método nativo flatMap para achatar e mapear o array com usando flatPaths em conjunto
 const paths = this.createPaths(piece, pieces).flatMap((s) => this.flatPaths(s));

 if (!paths.length) 
   throw new BadRequestException('Essa peça não tem movimentos disponíveis');

 return paths;
}

Até chegar no método público que move, captura e promove peças

createChainSquare - Este método procura a casa para onde a peça quer se mover, enquanto cria uma cadeia (array) de casas até as coordenadas correspondentes ao movimento. Se as coordenadas de destino não forem encontradas no caminho fornecido, o método retorna null.

private createChainSquare(
  coord: Coord, // Coordenada para onde a peça vai se mover
  path: Square[], // O caminho onde vai procurar
  chain: Square[] = [], // A cadeia que está sendo montada, necessário como parâmetro pois é recursiva
): Square[] | null {
  const pathAccum: Square[] = []; // Criando uma cadeia temporária

  for (const square of path) { // Iterando pelo caminho
    pathAccum.push(square); // Adiciona a casa na cadeia temporária

    const isFound = square.coord.x === coord.x && square.coord.y === coord.y; // Verifica se o quadrado atual corresponde à coordenada do movimento
    if (isFound) return [...chain, ...pathAccum]; // Se sim, termina a recursão e retorna a cadeia com o caminho temporário na ponta

    if (!square.side?.length) continue; // Se a casa atual não tiver caminhos laterais válidos, continue para a próxima casa
    const resultSides = square.side.map((pathSide) => // Se houver caminhos laterais, mapeie-os
      this.createChainSquare(coord, pathSide, [...chain, ...pathAccum]), // cria uma cadeia do caminho lateral a partir da cadeia atual
    );
    const result = resultSides.find((r) => r); // Verifica se a cadeia formada pelo caminho lateral contém as coordenadas do movimento
    if (result) return result; // Se sim, retorna a cadeia da lateral correspondente
  }

  return null; // Se nenhum caminho ou lateral correspondeu ao movimento, retorna null
}

movePiece - Este método percorre as direções disponiveis da peça em busca da coordenada do movimento. Quando encontra o caminho correto, ele transforma a cadeia de casas (que corresponde ao trajeto do movimento) em informações úteis.

private movePiece(pieces: Piece[], piece: Piece, mov: Coord) {
  const paths = this.createPaths(piece, pieces); // gero os caminhos disponveis para peça
  for (const path of paths) { //itero esses caminhos
    const chain = this.createChainSquare(mov, path); // procuro uma cadeia de movimento para aquele movimento no caminho
    if (!chain) continue; // se o movimentação não está nesse caminho, pula para o proximo

    // Crio uma cadeia de movimento até a casa correspondente às coordenadas de movimentação
    const chainOfMotion = chain.filter((c) => !c.piece).map((c) => c.coord);
    // Obtenho o ID das peças que estão nas casas da cadeia, considerando-as como capturadas.
    const piecesDeads = chain.filter((c) => c.piece).map((c) => c.piece.id);
      
    // verifico se esse movimento é uma promoção vendo se a peça se moveu para a extremidade oposta
    const isPromotion = piece.player === 'player1' ? mov.y === 7 : mov.y === 0;
    const isQueen = piece.isQueen || isPromotion; // ela é uma dama se já for uma ou acabou de se promover

    return { isQueen, chainOfMotion, piecesDeads }; // informações úteis 👍
  }
  // se nenhum caminho contiver o movimento, retorna undefined
}

pieceMove - Este é o método público que a aplicação chama para mover uma peça. Ele utiliza os métodos anteriores para gerar informações úteis, salva as alterações no banco de dados e retorna esses dados.

Na época não percebi que 'pieceMove' é apenas o nome do método anterior ao contrário...

 async pieceMove(piece: Piece, pieces: Piece[], mov: Coord) {
    const movePieceData = this.movePiece(pieces, piece, mov); // um método vai chamando outro até formar os dados correspondendo
    if (!movePieceData) throw new BadRequestException('Movimento inválido'); // se retornar undefined, o movimento não existe
    const { chainOfMotion, isQueen, piecesDeads } = movePieceData; 

    await this.dataSource.transaction(async (manager) => { // começo uma transação do typeOrm
      await manager.update(Piece, piece, { ...mov, isQueen }); // atualizo a coordenada da peça correspondendte
      if (piecesDeads.length) await manager.delete(Piece, piecesDeads); // deleto as peças capturadas
    });

    // retorno as informações
    return { pieceId: piece.id, isQueen, chainOfMotion, piecesDeads };
  }

Fim

É isso! O getPaths e o pieceMove são as pontas da classe que cuida dessa lógica. Você pode chamar qualquer uma delas com a peça que deseja mover, as peças da partida e, se quiser movimentar, as coordenadas também. Pronto! Ela cospe os movimentos disponíveis ou as alterações no tabuleiro que a movimentação da peça causou.

Explicando a lógica de movimento, captura e promoção de peças em um jogo de damas online