Game Engine, Gameplay, and Physics Programming Questions

Approach (brief)
Use a compact binary serialization for each ICommand, store commands keyed by tick in an InputHistory buffer, and provide deterministic Execute/Undo. On rollback, restore last confirmed state, replay commands from that tick.

Interfaces & core classes

// ICommand: deterministic execute/undo and compact serialize
public interface ICommand {
    int CommandId { get; } // small discriminator
    void Execute(int tick, GameState state);
    void Undo(int tick, GameState state);
    byte[] Serialize();            // compact binary
    void Deserialize(ReadOnlySpan<byte> data);
}

// Fixed-size ring buffer keyed by tick
public class InputHistory {
    private readonly Dictionary<int, List<ICommand>> _map = new();
    public void Add(int tick, ICommand cmd){
        if(!_map.TryGetValue(tick, out var list)){ list = new(); _map[tick]=list; }
        list.Add(cmd);
    }
    public IEnumerable<ICommand> GetRange(int fromTick, int toTick){
        for(int t=fromTick;t<=toTick;t++)
            if(_map.TryGetValue(t,out var l)) foreach(var c in l) yield return c;
    }
    public void TruncateBefore(int tick){
        var keys = _map.Keys.Where(k=>k<tick).ToList();
        foreach(var k in keys) _map.Remove(k);
    }
}

Example GameState (deterministic)

public class GameState {
    public Dictionary<int, Vector2> Positions = new();
    public List<Projectile> Projectiles = new();
    // Clone for rollback: implement efficient snapshot (diffs or full copy)
    public GameState Clone(){ /* deep copy deterministic */ return new(); }
}

MoveCommand example

public class MoveCommand : ICommand {
    public int CommandId => 1;
    public int EntityId;
    public short Dx, Dy; // compact
    public void Execute(int tick, GameState s){
        var p = s.Positions[EntityId];
        p += new Vector2(Dx, Dy);
        s.Positions[EntityId] = p;
    }
    public void Undo(int tick, GameState s){
        var p = s.Positions[EntityId];
        p -= new Vector2(Dx, Dy);
        s.Positions[EntityId] = p;
    }
    public byte[] Serialize(){
        Span<byte> b = stackalloc byte[1+4+2+2];
        b[0] = (byte)CommandId;
        BitConverter.TryWriteBytes(b.Slice(1,4), EntityId);
        BitConverter.TryWriteBytes(b.Slice(5,2), Dx);
        BitConverter.TryWriteBytes(b.Slice(7,2), Dy);
        return b.ToArray();
    }
    public void Deserialize(ReadOnlySpan<byte> d){
        EntityId = BitConverter.ToInt32(d.Slice(1,4));
        Dx = BitConverter.ToInt16(d.Slice(5,2));
        Dy = BitConverter.ToInt16(d.Slice(7,2));
    }
}

FireCommand example

public class FireCommand : ICommand {
    public int CommandId => 2;
    public int ShooterId;
    public ushort WeaponSeed; // deterministic RNG seed fragment
    public void Execute(int tick, GameState s){
        var pos = s.Positions[ShooterId];
        s.Projectiles.Add(new Projectile{ Id = GenerateId(ShooterId, tick, WeaponSeed), Position = pos });
    }
    public void Undo(int tick, GameState s){
        // remove last projectile matching generated id
        s.Projectiles.RemoveAll(p=>p.Id == GenerateId(ShooterId,tick,WeaponSeed));
    }
    public byte[] Serialize(){ /* similar compact layout */ return new byte[7]; }
    public void Deserialize(ReadOnlySpan<byte> d){ /* populate fields */ }
    private int GenerateId(int id,int tick,ushort seed) => (id<<16) ^ tick ^ seed;
}

Integration with rollback

• Each simulation frame: collect local inputs -> serialize -> send/receive over network -> store ICommand instances in InputHistory keyed by tick.
• On confirmed authoritative state mismatch (prediction error): restore saved GameState snapshot at authoritative tick, then iterate InputHistory.GetRange(tick+1, currentTick) and call Execute for each command in tick order to replay.
• Use deterministic RNG seeds (stored in commands) and avoid non-deterministic APIs. Use compact binary layouts to minimize bandwidth and validate deserialization by CommandId.

Notes / Best practices

• Keep commands small (use fixed-size fields), use pools to avoid allocations.
• Prefer diffs or incremental snapshots for efficient rollback.
• Validate checksums of serialized command streams to detect corruption.

Approach (brief)
Provide a small C# API for a GameObject's health with ApplyDamage, Heal, Die, invulnerability frames (i-frames), events for UI and other systems, and safeguards against negative health and duplicate damage from overlapping collisions. Show how death propagates via events.

Code (C# pseudocode)

using System;
using System.Collections;

public class HealthComponent
{
    public int MaxHealth { get; private set; }
    public int CurrentHealth { get; private set; }
    public bool IsAlive => CurrentHealth > 0;
    public bool IsInvulnerable { get; private set; }

    public event Action<int,int> OnHealthChanged; // (current, max)
    public event Action OnDamaged;
    public event Action OnHealed;
    public event Action OnDied; // other systems subscribe (UI, audio, respawn, scoreboard)

    private float invulnEndTime = 0f;
    private readonly float invulnDuration;
    private readonly HashSet<object> recentDamageSources = new HashSet<object>();

    public HealthComponent(int maxHealth, float invulnSeconds = 0.5f)
    {
        MaxHealth = Math.Max(1, maxHealth);
        CurrentHealth = MaxHealth;
        invulnDuration = Math.Max(0f, invulnSeconds);
    }

    public void UpdateTime(float timeNow)
    {
        if (timeNow >= invulnEndTime) { IsInvulnerable = false; recentDamageSources.Clear(); }
    }

    // source: optional unique identifier for collision source to prevent double-apply
    public void ApplyDamage(int amount, object source = null, float timeNow = 0f)
    {
        if (amount <= 0 || !IsAlive) return;
        UpdateTime(timeNow);

        if (IsInvulnerable) return;
        if (source != null && recentDamageSources.Contains(source)) return; // prevent duplicate

        CurrentHealth = Math.Max(0, CurrentHealth - amount);
        OnDamaged?.Invoke();
        OnHealthChanged?.Invoke(CurrentHealth, MaxHealth);

        if (source != null) recentDamageSources.Add(source);
        if (invulnDuration > 0f) { IsInvulnerable = true; invulnEndTime = timeNow + invulnDuration; }

        if (CurrentHealth == 0) Die();
    }

    public void Heal(int amount)
    {
        if (amount <= 0 || !IsAlive) return;
        CurrentHealth = Math.Min(MaxHealth, CurrentHealth + amount);
        OnHealed?.Invoke();
        OnHealthChanged?.Invoke(CurrentHealth, MaxHealth);
    }

    private void Die()
    {
        if (!IsAlive) // guard: ensure single die call
        {
            // already dead
            return;
        }
        CurrentHealth = 0;
        OnDied?.Invoke(); // propagate to game manager, spawner, audio, UI
        OnHealthChanged?.Invoke(CurrentHealth, MaxHealth);
    }
}

Key concepts & reasoning

• Events let UI, audio, scoring, and respawn systems subscribe; OnDied propagates death across systems.
• I-frames implemented with a timer and source tracking to avoid overlapping-collision double-damage.
• Safeguards: clamp health between 0 and MaxHealth; ignore non-positive amounts; idempotent Die.
• recentDamageSources prevents duplicate hits from same collision; cleared after invuln ends.

Usage notes

• In Unity, call UpdateTime(Time.time) each frame. Use unique collision IDs (Collider instance or attack ID) as source.
• Subscribers: UI binds to OnHealthChanged, enemy AI or game manager listens to OnDied to award XP or trigger respawn.

Brief comparison (practical)

• Dijkstra = A* with heuristic h(x)=0. It guarantees shortest path but explores uniformly outward from start; good for single-source full-map costs or when no heuristic is available.
• A* uses h to focus search toward goal, usually far fewer node expansions on grids. In games A* is the go-to for point-to-point pathfinding.

When to choose which

• Use A* for typical NPC pathfinding between two points (fast, minimal expansions).
• Use Dijkstra when you need distances to many targets from one source, or when admissible heuristic is unavailable or unreliable (e.g., highly dynamic/non-Euclidean cost fields).

Heuristic admissibility

• Admissible = never overestimates true cost (e.g., Manhattan for 4-neighbor orthogonal grids, Octile for 8-neighbor). Keeps A* optimal.
• If you use an inadmissible heuristic (overestimate) you can gain speed but lose optimality. Weighted A* (f = g + w*h, w>1) trades optimality for runtime — useful for realtime responsiveness when slight suboptimality is acceptable.

Memory and runtime trade-offs for real-time updates

• A*/Dijkstra store open/closed sets; worst-case memory is O(#nodes). On large maps use:
  • Hierarchical approaches (HPA*) to reduce graph size.
  • Anytime Repairing A* (ARA*) or Weighted A* for fast initial paths, refine later.
  • Incremental planners (D* Lite) for maps that change often — they reuse previous search work and are much faster than re-running A*/Dijkstra from scratch.
• Profiling: A* with a good heuristic reduces runtime and memory by cutting node expansions.

Tie-breaking effects

• When multiple nodes have equal f = g + h, tie-breaking changes behavior:
  • Prefer larger g (i.e., prefer node with greater g when f ties) tends to favor nodes closer to the goal direction, reduces re-opening and expansions, often faster and produces straighter, more goal-directed paths.
  • Prefer smaller g explores shallower nodes first, can produce more uniformly optimal search but may expand more nodes.
• In practice: tie-break toward larger g for better performance and nicer-looking paths in games; combine with smoothing (post-process) for visual quality.

Quick recommendations for game devs

• Default: A* with an admissible grid-aware heuristic (Manhattan/Octile).
• For large/dynamic worlds: HPA* + local replanning, or D* Lite for frequently changing obstacles.
• For strict frame budgets: Weighted A*/ARA* for quick path then refine off-frame.
• Tie-break by larger g and apply path smoothing to improve visual quality while keeping performance.

Approach
Use a 64-bit integer fixed-point (Q32.32) for sufficient range/precision. Implement basic arithmetic, helpers for constants, and a semi-implicit (symplectic) integrator: velocity += acceleration * dt; position += velocity * dt. All operations avoid floating-point for deterministic lockstep.

// FixedPoint Q32.32
#include <cstdint>

using i64 = int64_t;
constexpr int FRAC = 32;
constexpr i64 ONE = (i64)1 << FRAC;

struct Fixed {
    i64 v; // stored as Q32.32
    explicit Fixed(i64 raw=0): v(raw) {}
    static Fixed fromInt(int32_t x){ return Fixed((i64)x << FRAC); }
    static Fixed fromRaw(i64 raw){ return Fixed(raw); }
    i64 raw() const { return v; }
};

// basic ops
inline Fixed operator+(Fixed a, Fixed b){ return Fixed::fromRaw(a.v + b.v); }
inline Fixed operator-(Fixed a, Fixed b){ return Fixed::fromRaw(a.v - b.v); }
// multiply: (a.v * b.v) >> FRAC
inline Fixed operator*(Fixed a, Fixed b){ return Fixed::fromRaw((__int128)a.v * b.v >> FRAC); }
// divide: (a.v << FRAC) / b.v
inline Fixed operator/(Fixed a, Fixed b){ return Fixed::fromRaw(((__int128)a.v << FRAC) / b.v); }

// helpers
inline Fixed mulInt(Fixed a, int32_t n){ return Fixed::fromRaw(a.v * n); }
inline Fixed dtTicks(int64_t ticks, int64_t ticksPerSecond){ return Fixed::fromRaw((ticks << FRAC) / ticksPerSecond); }

// 2D vector with Fixed
struct Vec2 { Fixed x,y; };
void integrateSemiImplicit(Vec2 &pos, Vec2 &vel, Vec2 const &acc, Fixed dt){
    // vel = vel + acc * dt
    vel.x = vel.x + (acc.x * dt);
    vel.y = vel.y + (acc.y * dt);
    // pos = pos + vel * dt
    pos.x = pos.x + (vel.x * dt);
    pos.y = pos.y + (vel.y * dt);
}

Explanation & Notes

• Q32.32 gives ~32 bits integer range and 32 bits fractional precision — adjust FRAC for needs.
• Use __int128 for intermediate multiply/divide to avoid overflow.
• dt should be a Fixed representing timestep (e.g., dt = Fixed::fromRaw(ONE/60) for 1/60s).
• Semi-implicit integration is more stable for physics and conserves energy better than explicit Euler.
• Edge cases: clamp velocities/positions to avoid overflow, handle zero division, ensure identical integer math across platforms (same endianness/width assumptions). Alternative: Q16.48 for more fractional precision or use deterministic decimal libraries.

Answer (overview)
AoS: struct Entity { float x,y,z; float vx,vy,vz; int health; } entities[N];
SoA: separate arrays float X[N], Y[N], Z[N], VX[N], ... int Health[N];

Cache performance & memory access patterns

• AoS: good when you always need all fields for an entity (single-entity work). But when iterating just positions, each cache line pulls unused velocity/health bytes, wasting bandwidth and reducing effective cache capacity.
• SoA: tight, contiguous arrays per component. Scanning positions touches sequential memory, maximizing spatial locality and prefetching; more cache lines hold more usable elements of the needed field.

Vectorization potential

• SoA enables straightforward SIMD: load 4/8 floats from X[] and operate with one vector instruction. AoS interleaves fields, requiring shuffles/gathers or non-contiguous loads that hurt throughput.
• Modern compilers auto-vectorize tight SoA loops; AoS often prevents auto-vectorization or forces costly gather.

Concrete example & measurable speedup

• Scenario: update positions with velocities for 1M entities (simple physics step) on x86 AVX2.
• AoS loop reads 1M structs (24 bytes float pos+vel + 4 bytes health ≈ 28 bytes padded → 32). So each position update loads 32 bytes per entity.
• SoA loop reads 2 contiguous arrays of floats: X[i] and VX[i] — both cache-friendly; using AVX2 you can process 8 entities per iteration.

Example C++ (conceptual):

// AoS
for (int i=0;i<N;i++) { E[i].x += dt * E[i].vx; E[i].y += dt * E[i].vy; E[i].z += dt * E[i].vz; }

// SoA
for (int i=0;i<N;i++) { X[i] += dt * VX[i]; Y[i] += dt * VY[i]; Z[i] += dt * VZ[i]; }

On benchmarks, SoA often gives 2–6x speedup for such streaming SIMD workloads due to reduced memory traffic and full SIMD utilization. In games this reduces CPU time for physics/animation loops and improves frame stability.

When to choose which

• Use SoA for bulk numeric updates, SIMD-heavy systems (physics, particle systems). Use AoS when logic operates per-entity with many fields and random access, or when code simplicity/serialization matters.

Trade-offs

• SoA can complicate code and cache locality if you need all fields together; hybrid (AoSoA) can balance both.