面试全流程准备

自我介绍

面试官您好，我是浙江大学计算机科学与技术专业的大三学生ysj。我的技术栈以C++为核心，熟悉OpenGL、Qt等框架，熟悉python,Java语言，了解Lua脚本语言。具备游戏开发、操作系统和网络协议栈的实战经验。熟悉git、CMake等工具，了解Linux系统编程和多线程编程。我的学习能力比较强，团队合作能力很强，能快速适应新技术和新环境。 在游戏开发方面，我主导开发了《3D迷宫逃杀》和《四键交互音游》两个项目。
在《3D迷宫逃杀》中，我设计了迷宫随机生成算法，优化了A*寻路性能，并实现了复杂光照和立体音效，提升了沉浸感。
在音游项目中，我通过MVVM架构和多线程技术优化了实时交互性能，利用Qt实现动态渲染，提升了游戏流畅度和响应速度。 此外，我深入底层开发，曾用C语言实现Linux内核的进程调度和内存管理模块，并基于C++实现了TCP/IP协议栈，优化了吞吐量和延迟。我的优势在于能将底层原理与上层应用结合，解决性能瓶颈问题。同时我也开发过简单的前后端项目，熟悉数据结构与算法，能快速适应新技术。

我热爱游戏开发，期待能在不鸣科技的团队中继续提升自己的技术能力，并为公司的项目贡献力量。

项目拷打：

3D迷宫逃杀（2024.10 - 2024.12）

项目概述： 在此项目中，我使用C++和OpenGL开发了一个3D迷宫逃杀游戏。项目的核心功能包括迷宫随机生成、NPC智能寻路、复杂的光照与阴影效果、以及沉浸感极强的音效与视角切换。

技术亮点： - 迷宫生成算法：通过结合深度优先搜索（DFS）与随机化Prim算法，生成具有挑战性的动态迷宫。 - A*路径规划：优化了NPC的智能寻路，通过改进A算法提升了NPC与玩家互动的流畅性。 - OpenGL渲染与光照：实现了Phong光照模型，并通过法线贴图与环境贴图提升了游戏渲染效果。 - 立体音效与视角切换：使用OpenAL库实现了3D音效，并通过摄像机类实现了第一人称与第三人称视角的无缝切换。 - 多线程优化*：利用C++11线程库，优化了NPC路径计算与音效播放，确保游戏性能与响应速度。

个人贡献： - 负责迷宫生成算法与NPC寻路算法的实现，使用DFS与A*结合来确保每次游戏体验的独特性。 - 深入理解了OpenGL渲染管线，应用了顶点与片段着色器来实现复杂的墙体渲染与光照效果。 - 优化了内存管理，解决了内存泄漏问题，通过使用智能指针避免了手动内存管理的错误。

团队合作与工具： - 使用Git进行版本控制，确保了代码的高可维护性。通过Pull Request进行代码审查，提升了团队的协作效率。 - 在项目的最后阶段，进行了多次性能优化与测试，确保了游戏的稳定性与流畅性。

细节解释:

1. Prim:
   • Prim 找无环子集，权值和最小， 随机选点 相邻找权值最小 包含所有点停止
   • Prim迷宫生成算法
   • 1. 随机选一个点作为起点
   • 1. 随机选一个墙，加入到列表中
   • 1. 当列表中仍然有墙时
     2. 如果分割的两部分只有一个单元格被访问过，列表中移除这堵墙，让未访问的单元格成为迷宫的通路，再把这个格子的墙加入到列表中
     3. 如果两部分都访问过，则从列表中移除这堵墙

优化: 目前针对2D地图/迷宫xxx，基于瓦片xxx，3D

1. A*寻路
2. 初始化open_set和close_set；
3. 将起点加入open_set中，并设置优先级为0（优先级最高）；
4. 如果open_set不为空，则从open_set中选取优先级最高的节点n：
   • 如果节点n为终点，则：
     • 从终点开始逐步追踪parent节点，一直达到起点；
     • 返回找到的结果路径，算法结束；
   • 如果节点n不是终点，则：
     • 将节点n从open_set中删除，并加入close_set中；
     • 遍历节点n所有的邻近节点：
       • 如果邻近节点m在close_set中，则：
         • 跳过，选取下一个邻近节点
       • 如果邻近节点m也不在open_set中，则：
         • 设置节点m的parent为节点n
         • 计算节点m的优先级
         • 将节点m加入open_set中

5. Phong光照模型 主要结构由三个分量组成：环境光照（常量）、漫反射光照（方向性）和镜面反射光照（。每个分量都与材质属性和光源属性相关联。、

   norm和lightDir向量进行点乘 不等比缩放 viewDir, reflectDir 取它的32次幂

   总之就是通过VAO,VBO,EBO来实现顶点的渲染，使用着色器来实现光照效果。

   VAO | ├─ VBO（顶点数据） │ ├─ 顶点位置 │ └─ 法线/纹理坐标等属性 │ └─ EBO（索引数据） └─ 定义顶点绘制顺序

6. OpenAL音效 ALSource的几个参数：位置(Position)、速度(Velocity)、方向(Direction)、音量(Gain)

7. C++11多线程

   • 使用std::thread创建线程，std::mutex进行线程间同步
   • 使用std::condition_variable实现线程间的条件变量通知机制
   • 使用std::atomic实现原子操作，避免数据竞争
   • 使用std::future和std::promise实现异步任务的结果传递与获取

   总体上 主线程:状态机维护，输入处理，更新 - 渲染线程:渲染，资源加载 - 音效线程:空间音效播放 - NPC线程:寻路计算，NPC移动 - 玩家线程:玩家移动，碰撞检测

8. 自动保存检查点日志,崩溃场景恢复

   • 通过定时器定期保存游戏状态(玩家NPC位置，地图矩阵，太阳运行角度)到文本文件中
   • 崩溃后读取最近的检查点（即文件）进行恢复

可以改善的地方： - 游戏可以有更多地图，更多buff/debuff（比如加速，减速，隐身等） - 游戏可以有更多的NPC，增加难度 - 游戏大地图可以使用四叉树进行分割，减少渲染的物体数量 - 游戏可以有更多的音效，增加沉浸感 - 游戏可以有更多的光照效果，增加真实感

四键交互音游（2024.06 - 2024.09）

项目概述： 我参与了一个四键交互音游的开发，使用C++、Qt以及MVVM框架开发游戏前端，处理键盘交互与音符消除逻辑，优化了游戏体验的流畅性与响应速度。

技术亮点： - MVVM框架：通过MVVM架构分离了视图与逻辑，提高了代码的可维护性与可扩展性。 - 多线程优化：将音符生成与消除放在独立线程中，确保了游戏的实时响应。 - Qt图形视图框架：利用Qt的图形视图框架处理音符的动态加载与渲染，提升了图形渲染的效率。 - 性能优化：通过使用QOpenGLBuffer优化了渲染性能，同时通过QTimer减少了CPU占用，提升了游戏流畅度。

个人贡献： - 主要负责音符动态加载与渲染的实现，确保了游戏中音符显示的流畅性。 - 在多线程计算方面，负责音符的消除逻辑，并实现了线程之间的同步，保证数据一致性。

团队合作与工具： - 使用Git进行版本控制，保证项目结构清晰、代码易于维护。 - 在开发过程中，积极与团队成员沟通，确保项目的进度与质量。

细节解释

1. MVVM框架
2. Model：数据模型，负责数据的存储与管理
3. View：用户界面，负责数据的展示与用户交互
4. ViewModel：连接Model与View，处理业务逻辑与数据绑定
5. 通过数据绑定实现View与ViewModel之间的双向数据同步
   • 使用Qt的信号与槽机制实现View与ViewModel之间的通信
   • 通过QML实现动态UI，提升了用户体验
6. 主要处理了击打音符的逻辑
7. 多线程优化（在音符渲染和音符交互方面添加锁机制）
   • 使用QThread创建独立线程处理音符生成与消除逻辑
   • 使用QMutex进行线程间同步，确保数据一致性
   • 使用QWaitCondition实现线程间的条件变量通知机制
8. 生成移动渲染音效
9. 主要处理了音符按照时间轴生成与后续的逻辑

线程池 音符的信息处理是游戏前期加载的工作 音乐播放是一个线程，只负责播放音乐 音符的生成是一个线程，负责音符的生成与渲染（对于此时应当活跃的音符），然后实时渲染实时移动 playThread是一个线程，负责音符的消除

微型操作系统设计开发（Mini OS）（2024.09 - 2024.12）

项目概述： 在该项目中，我实现了一个简化版的Linux内核，涉及进程管理、调度、内存管理和中断处理等系统级模块。

技术亮点： - 进程管理与调度算法：实现了基于时间片的轮转调度算法，支持优先级调度。 - 内存管理：实现了页式内存管理与缺页异常处理，并优化了页面置换算法。 - 中断处理与用户态/内核态切换：设计了系统级中断处理机制，实现了高效的用户态与内核态的切换。 - 文件系统：实现了基本的文件读写操作，并优化了数据的持久化与检索机制。

个人贡献： - 负责设计与实现进程管理和调度算法，确保操作系统能够高效管理多个进程。 - 深入研究了内存管理，成功实现了缺页异常与页式内存管理。

详细解释：

1. 进程管理与调度算法
2. 实现了基于时间片的轮转调度算法，支持优先级调度
   • 简单复习：RR+Priority:FIFO+Quantum+Priority
3. 设计了进程控制块（PCB）结构体，存储进程状态、优先级、程序计数器等信息
   • 简单复习：
4. 实现了进程创建、销毁、阻塞与唤醒等基本操作
5. 内存管理
6. 实现了页式内存管理，使用页表映射虚拟地址到物理地址
7. 实现了缺页异常处理机制，当访问的页面不在内存中时，触发缺页异常
   • VMA（虚拟内存区域）结构体，存储虚拟地址范围、物理页框号等信息
8. 优化了页面置换算法，使用LRU算法选择最久未使用的页面进行置换
   • LRU
9. 中断处理与用户态/内核态切换
   • 设计了系统级中断处理机制，支持外部中断与内部中断
   • 实现了用户态与内核态的切换机制，通过保存与恢复上下文实现

---

计算机网络CS144（2024.09 - 2024.12）

项目概述： 在此项目中，我设计并实现了简化版的TCP/IP协议栈，支持跨子网通信与端到端可靠传输。

技术亮点： - 协议栈设计：实现了链路层CRC校验、IPv4路由（Dijkstra算法）与TCP滑动窗口机制。 - 性能优化：通过动态调整滑动窗口与丢包自适应算法，提升了吞吐量和数据完整性，延迟降至<50ms。 - 测试与工具：使用Mininet进行多节点网络仿真，利用Wireshark进行协议行为抓包分析。

个人贡献： - 负责实现TCP层的滑动窗口与拥塞控制算法，并进行性能优化以降低丢包率。 - 通过优化协议栈，提高了整体传输效率和网络稳定性。

微型数据库设计开发（Mini SQL）（2023.04 - 2023.06）

项目概述： 我基于C++实现了一个单用户SQL引擎，支持基本的SQL操作与高效的数据存储与检索。

技术亮点： - 数据存储：通过堆表与B+树索引提升了查询效率。 - 内存管理：使用LRU算法优化了Buffer Pool，减少了磁盘I/O。 - 事务与一致性：实现了主键与唯一约束索引，支持高效的等值与范围查询。

个人贡献： - 负责设计并实现B+树索引，并对数据库的查询优化进行了大量调试与测试。

一面问题

Q: 乱序排行榜

乱序排行榜10万个玩家，某位玩家如何知道其位置以及如何优化性能？

A:

快排二分 哈希表频率 跳表/平衡树

在10万个玩家的乱序排行榜中，要确定某玩家的排名，通过遍历排行榜（O(N)）、二分查找（O(log N)，前提是排序），或者使用哈希表存储排名（O(1)）都是不能解决问题的，时间/空间复杂度都很高。

如果均衡时间空间复杂度，可以考虑归并排序（O(N log N)），将排行榜分成多个块，每个块内进行排序，然后使用二分查找来确定玩家的排名。 综合一下，分成40块，冒泡排序O(N^2)，从第一个块向后比较，

或者哈希表+频率统计

而如果跳出内部排序方法，则可以考虑外部排序： 逐块加入内存然后快排，然后进行多路归并，（最小堆）得到最终的结果。然后二分查找或者者线性查找来确定玩家的排名。

为优化性能，可以采取以下措施： 1) 分页查询，每次只加载一部分数据； 2) 数据分片与索引，将数据分块以减少查询范围； 3) 缓存技术（如 Redis）加速常查询数据； 4) 增量更新，避免每次全量排序； 5) 并行处理，分布式查询和负载均衡提高性能。这些方法可以显著提升查询效率。

Q: 地图距离

玩家在地图中移动，如何快速找到距离最近的城镇？

A:

可以使用空间划分技术（如四叉树或八叉树）来快速找到距离最近的城镇。具体步骤如下： 1) 空间划分：将地图划分为多个区域，每个区域存储其内的城镇信息。 2) 区域查询：根据玩家当前位置，快速定位到其所在的区域。 3) 距离计算：在该区域内，计算玩家与城镇的距离，找到最近的城镇。 4) 邻近区域查询：如果该区域内没有城镇，向相邻区域扩展查询，直到找到最近的城镇。 5) 缓存机制：可以使用缓存机制存储最近查询的城镇，以减少重复计算。 6) 多线程处理：在大地图中，可以使用多线程并行计算不同区域的距离，进一步提高效率。 7) A*算法：如果需要考虑路径，可以使用A算法进行路径规划，找到最短路径到达城镇。 8) 预处理：在游戏开始时预处理城镇与玩家之间的距离，存储在数据结构中，以便快速查询。 9) 动态更新：如果城镇位置或玩家位置发生变化，及时更新距离信息，以保持数据的准确性。 10) 空间索引：使用R树等空间索引结构，快速定位城镇位置，提高查询效率。 11) 距离函数优化*：使用欧几里得距离或曼哈顿距离等简单的距离函数，避免复杂计算，提高性能。

Q: 超级手雷

32名玩家，每位玩家指挥100位士兵，向同一个地点丢手雷同时会有很多手雷爆炸，此时会很卡，如何优化？

A:

对象池

对象池（Object Pool）用于管理频繁创建和销毁的对象，减少内存分配开销。对于手雷和爆炸特效，使用对象池可以避免每次爆炸时都创建新对象，提升性能。

• 手雷对象池：管理所有投掷的手雷，使用完后回收，不必频繁创建和销毁对象。
• 爆炸特效池：爆炸时从池中获取特效对象，播放后回收。
• 粒子池：管理爆炸的粒子效果，减少粒子创建与销毁的开销。

示例（C++）：

class GrenadePool {
private:
    std::queue<std::shared_ptr<Grenade>> pool;

public:
    GrenadePool(size_t size) { /* 初始化池 */ }

    std::shared_ptr<Grenade> getGrenade() { /* 从池中获取手雷 */ }

    void returnGrenade(std::shared_ptr<Grenade> grenade) { /* 回收手雷 */ }
};

通过对象池，减少内存分配和垃圾回收，提高游戏性能。

线程池

线程池用于并行处理爆炸计算任务，避免频繁创建线程，提高计算效率。在手雷爆炸时，可以通过线程池并行处理每个手雷的爆炸影响（如伤害计算、物理效果等），避免阻塞主线程。

示例（C++）：

class ThreadPool {
private:
    std::vector<std::thread> workers;
    std::queue<std::function<void()>> tasks;
    std::mutex queueMutex;
    std::condition_variable condition;
    bool stop = false;

public:
    void enqueueTask(std::function<void()> task) { /* 将任务加入队列 */ }
};

通过线程池，可以将爆炸任务分配给多个线程并发处理，减少卡顿。

• 手雷对象池：减少对象创建与销毁，复用手雷、爆炸特效和粒子。
• 线程池：将爆炸计算分配给多个线程并行处理，提升效率。
• 空间划分：使用四叉树或网格划分地图，只处理与玩家相关的爆炸区域，减少计算范围。

• 事件合并：对爆炸事件进行合并，避免每个手雷爆炸时都进行计算。

• 使用 对象池 管理手雷和爆炸特效，避免内存频繁分配和回收。

• 使用 线程池 并行处理爆炸影响计算，提升游戏并发性能。
• 空间划分 和 事件合并 减少计算量，降低性能开销。

通过这些优化，可以有效提高大量爆炸事件下的游戏性能，避免卡顿，确保游戏流畅运行。

Lua底层

Q: Lua中数组名赋值的底层含义？ A: Lua中数组名赋值是浅拷贝。

二面

上一份面经拷打项目（设计缘由，如何提升） 状态机 手搓游戏设计 vector底层&多线程（八股）

项目中有迷宫的生成，直接拷打A*算法实现，问我优先级根据什么（曼哈顿距离），也问了Prim生成算法，描述了一下

关于第三人称视角，关于透视描边，子弹碰撞检测，爆头等等

八股：右值引用等等，C++11新特性，&和&&，static 和 const，多态