How to Implement Geometric Algorithms in Games

About us: Personal website of Timofey Bugaevsky and the company Zetka Interactive

Guides: A comprehensive collection of technical guides written from a senior developer's perspective. Each article provides in-depth explanations, practical code examples, and production-ready patterns.

Integrations: Third-party services and platform integrations

Game development frequently requires geometric calculations—from collision detection to physics simulation. Understanding fundamental geometric algorithms enables you to solve problems like finding where objects rest on surfaces, calculating intersections, and simulating realistic movement. This guide covers essential geometric algorithms from a senior developer's perspective.

Why Geometric Algorithms Matter

Geometric algorithms enable:

Physics Simulation: Objects interact realistically with terrain
Collision Detection: Know when and where objects touch
Pathfinding: Navigate around obstacles
Rendering: Calculate visibility and lighting
Procedural Generation: Create terrain and levels algorithmically

Track-on-Surface Algorithm

A classic problem in vehicle/physics games: finding where a track (caterpillar, ski, beam) rests on uneven terrain.

Problem Statement

Given:

A ground height function (terrain profile)
A rigid segment of known length
A center of mass position

Find: The angle and height at which the segment "rests" on the ground, touching at exactly two points without penetrating.

Algorithm Concept

The algorithm iteratively finds two contact points: 1. Start with the segment horizontal at the center position 2. Move outward from the center, checking ground heights 3. When the ground is higher than the segment, update the contact point 4. Recalculate the segment angle based on two contact points 5. Repeat until the segment spans its full length

Implementation

#include <cmath>
#include <algorithm>
enum Result { Success, Failure };
struct TerrainSolver {
float* groundFunction; // Array of ground heights
int groundLength; // Number of points in the terrain
float metersPerUnit; // Scale factor
// Find the segment resting position
Result findSegmentOnTerrain(
int centerX, // Center position (array index)
float lengthLeft, // Length from center to left edge (meters)
float lengthRight, // Length from center to right edge (meters)
float sharpnessCoeff, // Tolerance for "higher" determination
float& outAngle, // Output: segment angle (radians)
float& outCenterHeight // Output: height at center
) {
// Initialize at ground level, horizontal
outCenterHeight = groundFunction[
std::max(0, std::min(groundLength - 1, centerX))
];
outAngle = 0.0f;
int iterations = 0;
// Maximum distance to check from center
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;
// Trapezoid vertices tracking contact points
float prevLeftX = 0, prevRightX = 0;
float prevLeftY = outCenterHeight;
float prevRightY = outCenterHeight;
for (int i = 1; i < maxDistance; i++) {
// Sample ground at the current distance
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];
// Update contact points if the ground is higher than the segment
float newLeftX = prevLeftX, newLeftY = prevLeftY;
float newRightX = prevRightX, newRightY = prevRightY;
// Check left point
float segmentHeightAtLeft = outCenterHeight + leftX * tan(outAngle);
if (leftY > segmentHeightAtLeft) {
newLeftX = leftX;
newLeftY = leftY;
}
// Check right point
float segmentHeightAtRight = outCenterHeight + rightX * tan(outAngle);
if (rightY > segmentHeightAtRight) {
newRightX = rightX;
newRightY = rightY;
}
// Recalculate segment properties
if (newRightX != newLeftX) {
outAngle = atan2(
newRightY - newLeftY,
newRightX - newLeftX
);
outCenterHeight = newLeftY - newLeftX * tan(outAngle);
// Check if we've covered the required length
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:
// Verify no ground penetration
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];
// Apply sharpness tolerance
float adjustedSegmentY = segmentY > 0
? segmentY * (1.0f + sharpnessCoeff)
: segmentY * (1.0f - sharpnessCoeff);
if (adjustedSegmentY < groundY) {
goto restart; // Ground penetration found; recalculate
}
}
return Success;
}
};

Line-Line Intersection

Essential for collision detection and 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;
}
};
// Returns true if lines intersect; sets intersection point
bool lineIntersection(
Vector2 p1, Vector2 p2, // First line segment
Vector2 p3, Vector2 p4, // Second line segment
Vector2& intersection // Output
) {
Vector2 d1 = p2 - p1;
Vector2 d2 = p4 - p3;
float cross = d1.cross(d2);
// Parallel lines
if (fabs(cross) < 1e-10f) {
return false;
}
Vector2 d3 = p3 - p1;
float t = d3.cross(d2) / cross;
float u = d3.cross(d1) / cross;
// Check if the intersection is within both segments
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

Determine if a point is inside a 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 from point to the right
if ((a.y <= point.y && b.y > point.y) ||
(b.y <= point.y && a.y > point.y)) {
// Calculate x-coordinate of intersection
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

Find where a line intersects a circle:

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; // No intersection
}
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

Find the convex boundary of a set of points:

std::vector<Vector2> convexHull(std::vector<Vector2> points) {
int n = points.size();
if (n < 3) return points;
// Find the leftmost point
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++) {
// Find the most counterclockwise point
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);
}

Separating Axis Theorem (SAT)

Test collision between convex polygons:

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; // Separating axis found
}
}
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; // No separating axis; collision
}