O desenvolvimento de jogos requer frequentemente cálculos geométricos — desde deteção de colisões até à simulação de física. Compreender algoritmos geométricos fundamentais permite-lhe resolver problemas como determinar onde os objetos assentam sobre superfícies, calcular interseções e simular movimento realista. Este guia aborda algoritmos geométricos essenciais na perspetiva de um programador sénior.
Porque é que os Algoritmos Geométricos Importam
Os algoritmos geométricos permitem:
- Simulação de Física: Os objetos interagem de forma realista com o terreno
- Deteção de Colisões: Saber quando e onde os objetos se tocam
- Pathfinding: Navegar em torno de obstáculos
- Rendering: Calcular visibilidade e iluminação
- Geração Procedimental: Criar terreno e níveis de forma algorítmica
Algoritmo de Assentamento de Segmento sobre Superfície
Um problema clássico em jogos de veículos/física: determinar onde um segmento (lagarta, esqui, viga) assenta num terreno irregular.
Enunciado do Problema
Dado:
- Uma função de altura do solo (perfil do terreno)
- Um segmento rígido de comprimento conhecido
- Uma posição do centro de massa
Determinar: O ângulo e a altura a que o segmento «assenta» no solo, tocando exatamente em dois pontos sem penetrar.
Conceito do Algoritmo
O algoritmo encontra iterativamente dois pontos de contacto: 1. Começar com o segmento horizontal na posição do centro 2. Avançar para fora a partir do centro, verificando as alturas do solo 3. Quando o solo estiver mais alto do que o segmento, atualizar o ponto de contacto 4. Recalcular o ângulo do segmento com base nos dois pontos de contacto 5. Repetir até o segmento abranger todo o seu comprimento
Implementação
#include <cmath>
#include <algorithm>
enum Result { Success, Failure };
struct TerrainSolver {
float* groundFunction; // Array de alturas do solo
int groundLength; // Número de pontos no terreno
float metersPerUnit; // Fator de escala
// Determinar a posição de assentamento do segmento
Result findSegmentOnTerrain(
int centerX, // Posição do centro (índice do array)
float lengthLeft, // Comprimento do centro até à extremidade esquerda (metros)
float lengthRight, // Comprimento do centro até à extremidade direita (metros)
float sharpnessCoeff, // Tolerância para determinar «mais alto»
float& outAngle, // Saída: ângulo do segmento (radianos)
float& outCenterHeight // Saída: altura no centro
) {
// Inicializar ao nível do solo, horizontal
outCenterHeight = groundFunction[
std::max(0, std::min(groundLength - 1, centerX))
];
outAngle = 0.0f;
int iterations = 0;
// Distância máxima a verificar a partir do centro
int maxDistance = std::min(
std::max(lengthLeft, lengthRight) / metersPerUnit + 1,
(float)std::max(groundLength - centerX, centerX)
);
if (maxDistance < 1) return Failure;
restart:
iterations++;
if (iterations > 3) return Failure;
// Vértices do trapézio a acompanhar os pontos de contacto
float prevLeftX = 0, prevRightX = 0;
float prevLeftY = outCenterHeight;
float prevRightY = outCenterHeight;
for (int i = 1; i < maxDistance; i++) {
// Amostrar o solo à distância atual
int leftIdx = std::max(
centerX - std::min(i, (int)(lengthLeft / metersPerUnit)),
0
);
int rightIdx = std::min(
centerX + std::min(i, (int)(lengthRight / metersPerUnit)),
groundLength - 1
);
float leftX = (leftIdx - centerX) * metersPerUnit;
float rightX = (rightIdx - centerX) * metersPerUnit;
float leftY = groundFunction[leftIdx];
float rightY = groundFunction[rightIdx];
// Atualizar os pontos de contacto se o solo estiver mais alto do que o segmento
float newLeftX = prevLeftX, newLeftY = prevLeftY;
float newRightX = prevRightX, newRightY = prevRightY;
// Verificar o ponto esquerdo
float segmentHeightAtLeft = outCenterHeight + leftX * tan(outAngle);
if (leftY > segmentHeightAtLeft) {
newLeftX = leftX;
newLeftY = leftY;
}
// Verificar o ponto direito
float segmentHeightAtRight = outCenterHeight + rightX * tan(outAngle);
if (rightY > segmentHeightAtRight) {
newRightX = rightX;
newRightY = rightY;
}
// Recalcular as propriedades do segmento
if (newRightX != newLeftX) {
outAngle = atan2(
newRightY - newLeftY,
newRightX - newLeftX
);
outCenterHeight = newLeftY - newLeftX * tan(outAngle);
// Verificar se cobrimos o comprimento necessário
float cosAngle = cos(outAngle);
if (cosAngle != 0.0f) {
if ((-leftX) / cosAngle >= lengthLeft &&
rightX / cosAngle >= lengthRight) {
goto verify;
}
}
} else {
outAngle = 0;
outCenterHeight = std::max(newLeftY, newRightY);
}
prevLeftX = newLeftX;
prevLeftY = newLeftY;
prevRightX = newRightX;
prevRightY = newRightY;
}
verify:
// Verificar se não há penetração no solo
int startIdx = centerX - (int)(lengthLeft * cos(outAngle) / metersPerUnit) + 1;
int endIdx = centerX + (int)(lengthRight * cos(outAngle) / metersPerUnit) - 1;
for (int i = std::max(0, startIdx); i <= std::min(endIdx, groundLength - 1); i++) {
float x = (i - centerX) * metersPerUnit;
float segmentY = outCenterHeight + x * tan(outAngle);
float groundY = groundFunction[i];
// Aplicar tolerância de exatidão
float adjustedSegmentY = segmentY > 0
? segmentY * (1.0f + sharpnessCoeff)
: segmentY * (1.0f - sharpnessCoeff);
if (adjustedSegmentY < groundY) {
goto restart; // Foi detetada penetração no solo, recalcular
}
}
return Success;
}
};
Interseção Reta-Reta
Essencial para deteção de colisões e ray casting:
struct Vector2 {
float x, y;
Vector2 operator-(const Vector2& other) const {
return {x - other.x, y - other.y};
}
float cross(const Vector2& other) const {
return x * other.y - y * other.x;
}
};
// Devolve true se as retas se intersectarem; define o ponto de interseção
bool lineIntersection(
Vector2 p1, Vector2 p2, // Primeiro segmento de reta
Vector2 p3, Vector2 p4, // Segundo segmento de reta
Vector2& intersection // Saída
) {
Vector2 d1 = p2 - p1;
Vector2 d2 = p4 - p3;
float cross = d1.cross(d2);
// Retas paralelas
if (fabs(cross) < 1e-10f) {
return false;
}
Vector2 d3 = p3 - p1;
float t = d3.cross(d2) / cross;
float u = d3.cross(d1) / cross;
// Verificar se a interseção está dentro de ambos os segmentos
if (t >= 0 && t <= 1 && u >= 0 && u <= 1) {
intersection.x = p1.x + t * d1.x;
intersection.y = p1.y + t * d1.y;
return true;
}
return false;
}
Ponto no Polígono
Determinar se um ponto está dentro de um polígono:
bool pointInPolygon(Vector2 point, std::vector<Vector2>& polygon) {
int crossings = 0;
int n = polygon.size();
for (int i = 0; i < n; i++) {
Vector2 a = polygon[i];
Vector2 b = polygon[(i + 1) % n];
// Ray casting a partir do ponto para a direita
if ((a.y <= point.y && b.y > point.y) ||
(b.y <= point.y && a.y > point.y)) {
// Calcular a coordenada x da interseção
float t = (point.y - a.y) / (b.y - a.y);
float x = a.x + t * (b.x - a.x);
if (point.x < x) {
crossings++;
}
}
}
return (crossings % 2) == 1;
}
Interseção Círculo-Reta
Determinar onde uma reta intersecta um círculo:
int circleLineIntersection(
Vector2 center, float radius,
Vector2 p1, Vector2 p2,
Vector2& hit1, Vector2& hit2
) {
Vector2 d = p2 - p1;
Vector2 f = {p1.x - center.x, p1.y - center.y};
float a = d.x * d.x + d.y * d.y;
float b = 2 * (f.x * d.x + f.y * d.y);
float c = f.x * f.x + f.y * f.y - radius * radius;
float discriminant = b * b - 4 * a * c;
if (discriminant < 0) {
return 0; // Sem interseção
}
discriminant = sqrt(discriminant);
float t1 = (-b - discriminant) / (2 * a);
float t2 = (-b + discriminant) / (2 * a);
int count = 0;
if (t1 >= 0 && t1 <= 1) {
hit1 = {p1.x + t1 * d.x, p1.y + t1 * d.y};
count++;
}
if (t2 >= 0 && t2 <= 1 && discriminant > 0) {
if (count == 0) {
hit1 = {p1.x + t2 * d.x, p1.y + t2 * d.y};
} else {
hit2 = {p1.x + t2 * d.x, p1.y + t2 * d.y};
}
count++;
}
return count;
}
Envoltória Convexa
Determinar o limite convexo de um conjunto de pontos:
std::vector<Vector2> convexHull(std::vector<Vector2> points) {
int n = points.size();
if (n < 3) return points;
// Encontrar o ponto mais à esquerda
int left = 0;
for (int i = 1; i < n; i++) {
if (points[i].x < points[left].x) {
left = i;
}
}
std::vector<Vector2> hull;
int p = left, q;
do {
hull.push_back(points[p]);
q = (p + 1) % n;
for (int i = 0; i < n; i++) {
// Encontrar o ponto mais no sentido anti-horário
Vector2 a = points[q] - points[p];
Vector2 b = points[i] - points[p];
if (a.cross(b) < 0) {
q = i;
}
}
p = q;
} while (p != left);
return hull;
}
Distância de um Ponto a um Segmento de Reta
float pointToSegmentDistance(Vector2 point, Vector2 a, Vector2 b) {
Vector2 ab = b - a;
Vector2 ap = point - a;
float t = (ap.x * ab.x + ap.y * ab.y) / (ab.x * ab.x + ab.y * ab.y);
t = std::max(0.0f, std::min(1.0f, t));
Vector2 closest = {a.x + t * ab.x, a.y + t * ab.y};
Vector2 diff = point - closest;
return sqrt(diff.x * diff.x + diff.y * diff.y);
}
Teorema do Eixo Separador (SAT)
Testar colisão entre polígonos convexos:
bool polygonsCollide(
std::vector<Vector2>& poly1,
std::vector<Vector2>& poly2
) {
auto getAxes = [](std::vector<Vector2>& poly) {
std::vector<Vector2> axes;
for (int i = 0; i < poly.size(); i++) {
Vector2 edge = poly[(i + 1) % poly.size()] - poly[i];
axes.push_back({-edge.y, edge.x}); // Perpendicular
}
return axes;
};
auto project = [](std::vector<Vector2>& poly, Vector2 axis) {
float min = poly[0].x * axis.x + poly[0].y * axis.y;
float max = min;
for (auto& p : poly) {
float dot = p.x * axis.x + p.y * axis.y;
min = std::min(min, dot);
max = std::max(max, dot);
}
return std::make_pair(min, max);
};
std::vector<Vector2> axes1 = getAxes(poly1);
std::vector<Vector2> axes2 = getAxes(poly2);
for (auto& axis : axes1) {
auto [min1, max1] = project(poly1, axis);
auto [min2, max2] = project(poly2, axis);
if (max1 < min2 || max2 < min1) {
return false; // Foi encontrado um eixo separador
}
}
for (auto& axis : axes2) {
auto [min1, max1] = project(poly1, axis);
auto [min2, max2] = project(poly2, axis);
if (max1 < min2 || max2 < min1) {
return false;
}
}
return true; // Sem eixo separador, colisão
}
Principais Conclusões
- Estabilidade numérica: Use comparações com epsilon para vírgula flutuante
- Casos-limite: Trate casos degenerados (retas paralelas, ponto num vértice)
- Otimização: Filtragem de broad-phase antes de verificações detalhadas
- Sistemas de coordenadas: Seja consistente com Y-up vs Y-down
- Precisão: Escolha float vs double com base nos requisitos de escala
- Testes: Visualize os resultados dos algoritmos durante o desenvolvimento
Os algoritmos geométricos são fundamentais para o desenvolvimento de jogos — domine estes conceitos básicos e terá ferramentas para resolver problemas espaciais complexos de forma eficiente.
