Enquanto fazia esse jogo, queria um método rápido para detectar colisões, foi ai que me deparei com o SAT, ou Separating Axis Algorithm. Eu não vou me ater a como ele funciona em detalhes (aqui tem uma explicação muito boa, em inglês), vou apenas falar por cima e mostrar como eu implementei esse algoritimo e estou bem satisfeito com os resultados (Talvez se houver pedidos suficientes, eu faça uma explicação completa e tutorial, inclusive incluíndo código fonte completo da coisa).
O SAT projeta os poligonos em determinados eixos normais aos lados de cada objeto e testa a distância entre eles determinando se eles se tocam ou não. Se em todos os eixos eles se tocaram, então é garantido que os objetos se tocam e é possível determinar o eixo e a quantidade de penetração. Mas tudo isso só funciona se os polígonos forem convexos! (Caso não sejam, divida-os em diversos convexos menores)
Esse algoritimo é do tipo "early-out", ou seja, ele só roda por completo se realmente existir uma colisão. Assim que detecta um espaço entre os objetos testados, ele já garante que não ocorre colisão. Mas, nem tudo é perfeito, e se você for ligado em geometria, deve ter percebido que esse algoritimo só funciona em polígonos regulares, inclusive círculos.
Bem, chega de lero-lero, vamos ao (pseudo)código, nesse caso, C# e XNA. \o/
O primeiro passo é criar uma classe que possa representar um polígono qualquer. Ou seja, uma posição (x, y), um ângulo de rotação, uma escala, um centro, e claro, os vértices:
class Polygon
{
int x, y;
int rotation;
float scaleX;
float scaleY;
Matrix transform;
List<Vector2> transformedVertices = new List<Vector2>();
List<Vector2> rawVertices = new List<Vector2>();
Vector2 center;
}
Todos os campos devem ser auto-explicativos, com exceção talvez das duas listas de vértices. 'transformedVertices' retorna a lista com vértices rotacionados e com escala apropriada, enquanto 'rawVertices' retorna os vértices brutos, sem transformações. O método get de 'transformedVertices' foi implantado dessa forma:
public List<Vector2> TransformedVertices
{
get
{
transformedVertices.Clear();
for ( int i = 0; i < rawVertices.Count; i++ )
{
Vector2 temp = Vector2.Transform(rawVertices[i], transform);
temp.X += x;
temp.Y += y;
transformedVertices.Add(temp);
}
return transformedVertices;
}
}
Primeiro descartamos todos os vértices (aqui poderia ter uma otimização, para não recriar a lista todas as vezes, mas deixarei isso como exercício) e então para cada vértice bruto, aplicamos a matriz de transformação, somamos com a posição do polígono e fazendo isso cada vértice, temos a lista de vértices transformados prontos para colisão. Para atualizar a matriz de transformação, criamos este métodos:
private void updateTransformation()
{
transform = Matrix.Identity;
transform = Matrix.CreateScale(scaleX, scaleY, 0) *
Matrix.CreateRotationZ(rotation);
}
Simplesmente criamos uma escala e depois rotacionamos em torno do eixo Z. (Porque o eixo Z se estamos trabalhando em 2D? Quem será que responde? =D). Lembre-se que a escala 1 não altera o objeto, 0 o objeto não vai apareçer e acima de 1, bem, você já deve saber...
Tudo o que falta agora é a criação do polígono em si:
public static Polygon BasicPolygon(int sides = 3, int radius = 100, float creationAngle = 0f)
{
if ( sides < 3 ) throw new ArgumentException("Polygon - Needs at least 3 sides");
float sumX, sumY;
sumX = sumY = 0f;
Polygon poly = new Polygon();
float rotangle = (float)MathHelper.TwoPi / sides;
float angle;
Vector2 pt;
for ( int i = 0; i < sides; i++ )
{
angle = ( i * rotangle ) + ( ( (float)Math.PI - rotangle ) * 0.5f );
pt = new Vector2();
pt.X = (float)Math.Cos(angle) * radius;
pt.Y = (float)Math.Sin(angle) * radius;
pt = Vector2.Transform(pt, Matrix.CreateRotationZ(creationAngle));
sumX += pt.X;
sumY += pt.Y;
poly.AddVertexAtEnd(pt);
}
poly.RadiansRotation = 0;
poly.ScaleX = poly.ScaleY = 1;
poly.center = new Vector2(sumX / sides, sumY / sides);
return poly;
}
Tudo o que esse método faz é criar um polígino regular inscrito na circunferência de raio especificado, o centro do polígino também é calculado utilizando a média de todos os vértices. Estas coordenadas são locais, e não coordenadas de tela. Você pode criar outros métodos para retornar políginos não regulares ou para utilizar listas de pontos.
A última coisa a fazer antes de criar o SAT em si, é uma pequena classe para representar nossas informações de colisão:
public class CollisionInfo
{
public float OverlapAmount;
public Vector2 SmallestSeparationAxis;
public Vector2 NormalAxis;
public CollisionInfo()
{
OverlapAmount = 0;
SmallestSeparationAxis = new Vector2();
NormalAxis = new Vector2();
}
}
Essa classe deve ser auto-explicativa, mas mesmo assim, vamos lá: OverlapAmount indica quanto nossos polígonos penetraram um no outro enquanto SmallestSeparationAxis é o eixo onde ocorreu a menor penetração entre os polígonos, ou seja, para remover os objetos da colisão, basta mover um deles desse modo:
novaPosicao = info.OverlapAmount * info.SmallestSeparationAxis;
Ou da forma que lhe for conveniente.
E agora sim, podemos criar nosso método SAT! \o/
private static CollisionInfo SATCheckPolygons(Polygon polygonA, Polygon polygonB)
{
float minA, maxA;
float minB, maxB;
Vector2[] AxesForA = new Vector2[polygonA.Sides];
Vector2[] AxesForB = new Vector2[polygonB.Sides];
List<Vector2> verticesA;
List<Vector2> verticesB;
float overlap = float.MaxValue;
CollisionInfo result = new CollisionInfo();
result.IsShapeAOverlappedInB = true;
result.IsShapeBOverlappedInA = true;
verticesA = polygonA.TransformedVertices;
verticesB = polygonB.TransformedVertices;
//Pega todos os eixos dos dois polígonos.
for ( int i = 0; i < AxesForA.Length; i++ )
{
Vector2 vertex1 = verticesA[i];
Vector2 vertex2 = verticesA[i + 1 == polygonA.Sides ? 0 : i + 1];
Vector2 edge = vertex1 - vertex2;
AxesForA[i] = new Vector2(-edge.Y, edge.X);
AxesForA[i].Normalize();
}
for ( int i = 0; i < AxesForB.Length; i++ )
{
Vector2 vertex1 = verticesB[i];
Vector2 vertex2 = verticesB[i + 1 == polygonB.Sides ? 0 : i + 1];
Vector2 edge = vertex1 - vertex2;
AxesForB[i] = new Vector2(-edge.Y, edge.X);
AxesForB[i].Normalize();
}
/Projeta os dois polígonos em cada eixo e checa o resultado.
for ( int i = 0; i < AxesForA.Length; i++ )
{
projectPolygonToAxis(polygonA, AxesForA[i], out minA, out maxA);
projectPolygonToAxis(polygonB, AxesForA[i], out minB, out maxB);
if ( ( minA > maxB || minB > maxA ) ) return null; //Foi encontrado um "buraco"
else // Formar vetor de retorno de colisão
{
float o = Math.Min(maxA, maxB) - Math.Max(minA, minB);
if ( o < overlap )
{
overlap = o;
result.OverlapAmount = o;
result.SmallestSeparationAxis = AxesForA[i];
//Projeta a distância de A para B no eixo, se estiver na esquerda, não fazer nada já que usamos normais esquerdas, caso contrário, nega o eixo.
Vector2 v = polygonB.Center - polygonA.Center;
if ( Vector2.Dot(v, AxesForA[i]) > 0 )
result.SmallestSeparationAxis *= -1;
}
}
}
for ( int i = 0; i < AxesForB.Length; i++ )
{
projectPolygonToAxis(polygonA, AxesForB[i], out minA, out maxA);
projectPolygonToAxis(polygonB, AxesForB[i], out minB, out maxB);
if ( ( minA > maxB || minB > maxA ) ) return null; //Foi encontrado um "buraco"
else // Formar vetor de retorno de colisão
{
float o = Math.Min(maxA, maxB) - Math.Max(minA, minB);
if ( o < overlap )
{
overlap = o;
result.OverlapAmount = o;
result.SmallestSeparationAxis = AxesForB[i];
Vector2 v = polygonB.Center - polygonA.Center;
if ( Vector2.Dot(v, AxesForB[i]) > 0 )
result.SmallestSeparationAxis *= -1;
}
}
}
// Se chegou aqui, podemos garantir que houve colisão
return result;
}
Pronto! Basta jogar dois polígonos nesse método e ele vai retornar null caso não haja colisão ou um objeto CollisionInfo com as informações da colisão. Lembre-se que o SAT só suporta polígono convexos.
Depois farei um post semelhante detalhando como utilizar esse método com circunferências, tanto com outra cincunferência quanto com um polígono comum.
Abraços e espero que tenham gostado! Qualquer coisa grita ai em baixo! \o/
Nenhum comentário:
Postar um comentário