SDL_Collide - Colisão 2D para jogos

A primeira regra de qualquer jogo é a colisão. É claro que isso só inclui 99,99% dos jogos.
Como será o sistema de colisão em seu jogo é um fator determinante pra conclusão do projeto.
Como sempre tenho a SDL sempre a mão e para resolver este problema vou apresentar a SDL_Collide.

» Post Completo...*** SDL_Collide ***
Esta não é mais uma biblioteca de dependência para seu código, na verdade eu a considero como uma biblioteca de referência. Digo isso porque SDL_Collide possui apenas 240 linhas de código (totalmente comentadas) e estudando a lógica das funções (apenas 6) você é capaz de otimizar as suas.

int SDL_CollideTransparentPixel(SDL_Surface *surface, int u, int v);
Esta Função serve apenas para testar se um pixel[u][v] é ou não transparente.
É uma função que acessa um pixel (meio complicado de explicar) e no final compara com o colorkey da imagem.

return (pixelcolor == surface->format->colorkey);

int SDL_CollidePixel(SDL_Surface *as, int ax, int ay, SDL_Surface *bs, int bx, int by, int skip = 4);
Esta função faz um teste de colisão em pixel precisão. É muito lenta.
Por exemplo: SDL_CollidePixel("verde_claro",0,0,"verde_escuro",4,2,2);
Como é mostrado acima, o exemplo faria teste de colisão nos pixels de intercessão entre as imagens. O parâmetro skip (2) indica quantos pixels saltar (1 faz teste completo).
O exemplo retornou verdadeiro. Branco é nossa cor de transparência e a colisão foi detectada apenas uma vez.

int SDL_CollideBoundingBox(SDL_Surface *sa, int ax, int ay, SDL_Surface *sb, int bx, int by);
e
int SDL_CollideBoundingBox(SDL_Rect a, SDL_Rect b);
São responsáveis pela colisão entre retângulos e são muito rápidas.

int SDL_CollideBoundingBox(SDL_Rect a, SDL_Rect b){
if(b.x + b.w < a.x) //- b.direita < a.esquerda
return 0;
if(b.x > a.x + a.w) //- b.esquerda > a.direita
return 0;
if(b.y + b.h < a.y) //- b.baixo < a.cima
return 0;
if(b.y > a.y + a.h) //- b.cima > a.baixo
return 0;

return 1; //- retângulos se colidem
}

O primeiro teste "if(b.x + b.w < a.x)" é representado na figura pelas barras vermelhas.
Repare que a colisão só existe quando todos os testes falham. O algoritmo procura por algum lado que possa eliminar a colisão totalmente.

int SDL_CollideBoundingCircle(int x1, int y1, int r1, int x2, int y2, int r2, int offset);
Faz a comparação de colisão entre circulos. x e y são coordenadas do centro. use offset como 0 (deve ser alguma medida de precisão).

int SDL_CollideBoundingCircle(int x1, int y1, int r1, int x2, int y2, int r2, int offset){
int xdiff = x2 - x1; //- diferença no eixo x
int ydiff = y2 - y1; //- diferença no eixo y

/* Distância entre os centros dos círculos ao quadrado */
int dcentre_sq = (ydiff*ydiff) + (xdiff*xdiff);

/* Calcula a soma dos raios ao quadrado */
int r_sum_sq = r1 + r2;
r_sum_sq *= r_sum_sq; //- melhor que (r1+r2)*(r1+r2)

return (dcentre_sq - r_sum_sq <= (offset*offset));
}

Existe colisão quando a soma dos raios for maior que a distância.
Esta função está bem otimizada, tanto é que, para calcular a distância não foi utilizada a raiz quadrada.
A distância não é realmente necessária, ela serve apenas como comparativo. Como o cálculo da raiz quadrada não é uma operação trivial, é preferível comparar todas as somas (raios e dx dy) em potência de 2.

int SDL_CollideBoundingCircle(SDL_Surface *a, int x1, int y1, SDL_Surface *b, int x2, int y2, int offset);
É uma variação da função anterior onde o raio do circulo é calculado por aproximação (r1 = (a.w+a.h) / 4).

Download: SDL_Collide (o código fonte já vem com a versão )

*** O exemplo ***
Aproveitando o código anterior, criei um jogo de labirinto com itens (quase um Pac-Man) para que ficasse bem claro como pode ser feita a implementação de um jogo com colisões.
Para que ficasse funcional acabei complicando o código. Por isso vou explicar algumas das funções que realmente importam.
Não é sempre que se pode mover em todas as direções que pede o jogador, e é isso que a função mov() irá tratar:

bool Play::mov(int movX,int movY,Mapa *mapa){
if( !mov2(movX,movY,mapa) ){ //- teste de movimento em x e y
if( !mov2(movX,0,mapa) ){ //- teste de movimento em x
if( !mov2(0,movY,mapa) ) //- teste de movimento em y
return 0;
}
}
pegaItem(mapa);
return 1;
}

A função mov2() é a função que realmente move o nosso smiley. Ela cria um retângulo auxiliar com a nova posição e testa colisão com todos os retângulos vizinhos:

bool Play::mov2(int movX,int movY,Mapa *mapa){
SDL_Rect aux = {box.x+movX,box.y+movY,box.w,box.h}, ret;
int x,y,i,j,colisao;
char t; //- tile

x = aux.x/W; //- coordenada x no mapa (aproximada)
y = aux.y/H; //- coordenada y no mapa (aproximada)

//- loop nos tiles vizinhos
for(j=-1;j<2;j++){ //- -1,0,1
for(i=-1;i<2;i++){ //- -1,0,1
try{
t = mapa->tile(x+i,y+j);
}catch(...){ //- fora da grade
continue;
}
mapa->getRect(x+i,y+j,ret);
colisao = SDL_CollideBoundingBox(aux,ret);
if(colisao && (t==1 || t>3) ){ //- colisao com paredes
//printf("colisao> %d,%d x %d,%d\n",aux.x,aux.y,ret.x,ret.y);
return 0;
}
}
}
box.x += movX;
box.y += movY;
return 1;
}

Como eu disse, é possível otimizar as funções da SDL_Collide à sua maneira, e foi o que eu fiz:

int SDL_CollideBoundingBox(SDL_Rect a, SDL_Rect b){
if(b.x + b.w <= a.x) return 0;
if(b.x >= a.x + a.w) return 0;

if(b.y + b.h <= a.y) return 0;
if(b.y >= a.y + a.h) return 0;

return 1;
}

Fazer colisão usando o retângulo da própria imagem pode não ser uma boa. Meu personagem tem 32x32 e seu retêngulo de colisão apenas 20x20.
A movimentação não ficou muito boa. A explicação para isso é que não tratamos as colisões da melhor forma, pois sempre que há uma colisão não se faz absolutamente nada para corrigir.
Então é só ! Analise o código fonte para entender os detalhes.
Download: » código fonte

*** SinucaOS ***
Não tem como a gente falar de colisão de círculos sem lembrar de um jogo de sinuca.
Acredite, fazer um jogo de sinuca é realmente difícil. A física de um jogo de sinuca exige muito mais do que se pode ver. A tacada inicial, por exemplo, é uma explosão de colisões e isto fragiliza a implementação.
SinicaOS é um grupo que está desenvolvendo um jogo de sinuca open source em C e Allegro. Por enquanto, o foco principal é ter um simulador de física funcional.
A imagem acima(animação gif) mostra duas bolas grudadas no terceiro quadro. Isto mostra que não são poucos os problemas enfrentados.
Pode ser um bug do jogo, mas o grande causador deste problema é a quantidade de bolas, a proximidade entre elas e a alta precisão exigida. A maioria dos bons jogos de sinuca sobrem deste mesmo mal.

*** Link's ***
Download: » código fonte
» SDL - Site oficial
» SDL_Collide - Site do projeto

---
Feliz Natal !!!