Как реализовать геометрические алгоритмы в играх

О нас: Персональный сайт Тимофея Бугаевского и компании Зетка Интерактив

Руководства: Обширная коллекция технических руководств, написанных с точки зрения опытного разработчика. Каждая статья содержит подробные объяснения, практические примеры кода и паттерны для продакшена.

Интеграции: Сторонние сервисы и интеграции с платформами

Разработка игр часто требует геометрических вычислений — от обнаружения столкновений до симуляции физики. Понимание базовых геометрических алгоритмов позволяет решать задачи вроде определения того, где объекты «лежат» на поверхностях, вычисления пересечений и моделирования реалистичного движения. Это руководство охватывает ключевые геометрические алгоритмы с точки зрения senior-разработчика.

Почему геометрические алгоритмы важны

Геометрические алгоритмы позволяют:

Симуляция физики: объекты реалистично взаимодействуют с рельефом
Обнаружение столкновений: понимать, когда и где объекты соприкасаются
Поиск пути: обходить препятствия
Рендеринг: вычислять видимость и освещение
Процедурная генерация: алгоритмически создавать рельеф и уровни

Алгоритм «гусеница на поверхности»

Классическая задача в играх про транспорт/физику: определить, где гусеница (caterpillar), лыжа или балка опирается на неровный рельеф.

Постановка задачи

Дано:

Функция высоты поверхности (профиль рельефа)
Жёсткий отрезок известной длины
Положение центра масс

Найти: угол и высоту, при которых отрезок «лежит» на земле, касаясь ровно в двух точках и не проникая в поверхность.

Идея алгоритма

Алгоритм итеративно находит две точки контакта: 1. Начать с горизонтального отрезка в положении центра 2. Двигаться от центра наружу, проверяя высоты поверхности 3. Когда поверхность выше отрезка — обновить точку контакта 4. Пересчитать угол отрезка по двум точкам контакта 5. Повторять, пока отрезок не перекроет всю свою длину

Реализация

#include <cmath>
#include <algorithm>
enum Result { Success, Failure };
struct TerrainSolver {
float* groundFunction; // Массив высот поверхности
int groundLength; // Количество точек рельефа
float metersPerUnit; // Коэффициент масштаба
// Найти положение отрезка в состоянии опоры
Result findSegmentOnTerrain(
int centerX, // Положение центра (индекс массива)
float lengthLeft, // Длина от центра до левого края (метры)
float lengthRight, // Длина от центра до правого края (метры)
float sharpnessCoeff, // Допуск для определения «выше»
float& outAngle, // Выход: угол отрезка (радианы)
float& outCenterHeight // Выход: высота в центре
) {
// Инициализация на уровне поверхности, горизонтально
outCenterHeight = groundFunction[
std::max(0, std::min(groundLength - 1, centerX))
];
outAngle = 0.0f;
int iterations = 0;
// Максимальная дистанция проверки от центра
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;
// Вершины трапеции отслеживают точки контакта
float prevLeftX = 0, prevRightX = 0;
float prevLeftY = outCenterHeight;
float prevRightY = outCenterHeight;
for (int i = 1; i < maxDistance; i++) {
// Сэмплировать поверхность на текущем расстоянии
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];
// Обновить точки контакта, если поверхность выше отрезка
float newLeftX = prevLeftX, newLeftY = prevLeftY;
float newRightX = prevRightX, newRightY = prevRightY;
// Проверить левую точку
float segmentHeightAtLeft = outCenterHeight + leftX * tan(outAngle);
if (leftY > segmentHeightAtLeft) {
newLeftX = leftX;
newLeftY = leftY;
}
// Проверить правую точку
float segmentHeightAtRight = outCenterHeight + rightX * tan(outAngle);
if (rightY > segmentHeightAtRight) {
newRightX = rightX;
newRightY = rightY;
}
// Пересчитать параметры отрезка
if (newRightX != newLeftX) {
outAngle = atan2(
newRightY - newLeftY,
newRightX - newLeftX
);
outCenterHeight = newLeftY - newLeftX * tan(outAngle);
// Проверить, покрыта ли требуемая длина
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:
// Проверить отсутствие проникновения в поверхность
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];
// Применить допуск по резкости
float adjustedSegmentY = segmentY > 0
? segmentY * (1.0f + sharpnessCoeff)
: segmentY * (1.0f - sharpnessCoeff);
if (adjustedSegmentY < groundY) {
goto restart; // Обнаружено проникновение в поверхность, пересчитать
}
}
return Success;
}
};

Пересечение отрезков (Line-Line Intersection)

Критично для обнаружения столкновений и 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;
}
};
// Возвращает true, если линии пересекаются, и задаёт точку пересечения
bool lineIntersection(
Vector2 p1, Vector2 p2, // Первый отрезок
Vector2 p3, Vector2 p4, // Второй отрезок
Vector2& intersection // Выход
) {
Vector2 d1 = p2 - p1;
Vector2 d2 = p4 - p3;
float cross = d1.cross(d2);
// Параллельные линии
if (fabs(cross) < 1e-10f) {
return false;
}
Vector2 d3 = p3 - p1;
float t = d3.cross(d2) / cross;
float u = d3.cross(d1) / cross;
// Проверить, что пересечение находится в пределах обоих отрезков
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;
}

Точка в многоугольнике (Point in Polygon)

Определить, находится ли точка внутри многоугольника:

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 от точки вправо
if ((a.y <= point.y && b.y > point.y) ||
(b.y <= point.y && a.y > point.y)) {
// Вычислить x-координату пересечения
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;
}

Пересечение окружности и прямой (Circle-Line Intersection)

Найти, где прямая пересекает окружность:

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; // Пересечения нет
}
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;
}

Выпуклая оболочка (Convex Hull)

Найти выпуклую границу множества точек:

std::vector<Vector2> convexHull(std::vector<Vector2> points) {
int n = points.size();
if (n < 3) return points;
// Найти самую левую точку
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++) {
// Найти наиболее против часовой стрелки точку
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;
}

Расстояние от точки до отрезка (Distance Point to Line Segment)

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);
}

Теорема о разделяющей оси (SAT)

Проверка столкновения между выпуклыми многоугольниками:

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}); // Перпендикуляр
}
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; // Найдена разделяющая ось
}
}
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; // Разделяющей оси нет, столкновение
}

Ключевые выводы

Численная устойчивость: используйте сравнения с epsilon для чисел с плавающей запятой
Граничные случаи: обрабатывайте вырожденные случаи (параллельные линии, точка в вершине)
Оптимизация: выполняйте broad-phase фильтрацию перед детальными проверками
Системы координат: соблюдайте единообразие для Y-up и Y-down
Точность: выбирайте float или double в зависимости от требований к масштабу
Тестирование: визуализируйте результаты алгоритмов в процессе разработки

Геометрические алгоритмы — фундамент разработки игр: освоив эти основы, вы получите инструменты для эффективного решения сложных пространственных задач.