Game Programming Fundamentals Questions

Key differences — quick:

• Keyframe interpolation: Animation defined by discrete keyframes (time + value). At runtime you compute an interpolant t between surrounding keyframes and interpolate (linear, cubic, slerp for rotations). Sampling is time-driven: values depend on elapsed animation time.
• Frame-based playback: Each frame stores a full pose; playback steps to the next stored frame per render tick. Tightly coupled to frame rate; looks choppy or speed-changed if FR changes.

Why time-based sampling:
Ensures correct animation speed and smoothness regardless of variable frame rates, pauses, or resume. You sample animation by absolute/accumulated time, not by “next frame index.”

Implementation (concept + C# example):

• Maintain animationTime (float), playbackSpeed, playing flag.
• Each update: if playing, animationTime += deltaTime * playbackSpeed. Use engine delta (Time.deltaTime) or high-resolution timer. Cap large delta to avoid jumps (maxDelta).
• Find surrounding keyframes k0,k1, compute local t = (animationTime - k0.time)/(k1.time - k0.time), then interpolate.

// C# Unity-style example
float animTime = 0f;
float playbackSpeed = 1f;
bool playing = true;
const float maxDelta = 0.1f;

void Update() {
  if (!playing) return;
  float dt = Mathf.Min(Time.deltaTime, maxDelta);
  animTime += dt * playbackSpeed;
  SampleAnimation(animTime);
}

Notes & edge cases:

• Handle looping/clamping, negative playbackSpeed (reverse), seeking by setting animTime directly.
• For rotations use slerp/quaternion interpolation to avoid artifacts.
• For paused/resume, stop advancing animTime; when resuming continue from same animTime.
• For deterministic physics or networked playback, use fixed-step simulation with interpolation between physics ticks.

Summary of trade-offs

Value types (C# structs) store data inline; reference types (classes) live on the heap with a pointer. That difference drives copying cost, memory layout, GC behavior, and alignment—critical in hot loops and large arrays for games.

Memory layout & caching

• Struct arrays are contiguous: good cache locality for physics/renderer data (positions, velocities).
• Class arrays hold contiguous references but scattered objects -> poor locality and more cache misses.

Copying costs

• Small, immutable structs (<=16 bytes) are cheap to copy; large structs incur heavy stack/stack-frame or memcpy overhead when passed by value.
• Classes pass a pointer cheaply; mutation without copying.

Garbage collection

• Lots of short-lived class instances increase GC pressure and frame spikes. Structs avoid GC if stored in arrays or on the stack.
• Beware boxing: storing a struct in object or IEnumerable<T> causes heap allocation and boxing cost.

Alignment & padding

• Struct field ordering affects alignment and size; pack frequently accessed fields together to reduce padding.
• Use explicit layout or reorder fields to minimize size.

Recommendations for games

• Use small POD structs for arrays of components (positions, normals, transforms) for physics/rendering.
• For mutable large state, prefer classes or store big data in arrays and use indices to avoid copying.
• Mark structs readonly when immutable; pass by ref/in to avoid copies.
• Avoid virtual methods on hot structs; avoid boxing (use generics where possible).
• Profile: measure cache misses, GC allocations, and memcpy costs. Optimize based on hotspots.

Example patterns: Native arrays / Unsafe/Span or Unity’s ECS/NativeArray for predictable layout and minimal GC.

API surface (C#-style)

• public struct DetRng {
  public void Seed(ulong seed);
  public int NextInt(int minInclusive, int maxExclusive);
  public uint NextUInt();
  public float NextFloat();
  public byte[] GetState();
  public void SetState(byte[] state);
  }

Approach & reasoning

• I’d use xorshift128+ or PCG64 for speed, quality, small state (128 bits / 256 bits), deterministic across platforms if implemented in integer ops.
• API is minimal so each simulation/thread holds its own DetRng instance; no global state to avoid races.

Internal state layout

• Example (xorshift128+): two 64-bit words: state0, state1 (16 bytes total).
• Layout for GetState: little-endian concatenation: [ state0 (8 bytes) | state1 (8 bytes) ].

Serialization for sync/replay

• GetState returns fixed-size byte[] (16 bytes). Compact, constant-size, easy to send over network or write to replay file.
• On restore, SetState copies bytes into state words.
• For cross-language/network: use uint64 little-endian, include version byte if algorithm changes: [ version (1) | state... ].

Implementation sketch

// xorshift128+ nextUInt
uint NextUInt() {
  ulong s1 = state0;
  ulong s0 = state1;
  state0 = s0;
  s1 ^= s1 << 23;
  s1 ^= s1 >> 17;
  s1 ^= s0;
  s1 ^= s0 >> 26;
  state1 = s1;
  ulong result = state0 + state1;
  return (uint)(result & 0xFFFFFFFF);
}

Edge cases & notes

• Ensure non-zero seed state; provide Seed(seed) -> expand with SplitMix64 to populate state.
• Determinism: avoid floats produced by platform-specific libs; derive floats from integers (e.g., (uint>>9) / 2^23).
• Performance: inlined methods, no allocations in Next*; GetState allocates—offer Span overload to write into caller buffer for GC-free sync.

Overview (approach)
I’d build a deterministic two-pass resolver: first enforce dependency/feasibility with a dependency graph and topological-like ordering; second apply actions by priority and deterministic tie-breaks, handling cancels/conflicts as they are applied.

Data structures

• Action struct: { actorID, targets, priority, deps: Set[actionID], cancels: Set[actionID], timestamp, nonce }
• Graph G(V,E) where edge a->b means b depends on a.
• Priority buckets: map priority -> list, each list is sorted deterministically by (timestamp, actorID, nonce).
• Result list appliedActions and state snapshot for simulating effects.

Algorithm

1. Build G and compute in-degrees. Reject missing deps as failed.
2. Detect SCCs (Tarjan). For acyclic SCCs do a standard topological availability queue. For SCCs:
   • If mutual requirements exist, break deterministically: pick the action with highest priority; if tie, lowest actorID; if still tied, use per-tick seeded deterministic RNG to pick one (seed from tick and game RNG). Mark others failed or postpone per design.
3. While there are available actions:
   • Pull highest priority non-empty bucket; within bucket take next deterministic action.
   • Before applying, check if any active action cancels it or if its targets are invalidated by already-applied actions; if canceled, mark failed and continue.
   • Apply action to a working state snapshot, record in appliedActions, and decrement in-degrees of dependents (enqueue if zero).
4. After processing, return appliedActions and final state. Unapplied actions are returned with failure reasons.

Handling ties & fairness

• Deterministic tie-breaker order: priority -> timestamp -> actorID -> nonce -> per-tick seed. To ensure long-term fairness, maintain actor-specific round-robin offset in seed so repeated ties don’t starve actors.

Cycles & corner cases

• Circular dependencies: detect via SCCs. Options: (a) fail entire SCC; (b) resolve by priority within SCC (recommended); (c) allow conditional atomic group apply if all can succeed—only if effects are commutative and non-conflicting.
• Conflicting cancels: apply cancels immediately when action is applied; cancel precedence: higher priority applied earlier wins. If mutual cancels in same step, use deterministic tie-break.
• Missing targets/dead actors: treat as failure unless action is allowed to proceed (game rule).

Complexity

• Building graph and Tarjan: O(n + m). Processing via priority buckets: O(n log P) worst-case with P distinct priorities or O(n) if buckets array. Overall O(n + m + n log P).

Why this works for games

• Deterministic, replayable per-tick resolution; respects dependencies; predictable tie-breaking good for multiplayer lockstep; configurable SCC policy allows game designers to choose strictness vs permissiveness.

Approach (brief)
Compute the skinned position by blending bone-space transforms (4x4 matrices) weighted by bone weights, then apply to the vertex bind position. Use 4-influence skinning per vertex (common GPU pattern).

GLSL/HLSL pseudocode

// Assume vec3 a_position; ivec4 a_boneIndices; vec4 a_boneWeights;
// uniform mat4 u_BoneMatrices[ MAX_BONES ];

vec4 skinPosition(vec3 bindPos, ivec4 boneIdx, vec4 boneW)
{
    mat4 skinMat = mat4(0.0);
    // Accumulate weighted bone matrices
    skinMat += boneW.x * u_BoneMatrices[ boneIdx.x ];
    skinMat += boneW.y * u_BoneMatrices[ boneIdx.y ];
    skinMat += boneW.z * u_BoneMatrices[ boneIdx.z ];
    skinMat += boneW.w * u_BoneMatrices[ boneIdx.w ];

    // Transform position (use vec4 with w=1)
    return skinMat * vec4(bindPos, 1.0);
}

Key concepts & reasoning

• Blend matrices by weight then transform the position: fewer matrix*vector ops than transforming per-bone and summing.
• Use 4 influences per vertex for performance and cache-friendliness.
• Keep weights normalized (sum ~= 1) to avoid artifacts.

Limitations & mitigations

• Uniform/constant array size limit: many GPUs limit uniform array size (e.g., 256-1024 bones). Mitigations:
  • Use a texture buffer / samplerBuffer or SSBO to store bone matrices and fetch per-index.
  • Use dual-quaternion skinning (better rotation interpolation, less volume loss) stored in buffers.
  • Split into multiple draw calls with bone palette per draw (bind only required bones).
  • Compress matrices (quat + translation) to reduce memory and bandwidth.

Edge cases

• Zero weights, invalid indices — clamp/validate indices and normalize weights in vertex stream or shader.
• Precision: use highp for mobile where available.