一、写在前面：Unity 为什么要学算法？

很多人觉得“Unity 做游戏 = 调 API + 调特效”，算法离自己很远。实际在项目里你会频繁遇到这些问题：
  • 场景里成百上千个怪物/道具，怎么更快找到目标？
  • 掉落、排行榜、技能结算，怎么排序才不卡？
  • 格子地图、迷宫、战棋、塔防，怎么走路/扩散/搜索？
  • 攻击判定、范围检测、碰撞筛选，怎么少做无用计算？
  • 频繁 Instantiate/Destroy 导致卡顿，怎么减少 GC 和抖动？
算法不是“为了面试而背”，而是让你写出更稳、更快、更好维护的游戏逻辑。
i
本文会用“Unity 场景”来解释算法，并给出可直接复制的 C# 示例代码模板（偏实用、偏面试高频）。

二、Unity 高频基础算法（面试必考）

0. 先统一：复杂度怎么快速判断？

你不需要背所有推导，但要能快速判断“这段代码会不会随着对象数量暴涨而卡”。
  • O(1)：常数级（最爽）。例如数组按下标访问、Dictionary 查找（平均）。
  • O(log n)：对数级。典型：二分查找。
  • O(n)：线性级。典型：遍历列表、线性查找。
  • O(n log n)：常见高效排序复杂度（快速排序/归并排序平均）。
  • O(n²)：对象数量一大就容易卡（冒泡/选择/插入在最坏情况下）。

1. 查找类

1.1 线性查找（Linear Search）

适用场景：小规模集合 / 一次性查找；例如：
  • 遍历当前房间所有怪物，找最近的
  • 遍历掉落物列表，找某个 id 的道具
思路：从头到尾扫一遍，找到就返回。
复杂度：O(n)
page icon
当 n 从 100 → 10000 时，O(n) 的“每帧查找”很容易把帧率打爆。能缓存/建索引就别每帧线扫。

1.2 二分查找（Binary Search）

适用场景：数据必须是有序的；典型：
  • 配置表按 id 排序后快速查
  • 等级区间、数值阈值查表
复杂度：O(log n)

2. 排序类（只用基础三大排序 + 快排）

2.1 冒泡 / 选择 / 插入排序（基础必会）

适用场景：数据量很小（几十以内）或“近乎有序”。
在 Unity 中常见于：
  • UI 排行榜前 N 名（小 N）
  • 掉落物/任务列表（数量不大）
  • 编辑器工具排序
插入排序在“几乎有序”时非常好用（例如每次只插入一个新元素）：

2.2 快速排序（Quick Sort）

适用场景：大量数据排序（距离、血量、优先级）。
平均复杂度：O(n log n)，最坏 O(n²)（极端情况下选枢轴不好）。
项目里大多数情况下你会直接用：
  • List<T>.Sort(...)
  • Array.Sort(...)
但面试常让你讲原理或手写核心 partition。下面给一个“可讲可写”的模板：

3. 遍历 & 路径算法（游戏重中之重）

3.1 DFS 深度优先（Depth First Search）

适用场景：
  • 地图/节点遍历
  • 技能范围（连锁、传播）探索
  • 迷宫“是否可达”的探索
特点：一条路走到黑，走不通再回退（栈/递归）。
复杂度：O(V + E)
示例：格子地图 DFS（找所有可到达格子）

3.2 BFS 广度优先（Breadth First Search）

适用场景：
  • 无权图最短路（格子地图每步代价相同）
  • 范围扩散（AOE、毒圈、视野扩散）
  • A* 的基础前置
特点：一圈一圈扩散（队列），天然得到“最少步数”。
复杂度：O(V + E)
示例：格子地图 BFS（求最短步数）

3.3 A* 寻路（A Star）

Unity 刚需：怪物自动寻路、NPC 移动、塔防单位走位。即使你用 NavMesh，也建议懂核心思想：
  • BFS = 只看“已走步数 g”
  • A* = 同时看“已走步数 g” + “到终点的预估代价 h”
  • 目标：更快收敛到终点（少扩散无用节点）
面试常问三点：
  1. f = g + h
  1. h 要“合理”（如曼哈顿距离/欧氏距离）
  1. 用优先队列（小顶堆）维护 open list
（完整 A* 实现篇幅较长，建议你单独写一篇；本文先把 BFS/DFS 打扎实即可。）

4. 物理 & 碰撞常用算法

4.1 AABB 包围盒检测（Axis-Aligned Bounding Box）

适用场景：大量物体先做“粗检测”，过滤掉明显不可能碰撞的对象，再做精检测（减少 Physics 调用）。
二维 AABB 是否相交：

4.2 射线/球形检测（Ray / Sphere）

适用场景：
  • 交互点击拾取
  • 子弹命中（射线/胶囊）
  • 技能范围（SphereOverlap）
项目里直接用 Physics API，但要会解释“为什么要先做层级过滤/先粗后细”。

三、游戏开发专属高频算法 / 设计思想

这部分是 Unity 区别于普通后端开发的核心：
  1. 对象池（缓存复用算法）：子弹、怪物、特效频繁生成销毁，用对象池降 GC，面试必问手写
  1. 插值算法：Lerp、Slerp、平滑过渡、缓动函数（移动、旋转、UI 动画）
  1. 随机算法：权重随机（掉落、抽卡）、伪随机、随机不重复
  1. 裁剪 & 优化算法：视锥裁剪、遮挡剔除、场景分块，降低渲染压力
  1. 平滑旋转、向量运算：点乘、叉乘（判断朝向、左右、角度、范围），属于游戏基础数学算法

四、面试怎么答：用“Unity 场景”把算法讲清楚

面试官问算法，往往不是要你背定义，而是看你能不能落地。
你可以用这个回答模板：
  1. 它解决什么问题（在项目里哪里出现）
  1. 核心思路（用一句话讲明白）
  1. 复杂度（大概量级即可）
  1. 什么时候不用它（边界/陷阱）
  1. Unity 落地例子（怪物查找、范围扩散、寻路、碰撞筛选）

五、总结

  • 查找：小数据线性查找；有序数据二分查找
  • 排序：小规模用插入；大规模用系统 Sort（底层优化）+ 理解快排原理
  • 图与搜索：DFS/BFS 是一切寻路/范围算法的基础
  • 性能：先粗后细（AABB/层级过滤），避免每帧 O(n) 暴力扫
后续如果你要把系列写完整，建议按“可复用模板”拆分成专题：
  • BFS/DFS 专题（带范围扩散、迷宫、连锁技能）
  • A* 专题（优先队列 + 启发式 + 路径回溯）
  • 对象池专题（通用池 + 预热 + 回收策略）