2020年4月11日晚上19:00到21:30我参加了某游戏大厂的游戏研发暑期实习笔试。2.5小时没有休息客观题加四道编程题考到后面脑子确实有点发木。这不是我第一次接触游戏岗的笔试但那场题覆盖面很典型横跨C、数据结构、图形学基础和算法复盘了好几天才把几道题完全消化掉。如果你也在准备游戏研发岗的暑期实习这套题无论从题型还是难度上都很有参考价值我尽量把当时的解题思路、现场判断和事后复盘都展开聊聊。当时考场的状态大概是这样的晚上7点开考先是一轮客观题紧接着四道编程题每道题都不算大路货没有一道是“纯背模板”就能写出来的。我出来之后第一反应是这类笔试已经不是单纯刷题能应付的了游戏研发岗确实在考和游戏行业强相关的东西——内存布局、渲染基础、地图寻路、资源分配每一题背后都能看到游戏业务场景的影子。1. 这场笔试的整体设计与考察逻辑1.1 岗位视角下的考点分布先说客观题的组成部分。大概有15到20道不定项选择内容集中在C语法细节、数据结构性质、操作系统并发、基础网络模型还有一小部分图形学常识。和普通后端岗的八股文不一样游戏研发岗的考点明显偏向底层和实时性。比如C部分会反复出现内存对齐、sizeof计算、虚函数表布局、new/delete与malloc/free的区别这类问题。这类题在别的岗位笔试里可能只是偶尔出现但在游戏研发岗里是高频考点因为游戏引擎核心模块基本都是C写的所有对象都在堆上频繁创建销毁对内存布局的理解直接决定引擎能不能跑得稳。数据结构这边没有绕弯考的都是“性质型”问题比如哈希表冲突处理、平衡树旋转、堆在不同场景下怎么选。但设问方式比较刁钻不是问你哈希表时间复杂度是O(1)而是给出一段具体负载因子下的退化场景判断最差情况什么时候发生什么时候退化。这种题目需要你在知道结论的基础上还要能快速推导边界条件。图形学部分更典型。我当时遇到了向量点乘判夹角、绕轴旋转的矩阵计算、光栅化流程先后顺序这类题。说实话如果没做过任何图形学实验纯靠背概念很难答全。有几道题不仅是单选还是不定项错选漏选都不得分这个容错压力在考场上还是比较明显的。1.2 为什么这套题值得好好复盘这套题最有意思的地方在于它不是“算法题拼接”而是把游戏研发岗位的日常工作场景拆开揉碎再用笔试的形式考出来。四道编程题里有字符串处理、地图寻路、贪心调度和序列动态规划每一道都能映射到游戏开发里的一个具体场景活动公告文案处理、战斗地图AI寻路、副本资源掉落分配、伤害数值平衡计算等等。所以与其说这是一场“考算法”的笔试不如说它是在模拟“游戏研发工程师怎么解决现实问题”。如果你还在用传统后端笔试的思路准备只看重“这题考了什么算法模板”很容易在现场吃亏。我自己当时有两道题就是改用游戏场景的角度去理解才很快找到了建模方向。另外2.5小时的时间压力也很关键。客观题如果单题耗时超过两分钟后面编程题大概率写不完。所以“取舍”本身就是笔试里的一道隐形题。这个后面我会单独讲考场时间分配先说客观题的具体复盘。2. 客观题复盘看似基础处处是坑2.1 C语法细节与内存管理题目这一块我记得最深的是几道关于结构体对齐和类大小的题。平时开发的时候大部分人对内存对齐的感觉停留在“编译器会自动补”很少去手算实际大小。但笔试里会直接给出结构体成员排列问sizeof值在特定编译器下是多少。这类题的解题关键是记住对齐规则每个成员按自身大小对齐结构体整体按最大成员对齐嵌套结构体按内部最大成员对齐。还要注意成员声明顺序会影响最终大小同样的成员换一下顺序大小可能直接少8字节。考场上如果没做过这类专项训练很容易就在这丢分。还有一个高频点虚函数机制。题目给一个带虚函数的类问你sizeof大小或者问你虚函数表存放在哪一段、构造函数里能不能调用虚函数。游戏引擎里到处都是继承和接口这套机制你不会的话读引擎源码就跟看天书一样。我当时的建议是准备这类笔试时不要只背“虚函数表指针占8字节”这种结论最好自己用代码打印过内存布局理解菱形继承里的虚基类指针否则题目稍微换一下结论就不好用了。再说new/delete与malloc/free的区别。这个知识点本身不算难但笔试会把它和运算符重载、异常安全捏在一起考。比如new[]和delete[]匹配错误会怎么样什么时候会崩哪个阶段会调用构造函数等等。这些都是引擎开发里每天要面对的问题——对象池、组件释放、内存碎片底层概念理解透了上层框架才不会踩坑。2.2 操作系统与网络基础题目游戏研发岗并不是只考纯底层C操作系统的并发和同步也占了不小的比重。有一类题是给你多线程读写同一个容器问哪个选项能保证安全。这种题衍生出的考点包括锁的粒度怎么控制、原子操作什么时候够用、条件变量为什么需要配合互斥锁使用、无锁队列适合什么样的生产消费模型。游戏服务器架构里网络线程、逻辑线程、渲染线程是多线程协作的典型场景所以这些同步问题离实际工作很近。笔试不会直接问你“什么是死锁”而是给一段伪代码四个线程两两加锁问你进程是正常退出、阻塞、还是抛出异常。这种题不仅考查概念还考查“会不会在真实场景里写出问题代码”。网络部分倒不深主要集中在TCP握手、UDP与TCP的选择、粘包半包问题。我做题时意识到游戏岗对网络的要求更贴近实际业务帧同步用UDP多点可靠传输状态同步用TCP保证顺序这些线下的经验积累在笔试里其实很有帮助。2.3 图形学常识与向量运算如果说C和数据结构是游戏研发笔试的地基那图形学常识就是它的门槛。我记得当时有几道题涉及点乘、叉乘的几何意义以及矩阵变换的顺序问题。比如一道题问先旋转再平移和先平移再旋转最后得到的物体世界坐标是否一样。这个问题的关键是矩阵乘法不满足交换律变换顺序不同结果完全不同。做过的都知道引擎里Transform的层级关系本质就是在做矩阵乘法父节点矩阵乘子节点矩阵顺序一旦写反模型位置马上错乱。还有光栅化流程的排序题顶点变换、视锥裁剪、透视除法、背面剔除、深度测试、片段着色这些步骤的先后关系一定要清楚。当时我不太确定的一个点是背面剔除到底发生在裁剪前还是裁剪后现在复盘下来这个顺序在标准渲染管线里是有明确位置的。如果你正在准备这类笔试建议把渲染管线从头到尾画一遍比反复背概念题高效得多。其实客观题整体并不超纲但覆盖面广、设问方式活加上不定项的选择机制容错率低。我统计了一下自己在客观题上大概花了35到40分钟这不算快但保证了后面编程题还有大约110分钟可用。时间分配这件事我放到后面专门讲先重点复盘四道编程题。3. 编程题一字符串重组问题3.1 题目复述与思考过程第一道编程题是一道字符串题大体场景是给一个长字符串和若干规则要求把字符串中的部分子串按照规则重新组合最终输出满足字典序最小的结果。具体规则细节我记不太清了但核心是一个“可重排”问题即对字符串里的若干组字符做位置交换后要求整体字典序尽可能小。这类题现场很容易想复杂。我一开始想的是把每个位置的字符拿出来做全排列再判断约束条件但很快发现字符串长度最多到10万级别全排列肯定不现实。随后转念一想这其实是一个贪心问题字典序最小本质上就是尽量让越靠前的位置字符越小同时要保证交换操作合法。当时我在草稿上演算了几组数据发现关键是把字符分组每个连通组内部可以自由排序要让整体字典序最小只需要在每个组内用counter排序后按位置依次填入即可。这个思路和“对图进行连通分量划分每个连通分量内部排序”很像本质是并查集的应用。3.2 解题思路与C实现要点建模过程是这样的字符之间若满足可交换条件就建立一条边把字符串位置的索引连接起来。求出所有连通分量后对每个分量记录它所包含的原字符串位置再把相应字符收集起来排序最后按位置填回去。这个方案有两个关键点并查集要按秩或路径压缩维护不然会退化。每个连通分量单独排序而不是全局排序否则会违反交换约束。我当时的实现核心大概是#include bits/stdc.h using namespace std; vectorint fa, rk; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void merge(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) { if (rk[ra] rk[rb]) swap(ra, rb); fa[rb] ra; if (rk[ra] rk[rb]) rk[ra]; } } int main() { string s; cin s; int n s.size(); // 假设给了若干可交换对 (x, y) // 初始化 fa, rk 后对每对调用 merge vectorvectorint comp(n); for (int i 0; i n; i) comp[find(i)].push_back(i); for (int i 0; i n; i) { if (comp[i].empty()) continue; string tmp; for (int pos : comp[i]) tmp.push_back(s[pos]); sort(tmp.begin(), tmp.end()); for (int j 0; j comp[i].size(); j) { s[comp[i][j]] tmp[j]; } } cout s \n; }当时这题我写了20多分钟主要时间花在证明贪心思路的正确性上。考场里不会要求严格数学证明但必须给自己一个“为什么这样选是最优”的理由否则写出来的代码心里没底。3.3 这类题的易错点这类题最大的坑有两个。第一只想到排序但没有用并查集维护连通分量导致交换范围超限第二原地填字符时如果直接对原字符串局部操作不先把字符收集排序很容易在原位置覆盖时丢字符。另外字符串长度大的时候cin读入可能会稍慢建议用快读而是直接关同步保证稳定。这道题我AC之后心态稳了不少也为后面的地图题节省了思考余量。4. 编程题二游戏地图的最短路径变体4.1 题目场景与分析第二道编程题直接就是游戏场景给定一张N x M的地图每个格子上有不同类型的机关玩家从起点走到终点每一步上下左右移动某些机关需要消耗特定道具才能通过道具可以在特定的格子上拾取。问从起点到终点的最小步数或者是否可达。这题看完第一反应是“这不是普通BFS”因为玩家所处的状态不仅和坐标有关还和手里有哪些道具有关。如果只记录坐标就会出现踩过某个格子后再绕回来时因为道具不同而能走新路线的情况。所以状态必须扩展成坐标道具集合。我当时在地图上看到道具种类只有1到3种立刻意识到可以把道具集合压成一个二进制状态mask再用vis[x][y][mask]做去重。这样BFS状态数大致是N乘M乘2的K次方K很小的时候是完全可搜的。4.2 BFS状态设计的关键状态设计的核心在于入队一个状态时不仅要记录步数还要更新当前携带的道具集合。每次从一个格子走到相邻格子先判断新格子是否需要道具如果需要且当前mask里没有则不能通行如果格子是道具点把新道具加入mask再继续扩展。这里有个容易踩坑的地方先检查能不能走再决定要不要更新道具顺序不能反。有些题目的机关格拾取道具和消耗道具可能发生在同一格如果顺序错了要么多消耗要么少拾取边界条件会复杂很多。我当时用了一个三维vis数组配合deque写BFS。因为每步代价都是1普通队列就够了不用上Dijkstra。如果地图很大且状态数过多还可以加启发式剪枝但笔试场景下N、M给得都比较克制没必要过度优化。核心片段可以是这样的思路struct State { int x, y, mask, step; }; int bfs(vectorvectorint grid, pairint,int start, pairint,int end, int totalKinds) { int n grid.size(), m grid[0].size(); int maxMask 1 totalKinds; vectorvectorvectorbool vis(n, vectorvectorbool(m, vectorbool(maxMask, false))); queueState q; int initMask 0; if (grid[start.first][start.second] 0) initMask | 1 grid[start.first][start.second]; q.push({start.first, start.second, initMask, 0}); vis[start.first][start.second][initMask] true; // four directions int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; while (!q.empty()) { State cur q.front(); q.pop(); if (cur.x end.first cur.y end.second) return cur.step; for (int i 0; i 4; i) { int nx cur.x dx[i], ny cur.y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; int need grid[nx][ny]; // need 0 表示机关需要特定道具使用负数值编码 if (need 0 !(cur.mask (1 (-need - 1)))) continue; int nmask cur.mask; if (need 0) nmask | (1 need); if (vis[nx][ny][nmask]) continue; vis[nx][ny][nmask] true; q.push({nx, ny, nmask, cur.step 1}); } } return -1; }代码里用正负数区分道具点和机关点这只是编码方式的一种实际题目里具体定义会不同。重要的是vis数组的下标要完整描述“我在哪、我有哪些道具”这一状态不然就一定出错。4.3 地图类BFS的普适套路复盘下来地图题在游戏研发笔试里真的太常考了。除了这种带道具的变体还有带钥匙的门、会上下移动的传送带、多人在线同步位置本质上都是“当前位置状态集合”的搜索模型。这类题的通用解法是先明确状态中除了坐标还有什么维度再判断维度上限能用bitmask压缩的就用bitmask不能用就考虑状态降维。比如有些题传送门只会让你传送一次那状态就加一维“是否用过传送门”如果某类机关玩家吃一次对应的药就能免疫后续所有同类机关那状态也可压缩成mask。当时这题我是一次AC做完还剩一些时间给第三题开了个好头。不过第三题就没那么顺利了因为我一开始把贪心策略想反了。5. 编程题三资源分配与贪心调度5.1 题目模型与场景还原第三道题是一个调度题我记得大概场景是副本里有若干个关卡玩家每天可以打固定次数每次打完一个关卡会获得一个奖励有些关卡在特定条件下会触发额外奖励要求设计一个挑战顺序使固定次数内的总奖励最大化。本质上是一个带前置条件和奖励衰减的贪心模型每个关卡有一个基础奖励如果选择了一组前置关卡额外奖励才会生效。次数有限要在有限的次数里选择哪些关卡去打、按什么顺序打。这道题我第一反应是“背包问题”因为次数相当于背包容量关卡奖励相当于价值。但很快发现关卡之间有前置依赖而且顺序会影响奖励触发这不是一个标准背包能直接套的。后来我意识到题目给出的条件满足一个关键性质——基础奖励不会有衰减、额外奖励的触发条件只是一个简单的依赖集合。在这个前提下问题被简化成了先打前置关卡再打收益最高的后续关卡用贪心就可以解决。5.2 贪心策略的证明与坑点我当时定的策略是把所有关卡按“基础奖励额外奖励”的总收益排序优先打总收益最高的如果某个高收益关卡需要前置关卡必须先把前置关卡排进序列。这个策略在依赖关系是“每个额外奖励最多只依赖一个前置关卡”的情况下是对的。但如果依赖链变长单纯按总收益排序就会出问题。举个简单例子A关卡基础奖励1额外触发B后奖励100B关卡基础奖励30无额外。按总收益排序A排在B前面但你不打B就触发不了A的额外奖励。所以正确的贪心方向应该是优先打依赖链底部的关卡然后用小顶堆维护已完成前置条件的最高收益关卡每打一次取堆顶更新。这个思路写起来是经典贪心模板把所有关卡按前置完成度排序初始时选所有没有前置要求的关卡加入候选堆每次从堆顶取出收益最高的一个完成后再把解锁的新关卡加入堆。每打一个关卡消耗一次次数直到次数用完或堆空为止。这一步其实就是拓扑排序优先队列的组合我在现场没有第一时间想清楚绕了一点路。复盘后我把核心流程整理成构建依赖关系图统计每个关卡的前置数量。将前置数量为0的关卡按收益加入优先队列。每次从优先队列取收益最大关卡消耗一次次数累加收益。更新该关卡后续影响的关卡前置减到0时入堆。次数用尽或队列空则停止。关键点是优先队列的排序基准。如果额外奖励要依赖多个前置关卡那么“全部前置完成”才算解锁判断逻辑要放在更新后脑补边时做而不是在最初入堆时做。5.3 关于贪心正确性的判断经验做这类贪心题我现在的经验是先把问题抽象成“排序选择问题”然后找反例。如果能在三分钟内构造出一个反例说明思路不对如果尝试多个场景都找不到反例就大胆写写完留出时间做对数验证。考场上我遇到DC这个点花了些时间但最终还是通过反例调整了方向。这类调度题在游戏研发岗出现概率很高比如活动排期、背包格子排序、技能触发顺序底层都是这种优先级队列的思维。如果笔试准备时间充足建议把拓扑排序、优先队列、事件驱动的模拟题都练熟。6. 编程题四序列上的状态优化6.1 题目转化与DP建模第四道题压轴是一道序列动态规划题目乍一看像简单的一维DP实际上藏着优化点。大致题意是给定一个长度为N的序列要求划分成若干连续段每个段有一个评估函数值求划分后总价值最大或最小。如果直接枚举段数、枚举断点复杂度是O(N^2)但题目数据范围通常到10^5必须优化。这类题的经典套路是如果段价值函数满足“四边形不等式”或者可以利用前缀和简化转移就可以优化到O(N log N)或者O(N)。我当时推导出转移方程大概是dp[i] min(dp[j] cost(j1, i))其中j从某个位置到i-1。问题的关键变成了cost(j1, i)怎么快速计算。如果cost是区间最大值或区间和都可以通过前缀结构O(1)取得。我当时那题恰好cost可以用前缀和配合一个单调变量简化转移变成了维护一个关于j的“候选最小值”然后用单调队列在线性时间内求出所有dp[i]。6.2 单调队列优化转移的现场推导单调队列优化适用的情况是转移决策点j的候选集合随着i单调移动并且我们要维护的目标值也能用单调队列维护。比如dp[j]减去某个随j单调变化的加权项入队时保证候选值单调出队时淘汰不再可能成为最优的旧决策。现场推导时我先把转移方程写出来把含j的项和含i的项分开把只含j的部分构造成一个可维护的“候选值”这样dp[i]就等于当前最优候选值加上含i的项。如果候选值集合满足滑动窗口性质就可以用一个双端队列维护。一旦写清楚这个形式代码就比较模式化了。这类题特别考验把公式拆开重组的能力。我在准备阶段练过不少单调栈、单调队列的题但现场看到题目藏了一层前缀和的变换差点没认出来。复盘后我总结出一个技巧当你写完O(N^2)DP后如果发现数据范围明显不匹配就先去观察转移点i和j的间距限制看看随着i增加j的可行区间是否也单向移动如果是大概率可以用单调队列。6.3 边界处理与笔试实测心得这种DP题最危险的是边界状态。比如合法的断点必须保证最后一个段不为空有些转移要求段内的特性满足特定条件否则最优值可能是负无穷这些都要在初始化时处理到位。我当时把dp[0]初始化为0其余初始化为正无穷求最小循环时小心处理了前缀下标偏移AC之后才松了口气。其实现在回想第四题难度本身并不算高但放在整场笔试的最后配合前面三题消耗的精力读题和推导的速度都会被拖慢。这就是为什么考场上的题目顺序很讲究前快后慢最后留足时间给状态题。7. 考场时间分配与后续备战清单7.1 150分钟实战时间表整场笔试2.5小时客观题加四道编程题。我当时实际的时间分配大概是这样的时间段用时任务19:00-19:2020分钟快速浏览全部题目标记客观题难题19:20-19:5535分钟完成客观题不确定的题先跳过19:55-20:2025分钟完成第一道字符串排序题20:20-20:5535分钟完成第二道地图BFS题20:55-21:1015分钟第三道贪心题中途思路调整21:10-21:2515分钟第四道DP题推导实现21:25-21:305分钟检查输入输出格式和特殊边界看上去第四题只剩15分钟其实我前面做题时已经在心里推导了它的转移框架所以真正编码时比较快。如果客观题耗时过长或一道编程题卡死超过40分钟后面的题就没时间做了。我的建议是开考后先花10到15分钟把整个试卷浏览一遍判断题的难度梯度把能拿的先拿不要被一道题缠住。7.2 复盘后的备战清单笔试结束后的复盘比考试本身更重要。我按“是否能在三天内完全吃透”的标准把考点分成了几类。C内存布局、虚函数、内存对齐这些是需要反复练习的建议拿真实代码做实验看看sizeof输出和编译器警告加深印象。数据结构方面重点是并查集、优先队列、单调队列、拓扑排序这些“算法组件”每种数据结构对应的应用场景要能脱口而出。像字符串重组题考并查集资源调度题考优先队列拓扑排序这两类可以组合练习遇到一个场景就能联想到一套组件考场上就不慌。图形学和渲染管线这部分不是短期冲刺能学完的但基础题就那几个比如向量运算、矩阵变换、摄像机投射、光照模型。建议至少把变换矩阵推导一遍自己画一画视锥体理解正交投影和透视投影的区别。游戏研发岗笔试不会考太深但“完全没概念”和“能推导”的差距在答题速度上体现得很明显。刷题方向上比起随机刷题我更推荐按游戏场景做专题寻路、地图、资源分配、序列收益最大化这几个方向几乎每场笔试都能碰到。我当时制定了一个计划每天两道BFS变体和一道贪心题配合每周一次模拟笔试最后效果比漫无目的地刷数量好很多。复盘完整场笔试我个人最大的体会是游戏研发实习笔试的核心不是比谁会背的模板多而是比谁能快速把实际问题转化成算法模型。字符串可以变成并查集地图可以变成状态压缩BFS资源调度可以变成拓扑排序和优先队列序列问题可以变成单调队列DP这种“场景建模”的能力才是整场考试真正想筛选的东西。如果你还有时间准备游戏方向的面试不妨在刷题之外多读一些开源游戏引擎的底层源码试着把一个简单玩法拆分成系统模块再从模块想到对应的数据结构。那个过程虽然慢但比刷一百道题更能建立岗位直觉。祝后面笔试的朋友都能稳住心态拿到满意的实习机会。