Textos sobre desenvolvimento de jogos em geral

Detecção de Colisões

Este página explica alguns conceitos sobre colisões, principalmente em 2 dimensões.

Quando 2 ou mais objetos (neste texto denominados de "atores" do jogo, tais uma naves, tanques, tiros, mísseis, etc) "se tocam" (um está sobre o outro), ocorre o que chamamos de "colisão".

Isto ocorre, por exemplo, quando um míssel acerta o jogador ou um inimigo, quando jogador e inimigo encostam um no outro, etc. Normalmente quando ocorre colisão há um determinado efeito no jogo (por exemplo, quando um míssel acerta um inimigo, ele é destruído).

Para verificar se um ator está colidindo com outro, existem alguns problemas:

• 1. Como saber se está havendo ou houve colisão (detecção de colisão)?
• 2. Como calcular as colisões de forma rápida (você verá abaixo que a detecção de colisão pode ser bastante lenta)?

1. Como saber se está havendo ou houve colisão (detecção de colisão)?

Quanto a questão 1, entre as técnicas utilizadas para detectar colisões estão o teste ponto-a-ponto e o teste através de cálculos matemáticos:

Teste ponto-a-ponto:

Neste teste, verifica-se se algum ponto da imagem de um ator está colidindo com a imagem de outro ator. Esta verificação é realizada ponto-a-ponto entre as duas imagens (ou seja, se algum ponto de um ator colidir com algum ponto de outro, a colisão é detectada).

Este método é bem lento (por exemplo, se a imagem de cada um dos atores for pequena, tendo 32x32 pontos (ou seja 32 pontos na horizontal e 32 pontos na vertical), serão necessárias até 32*32=1024 comparações) e tem a desvantagem de perder a precisão de acordo com o movimento do ator (como será descrito abaixo).

Teste através de cálculos matemáticos (utilizando figuras geométricas):

O teste de colisão entre os atores é realizado através de testes de colisão entre figuras geométricas. Por exemplo, é como se cada ator tivesse um retângulo interno (ou qualquer outra figura geométrica que for conveniente). Caso o retângulo de um ator colida com o retângulo de outro ator, então a colisão é detectada.

Este método é muito mais rápido que o anterior, e tem a vantagem de poder ser calculado com precisão quando o movimento do ator é rápido (como descrito abaixo).

Além disto, no jogo geralmente não se precisa da precisão de colisão dada pelo método de testes ponto-a-ponto, porque a movimentação do jogo não permite que os jogadores possam perceber a imprecisão da colisão. Na verdade o importante é a percepção do jogador, não a precisão total. Tem que se ver que o jogador percebe ou não uma colisão que deveria ter
ocorrido.

Os testes de colisão podem ser melhorados:

• usando outras figuras geométricas em vez de retângulos (tais como círculos, etc).
  A vantagem do retângulo é que é bem rápido de testar a colisão (usam algumas
  poucas comparações de maior que e menor que). Para outras figuras, os cálculos são mais lentos (utilizam fórmulas mais complexas).
• colocando mais figuras geométricas no objeto (por exemplo: fazer com que a
  nave seja composta por 3 ou quatro retângulos ou outras figuras
  geométricas).

Descrição de como testar a colisão entre retângulos:

Imagine que cada ator do jogo (cada nave, ou uma nave e um tiro) tem um retângulo interno, com tamanho parecido com o tamanho de dentro o ator. Estes atores estão em movimento. Quando estes retângulos encostarem um no outro, então houve colisão.

Supondo:

• as coordenadas da nave A:
  • ponto superior esquerdo: a.x1, a.y1
  • ponto inferior direito: a.x2, a.y2
• as coordenadas da nave B:
  • ponto superior esquerdo: b.x1, b.y1
  • ponto inferior direito: b.x2, b.y2

Para ver se houve colisao, basta verificar se:
(a.X1 <= b.X2) and (a.X2 >= b.X1) and (a.Y1 <= b.Y2) and (a.Y2 >= b.Y1);

Caso esta condição for verdadeira, um está sobre o outro (há colisão, ou seja, pelo menos 1 ponto do retângulo "A" está sobre o retângulo "B").

Agora surge um outro problema: o problema do movimento rápido dos objetos. Eventualmente, se as diferenças de velocidade entre os objetos for muito grande, entao "um poderá passar pelo outro" sem colidir (ou seja, sem que a colisão seja detectada). Por exemplo:

• um objeto "A" de tamanho 10x10 esta na posição x=50,y=0 (canto superior
  esquerdo do objeto)
• um objeto "B" de tamanho 10x10 esta na posição x=150,y=0 (canto superior
  esquerdo do objeto)
• em um frame do jogo, o objeto "A" se move para a esquerda bem rápido (se move 70 pontos para a esquerda, indo para a posicao x=120,y=0) e o objeto "B" se move para a direita bem rápido (se move 90 pontos para a direita indo para a posicao x=60,y=0)
• neste caso, não foi detectada colisão, porque num frame eles andaram muito
  rápido, e "passaram" um pelo outro
• ou seja, caso a velocidade dos objetos puder ser muito alta no jogo, isto
  poderá acontecer (em muitos jogos 2D, a velocidade não é tão alta, e este problema não ocorre, mas em jogos mais rápidos isto pode ocorrer).
• Neste caso será necessário utilizar alguma técnica que "simule" que os objetos andam mais devagar, para testar as colisões em vários pontos intermediários ou então é necessário utilizar um método de calculo matemático mais apurado.

Em outras palavras, entre um frame da imagem e o frame seguinte, um objeto pode se deslocar um número razoável de pontos (por exemplo: 50 pontos). Testes até exatos (tais como o teste pixel-a-pixel) podem não serem muito precisos em movimento, porque para serem precisos mesmo teria que haver uma simulacao de todo o movimento.

No caso, por exemplo, de o objeto se mover 50 pontos para o lado em um frame, o objeto nao poderia de deslocar diretamente 50 pontos para o lado, mas teria que ser testado cada movimento de um ponto, ou seja, 50 "passos" de simulacao.

Utilizando figuras geométricas, você poderia, por exemplo, criar uma fórmula para identificar diretamente se houve colisão de uma figura com a outra, quando a primeira figura se movimenta de um ponto a outro ponto qualquer. A engine GameBase utiliza-se desta técnica para detectar a colisão e fazer o cálculo exato do tempo em que ocorreu a colisão.

1.2. Como calcular as colisões de forma rápida?

Os testes de colisão normalmente são realizados entre 2 atores (dois-a-dois). Ou seja, por exemplo:

• Caso existam 2 atores no jogo, será realizado 1 teste de colisão
• Caso existam 3 atores no jogo (por exemplo: ator A, ator B e ator C) serão realizados 3 testes de colisão (A-B, A-C, B-C).
• Caso existam 4 atores no jogo (por exemplo: ator A, ator B, ator C, ator D) serão realizados 6 testes de colisão (A-B, A-C, A-D, B-C, B-D, C-D).
• Caso existam 50 atores no jogo serão realizados 1225 testes de colisão (a formula é: (n)*(n - 1)/2).
• Caso existam 100 atores no jogo serão realizados 4950 testes de colisão.

Em outras palavras, o número de testes é "quase exponencial", ou seja, quanto mais atores testados, muito mais testes serão necessários, o que pode tornar inviável testes de colisão entre muitos atores.

A solução para este problema é reduzir o número de testes, quando o número de atores no jogo é grande.

Uma das alternativas é "setorizar" o cenário de jogo (a área onde os atores estão), ou seja, dividir todo o cenário em retângulos, e incluir os atores nestes retângulos. E somente testar a colisão entre os atores de mesmos retângulos ou retângulos contíguos. A engine GameBase utiliza-se desta técnica para reduzir o número de testes de colisão.

Autor: Giovani Kliemann,
Equipe GameBase (www.gamebase.hpg.com.br)
E-mail: gio.k@ig.com.br.

Versão do documento: 11/05/2002