Executando verificação de segurança...
9
GeleiaRei
11 min de leitura ·

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

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:

  1. Os dois jogadores são retirados da sala queue.
  2. Uma entidade Match é criada, juntamente com 12 Piece para cada jogador.
  3. Os dois jogadores entram na sala correspondente à partida.
  4. É 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):

  1. O jogador clica em uma peça.
  2. O frontend requisita ao backend os movimentos disponíveis para aquela peça.
  3. O frontend recebe as informações e exibe os movimentos disponíveis como casas verdes.
  4. O jogador clica na casa verde para onde deseja mover a peça.
  5. O frontend envia o ID da peça junto com as coordenadas do movimento para o backend.
  6. 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.
  7. 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.
  8. 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;

Plano cartesiano

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

Exemplo de caminho

  • 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.

Exemplo de Captura em cadeia com curvas

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.

  1. 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
    }
  }

  2. 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
    }
  }

  3. 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
}

  4. 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

  1. 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;
}

  2. 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

  1. 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
}
  2. 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
}
  3. 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.

Links:

Carregando publicação patrocinada...
1
0