Outro post para os programadores. Dessa vez, venho descrever um probleminha que encontrei no porting de um jogo infantil de PC (feito em Director) para mobile (Java ME) e como solucionei o mesmo. O porting foi de um simples jogo de corrida, com um personagem controlado pelo jogador e outro pelo computador, sem nenhuma Inteligência Artificial avançada (nem intermediária, podemos dizer). Segue uma imagem do jogo:

O problema era referente a colisão do carro com as bordas das pistas, que são irregulares, e também com o oponente. Usar bounding boxes não produzia resultados satisfatórios, como vocês já devem ter percebido. E como os carros possuem 12 direções diferentes, usar AABB (axis-aligned bounding box) para eles também não era a solução. Então, tomei a seguinte decisão: os carros usariam OBB (oriented bounding box) e a colisão das bordas das pistas seriam definidas através de segmentos de reta.

Para os carros, como as direções/ângulos deles já estavam pré-definidas, não precisei recalcular de tempos em tempos o OBB de cada um, o que facilitou tanto na questão de código como de performance. Pré-defini um array de coordenadas (x,y) para cada direção do carro, que seriam adicionadas à posição (x,y) atual de cada carro. Para a pista, também usei valores pré-definidos, isto é, um array contendo as coordenadas (x,y) de todos os pontos que formam os segmentos de reta. A imagem abaixo mostra o jogo com meu ‘debug info’ ativado:

E uma screenshot sem imagem alguma do jogo, somente com informações de colisão, posição dos carros e caminho para o carro controlado pelo computador seguir. Note que não preciso ter as imagens do jogo para que o o mesmo seja jogável (embora precisei das imagens para definir as retas de colisão e caminho).

O que significa esse monte de linhas? Vamos lá… As retas e pontos em vermelho indicam o caminho que o carro controlado pelo computador deve seguir. IA super-ultra-mega-avançada! Tão avançado que o computador nem desvia do jogador (o jogo original era assim). Nada mais é que um path following…

As retas em amarelo são as retas de colisão para que o jogador não saia da pista. Na verdade eu uso o (x,y) de cada ponto para construir a reta e calcular a colisão. Em verde estão indicados os OBB dos carros. Opa! Mas há duas retas em verde que se cruzam. Fazem parte dos OBB dos carros? Não, essas retas indicam os setores da pista.

Eu dividi a pista em setores para diminuir a quantidade de checagem de colisão a cada quadro. Caso contrário, o processador precisaria calcular muita, mas muita colisão, deixando a performance do jogo lá na pqp. Verifico colisão apenas com os segmentos de reta de cada setor onde o jogador se encontra e, caso o oponente esteja em outro setor, não verifico colisão com ele.

Minha explicação foi clara? Para fechar o post, deixo o código que escrevi para a checagem de colisão entre os segmentos de reta, que foi o ‘core’ da implementação. O comentário está em inglês (já que trabalho com noruegueses) mas creio que dê para entender:

// int _11x means line 1, point 1, x
// int _11y means line 1, point 1, y and so on...
public boolean checkCollision(int _11x, int _11y, int _12x, int _12y, int _21x, int _21y, int _22x, int _22y) {
// equation of line 1 -> (_11y - _12y) * x - (_11x - _12x) * y = -(_11x * _12y) + (_12x * _11y);
// equation of line 2 -> (_21y - _22y) * x - (_21x - _22x) * y = -(_21x * _22y) + (_22x * _21y);

// We have two lines, AB and CD
// r1 = you should use point A into CD equation
// r2 = you should use point B into CD equation
// If the sign of r1 and r2 are different, then AB cross CD
// Then you should do the same for points C and D into AB equation
int line1R1 = (_11y - _12y) * _21x - (_11x - _12x) * _21y + (_11x * _12y) - (_12x * _11y);
int line1R2 = (_11y - _12y) * _22x - (_11x - _12x) * _22y + (_11x * _12y) - (_12x * _11y);
int line2R1 = (_21y - _22y) * _11x - (_21x - _22x) * _11y + (_21x * _22y) - (_22x * _21y);
int line2R2 = (_21y - _22y) * _12x - (_21x - _22x) * _12y + (_21x * _22y) - (_22x * _21y);

return( ((line1R1 >= 0) != (line1R2 >= 0)) && ((line2R1 >= 0) != (line2R2 >= 0)) );
}