跳到主要内容

002 - 游戏客户端笔试001

使用AI辅助复盘，结果不一定对。

看代码​

智能指针和锁​

class TextureManager {
    std::unordered_map<std::string, std::shared_ptr<Texture>> _cache;
    std::mutex _mutex;

public:
    std::shared_ptr<Texture> Load(const std::string& path)
    {
        std::lock_guard<std::mutex> lock(_mutex);
        auto it = _cache.find(path);
        if (it != _cache.end())  return it->second;

        auto tex = std::make_shared<Texture> path;
        _cache[path] = tex;
        return tex;
    }

    void UnloadUnused() {
        std::lock_guard<std::mutex> lock(_mutex);
        for (auto it = _cache.begin(); it != _cache.end();)
        {
            if (it->second.use_count() == 1)  it = _cache.erase(it);
            else ++it;
        }
    }
};

对于上述代码：

  1. 为什么使用std::shared_ptr而不是std::unique_ptr?
    • std::shared_ptr 用于共享所有权，允许多个使用者同时持有对纹理的引用。当最后一个使用者释放指针时，纹理才会被销毁。
    • 使用 std::shared_ptr 可以方便地实现引用计数，通过 use_count() 可以知道有多少地方正在使用这个纹理（这在 UnloadUnused 方法中很重要）。
    • 如果用 std::unique_ptr，则纹理的所有权是唯一的，难以实现多处共享使用同一个纹理的需求，也不容易判断纹理是否还在被使用。
  2. UnloadUnused()方法作用是什么？
    • 这个方法会遍历缓存中的所有纹理，检查每个纹理的引用计数。如果某个纹理的 use_count() == 1，说明只有缓存本身持有这个纹理（没有外部使用者），就会从缓存中移除它。这是一种自动清理机制，可以释放不再被使用的纹理资源，避免内存浪费。
    • 注意：use_count() == 1 而不是 0，因为 _cache 中的 shared_ptr 本身就是第一个引用。
  3. 为何需要std::mutex？
    • 这个类可能被多个线程同时访问（多线程环境下）。
    • Load 和 UnloadUnused 方法都会修改 _cache，需要互斥锁保护以避免数据竞争。
    • 如果没有 mutex，当两个线程同时调用 Load 时，可能会导致缓存数据损坏。
    • std::lock_guard 提供了 RAII 风格的锁管理，确保在作用域结束时自动释放锁。

反思：三个问题回答的意思都差不多正确，但没有AI回答的详细。

多线程​

以下代码存在什么问题，如何修复？

std::vector<int> data;

void ThreadA()
{
    while (true) data.push_back(1);
}

void ThreadB()
{
    while (true)
    {
        if (!data.empty()) data.pop_back();
    }
}

这段代码存在 线程安全问题，因为多个线程（ThreadA 和 ThreadB）同时访问和修改 std::vector<int> data，而 std::vector 本身 不是线程安全 的容器。具体问题如下：

  1. 数据竞争（Data Race）：
    • ThreadA 调用 push_back 修改 data，同时 ThreadB 调用 empty() 和 pop_back()，可能导致 迭代器失效 或 内存损坏。
    • std::vector 的 push_back 和 pop_back 可能触发动态内存分配/释放，多线程并发操作会引发未定义行为（UB）。
  2. 条件竞争（Race Condition）：
    • ThreadB 检查 !data.empty() 后，ThreadA 可能立即修改 data，导致 pop_back() 在空容器上调用（尽管 empty() 检查了，但无锁保护）。

解决方法：

  1. 使用互斥锁(std::mutex):

    std::vector<int> data;
    std::mutex data_mutex; // 保护 data 的互斥锁

    void ThreadA() {
        while (true) {
            std::lock_guard<std::mutex> lock(data_mutex);
            data.push_back(1);
        }
    }

    void ThreadB() {
        while (true) {
            std::lock_guard<std::mutex> lock(data_mutex);
            if (!data.empty()) {
                data.pop_back();
            }
        }
    }

  2. 也能使用信号量（C++20）和条件变量；

  3. 使用线程安全的容器，如tbb::concurrent_vector；

反思：部分正确，有关多线程术语只会口上说说，而没有实践。

多态类与memset​

class Point2D
{
public:
    int x;
    int y;
    virtual ~Point2D();
    virtual int Area();
}

int main()
{
    Point2D pt1;
    memset(&pt1, 0, sizeof(Point2D));
}

以上代码有什么严重问题：

  1. memset 会破坏虚函数表（vtable）

    • Point2D 是一个 多态类（有 virtual 函数），它的对象内部会包含一个 虚函数表指针（vptr），用于动态调用虚函数（如 Area()）。

    • memset(&pt1, 0, sizeof(Point2D)) 会覆盖 vptr，导致后续调用虚函数时 未定义行为（UB），可能程序崩溃。

  2. Area() 没有默认实现

    • Point2D::Area() 是 virtual 但没有实现（纯虚函数应该用 = 0 标记），导致 链接错误（除非在别处定义）。

    • 如果 Area() 是纯虚函数（virtual int Area() = 0;），则 Point2D 是抽象类，不能直接实例化 Point2D pt1。

  3. memset 会覆盖所有成员，包括 x 和 y

    • 虽然 memset 清零 x 和 y 看似无害，但如果 Point2D 有非平凡类型成员（如 std::string），memset 会破坏它们，导致 UB。

反思：仅回答正确第2点，有关memset()和多态类的内存分布仍不熟悉。

内存对齐​

struct Particle
{
    bool isActive;
    float position[3];
    char color[4];
    bool isAnchored;
    float velocity[3];
    Particle* parent;
};

优化以上结构体的内存布局，并写出优化前后结构体分别占用多少内存（64位程序，默认对齐）。

优化前：

struct Particle
{
    bool isActive;       // 1 byte (+3 padding)
    float position[3];   // 12 bytes
    char color[4];       // 4 bytes
    bool isAnchored;     // 1 byte (+3 padding)
    float velocity[3];   // 12 bytes
    Particle* parent;    // 8 bytes
};
// 第1个8字节: bool null null null, float[0]
// 第2个8字节: float[1]           , float[2]
// 第3个8字节: char[0 ~ 3]        , bool null null null
// 第4个8字节: float[0]           , float[1]
// 第5个8字节: float[2]           , null null null null
// 第6个8字节: Particle*

一共48字节。

优化后：

struct Particle
{
    Particle* parent;    // 8 bytes (highest alignment)
    float position[3];   // 12 bytes
    float velocity[3];   // 12 bytes
    char color[4];       // 4 bytes
    bool isActive;       // 1 byte
    bool isAnchored;     // 1 byte (+2 padding)
};
// 第1个8字节: Particle*
// 第2个8字节: float[0]          , float[1]
// 第3个8字节: float[2]          , float[0]
// 第4个8字节: float[1]          , float[2]
// 第5个8字节: char[0 ~ 3]       , bool bool null null

一共40字节。

反思：写对了，需要注意32位和64位下的区别。

基本数据类型的大小和对齐（32位 vs 64位）

类型32 位大小（对齐）64 位大小（对齐）变化原因
bool1 字节（1）1 字节（1）无变化
char1 字节（1）1 字节（1）无变化
short2 字节（2）2 字节（2）无变化
int4 字节（4）4 字节（4）无变化
long4 字节（4）8 字节（8）64 位下 long 通常变长
float4 字节（4）4 字节（4）无变化
double8 字节（4）8 字节（8）64 位对齐更严格
long long8 字节（4）8 字节（8）64 位对齐更严格
指针（void*, T*）4 字节（4）8 字节（8）64 位指针更大

关键变化：

  • 指针 从 4 字节 → 8 字节（影响结构体对齐）。
  • long 和 long long 在 64 位下可能更大（取决于平台，Windows x64 用 LLP64，Linux x64 用 LP64）。
  • double 和 long long 在 32 位下可能只按 4 字节对齐，但在 64 位下按 8 字节对齐。

循环队列​

class CircularQueue
{
    int* _data;       // 存放数据的数组
    int _capacity;    // 最大可存储元素数
    int _head = 0;    // 队头指针
    int _tail = 0;    // 队尾指针
public:
    bool IsEmpty() const { return _head = _tail; }
    bool IsFull() const 
    { 
        return (_tail + 1) % (_capacity + 1) == _head;
    }
};

根据循环队列的判空和判满代码作答：

  1. 为何IsFull 需要 % (_capacity + 1)；

    循环队列的判满逻辑需要 牺牲一个存储槽位 来区分“空”和“满”的状态。如果数组大小正好是 _capacity，那么 _tail + 1 == _head 会和 _head == _tail 冲突。

    此外，还能绕开对0取模的问题。

  2. 若队列容量为8，画出_head = 2, _tail = 0时的内存状态，并指明可用槽位数；

    Index:   0 1 2 3 4 5 6 7 8
    Status:  * _ X * * * * * *
    Pointer: T   H

    其中, *为有数据, _为无数据, X为不能装数据, 判满用
         T为tail, H为head

    如果可用槽位指的是有效数据，那么为7；如果可用槽位指的是还能添加多少个数据，那么为1。

反思：完全回答错了，唉。虽然容量为0的边界情况可能也算对一点吧。

均匀随机采样​

在三角形内均匀随机采样：

Point RandomInTriangle(Point A, Point B, Point C)
{
    float u = rand(), v = rand();
    if (u + v > 1) { u = 1 - u; v = 1 - v; }
    return {
        A.x * (1 - u - v) + B.x * u + C.x * v,
        A.y * (1 - u - v) + B.y * u + C.y * v
    };
}

  1. 解释为何需要u + v > 1的条件。

    该算法使用 重心坐标（Barycentric Coordinates） 在三角形内均匀采样。u 和 v 是两个随机变量，范围在 [0, 1]，但直接使用 (u, v) 会导致采样在 平行四边形 上不均匀分布，而非三角形。

    直观解释​

    • 设 u, v ∈ [0, 1]，则 (u, v) 覆盖的单位正方形可以映射到由 A, B, C 定义的平行四边形：
      • P = A + u·(B - A) + v·(C - A)。
    • 但三角形仅占该平行四边形的一半面积（u + v ≤ 1 的部分）。
    • 如果 u + v > 1，则 P 会落在 互补三角形（A'B'C'，即 A + (B - A) + (C - A) = B + C - A 定义的区域）中。

    修正方法​

    • 当 u + v > 1 时，将 (u, v) 对称映射回三角形内：

      cpp

      复制

      if (u + v > 1) { u = 1 - u; v = 1 - v; }

      这样，所有 (u, v) 都会落在 u + v ≤ 1 的三角形区域内，保证均匀采样。

  2. 证明采样均匀性。

    我们需要证明该算法在三角形 ABC 上的采样概率密度是 均匀分布（即面积均匀）。

    步骤 1：参数空间分析​

    • 设 u, v 是独立均匀分布在 [0, 1] 的随机变量。
    • 在 (u, v) 平面上，u + v ≤ 1 的区域是一个 下三角，面积 = 0.5。
    • u + v > 1 的区域也是一个面积 = 0.5 的 上三角。

    步骤 2：映射后的分布​

    • 当 u + v > 1 时，执行 u' = 1 - u, v' = 1 - v，此时 u' + v' = 2 - (u + v) < 1。
    • 因此，所有 (u, v) 都被映射到 u + v ≤ 1 的区域，且 概率密度均匀：
      • 原 (u, v) 在 [0,1]×[0,1] 的联合概率密度 f(u, v) = 1。
      • 映射后，(u', v') 在 u' + v' ≤ 1 的区域仍保持均匀分布，因为对称变换不改变概率密度。

    步骤 3：重心坐标的线性变换​

    • 返回的点 P 由重心坐标计算：

      P = A * (1 - u - v) + B * u + C * v

      这是一个 线性变换，保持均匀性：

      • 在 (u, v) 均匀分布时，P 在三角形 ABC 上的分布也是均匀的。

反思：也差不多完全回答错误，竟然没想到这是重心坐标，并且证明过程也不严谨。唉。

设计题​

玩家同步协议​

设计玩家位置同步协议：每秒同步20次，5000个玩家，所有玩家总上行带宽限制1MB/s。

首先分析每个玩家最多能上传多少数据：

总上行带宽：
1 MB/s（= 1024 × 1024 = 1048576 字节/秒）

每次同步的总数据量：
1048576 字节 / 20 次 = 52428.8 字节 ≈ 52KB / 次

具体到每个玩家：
52KB / 5000 ≈ 10.48 字节 / 玩家 / 次

也就是说每个玩家每次最多只能发送约10字节的数据。接下来看看每个玩家的数据包：

字段字节数说明
玩家ID2唯一标识（0~65535）
x坐标216位有符号整数
y坐标2同上
z坐标2同上
Yaw + 状态2低10位为状态，高6位为Yaw
总计10字节满足带宽约束

最后是全局数据包结构：

  • 包头（4字节）：
    • 时间戳/帧号（2字节）：标识同步批次。
    • 玩家数量（2字节）：动态同步时实际更新的玩家数。
  • 玩家数据块：
    • 每个玩家数据10字节，5000玩家共 10 × 5000 = 50,000 字节。
  • 总数据量：
    • 50,000 + 4 = 50,004 字节/次 → 每秒 50,004 × 20 = 1,000,080 字节 ≈ 977 KB/s（接近1MB/s上限）。

反思：对计网这块一点也不清楚，唉。

Gameplay逻辑​

在平面战场游戏中，以摄像机位置为中心，存在多个敌方实体(数量不定)。每个实体根据以下规则计算其监控优先级分数:

1.视野约束:

  • 摄像机水平视域为 90 度(左右各 45 度)

  • 如果实体在当前摄像机水平视域内，该实体分数视为1分，否则视为0分

  • 摄像机 Pitch 角度与 RoIl 角度均为 0

2.地形约束:

  • 所有实体与摄像机处于同一水平面(二维坐标)

3.距离约束:

  • 仅统计 240 米范围内的敌方实体，240 米范围外的敌方实体视为0分

任务：完整实现以下函数，使得当摄像机位置固定时，返回摄像机水平(Yaw 轴)旋转角度theta (0°≤theta<360°)，在该角度theta下，摄像机半径 240 米范围内所有实体的总监控优先级分数达到最大值。

float FindOptimalcameraAngle(
    constTArray<FVector>& EntityPositions,
    FVector& CameraLocation,
) {
    constexpr floatViewDistance = 240.0f; // 监控半径(米)
    constexpr float FOV = 90.0f;                // 水平视野角度(degree)
    constexpr float VisibleScore = 1.0f;     // 实体可见时额外增加的分数

    // TODO...
}

问题补足说明：

  1. 距离计算：使用二维平面欧氏距离，忽略高度差异；
  2. 视域判定：实体坐标与角色连线的方位角在[theta-45, theta+45]区间内视为可见；
  3. 输入示例：
{
 "EntityPositions":
[
   {"x": 100, "y": 50, "z": 0},
   // ...... 上万条数据
],
"CameraLocation:" {"x": 35, "y":35, "z": 0 }
}

解答：

我们需要找到一个摄像机角度 theta，使得在该角度下，240米范围内且在90度视野内的敌方实体数量最多。由于角度是连续的，直接枚举所有可能的角度不现实。但我们可以利用以下观察：

  1. 关键角度：只有当某个实体的方位角刚好处于视野边界时（即 theta 旋转到刚好包含或排除该实体时），总分数才会发生变化。因此，我们只需要检查这些关键角度即可。
  2. 滑动窗口：可以将问题转化为在角度空间上的滑动窗口问题，窗口大小为90度，统计窗口内的实体数量。

算法步骤

  1. 过滤实体：首先排除距离超过240米的实体。
  2. 计算方位角：对于每个剩余实体，计算其相对于摄像机的方位角（0到360度）。
  3. 生成事件点：对于每个实体，生成两个事件点：一个是进入视野的角度，一个是离开视野的角度。
  4. 排序事件点：将所有事件点排序，便于滑动窗口处理。
  5. 滑动窗口统计：使用滑动窗口统计覆盖最多实体的角度范围。
  6. 处理循环边界：由于角度是循环的（0度=360度），需要特殊处理跨越360度的情况。

代码：

float FindOptimalCameraAngle(
    const TArray<FVector>& EntityPositions,
    const FVector& CameraLocation
) {
    constexpr float ViewDistance = 240.0f;
    constexpr float FOV = 90.0f;
    constexpr float HalfFOV = FOV / 2.0f;
    constexpr float VisibleScore = 1.0f;

    TArray<float> Angles;

    // Step 1: Filter entities within 240m and compute their angles (UE-friendly)
    for (const FVector& EntityPos : EntityPositions) {
        const FVector Delta = EntityPos - CameraLocation;
        const float Distance = FVector2D(Delta.X, Delta.Y).Size(); // 2D distance
        if (Distance > ViewDistance || Distance < KINDA_SMALL_NUMBER) {
            continue;
        }

        // Calculate angle in degrees [0, 360) using UE's Atan2
        const float Angle = FMath::RadiansToDegrees(FMath::Atan2(Delta.Y, Delta.X));
        Angles.Add(FMath::Fmod(Angle + 360.0f, 360.0f));
    }

    // Step 2: Generate interval events (enter/exit)
    TArray<TPair<float, int32>> Events;
    for (const float Angle : Angles) {
        const float Start = Angle - HalfFOV;
        const float End = Angle + HalfFOV;
        Events.Emplace(TPair<float, int32>(Start, 1));  // Enter
        Events.Emplace(TPair<float, int32>(End, -1));   // Exit
    }

    // Step 3: Sort events by angle (UE's Sort uses predicate)
    Events.Sort([](const TPair<float, int32>& A, const TPair<float, int32>& B) {
        return A.Key < B.Key;
    });

    // Step 4: Sliding window to find max coverage
    int32 MaxCount = 0;
    float BestTheta = 0.0f;
    int32 CurrentCount = 0;

    // First pass (0-360)
    for (const auto& Event : Events) {
        CurrentCount += Event.Value;
        if (CurrentCount > MaxCount) {
            MaxCount = CurrentCount;
            BestTheta = Event.Key + HalfFOV; // Center of FOV window
        }
    }

    // Handle circular boundary (wrap around 360)
    for (const auto& Event : Events) {
        const float WrappedAngle = Event.Key + 360.0f;
        CurrentCount += Event.Value;
        if (CurrentCount > MaxCount) {
            MaxCount = CurrentCount;
            BestTheta = WrappedAngle + HalfFOV;
        }
    }

    // Normalize to [0, 360)
    BestTheta = FMath::Fmod(BestTheta, 360.0f);
    if (BestTheta < 0) BestTheta += 360.0f;

    return BestTheta;
}

反思：我直接暴力枚举旋转角度，是不提倡的做法，并且不熟悉UE的接口，应该是寄了。

算法题​

有序数组去重​

实现有序数组去重，空间复杂度O(1)，并分析时间复杂度。

void myUnique(std::vector<int>& arr) {
    if (arr.empty()) return;
    
    size_t uniquePos = 1; // 无符号类型
    for (size_t i = 1; i < arr.size(); ++i) {
        if (arr[i] != arr[uniquePos - 1]) {
            arr[uniquePos] = arr[i];
            ++uniquePos;
        }
    }
    arr.resize(uniquePos);
}

双指针（uniquePos 和 i）的逻辑是标准的去重方法。时间复杂度为 O(N)，因为只遍历了一次数组。

反思：写对了，希望下次碰到的时候也能写对。