Core Techniques and Algorithms in Game Programming Skill

Game Architecture

The Game Loop

// Classic fixed-timestep game loop
void GameLoop() {
    const double TICK_RATE = 1.0 / 60.0;  // 60 Hz simulation
    double accumulator = 0.0;
    double previousTime = GetTime();

    while (running) {
        double currentTime = GetTime();
        double frameTime = currentTime - previousTime;
        previousTime = currentTime;

        // Cap frame time to prevent spiral of death
        if (frameTime > 0.25) frameTime = 0.25;
        accumulator += frameTime;

        // Fixed-rate simulation updates
        while (accumulator >= TICK_RATE) {
            ProcessInput();
            Update(TICK_RATE);         // physics, AI, game logic
            accumulator -= TICK_RATE;
        }

        // Render at display rate (interpolate between states)
        double alpha = accumulator / TICK_RATE;
        Render(alpha);
    }
}

Game Architecture Layers

Presentation Layer
  ├── Renderer (2D/3D)
  ├── Audio manager
  ├── Particle systems
  └── Animation system

Game Logic Layer
  ├── Scene manager / entity system
  ├── AI system
  ├── Physics system
  ├── Input manager
  └── Scripting engine

Platform Layer
  ├── OS abstraction (input, timing, file I/O)
  ├── Networking
  └── Memory manager

---

Design Patterns for Games

Game Object / Component Pattern

// Avoid deep inheritance hierarchies — use composition
class GameObject {
    std::vector<std::unique_ptr<Component>> components_;
    std::string name_;

public:
    template<typename T, typename... Args>
    T* addComponent(Args&&... args) {
        auto c = std::make_unique<T>(std::forward<Args>(args)...);
        T* ptr = c.get();
        components_.push_back(std::move(c));
        return ptr;
    }

    template<typename T>
    T* getComponent() {
        for (auto& c : components_)
            if (auto* p = dynamic_cast<T*>(c.get()))
                return p;
        return nullptr;
    }

    void update(float dt) {
        for (auto& c : components_)
            c->update(dt);
    }
};

State Pattern (AI/Game States)

class State {
public:
    virtual void enter(Entity& entity) = 0;
    virtual void update(Entity& entity, float dt) = 0;
    virtual void exit(Entity& entity) = 0;
    virtual ~State() {}
};

class StateMachine {
    State* current_ = nullptr;

public:
    void changeState(State* newState, Entity& entity) {
        if (current_) current_->exit(entity);
        current_ = newState;
        if (current_) current_->enter(entity);
    }

    void update(Entity& entity, float dt) {
        if (current_) current_->update(entity, dt);
    }
};

Singleton for Managers (use sparingly)

template<typename T>
class Singleton {
    static T* instance_;
public:
    static T& getInstance() {
        if (!instance_) instance_ = new T();
        return *instance_;
    }
protected:
    Singleton() {}
};
// Usage: AudioManager::getInstance().play("explosion.wav");

Observer Pattern (Events)

class EventSystem {
    std::unordered_map<std::string, std::vector<std::function<void(Event&)>>> listeners_;
public:
    void subscribe(const std::string& event, std::function<void(Event&)> cb) {
        listeners_[event].push_back(cb);
    }
    void emit(const std::string& event, Event& e) {
        for (auto& cb : listeners_[event]) cb(e);
    }
};

---

Fundamental AI Technologies

Finite State Machines

// FSM for enemy AI
enum class EnemyState { IDLE, PATROL, CHASE, ATTACK, FLEE };

class Enemy {
    EnemyState state_ = EnemyState::PATROL;
    float alertRadius_ = 100.f;
    float attackRadius_ = 20.f;

public:
    void update(const Player& player, float dt) {
        float dist = distance(position_, player.position());

        switch (state_) {
        case EnemyState::PATROL:
            if (dist < alertRadius_) transitionTo(EnemyState::CHASE);
            else patrol(dt);
            break;
        case EnemyState::CHASE:
            if (dist < attackRadius_) transitionTo(EnemyState::ATTACK);
            else if (dist > alertRadius_ * 1.5f) transitionTo(EnemyState::PATROL);
            else chasePlayer(player, dt);
            break;
        case EnemyState::ATTACK:
            if (dist > attackRadius_) transitionTo(EnemyState::CHASE);
            else attack(player, dt);
            break;
        }
    }
};

A* Pathfinding

struct Node {
    Vec2i pos;
    float g = 0;   // cost from start
    float h = 0;   // heuristic to goal
    float f() const { return g + h; }
    Node* parent = nullptr;
};

float heuristic(Vec2i a, Vec2i b) {
    // Manhattan distance (grid movement)
    return std::abs(a.x - b.x) + std::abs(a.y - b.y);
    // Euclidean: return std::sqrt((a.x-b.x)^2 + (a.y-b.y)^2);
}

std::vector<Vec2i> aStar(Grid& grid, Vec2i start, Vec2i goal) {
    auto cmp = [](Node* a, Node* b){ return a->f() > b->f(); };
    std::priority_queue<Node*, std::vector<Node*>, decltype(cmp)> open(cmp);

    std::unordered_map<Vec2i, Node*> allNodes;
    Node* startNode = new Node{start, 0, heuristic(start, goal)};
    open.push(startNode);
    allNodes[start] = startNode;

    std::unordered_set<Vec2i> closed;

    while (!open.empty()) {
        Node* current = open.top(); open.pop();
        if (current->pos == goal) return reconstructPath(current);
        closed.insert(current->pos);

        for (Vec2i neighbor : grid.neighbors(current->pos)) {
            if (closed.count(neighbor) || !grid.walkable(neighbor)) continue;
            float tentativeG = current->g + grid.cost(current->pos, neighbor);
            if (!allNodes.count(neighbor) || tentativeG < allNodes[neighbor]->g) {
                Node* n = new Node{neighbor, tentativeG, heuristic(neighbor, goal), current};
                allNodes[neighbor] = n;
                open.push(n);
            }
        }
    }
    return {};  // no path
}

Influence Maps (Tactical AI)

// Grid where each cell stores influence value (positive = friendly, negative = enemy)
class InfluenceMap {
    std::vector<float> influence_;
    int width_, height_;

public:
    void propagate(float decay = 0.9f, int iterations = 3) {
        for (int iter = 0; iter < iterations; ++iter) {
            auto next = influence_;
            for (int y = 0; y < height_; ++y) {
                for (int x = 0; x < width_; ++x) {
                    float maxVal = influence_[y * width_ + x];
                    for (auto [nx, ny] : neighbors(x, y)) {
                        float v = influence_[ny * width_ + nx] * decay;
                        if (std::abs(v) > std::abs(maxVal)) maxVal = v;
                    }
                    next[y * width_ + x] = maxVal;
                }
            }
            influence_ = next;
        }
    }

    // Tactical decisions based on influence:
    // high positive → safe for allied units
    // high negative → enemy-controlled, avoid or attack
    // near zero → contested, front line
    float getInfluence(int x, int y) const { return influence_[y * width_ + x]; }
};

---

Action-Oriented AI

Steering Behaviors

struct SteeringBehaviors {
    // Seek: move toward target
    Vec3 seek(const Vec3& pos, const Vec3& target, float maxSpeed) {
        Vec3 desired = normalize(target - pos) * maxSpeed;
        return desired;  // steer toward
    }

    // Flee: move away
    Vec3 flee(const Vec3& pos, const Vec3& threat, float maxSpeed, float panicDist) {
        if (distance(pos, threat) > panicDist) return Vec3{0};
        return -seek(pos, threat, maxSpeed);
    }

    // Arrival: slow down as approaching target
    Vec3 arrive(const Vec3& pos, const Vec3& target, float maxSpeed, float slowRadius) {
        Vec3 toTarget = target - pos;
        float dist = length(toTarget);
        float speed = maxSpeed;
        if (dist < slowRadius) speed = maxSpeed * (dist / slowRadius);
        return normalize(toTarget) * speed;
    }

    // Pursuit: predict where target will be
    Vec3 pursue(const Vec3& pos, const Vec3& targetPos, const Vec3& targetVel, float maxSpeed) {
        float lookAhead = distance(pos, targetPos) / maxSpeed;
        Vec3 futurePos = targetPos + targetVel * lookAhead;
        return seek(pos, futurePos, maxSpeed);
    }

    // Obstacle avoidance: probe ahead, steer around
    Vec3 avoidObstacle(const Vec3& pos, const Vec3& vel, const std::vector<Obstacle>& obstacles) {
        float aheadDist = length(vel) * 1.5f;
        Vec3 ahead = pos + normalize(vel) * aheadDist;
        for (auto& obs : obstacles) {
            if (distance(ahead, obs.center) < obs.radius) {
                return normalize(ahead - obs.center) * 100.f;  // push away
            }
        }
        return Vec3{0};
    }
};

---

3D Graphics Pipeline

Transformation Pipeline

Object Space → World Space → View Space → Clip Space → NDC → Screen Space

Model matrix (M): position, rotation, scale of object
View matrix (V): camera transform (inverse of camera model matrix)
Projection matrix (P): perspective or orthographic

MVP = P * V * M
clip_pos = MVP * object_pos

Perspective division: NDC = clip_pos.xyz / clip_pos.w
Viewport transform: screen_pos = NDC * (width/2, height/2) + (width/2, height/2)

Perspective Projection Matrix

glm::mat4 perspective(float fovY_deg, float aspect, float near, float far) {
    float f = 1.0f / std::tan(glm::radians(fovY_deg) / 2.0f);
    glm::mat4 result{0};
    result[0][0] = f / aspect;
    result[1][1] = f;
    result[2][2] = (far + near) / (near - far);
    result[2][3] = -1.0f;
    result[3][2] = (2.0f * far * near) / (near - far);
    return result;
}

Quaternions for Rotation

// Quaternion: avoids gimbal lock, interpolates smoothly
struct Quaternion {
    float w, x, y, z;

    static Quaternion fromAxisAngle(Vec3 axis, float angle) {
        float half = angle / 2.0f;
        float s = std::sin(half);
        return {std::cos(half), axis.x * s, axis.y * s, axis.z * s};
    }

    Quaternion operator*(const Quaternion& b) const {
        return {
            w*b.w - x*b.x - y*b.y - z*b.z,
            w*b.x + x*b.w + y*b.z - z*b.y,
            w*b.y - x*b.z + y*b.w + z*b.x,
            w*b.z + x*b.y - y*b.x + z*b.w
        };
    }

    // SLERP: smooth quaternion interpolation
    static Quaternion slerp(Quaternion a, Quaternion b, float t) {
        float cosTheta = a.w*b.w + a.x*b.x + a.y*b.y + a.z*b.z;
        if (cosTheta < 0) { b = {-b.w,-b.x,-b.y,-b.z}; cosTheta = -cosTheta; }
        if (cosTheta > 0.9999f) {
            // Linear interpolation for very close quaternions
            return normalize(Quaternion{
                a.w + t*(b.w-a.w), a.x + t*(b.x-a.x),
                a.y + t*(b.y-a.y), a.z + t*(b.z-a.z)});
        }
        float theta = std::acos(cosTheta);
        float sinTheta = std::sin(theta);
        return {(std::sin((1-t)*theta)/sinTheta) * a.w + (std::sin(t*theta)/sinTheta) * b.w,
                /* similar for x, y, z */ };
    }
};

---

Rendering Algorithms

BSP Tree (Binary Space Partition)

struct BSPNode {
    Plane splitPlane;
    std::vector<Polygon> polygons;
    std::unique_ptr<BSPNode> front, back;
};

// Build BSP tree (preprocessed offline)
std::unique_ptr<BSPNode> buildBSP(std::vector<Polygon> polygons) {
    if (polygons.empty()) return nullptr;
    auto node = std::make_unique<BSPNode>();
    node->splitPlane = pickBestSplitPlane(polygons);  // minimize splits

    std::vector<Polygon> front, back;
    for (auto& poly : polygons) {
        switch (classifyPolygon(poly, node->splitPlane)) {
        case FRONT: front.push_back(poly); break;
        case BACK:  back.push_back(poly);  break;
        case COPLANAR: node->polygons.push_back(poly); break;
        case SPANNING:
            auto [f, b] = splitPolygon(poly, node->splitPlane);
            front.push_back(f); back.push_back(b);
            break;
        }
    }
    node->front = buildBSP(std::move(front));
    node->back  = buildBSP(std::move(back));
    return node;
}

// Render back-to-front from camera position (painter's algorithm)
void renderBSP(const BSPNode* node, const Camera& cam) {
    if (!node) return;
    bool inFront = node->splitPlane.sideOf(cam.position()) == FRONT;
    renderBSP(inFront ? node->back.get() : node->front.get(), cam);
    renderPolygons(node->polygons);
    renderBSP(inFront ? node->front.get() : node->back.get(), cam);
}

Level of Detail (LOD) for Terrain

// Geomipmapping: terrain divided into patches, each with multiple LOD meshes
class TerrainPatch {
    float* heightData_;
    int size_;
    std::array<Mesh, 4> lodMeshes_;  // LOD 0 = highest detail

public:
    int computeLOD(const Camera& cam) const {
        float dist = distance(cam.position(), center());
        if (dist < 100) return 0;
        if (dist < 300) return 1;
        if (dist < 600) return 2;
        return 3;
    }

    void render(const Camera& cam) {
        int lod = computeLOD(cam);
        // Fix LOD cracks at patch boundaries
        int neighborLOD = getNeighborMinLOD();
        lod = std::max(lod, neighborLOD);
        lodMeshes_[lod].render();
    }
};

---

Character Animation

Skeletal Animation

struct Bone {
    std::string name;
    int parentIndex;          // -1 for root
    glm::mat4 bindPose;       // rest pose in local space
    glm::mat4 invBindPose;    // precomputed inverse
};

struct AnimationClip {
    float duration;
    float ticksPerSecond;
    std::vector<BoneChannel> channels;  // per-bone keyframes
};

struct BoneChannel {
    std::vector<KeyPosition>   posKeys;   // time, Vec3
    std::vector<KeyRotation>   rotKeys;   // time, Quaternion
    std::vector<KeyScale>      scaleKeys; // time, Vec3
};

// Compute final bone matrices for a given time
std::vector<glm::mat4> computeBoneMatrices(const AnimationClip& clip,
                                            const Skeleton& skeleton, float time) {
    int numBones = skeleton.bones.size();
    std::vector<glm::mat4> globalTransforms(numBones);

    for (int i = 0; i < numBones; ++i) {
        auto& channel = clip.channels[i];
        // Interpolate position, rotation, scale at 'time'
        glm::vec3 pos = interpolate(channel.posKeys, time);
        glm::quat rot = slerp(channel.rotKeys, time);
        glm::vec3 scale = interpolate(channel.scaleKeys, time);

        glm::mat4 localTransform = TRS(pos, rot, scale);

        // Accumulate from root to leaf
        int parent = skeleton.bones[i].parentIndex;
        if (parent == -1)
            globalTransforms[i] = localTransform;
        else
            globalTransforms[i] = globalTransforms[parent] * localTransform;
    }

    // Final skinning matrix = globalTransform * invBindPose
    std::vector<glm::mat4> skinMatrices(numBones);
    for (int i = 0; i < numBones; ++i)
        skinMatrices[i] = globalTransforms[i] * skeleton.bones[i].invBindPose;

    return skinMatrices;
}

Inverse Kinematics (CCD)

// Cyclic Coordinate Descent IK — iterative, converges quickly
void solveCCD(std::vector<Bone*>& chain, const Vec3& target, int maxIter = 10) {
    Vec3 endEffector = chain.back()->worldPosition();

    for (int iter = 0; iter < maxIter; ++iter) {
        if (distance(endEffector, target) < 0.01f) break;

        // Rotate each bone from end to root
        for (int i = chain.size() - 2; i >= 0; --i) {
            Vec3 toEnd    = normalize(endEffector - chain[i]->worldPosition());
            Vec3 toTarget = normalize(target     - chain[i]->worldPosition());
            float angle = acos(dot(toEnd, toTarget));
            Vec3 axis   = cross(toEnd, toTarget);

            if (length(axis) > 0.0001f && angle > 0.001f) {
                chain[i]->rotateLocal(axis, angle);
                // Update child positions after rotation
                for (int j = i + 1; j < chain.size(); ++j)
                    chain[j]->updateWorldTransform();
            }
            endEffector = chain.back()->worldPosition();
        }
    }
}

---

Camera Systems

First-Person Camera

class FPSCamera {
    Vec3 position_;
    float yaw_ = 0;    // horizontal rotation
    float pitch_ = 0;  // vertical rotation (clamp to ±89°)

public:
    void handleMouse(float dx, float dy, float sensitivity = 0.1f) {
        yaw_   += dx * sensitivity;
        pitch_ -= dy * sensitivity;  // invert Y
        pitch_  = std::clamp(pitch_, -89.0f, 89.0f);
    }

    glm::mat4 getViewMatrix() const {
        Vec3 front{
            std::cos(glm::radians(yaw_)) * std::cos(glm::radians(pitch_)),
            std::sin(glm::radians(pitch_)),
            std::sin(glm::radians(yaw_)) * std::cos(glm::radians(pitch_))
        };
        return glm::lookAt(position_, position_ + normalize(front), Vec3{0,1,0});
    }

    void move(Vec3 direction, float speed) {
        position_ += direction * speed;
        // Apply inertia: lerp toward target velocity for smoother feel
    }
};

Third-Person Camera (Spring Arm)

class ThirdPersonCamera {
    Vec3 target_;          // follow target (player)
    float distance_ = 5.f; // spring arm length
    float yaw_, pitch_;
    Vec3 currentPos_;      // actual camera position (smoothed)

public:
    void update(const Vec3& targetPos, float dt) {
        target_ = targetPos;
        // Desired camera position behind and above target
        Vec3 offset{
            distance_ * cos(pitch_) * cos(yaw_),
            distance_ * sin(pitch_),
            distance_ * cos(pitch_) * sin(yaw_)
        };
        Vec3 desiredPos = target_ + offset;

        // Lag: smooth camera follows with spring
        currentPos_ = lerp(currentPos_, desiredPos, dt * 10.f);

        // Collision: shorten spring arm if blocked
        if (raycast(target_, currentPos_).hit) {
            currentPos_ = raycast(target_, currentPos_).hitPoint;
        }
    }

    glm::mat4 getViewMatrix() const {
        return glm::lookAt(currentPos_, target_, Vec3{0,1,0});
    }
};

---

Particle Systems

Particle Data Structure

struct Particle {
    Vec3 position;
    Vec3 velocity;
    Vec3 acceleration;
    float life;          // remaining lifetime in seconds
    float maxLife;
    float size;
    float sizeGrowth;    // change per second
    Color color;
    Color colorEnd;
    float rotation;
    float rotationSpeed;
};

class ParticleSystem {
    std::vector<Particle> particles_;
    Vec3 emitPos_;
    int maxParticles_;
    float emitRate_;     // particles per second
    float emitAccum_ = 0;

public:
    void update(float dt) {
        // Emit new particles
        emitAccum_ += emitRate_ * dt;
        while (emitAccum_ >= 1 && particles_.size() < maxParticles_) {
            emitAccum_ -= 1;
            particles_.push_back(spawnParticle());
        }

        // Update existing particles
        for (auto& p : particles_) {
            p.velocity += p.acceleration * dt;
            p.position += p.velocity * dt;
            p.size     += p.sizeGrowth * dt;
            p.color     = lerp(p.color, p.colorEnd, 1 - p.life/p.maxLife);
            p.rotation += p.rotationSpeed * dt;
            p.life     -= dt;
        }

        // Remove dead particles
        particles_.erase(
            std::remove_if(particles_.begin(), particles_.end(),
                           [](const Particle& p){ return p.life <= 0; }),
            particles_.end());
    }
};

---

Multiplayer Networking

Client-Server Architecture

Authoritative server:
  - Server runs simulation, clients send inputs
  - Server broadcasts authoritative state
  - Client prediction: simulate locally, reconcile with server state

Lockstep (RTS/turn-based):
  - All clients receive inputs, simulate identically
  - Deterministic simulation required
  - Higher latency but simpler consistency

Network Message Protocol

// Simple UDP game protocol with sequence numbers
struct GamePacket {
    uint16_t sequence;     // for ordering and drop detection
    uint16_t ack;          // last received sequence from remote
    uint32_t ackBits;      // bitmask of last 32 received sequences
    PacketType type;
    union {
        InputData input;
        WorldState state;
    };
};

// Interpolation buffer: delay rendering to smooth out jitter
class InterpolationBuffer {
    struct StateSnapshot {
        float serverTime;
        EntityState state;
    };
    std::deque<StateSnapshot> buffer_;
    float renderDelay_ = 0.1f;  // 100ms behind server

public:
    EntityState getState(float currentTime) {
        float renderTime = currentTime - renderDelay_;
        // Find two snapshots bracketing renderTime and interpolate
        for (int i = 0; i < buffer_.size() - 1; ++i) {
            if (buffer_[i].serverTime <= renderTime &&
                buffer_[i+1].serverTime >= renderTime) {
                float t = (renderTime - buffer_[i].serverTime) /
                          (buffer_[i+1].serverTime - buffer_[i].serverTime);
                return lerp(buffer_[i].state, buffer_[i+1].state, t);
            }
        }
        return buffer_.back().state;
    }
};