Subchapter 178.2

Algorithms

references/algorithms.mdMarkdown24 KBView on GitHub

Game Development Algorithms

A comprehensive reference covering essential algorithms for game development, including line drawing, raycasting, collision detection, physics simulation, and vector mathematics.

Algorithms · Game Engine · github/awesome-copilot · Skills Docs

function bresenham(x0, y0, x1, y1):
    dx = abs(x1 - x0)
    dy = abs(y1 - y0)
    sx = sign(x1 - x0)   // -1 or +1
    sy = sign(y1 - y0)   // -1 or +1
    err = dx - dy

    while true:
        visit(x0, y0)          // process or record this cell

        if x0 == x1 AND y0 == y1:
            break

        e2 = 2 * err

        if e2 > -dy:
            err = err - dy
            x0  = x0 + sx

        if e2 < dx:
            err = err + dx
            y0  = y0 + sy

public function hasLineOfSight(x0:Int, y0:Int, x1:Int, y1:Int):Bool {
    var dx = hxd.Math.iabs(x1 - x0);
    var dy = hxd.Math.iabs(y1 - y0);
    var sx = (x0 < x1) ? 1 : -1;
    var sy = (y0 < y1) ? 1 : -1;
    var err = dx - dy;

    while (true) {
        if (isBlocking(x0, y0))
            return false;

        if (x0 == x1 && y0 == y1)
            return true;

        var e2 = 2 * err;
        if (e2 > -dy) {
            err -= dy;
            x0 += sx;
        }
        if (e2 < dx) {
            err += dx;
            y0 += sy;
        }
    }
}

// Broad phase: spatial hash or sweep-and-prune
candidates = broadPhase(allObjects)

for each pair (a, b) in candidates:
    overlap = narrowPhaseTest(a, b)

    if overlap:
        // Compute penetration vector
        penetration = computePenetration(a, b)

        // Resolve: push objects apart along the minimum penetration axis
        if a.isStatic:
            b.position += penetration
        else if b.isStatic:
            a.position -= penetration
        else:
            a.position -= penetration * 0.5
            b.position += penetration * 0.5

        // Optional: apply impulse for velocity response
        relativeVelocity = a.velocity - b.velocity
        impulse = computeImpulse(relativeVelocity, penetration.normal, a.mass, b.mass)
        a.velocity -= impulse / a.mass
        b.velocity += impulse / b.mass

function computePenetration(a, b):
    overlapX_left  = (a.x + a.halfW) - (b.x - b.halfW)
    overlapX_right = (b.x + b.halfW) - (a.x - a.halfW)
    overlapY_top   = (a.y + a.halfH) - (b.y - b.halfH)
    overlapY_bot   = (b.y + b.halfH) - (a.y - a.halfH)

    minOverlapX = min(overlapX_left, overlapX_right)
    minOverlapY = min(overlapY_top, overlapY_bot)

    if minOverlapX < minOverlapY:
        return Vector(sign * minOverlapX, 0)
    else:
        return Vector(0, sign * minOverlapY)

Strategy	Best For	Description
Uniform Grid	Evenly distributed objects	Divide world into fixed cells; objects register in their cell(s).
Quadtree	Non-uniform distribution	Recursively subdivide space into 4 quadrants. Efficient for sparse scenes.
Spatial Hash	Dynamic scenes	Hash object positions to buckets. O(1) lookup for neighbors.
Sweep and Prune	Many moving objects	Sort by axis; only test overlapping intervals.

Speed: A scalar quantity representing how fast an object moves, regardless of direction.
```
speed = |velocity| = sqrt(vx^2 + vy^2)
```
Velocity: A vector quantity representing both speed and direction.
```
velocity = (vx, vy)
```
Acceleration: The rate of change of velocity over time.
```
acceleration = (ax, ay)
velocity += acceleration * deltaTime
```

function update(entity, deltaTime):
    // Apply acceleration (gravity, thrust, friction, etc.)
    entity.velocity.x += entity.acceleration.x * deltaTime
    entity.velocity.y += entity.acceleration.y * deltaTime

    // Clamp speed to a maximum
    currentSpeed = magnitude(entity.velocity)
    if currentSpeed > entity.maxSpeed:
        entity.velocity = normalize(entity.velocity) * entity.maxSpeed

    // Apply friction / drag
    entity.velocity.x *= (1 - entity.friction * deltaTime)
    entity.velocity.y *= (1 - entity.friction * deltaTime)

    // Update position
    entity.position.x += entity.velocity.x * deltaTime
    entity.position.y += entity.velocity.y * deltaTime

accumulator = 0
fixedDeltaTime = 1 / 60  // 60 Hz physics

function physicsUpdate(frameDeltaTime):
    accumulator += frameDeltaTime

    while accumulator >= fixedDeltaTime:
        step(fixedDeltaTime)
        accumulator -= fixedDeltaTime

Property	Description
`position`	Center of mass in world space
`velocity`	Linear velocity vector
`acceleration`	Sum of all forces / mass
`mass`	Resistance to linear acceleration
`inverseMass`	`1 / mass` (0 for static objects)
`angle`	Rotation angle
`angularVelocity`	Rate of rotation
`inertia`	Resistance to angular acceleration
`restitution`	Bounciness (0 = no bounce, 1 = perfectly elastic)
`friction`	Surface friction coefficient

function applyForce(body, force):
    body.forceAccumulator += force

function integrate(body, dt):
    body.acceleration = body.forceAccumulator * body.inverseMass
    body.velocity += body.acceleration * dt
    body.position += body.velocity * dt
    body.forceAccumulator = (0, 0)  // reset

function resolveCollision(a, b, normal, penetration):
    // Relative velocity at the contact point
    relVel = b.velocity - a.velocity
    velAlongNormal = dot(relVel, normal)

    // Do not resolve if objects are separating
    if velAlongNormal > 0:
        return

    // Coefficient of restitution (take minimum)
    e = min(a.restitution, b.restitution)

    // Impulse magnitude
    j = -(1 + e) * velAlongNormal
    j /= a.inverseMass + b.inverseMass

    // Apply impulse
    impulse = j * normal
    a.velocity -= impulse * a.inverseMass
    b.velocity += impulse * b.inverseMass

    // Positional correction (prevent sinking)
    correction = max(penetration - slop, 0) / (a.inverseMass + b.inverseMass) * percent
    a.position -= correction * a.inverseMass * normal
    b.position += correction * b.inverseMass * normal

function step(dt):
    // 1. Apply external forces (gravity, player input, etc.)
    for each body in world.bodies:
        if not body.isStatic:
            body.applyForce(gravity * body.mass)

    // 2. Integrate velocities and positions
    for each body in world.bodies:
        if not body.isStatic:
            body.velocity += (body.forceAccumulator * body.inverseMass) * dt
            body.position += body.velocity * dt
            body.angularVelocity += body.torque * body.inverseInertia * dt
            body.angle += body.angularVelocity * dt
            body.forceAccumulator = (0, 0)
            body.torque = 0

    // 3. Broad-phase collision detection
    pairs = broadPhase(world.bodies)

    // 4. Narrow-phase collision detection
    contacts = []
    for each (a, b) in pairs:
        contact = narrowPhase(a, b)
        if contact:
            contacts.append(contact)

    // 5. Resolve collisions (iterative solver)
    for i in range(solverIterations):   // typically 4-10 iterations
        for each contact in contacts:
            resolveCollision(contact.a, contact.b,
                             contact.normal, contact.penetration)

class Vector2D:
    x, y

    function add(other):
        return Vector2D(x + other.x, y + other.y)

    function subtract(other):
        return Vector2D(x - other.x, y - other.y)

    function scale(scalar):
        return Vector2D(x * scalar, y * scalar)

    function magnitude():
        return sqrt(x * x + y * y)

    function magnitudeSquared():
        return x * x + y * y

    function normalize():
        mag = magnitude()
        if mag > 0:
            return Vector2D(x / mag, y / mag)
        return Vector2D(0, 0)

    function dot(other):
        return x * other.x + y * other.y

    function cross(other):
        return x * other.y - y * other.x

    function perpendicular():
        return Vector2D(-y, x)

    function reflect(normal):
        d = dot(normal)
        return Vector2D(x - 2 * d * normal.x, y - 2 * d * normal.y)

    function angleTo(other):
        return acos(normalize().dot(other.normalize()))

    function distanceTo(other):
        return subtract(other).magnitude()

    function lerp(other, t):
        return Vector2D(
            x + (other.x - x) * t,
            y + (other.y - y) * t
        )

Movement and steering: Add velocity vectors to position; normalize direction vectors and multiply by speed for consistent movement.
Distance checks: Use squared magnitude for performance-friendly radius checks (e.g., “is this enemy within range?”).
Field-of-view: Use the dot product between an entity’s forward vector and the direction to a target to determine if the target is within a vision cone.
Wall sliding: Project the velocity onto the wall’s tangent (perpendicular to the normal) to allow smooth sliding along surfaces.
Reflections and bouncing: Use the reflection formula when a projectile or ball hits a surface.
Interpolation: Use lerp (linear interpolation) between two vectors for smooth movement, camera tracking, and animations.

Rotation: Rotate a vector by an angle using trigonometry:

rotated.x = v.x * cos(angle) - v.y * sin(angle)
rotated.y = v.x * sin(angle) + v.y * cos(angle)

Algorithm / Concept	Primary Use Case	Complexity
Bresenham’s Line	Grid raycasting, line of sight	O(max(dx, dy)) per ray
AABB Overlap	Fast collision detection	O(1) per pair
Circle Overlap	Round collider detection	O(1) per pair
Separating Axis Theorem	Convex polygon collision	O(n) per pair (n = edges)
Spatial Hashing	Broad-phase collision culling	O(1) average lookup
Euler Integration	Simple physics stepping	O(1) per body per step
Verlet Integration	Constraint-based physics	O(1) per body per step
Impulse Resolution	Collision response	O(iterations * contacts)
Vector Normalization	Direction extraction	O(1)
Dot Product	Angle/projection queries	O(1)
Cross Product	Perpendicularity / winding	O(1)
Reflection	Bounce / ricochet	O(1)