游戏相关算法

A* 寻路原理是什么？

A* 寻路原理是什么？ A* 是一种常用寻路算法，游戏里经常用在网格地图、战棋、怪物追玩家、NPC 绕障碍移动。

它每次不是盲目扩散，而是优先选择“看起来最有希望到达终点”的格子。

核心公式：

f = g + h

含义是：

g：从起点走到当前点，已经花了多少代价
h：从当前点到终点，预计还要花多少代价
f：综合评分，A* 每次优先走 f 最小的点

Open 和 Closed 是什么？

A* 里有两个重要集合：

Open List：待检查的格子
Closed Set：已经检查过的格子

流程大概是：

1. 把起点放进 Open List
2. 每次从 Open List 里拿 f 最小的格子
3. 检查它周围的邻居
4. 如果邻居能走，并且从当前格子过去更短，就更新邻居
5. 记录邻居的 parent，用来最后还原路径
6. 找到终点后，从终点沿 parent 倒推回起点

C# 基础版代码

这个版本用 List<Node> 做 Open List，方便你看懂原理。项目里大量寻路时，可以把 List 换成小根堆或优先队列。

using System; // 引入 System 命名空间，用来使用 Math.Abs 等基础功能
using System.Collections.Generic; // 引入集合命名空间，用来使用 List
public class AStarPathfinder // 定义 A* 寻路类
{ // AStarPathfinder 类开始
    private class Node // 定义节点类，每个格子对应一个节点
    { // Node 类开始
        public int X; // 节点的行坐标
        public int Y; // 节点的列坐标
        public int G; // 从起点走到当前节点的真实代价
        public int H; // 从当前节点到终点的预估代价
        public int F => G == int.MaxValue ? int.MaxValue : G + H; // 当前节点的综合评分，F 等于 G 加 H
        public Node Parent; // 当前节点的父节点，用来最后还原路径
        public Node(int x, int y) // 定义节点构造函数
        { // 构造函数开始
            X = x; // 保存行坐标
            Y = y; // 保存列坐标
            G = int.MaxValue; // 初始真实代价设为极大值，表示暂时不可达
            H = 0; // 初始预估代价设为 0
            Parent = null; // 初始父节点为空
        } // 构造函数结束
    } // Node 类结束
    public List<(int x, int y)> FindPath(int[,] grid, (int x, int y) start, (int x, int y) goal) // 定义寻路函数，输入地图、起点和终点，返回路径坐标
    { // FindPath 函数开始
        int rows = grid.GetLength(0); // 获取地图行数
        int cols = grid.GetLength(1); // 获取地图列数
        Node[,] nodes = new Node[rows, cols]; // 创建节点数组，让每个格子都有一个 Node
        bool[,] closed = new bool[rows, cols]; // 创建 Closed 数组，记录哪些格子已经处理过
        List<Node> openList = new List<Node>(); // 创建 Open List，保存待检查的节点
        for (int x = 0; x < rows; x++) // 遍历每一行
        { // 外层 for 循环开始
            for (int y = 0; y < cols; y++) // 遍历每一列
            { // 内层 for 循环开始
                nodes[x, y] = new Node(x, y); // 为当前格子创建对应节点
            } // 内层 for 循环结束
        } // 外层 for 循环结束
        Node startNode = nodes[start.x, start.y]; // 获取起点节点
        startNode.G = 0; // 起点到自己的真实代价是 0
        startNode.H = Heuristic(start.x, start.y, goal.x, goal.y); // 计算起点到终点的预估代价
        openList.Add(startNode); // 把起点加入 Open List
        int[] dx = new int[] { -1, 1, 0, 0 }; // 定义四方向移动的行变化：上、下、左、右
        int[] dy = new int[] { 0, 0, -1, 1 }; // 定义四方向移动的列变化：上、下、左、右
        while (openList.Count > 0) // 只要 Open List 里还有待检查节点
        { // while 循环开始
            Node current = GetLowestFNode(openList); // 从 Open List 中取出 F 最小的节点
            openList.Remove(current); // 从 Open List 中移除当前节点
            closed[current.X, current.Y] = true; // 把当前节点标记为已经处理过
            if (current.X == goal.x && current.Y == goal.y) // 如果当前节点就是终点
            { // if 语句开始
                return BuildPath(current); // 根据父节点倒推路径并返回
            } // if 语句结束
            for (int dir = 0; dir < 4; dir++) // 遍历四个方向的邻居
            { // for 循环开始
                int nx = current.X + dx[dir]; // 计算邻居的行坐标
                int ny = current.Y + dy[dir]; // 计算邻居的列坐标
                if (!IsInside(nx, ny, rows, cols)) // 如果邻居坐标越界
                { // if 语句开始
                    continue; // 越界格子不能走，直接跳过
                } // if 语句结束
                if (grid[nx, ny] == 1) // 如果邻居是障碍物
                { // if 语句开始
                    continue; // 障碍格子不能走，直接跳过
                } // if 语句结束
                if (closed[nx, ny]) // 如果邻居已经在 Closed Set 里
                { // if 语句开始
                    continue; // 已处理过的格子不重复处理
                } // if 语句结束
                Node neighbor = nodes[nx, ny]; // 获取邻居节点对象
                int newG = current.G + 1; // 计算从当前节点走到邻居的新真实代价
                if (newG < neighbor.G) // 如果这条新路径比之前记录的路径更短
                { // if 语句开始
                    neighbor.G = newG; // 更新邻居的真实代价
                    neighbor.H = Heuristic(nx, ny, goal.x, goal.y); // 更新邻居到终点的预估代价
                    neighbor.Parent = current; // 记录邻居是从当前节点走过来的
                    if (!openList.Contains(neighbor)) // 如果邻居还不在 Open List 中
                    { // if 语句开始
                        openList.Add(neighbor); // 把邻居加入 Open List，等待后续检查
                    } // if 语句结束
                } // if 语句结束
            } // for 循环结束
        } // while 循环结束
        return new List<(int x, int y)>(); // 如果没有找到路径，返回空列表
    } // FindPath 函数结束
    private int Heuristic(int x1, int y1, int x2, int y2) // 定义启发函数，计算曼哈顿距离
    { // Heuristic 函数开始
        return Math.Abs(x1 - x2) + Math.Abs(y1 - y2); // 返回四方向网格常用的曼哈顿距离
    } // Heuristic 函数结束
    private bool IsInside(int x, int y, int rows, int cols) // 定义边界检查函数
    { // IsInside 函数开始
        return x >= 0 && x < rows && y >= 0 && y < cols; // 判断坐标是否在地图范围内
    } // IsInside 函数结束
    private Node GetLowestFNode(List<Node> openList) // 定义函数，从 Open List 中找 F 最小的节点
    { // GetLowestFNode 函数开始
        Node best = openList[0]; // 先假设第一个节点是最优节点
        for (int i = 1; i < openList.Count; i++) // 从第二个节点开始遍历
        { // for 循环开始
            Node node = openList[i]; // 取出当前遍历到的节点
            if (node.F < best.F || node.F == best.F && node.H < best.H) // 如果当前节点 F 更小，或者 F 相同但 H 更小
            { // if 语句开始
                best = node; // 更新最优节点
            } // if 语句结束
        } // for 循环结束
        return best; // 返回 F 最小的节点
    } // GetLowestFNode 函数结束
    private List<(int x, int y)> BuildPath(Node endNode) // 定义路径还原函数
    { // BuildPath 函数开始
        List<(int x, int y)> path = new List<(int x, int y)>(); // 创建路径列表
        Node current = endNode; // 从终点开始往父节点倒推
        while (current != null) // 只要当前节点不为空
        { // while 循环开始
            path.Add((current.X, current.Y)); // 把当前节点坐标加入路径
            current = current.Parent; // 移动到父节点
        } // while 循环结束
        path.Reverse(); // 因为刚才是从终点倒推到起点，所以需要反转
        return path; // 返回从起点到终点的路径
    } // BuildPath 函数结束
} // AStarPathfinder 类结束

怎么使用这个代码？

int[,] grid = new int[,] { { 0, 0, 0 }, { 1, 1, 0 }, { 0, 0, 0 } }; // 创建地图，0 表示可走，1 表示障碍
AStarPathfinder finder = new AStarPathfinder(); // 创建 A* 寻路对象
List<(int x, int y)> path = finder.FindPath(grid, (0, 0), (2, 2)); // 从左上角寻路到右下角

复杂度

这个基础版用 List 找最小 F：

时间复杂度：最坏接近 O(V²)
空间复杂度：O(V)

如果换成小根堆 / 优先队列：

时间复杂度：O(E log V)
空间复杂度：O(V)

其中：

V 是节点数量
E 是边数量

面试高分回答

TIP

A* 是一种启发式最短路径算法。它在 Dijkstra 的基础上加入了启发函数 h，用 f = g + h 评估节点优先级。其中 g 是起点到当前节点的真实代价，h 是当前节点到终点的预估代价，f 越小表示越值得优先搜索。算法维护 Open List 和 Closed Set，每次从 Open List 中取出 f 最小的节点，检查它的邻居，如果通过当前节点到邻居的路径更短，就更新邻居的 g、h 和父节点。找到终点后，通过父节点从终点反向还原路径。四方向网格中常用曼哈顿距离作为启发函数。A* 当 h = 0 时就退化成 Dijkstra。

BFS 和 A* 区别是什么？

一句话区别BFS 是“一圈一圈扩散”，适合无权图或者每条边代价都一样的图。 A* 是“带方向感的搜索”，会用 f = g + h 优先搜索更可能靠近终点的节点。

BFS 是什么？

BFS 叫广度优先搜索。

它的特点是：

从起点开始，先搜索距离 1 步的点，再搜索距离 2 步的点，再搜索距离 3 步的点。

所以它像水波一样往外扩散。

如果地图里每走一步代价都一样，那么：

BFS 第一次到达终点时，一定是最短步数。

比如普通网格里：

上、下、左、右移动，每走一格成本都是 1

这种情况用 BFS 很合适。

A* 是什么？

A* 是启发式寻路算法。

它不只是看：

我已经走了多远

还会看：

我离终点大概还有多远

核心公式是：

f = g + h

其中：

g：从起点走到当前点的真实代价
h：从当前点到终点的预估代价
f：综合评分，越小越优先搜索

所以 A* 比 BFS 更有方向感。 它不会像 BFS 那样平均向四周扩散，而是更愿意朝终点方向走。

核心对比

对比点	BFS	A*
搜索方式	一层一层扩散	优先搜索 f 最小的节点
是否有方向感	没有	有
是否使用估价	不使用	使用 h 启发函数
常用结构	Queue	Open List / PriorityQueue
适合场景	无权图、等权图	游戏寻路、地图寻路
最短路保证	等权图保证最短	h 不高估时保证最短
性能特点	可能扩散很多无关节点	通常更快靠近终点

BFS 的 C# 基础代码

下面是网格 BFS，0 表示可走，1 表示障碍。

using System.Collections.Generic; // 引入集合命名空间，用来使用 Queue、List
public class BfsPathfinder // 定义 BFS 寻路类
{ // BfsPathfinder 类开始
    public int ShortestPath(int[,] grid, (int x, int y) start, (int x, int y) goal) // 定义 BFS 最短步数函数
    { // ShortestPath 函数开始
        int rows = grid.GetLength(0); // 获取地图行数
        int cols = grid.GetLength(1); // 获取地图列数
        bool[,] visited = new bool[rows, cols]; // 创建访问数组，记录格子是否访问过
        Queue<(int x, int y, int step)> queue = new Queue<(int x, int y, int step)>(); // 创建队列，保存坐标和步数
        queue.Enqueue((start.x, start.y, 0)); // 把起点加入队列，起点步数是 0
        visited[start.x, start.y] = true; // 标记起点已经访问过
        int[] dx = new int[] { -1, 1, 0, 0 }; // 定义四方向的行变化
        int[] dy = new int[] { 0, 0, -1, 1 }; // 定义四方向的列变化
        while (queue.Count > 0) // 只要队列里还有节点
        { // while 循环开始
            var current = queue.Dequeue(); // 取出队首节点，BFS 按先进先出扩展
            if (current.x == goal.x && current.y == goal.y) // 如果当前节点是终点
            { // if 语句开始
                return current.step; // 返回当前步数，这就是最短步数
            } // if 语句结束
            for (int i = 0; i < 4; i++) // 遍历四个方向
            { // for 循环开始
                int nx = current.x + dx[i]; // 计算邻居行坐标
                int ny = current.y + dy[i]; // 计算邻居列坐标
                if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) // 判断邻居是否越界
                { // if 语句开始
                    continue; // 越界不能走，跳过
                } // if 语句结束
                if (grid[nx, ny] == 1 || visited[nx, ny]) // 如果是障碍或者已经访问过
                { // if 语句开始
                    continue; // 不能重复走，跳过
                } // if 语句结束
                visited[nx, ny] = true; // 标记邻居已经访问
                queue.Enqueue((nx, ny, current.step + 1)); // 把邻居加入队列，步数加 1
            } // for 循环结束
        } // while 循环结束
        return -1; // 如果找不到终点，返回 -1
    } // ShortestPath 函数结束
} // BfsPathfinder 类结束

A* 的 C# 核心区别代码

A* 的完整代码我前面已经给过，这里只看它和 BFS 最不同的地方： BFS 是 Queue，A* 是每次找 F 最小的节点。

private Node GetLowestFNode(List<Node> openList) // 从 Open List 中找出 F 最小的节点
{ // GetLowestFNode 函数开始
    Node best = openList[0]; // 先假设第一个节点是最优节点
    for (int i = 1; i < openList.Count; i++) // 从第二个节点开始遍历
    { // for 循环开始
        Node node = openList[i]; // 取出当前节点
        if (node.F < best.F || node.F == best.F && node.H < best.H) // 如果 F 更小，或者 F 相同但 H 更小
        { // if 语句开始
            best = node; // 更新当前最优节点
        } // if 语句结束
    } // for 循环结束
    return best; // 返回 F 最小的节点
} // GetLowestFNode 函数结束

怎么选择？

如果面试官问你实际项目里怎么选，可以这样说：

如果是无权图，或者每一步代价都一样，只要求最短步数，用 BFS。
如果是游戏地图寻路，有明确目标点，希望减少搜索范围，用 A*。
如果边权不同但没有启发方向，可以用 Dijkstra。
如果 A* 的 h = 0，它就退化成 Dijkstra。

面试高分回答

NOTE

BFS 和 A* 都可以用来做路径搜索，但适用场景不同。BFS 使用队列，按层扩展节点，在无权图或等权图中，第一次到达终点就是最短路径。A* 使用 f = g + h 作为节点优先级，其中 g 是起点到当前节点的真实代价，h 是当前节点到终点的估计代价，因此它比 BFS 更有方向性，通常能减少大量无关节点的搜索。BFS 不需要启发函数，实现简单但可能扩散范围大；A* 更适合游戏寻路，但启发函数要设计合理，不能高估真实代价，否则可能无法保证最短路径。

如何做地图网格寻路？

地图网格寻路怎么做？ 核心思路是：先把地图切成一个个格子，每个格子记录“能不能走”，然后用 BFS 或 A* 找出从起点到终点的一串格子坐标，最后让角色沿着这些坐标移动。

一般游戏里会这样做：

地图 → 网格数据 → 判断可走/不可走 → A* 搜索 → 得到路径 → 角色移动

网格数据怎么表示？

最简单可以用二维数组：

0 表示可走
1 表示障碍

比如：

0 0 0 0
1 1 0 0
0 0 0 1
0 1 0 0

在代码里就是：

int[,] grid = new int[,] // 创建二维数组表示地图
{ // 地图数组开始
    { 0, 0, 0, 0 }, // 第 0 行，0 表示可走
    { 1, 1, 0, 0 }, // 第 1 行，1 表示障碍
    { 0, 0, 0, 1 }, // 第 2 行
    { 0, 1, 0, 0 } // 第 3 行
}; // 地图数组结束

实际项目流程

第一步，把世界坐标转成网格坐标：

角色点击了世界坐标 worldPos
把 worldPos 转成 gridX、gridY

第二步，判断起点和终点是否合法：

不能越界
不能是障碍

第三步，用 A* 搜索路径。

第四步，把路径里的格子坐标转回世界坐标。

第五步，让角色依次移动到这些点。

C# A* 网格寻路代码

下面是一个基础可读版。 它适合面试讲原理，也适合小地图测试。

using System; // 引入 System 命名空间，用来使用 Math.Abs
using System.Collections.Generic; // 引入集合命名空间，用来使用 List
public class GridAStar // 定义网格 A* 寻路类
{ // GridAStar 类开始
    private class Node // 定义节点类，每个格子对应一个节点
    { // Node 类开始
        public int X; // 节点所在的行坐标
        public int Y; // 节点所在的列坐标
        public int G; // 从起点走到当前节点的真实代价
        public int H; // 从当前节点到终点的预估代价
        public int F => G + H; // 当前节点的综合评分，F 等于 G 加 H
        public Node Parent; // 当前节点的父节点，用来最后还原路径
        public Node(int x, int y) // 定义节点构造函数
        { // 构造函数开始
            X = x; // 保存行坐标
            Y = y; // 保存列坐标
            G = int.MaxValue; // 初始真实代价设为极大值，表示暂时不可达
            H = 0; // 初始预估代价设为 0
            Parent = null; // 初始父节点为空
        } // 构造函数结束
    } // Node 类结束
    public List<(int x, int y)> FindPath(int[,] grid, (int x, int y) start, (int x, int y) end) // 定义寻路函数，输入地图、起点和终点
    { // FindPath 函数开始
        int rows = grid.GetLength(0); // 获取地图行数
        int cols = grid.GetLength(1); // 获取地图列数
        if (!CanWalk(grid, start.x, start.y)) // 如果起点不能走
        { // if 语句开始
            return new List<(int x, int y)>(); // 返回空路径
        } // if 语句结束
        if (!CanWalk(grid, end.x, end.y)) // 如果终点不能走
        { // if 语句开始
            return new List<(int x, int y)>(); // 返回空路径
        } // if 语句结束
        Node[,] nodes = new Node[rows, cols]; // 创建节点数组
        bool[,] closed = new bool[rows, cols]; // 创建关闭列表标记数组
        List<Node> open = new List<Node>(); // 创建开放列表
        for (int x = 0; x < rows; x++) // 遍历每一行
        { // 外层 for 循环开始
            for (int y = 0; y < cols; y++) // 遍历每一列
            { // 内层 for 循环开始
                nodes[x, y] = new Node(x, y); // 给每个格子创建一个节点对象
            } // 内层 for 循环结束
        } // 外层 for 循环结束
        Node startNode = nodes[start.x, start.y]; // 获取起点节点
        startNode.G = 0; // 起点到自己的真实代价是 0
        startNode.H = Heuristic(start.x, start.y, end.x, end.y); // 计算起点到终点的预估代价
        open.Add(startNode); // 把起点加入开放列表
        int[] dx = new int[] { -1, 1, 0, 0 }; // 定义四方向行变化
        int[] dy = new int[] { 0, 0, -1, 1 }; // 定义四方向列变化
        while (open.Count > 0) // 只要开放列表还有节点
        { // while 循环开始
            Node current = GetBestNode(open); // 取出 F 最小的节点
            open.Remove(current); // 从开放列表移除当前节点
            closed[current.X, current.Y] = true; // 把当前节点加入关闭列表
            if (current.X == end.x && current.Y == end.y) // 如果当前节点就是终点
            { // if 语句开始
                return BuildPath(current); // 还原路径并返回
            } // if 语句结束
            for (int i = 0; i < 4; i++) // 遍历四个方向
            { // for 循环开始
                int nx = current.X + dx[i]; // 计算邻居行坐标
                int ny = current.Y + dy[i]; // 计算邻居列坐标
                if (!CanWalk(grid, nx, ny)) // 如果邻居不能走
                { // if 语句开始
                    continue; // 跳过这个邻居
                } // if 语句结束
                if (closed[nx, ny]) // 如果邻居已经处理过
                { // if 语句开始
                    continue; // 跳过这个邻居
                } // if 语句结束
                Node neighbor = nodes[nx, ny]; // 获取邻居节点
                int newG = current.G + 1; // 计算从当前节点走到邻居的新代价
                if (newG < neighbor.G) // 如果新路径比旧路径更短
                { // if 语句开始
                    neighbor.G = newG; // 更新邻居真实代价
                    neighbor.H = Heuristic(nx, ny, end.x, end.y); // 更新邻居预估代价
                    neighbor.Parent = current; // 记录邻居从当前节点走来
                    if (!open.Contains(neighbor)) // 如果邻居还不在开放列表里
                    { // if 语句开始
                        open.Add(neighbor); // 把邻居加入开放列表
                    } // if 语句结束
                } // if 语句结束
            } // for 循环结束
        } // while 循环结束
        return new List<(int x, int y)>(); // 找不到路径时返回空路径
    } // FindPath 函数结束
    private bool CanWalk(int[,] grid, int x, int y) // 定义格子是否可走的判断函数
    { // CanWalk 函数开始
        int rows = grid.GetLength(0); // 获取地图行数
        int cols = grid.GetLength(1); // 获取地图列数
        if (x < 0 || x >= rows || y < 0 || y >= cols) // 如果坐标越界
        { // if 语句开始
            return false; // 越界不可走
        } // if 语句结束
        return grid[x, y] == 0; // 只有值为 0 的格子可以走
    } // CanWalk 函数结束
    private int Heuristic(int x1, int y1, int x2, int y2) // 定义启发函数
    { // Heuristic 函数开始
        return Math.Abs(x1 - x2) + Math.Abs(y1 - y2); // 返回曼哈顿距离
    } // Heuristic 函数结束
    private Node GetBestNode(List<Node> open) // 定义从开放列表中取最优节点的函数
    { // GetBestNode 函数开始
        Node best = open[0]; // 先假设第一个节点最优
        for (int i = 1; i < open.Count; i++) // 遍历开放列表中的其他节点
        { // for 循环开始
            Node node = open[i]; // 取出当前节点
            if (node.F < best.F || node.F == best.F && node.H < best.H) // 如果 F 更小，或者 F 相同但 H 更小
            { // if 语句开始
                best = node; // 更新最优节点
            } // if 语句结束
        } // for 循环结束
        return best; // 返回最优节点
    } // GetBestNode 函数结束
    private List<(int x, int y)> BuildPath(Node endNode) // 定义路径还原函数
    { // BuildPath 函数开始
        List<(int x, int y)> path = new List<(int x, int y)>(); // 创建路径列表
        Node current = endNode; // 从终点开始倒推
        while (current != null) // 只要当前节点不为空
        { // while 循环开始
            path.Add((current.X, current.Y)); // 把当前节点坐标加入路径
            current = current.Parent; // 继续移动到父节点
        } // while 循环结束
        path.Reverse(); // 反转路径，变成从起点到终点
        return path; // 返回最终路径
    } // BuildPath 函数结束
} // GridAStar 类结束

怎么调用？

int[,] grid = new int[,] { { 0, 0, 0 }, { 1, 1, 0 }, { 0, 0, 0 } }; // 创建地图，0 可走，1 障碍
GridAStar astar = new GridAStar(); // 创建 A* 寻路对象
List<(int x, int y)> path = astar.FindPath(grid, (0, 0), (2, 2)); // 从左上角寻找路径到右下角

Unity 里还要做什么？

面试时可以补一句工程化内容：

算法返回的是格子坐标，Unity 角色移动需要世界坐标。

所以通常还要写：

GridToWorld：网格坐标转世界坐标
WorldToGrid：世界坐标转网格坐标

比如：

gridX = Mathf.FloorToInt(worldPos.x / cellSize)
gridY = Mathf.FloorToInt(worldPos.z / cellSize)

然后角色按路径点移动：

path[0] → path[1] → path[2] → ... → 终点

面试高分回答

NOTE

地图网格寻路通常先把地图离散成二维网格，每个格子记录是否可走。起点和终点先从世界坐标转换成网格坐标，然后使用 BFS 或 A* 搜索路径。BFS 适合所有边代价都一样、地图较简单的情况；游戏里更常用 A*，因为它通过 f = g + h 同时考虑已走代价和到终点的预估代价，可以减少无关节点搜索。搜索时维护 Open List 和 Closed Set，更新邻居节点的 gCost、hCost 和 parent，找到终点后通过 parent 从终点反向还原路径。实际项目中还要处理世界坐标和网格坐标转换、动态障碍、路径平滑、分帧寻路和路径缓存。

如何做视野检测？

视野检测是什么？ 视野检测就是判断一个角色，比如怪物、NPC、守卫，能不能“看到”目标，比如玩家。

游戏里一般不是简单判断距离，而是三步：

1. 距离够不够近
2. 角度是不是在正前方视野范围内
3. 中间有没有墙、障碍物挡住

只有三个条件都满足，才算真正看见目标。

核心判断流程

假设 NPC 有一个视野：

视野半径 viewRadius = 10
视野角度 viewAngle = 90

意思是：

NPC 最远能看 10 米
只能看到正前方左右各 45 度范围内的目标

所以判断目标能不能被看到，要这样：

先看目标是否在 10 米内
再看目标是否在正前方 90 度扇形里
最后用射线检查中间有没有墙

为什么不能只判断距离？

因为只判断距离会出现这种问题：

玩家站在 NPC 背后
距离很近
但是 NPC 不应该看到玩家

所以还要判断角度。

为什么不能只判断角度？

因为玩家虽然在正前方，但可能非常远：

方向对了
但是超过视野距离

所以还要判断距离。

为什么还要 Raycast？

因为玩家可能在正前方，也在距离内，但是中间有墙。

NPC ---- 墙 ---- 玩家

这种情况 NPC 不应该看到玩家。

所以最后要用：

Physics.Raycast

检测中间有没有障碍物。

Unity C# 代码

下面是最常见的 Unity 视野检测写法。

using UnityEngine; // 引入 UnityEngine 命名空间，用来使用 MonoBehaviour、Transform、Physics 等 Unity API
using System.Collections.Generic; // 引入集合命名空间，用来使用 List
public class FieldOfViewDetector : MonoBehaviour // 定义视野检测组件类，挂在 NPC 或怪物身上
{ // FieldOfViewDetector 类开始
    public float viewRadius = 10f; // 定义视野半径，表示最多能看多远
    public float viewAngle = 90f; // 定义视野角度，表示正前方扇形范围是多少度
    public float eyeHeight = 1.6f; // 定义眼睛高度，避免射线从脚底发出
    public LayerMask targetMask; // 定义目标层，比如 Player 层
    public LayerMask obstacleMask; // 定义障碍层，比如 Wall 层
    public List<Transform> visibleTargets = new List<Transform>(); // 保存当前能看到的目标列表
    private void Update() // Unity 每帧调用 Update
    { // Update 函数开始
        FindVisibleTargets(); // 每帧执行视野检测
    } // Update 函数结束
    private void FindVisibleTargets() // 定义查找可见目标的函数
    { // FindVisibleTargets 函数开始
        visibleTargets.Clear(); // 每次检测前先清空上一帧看到的目标
        Vector3 eyePosition = transform.position + Vector3.up * eyeHeight; // 计算眼睛位置，用来作为射线起点
        Collider[] targetsInRadius = Physics.OverlapSphere(transform.position, viewRadius, targetMask); // 找到视野半径内所有目标层碰撞体
        for (int i = 0; i < targetsInRadius.Length; i++) // 遍历所有范围内目标
        { // for 循环开始
            Transform target = targetsInRadius[i].transform; // 获取当前目标的 Transform
            Vector3 targetPosition = target.position + Vector3.up * eyeHeight; // 计算目标大概眼睛高度的位置
            Vector3 directionToTarget = (targetPosition - eyePosition).normalized; // 计算从 NPC 眼睛指向目标的单位方向
            float angleToTarget = Vector3.Angle(transform.forward, directionToTarget); // 计算 NPC 正前方和目标方向之间的夹角
            if (angleToTarget > viewAngle * 0.5f) // 如果目标不在视野角度的一半范围内
            { // if 语句开始
                continue; // 角度不满足，跳过这个目标
            } // if 语句结束
            float distanceToTarget = Vector3.Distance(eyePosition, targetPosition); // 计算 NPC 眼睛到目标位置的距离
            bool blocked = Physics.Raycast(eyePosition, directionToTarget, distanceToTarget, obstacleMask); // 发射射线检查中间有没有障碍物
            if (blocked) // 如果射线打到了障碍物
            { // if 语句开始
                continue; // 被障碍物挡住，跳过这个目标
            } // if 语句结束
            visibleTargets.Add(target); // 距离、角度、遮挡都通过，把目标加入可见列表
        } // for 循环结束
    } // FindVisibleTargets 函数结束
} // FieldOfViewDetector 类结束

代码执行顺序

这段代码每帧大概做了这些事：

1. 清空 visibleTargets
2. 用 OverlapSphere 找到半径内的目标
3. 对每个目标计算方向
4. 用 Vector3.Angle 判断是否在视野扇形内
5. 用 Raycast 判断中间有没有墙
6. 如果都通过，就加入 visibleTargets

为什么用 OverlapSphere？

因为直接遍历场景里所有玩家、怪物、单位会很浪费。

OverlapSphere 的作用是：

先粗略找出附近的目标

这一步叫：

宽阶段筛选

先把明显太远的目标过滤掉。

然后再对少量目标做角度和射线判断。

为什么射线起点要加 eyeHeight？

如果从角色脚底发射射线：

transform.position

可能会被地面、台阶、低矮碰撞体影响。

所以通常用：

transform.position + Vector3.up * eyeHeight

表示从眼睛高度看出去，更符合实际视觉。

优化版：不要每帧检测

如果敌人很多，每帧都做 OverlapSphere 和 Raycast 会比较贵。

可以改成隔一段时间检测一次。

using UnityEngine; // 引入 UnityEngine 命名空间，用来使用 MonoBehaviour 和 Time
public class VisionTick : MonoBehaviour // 定义间隔检测组件
{ // VisionTick 类开始
    public FieldOfViewDetector detector; // 保存视野检测组件引用
    public float checkInterval = 0.1f; // 定义检测间隔，0.1 秒检测一次
    private float timer = 0f; // 定义计时器
    private void Update() // Unity 每帧调用 Update
    { // Update 函数开始
        timer += Time.deltaTime; // 累加上一帧到这一帧经过的时间
        if (timer < checkInterval) // 如果还没到检测间隔
        { // if 语句开始
            return; // 直接返回，不执行检测
        } // if 语句结束
        timer = 0f; // 重置计时器
        SendMessage("FindVisibleTargets", SendMessageOptions.DontRequireReceiver); // 调用检测函数，示例写法，实际项目更建议直接调用公开方法
    } // Update 函数结束
} // VisionTick 类结束

更推荐的优化方式

上面的 SendMessage 是为了演示“间隔调用”，项目里我更推荐把检测函数改成 public，然后直接调用。

public void FindVisibleTargets() // 把检测函数改成 public，方便外部组件直接调用
{ // 函数开始
    // 这里放原来的视野检测逻辑 // 保留原来的检测逻辑
} // 函数结束

更高性能：用 Dot 替代 Angle

Vector3.Angle 好理解，但内部会算角度，性能略贵。

可以用点积优化。

判断逻辑是：

两个方向越接近，Dot 越接近 1
两个方向垂直，Dot 接近 0
两个方向相反，Dot 接近 -1

优化版判断：

float cosHalfAngle = Mathf.Cos(viewAngle * 0.5f * Mathf.Deg2Rad); // 计算半视野角的余弦值
float dot = Vector3.Dot(transform.forward, directionToTarget); // 计算正前方和目标方向的点积
if (dot < cosHalfAngle) // 如果点积小于半视野角余弦值
{ // if 语句开始
    continue; // 说明目标不在视野扇形内，跳过
} // if 语句结束

Unity 项目里常见注意点

视野检测通常要注意：

targetMask 只选 Player 或 Enemy，不要把所有层都放进去。
obstacleMask 只选 Wall、Ground、Obstacle 等遮挡层。
Raycast 起点不要从脚底发射，最好从眼睛位置。
如果 NPC 很多，不要每帧全部检测，可以分帧或间隔检测。
如果是 2D 游戏，用 Physics2D.OverlapCircle 和 Physics2D.Raycast。
如果是潜行游戏，可以把光照、蹲伏、草丛、隐身状态加入最终权重。

面试高分回答

NOTE

视野检测一般分成距离、角度和遮挡三步。首先用 Physics.OverlapSphere 找到视野半径内的候选目标，这是宽阶段筛选；然后计算 NPC 正前方 transform.forward 和目标方向之间的夹角，判断目标是否在视野扇形内；最后从 NPC 眼睛位置向目标发射 Raycast，如果中间没有命中障碍层，才认为目标可见。实际项目中要设置好 targetMask 和 obstacleMask，避免检测无关物体。大量 NPC 时不要每帧全部检测，可以间隔检测、分帧检测，或者用点积 Vector3.Dot 替代 Vector3.Angle 做角度判断，提高性能。

如何做碰撞检测 broad phase？

Broad Phase 是什么？ 碰撞检测一般分两步：

Broad Phase：宽阶段，先快速找出“可能碰撞”的对象对
Narrow Phase：窄阶段，再对这些候选对做精确碰撞检测

一句话理解：

Broad Phase 负责快速排除大量不可能碰撞的对象。

比如场景里有 1000 个物体，如果暴力两两检测：

1000 * 999 / 2 = 499500 对

这太贵了。

Broad Phase 的目标是把它变成：

只检测附近的几十对或几百对

为什么需要 Broad Phase？

假设你有很多物体：

玩家
怪物
子弹
墙体
掉落物
机关

如果每个物体都和其他所有物体检测一次，复杂度是：

O(N²)

物体数量越多，性能下降越明显。

Broad Phase 会先用比较便宜的方式判断：

这两个物体离得很远，不可能碰撞
这两个物体在同一片区域，可能碰撞

然后只把“可能碰撞”的对象交给窄阶段。

Broad Phase 允许误判，但不能漏判

Broad Phase 可以出现：

false positive：看起来可能碰撞，但精确检测后发现没碰

这是可以接受的。

但不能出现：

false negative：明明会碰撞，却被 Broad Phase 过滤掉

这是严重错误。

所以 Broad Phase 的原则是：

宁愿多给一些候选对，也不能漏掉真实碰撞对。

常见 Broad Phase 方法

常见方案有这些：

AABB 包围盒
Uniform Grid 均匀网格
Spatial Hash 空间哈希
Sweep and Prune 扫描排序
QuadTree 四叉树
Octree 八叉树
BVH 包围体层次结构

面试里最常讲的是：

AABB + Uniform Grid

因为容易理解，也很适合游戏场景。

AABB 是什么？

AABB 全称是：

Axis-Aligned Bounding Box

中文叫：

轴对齐包围盒

它是一个不旋转的矩形或盒子，用来粗略包住物体。

2D 里可以表示成：

MinX, MinY, MaxX, MaxY

两个 AABB 是否相交，可以这样判断：

A 的右边 >= B 的左边
A 的左边 <= B 的右边
A 的上边 >= B 的下边
A 的下边 <= B 的上边

Uniform Grid 怎么做？

Uniform Grid 就是把地图切成很多固定大小的格子。

流程是：

1. 把空间切成格子
2. 每个物体根据 AABB 放入它覆盖到的格子
3. 同一个格子里的物体两两生成候选对
4. 对候选对去重
5. 把候选对交给 Narrow Phase

比如：

A 和 B 在同一个格子里

那么：

(A, B) 是候选碰撞对

但它们不一定真的碰撞。 后面还要做精确检测。

C# 示例：Uniform Grid Broad Phase

下面代码实现的是 2D 版本的宽阶段。 它输入一组带 AABB 的物体，输出“可能碰撞”的对象对。

using System; // 引入 System 命名空间，用来使用 Math.Floor
using System.Collections.Generic; // 引入集合命名空间，用来使用 List、Dictionary、HashSet
public struct Aabb2D // 定义 2D AABB 包围盒结构体
{ // Aabb2D 结构体开始
    public float MinX; // 包围盒最小 X 坐标
    public float MinY; // 包围盒最小 Y 坐标
    public float MaxX; // 包围盒最大 X 坐标
    public float MaxY; // 包围盒最大 Y 坐标
    public Aabb2D(float minX, float minY, float maxX, float maxY) // 定义 AABB 构造函数
    { // 构造函数开始
        MinX = minX; // 保存最小 X 坐标
        MinY = minY; // 保存最小 Y 坐标
        MaxX = maxX; // 保存最大 X 坐标
        MaxY = maxY; // 保存最大 Y 坐标
    } // 构造函数结束
} // Aabb2D 结构体结束
public class Body2D // 定义参与碰撞检测的物体类
{ // Body2D 类开始
    public int Id; // 物体唯一编号
    public Aabb2D Bounds; // 物体的 AABB 包围盒
    public Body2D(int id, Aabb2D bounds) // 定义物体构造函数
    { // 构造函数开始
        Id = id; // 保存物体编号
        Bounds = bounds; // 保存物体包围盒
    } // 构造函数结束
} // Body2D 类结束
public struct Pair // 定义候选碰撞对结构体
{ // Pair 结构体开始
    public int A; // 候选对中的第一个物体编号
    public int B; // 候选对中的第二个物体编号
    public Pair(int a, int b) // 定义候选对构造函数
    { // 构造函数开始
        A = Math.Min(a, b); // 把较小编号放在 A，方便去重
        B = Math.Max(a, b); // 把较大编号放在 B，方便去重
    } // 构造函数结束
} // Pair 结构体结束
public class UniformGridBroadPhase // 定义均匀网格宽阶段类
{ // UniformGridBroadPhase 类开始
    private readonly float cellSize; // 保存每个网格的尺寸
    private readonly Dictionary<(int x, int y), List<Body2D>> cells; // 保存每个格子里有哪些物体
    public UniformGridBroadPhase(float cellSize) // 定义宽阶段构造函数
    { // 构造函数开始
        this.cellSize = cellSize; // 保存传入的格子大小
        cells = new Dictionary<(int x, int y), List<Body2D>>(); // 创建格子字典
    } // 构造函数结束
    public List<Pair> ComputePairs(List<Body2D> bodies) // 定义计算候选碰撞对的函数
    { // ComputePairs 函数开始
        cells.Clear(); // 每帧重新构建网格前，先清空旧数据
        for (int i = 0; i < bodies.Count; i++) // 遍历所有物体
        { // for 循环开始
            InsertBody(bodies[i]); // 把当前物体插入它覆盖到的格子
        } // for 循环结束
        HashSet<string> pairKeys = new HashSet<string>(); // 创建字符串集合，用来给候选对去重
        List<Pair> pairs = new List<Pair>(); // 创建候选对列表
        foreach (List<Body2D> list in cells.Values) // 遍历每一个格子里的物体列表
        { // foreach 循环开始
            for (int i = 0; i < list.Count; i++) // 枚举格子里的第一个物体
            { // 外层 for 循环开始
                for (int j = i + 1; j < list.Count; j++) // 枚举格子里的第二个物体
                { // 内层 for 循环开始
                    Pair pair = new Pair(list[i].Id, list[j].Id); // 创建一个候选碰撞对
                    string key = pair.A + "_" + pair.B; // 创建候选对唯一 key，避免重复添加
                    if (pairKeys.Contains(key)) // 如果这个候选对已经出现过
                    { // if 语句开始
                        continue; // 跳过重复候选对
                    } // if 语句结束
                    pairKeys.Add(key); // 记录这个候选对已经出现
                    pairs.Add(pair); // 把候选对加入结果列表
                } // 内层 for 循环结束
            } // 外层 for 循环结束
        } // foreach 循环结束
        return pairs; // 返回所有候选碰撞对
    } // ComputePairs 函数结束
    private void InsertBody(Body2D body) // 定义插入物体到网格的函数
    { // InsertBody 函数开始
        int minCellX = ToCell(body.Bounds.MinX); // 计算包围盒左边所在的格子 X
        int minCellY = ToCell(body.Bounds.MinY); // 计算包围盒下边所在的格子 Y
        int maxCellX = ToCell(body.Bounds.MaxX); // 计算包围盒右边所在的格子 X
        int maxCellY = ToCell(body.Bounds.MaxY); // 计算包围盒上边所在的格子 Y
        for (int x = minCellX; x <= maxCellX; x++) // 遍历包围盒覆盖到的所有格子 X
        { // 外层 for 循环开始
            for (int y = minCellY; y <= maxCellY; y++) // 遍历包围盒覆盖到的所有格子 Y
            { // 内层 for 循环开始
                (int x, int y) key = (x, y); // 创建当前格子的 key
                if (!cells.ContainsKey(key)) // 如果当前格子还没有物体列表
                { // if 语句开始
                    cells[key] = new List<Body2D>(); // 给当前格子创建物体列表
                } // if 语句结束
                cells[key].Add(body); // 把当前物体加入这个格子
            } // 内层 for 循环结束
        } // 外层 for 循环结束
    } // InsertBody 函数结束
    private int ToCell(float value) // 定义世界坐标转格子坐标的函数
    { // ToCell 函数开始
        return (int)Math.Floor(value / cellSize); // 用坐标除以格子大小并向下取整
    } // ToCell 函数结束
} // UniformGridBroadPhase 类结束

怎么使用？

List<Body2D> bodies = new List<Body2D>(); // 创建物体列表
bodies.Add(new Body2D(1, new Aabb2D(0f, 0f, 1f, 1f))); // 添加编号 1 的物体
bodies.Add(new Body2D(2, new Aabb2D(0.8f, 0.8f, 2f, 2f))); // 添加编号 2 的物体
bodies.Add(new Body2D(3, new Aabb2D(10f, 10f, 11f, 11f))); // 添加编号 3 的远处物体
UniformGridBroadPhase broadPhase = new UniformGridBroadPhase(2f); // 创建格子大小为 2 的宽阶段对象
List<Pair> pairs = broadPhase.ComputePairs(bodies); // 计算所有可能碰撞的候选对

为什么要去重？

因为一个物体的 AABB 可能覆盖多个格子。

比如物体 A 和物体 B 同时覆盖了两个格子：

cell(1,1)
cell(1,2)

如果不去重，就会生成两次：

(A, B)
(A, B)

所以代码里用了：

HashSet

来保证每个候选对只出现一次。

格子大小怎么选？

格子大小很关键。

如果格子太大：

很多物体都落在同一个格子里
候选对还是很多

如果格子太小：

一个大物体会覆盖很多格子
插入和去重成本变高

经验上：

格子大小可以接近常见物体的平均尺寸或最大尺寸。

如果物体大小差异特别大，Uniform Grid 可能不是最好选择，可以考虑：

QuadTree
BVH
分层 Grid

Broad Phase 常见方案怎么选？

Uniform Grid：

适合大量大小差不多的物体，比如弹幕、小游戏单位、2D 碰撞。

Spatial Hash：

本质类似网格，但不用真的开巨大二维数组，适合无限地图或稀疏地图。

Sweep and Prune：

按 X 轴或多个轴排序，适合物体移动比较平滑的场景。

QuadTree / Octree：

适合空间分布不均匀的场景。
2D 常用 QuadTree。
3D 常用 Octree。

BVH：

适合复杂模型、三角形、静态场景或物理引擎内部结构。

面试高分回答

CAUTION

碰撞检测通常分为 Broad Phase 和 Narrow Phase。Broad Phase 的作用是快速过滤掉不可能碰撞的对象对，避免所有物体两两检测导致 O(N²) 的开销。它一般使用 AABB、空间网格、空间哈希、Sweep and Prune、四叉树或 BVH 等结构生成候选碰撞对。Broad Phase 可以产生误报，也就是候选对最后不一定真的碰撞，但不能漏报真实碰撞。以 Uniform Grid 为例，会把空间划分成固定大小格子，每个物体根据自己的 AABB 插入覆盖到的格子，同一个格子内的物体两两生成候选对，并用 HashSet 去重，最后把候选对交给 Narrow Phase 做精确形状检测。实际项目中还要考虑层过滤、静态和动态物体分离、格子大小选择、大物体跨格子、重复 pair 去重和多线程更新等问题。

四叉树/八叉树有什么用？

四叉树 / 八叉树有什么用？ 它们都是“空间划分结构”。

一句话理解：

把一个大空间切成很多小区域，让我们快速找到某个范围附近有哪些对象。

比如游戏场景里有 10000 个怪物、子弹、掉落物，如果你每次都遍历全部对象，会很慢。 四叉树 / 八叉树可以帮你快速缩小范围：

不要查全世界，只查目标附近那几块区域。

四叉树是什么？

四叉树主要用于：

2D 平面

它会把一个矩形区域切成 4 份：

左上
右上
左下
右下

如果某个区域里的对象太多，就继续把这个区域再切成 4 份。

所以它叫：

四叉树 Quadtree

比如 2D 游戏里：

找玩家附近的怪物
找范围技能命中的单位
做 2D 碰撞 broad phase
做小地图区域查询

这些都可以用四叉树。

八叉树是什么？

八叉树主要用于：

3D 空间

因为 3D 有：

x 方向
y 方向
z 方向

每个方向切一半，就会得到：

2 * 2 * 2 = 8

所以一个 3D 空间会被切成 8 个小立方体。

它叫：

八叉树 Octree

常见用途：

3D 碰撞 broad phase
3D 场景可见性剔除
射线查询附近物体
大世界对象管理
空间音效范围查询
LOD 区域管理

为什么它们能提升性能？

如果不用空间结构，查找附近对象可能是：

遍历所有对象

复杂度接近：

O(N)

如果每个对象还要两两检测碰撞，可能变成：

O(N²)

使用四叉树或八叉树后，可以先定位区域：

目标在哪个节点里
查询范围和哪些节点相交
只遍历这些节点里的对象

这样就能跳过大量无关对象。

它们适合解决什么问题？

最常见是这些：

碰撞检测 Broad Phase
范围技能查询
视野检测候选目标筛选
找附近敌人
找附近资源点
场景对象管理
渲染剔除
LOD 管理
射线检测加速

比如释放一个圆形范围技能：

技能中心点 position
技能半径 radius

如果没有四叉树：

遍历场上所有敌人，判断距离

如果有四叉树：

先查这个圆形范围覆盖到哪些空间节点
只检测这些节点里的敌人

四叉树 C# 基础代码

下面是一个 2D 四叉树的基础版。 它支持：

插入对象
范围查询对象

为了面试容易讲，我这里用矩形范围 Rect2D 表示对象和查询区域。

using System.Collections.Generic; // 引入集合命名空间，用来使用 List
public struct Rect2D // 定义 2D 矩形结构体
{ // Rect2D 结构体开始
    public float X; // 矩形左下角 X 坐标
    public float Y; // 矩形左下角 Y 坐标
    public float Width; // 矩形宽度
    public float Height; // 矩形高度
    public Rect2D(float x, float y, float width, float height) // 定义矩形构造函数
    { // 构造函数开始
        X = x; // 保存 X 坐标
        Y = y; // 保存 Y 坐标
        Width = width; // 保存宽度
        Height = height; // 保存高度
    } // 构造函数结束
    public bool Contains(PointObject obj) // 判断当前矩形是否包含某个点对象
    { // Contains 函数开始
        return obj.X >= X && obj.X <= X + Width && obj.Y >= Y && obj.Y <= Y + Height; // 判断对象坐标是否在矩形范围内
    } // Contains 函数结束
    public bool Intersects(Rect2D other) // 判断当前矩形是否和另一个矩形相交
    { // Intersects 函数开始
        bool separated = other.X > X + Width || other.X + other.Width < X || other.Y > Y + Height || other.Y + other.Height < Y; // 判断两个矩形是否完全分离
        return !separated; // 如果没有完全分离，就说明两个矩形相交
    } // Intersects 函数结束
} // Rect2D 结构体结束
public class PointObject // 定义点对象类，用来表示场景中的一个对象
{ // PointObject 类开始
    public int Id; // 对象唯一编号
    public float X; // 对象 X 坐标
    public float Y; // 对象 Y 坐标
    public PointObject(int id, float x, float y) // 定义点对象构造函数
    { // 构造函数开始
        Id = id; // 保存对象编号
        X = x; // 保存 X 坐标
        Y = y; // 保存 Y 坐标
    } // 构造函数结束
} // PointObject 类结束
public class QuadTree // 定义四叉树类
{ // QuadTree 类开始
    private Rect2D boundary; // 当前节点负责的矩形区域
    private int capacity; // 当前节点最多能直接存多少对象
    private List<PointObject> objects; // 当前节点直接保存的对象列表
    private bool divided; // 当前节点是否已经分裂成四个子节点
    private QuadTree northWest; // 左上子节点
    private QuadTree northEast; // 右上子节点
    private QuadTree southWest; // 左下子节点
    private QuadTree southEast; // 右下子节点
    public QuadTree(Rect2D boundary, int capacity) // 定义四叉树构造函数
    { // 构造函数开始
        this.boundary = boundary; // 保存当前节点负责的区域
        this.capacity = capacity; // 保存节点容量
        objects = new List<PointObject>(); // 创建对象列表
        divided = false; // 初始还没有分裂
    } // 构造函数结束
    public bool Insert(PointObject obj) // 定义插入对象函数
    { // Insert 函数开始
        if (!boundary.Contains(obj)) // 如果对象不在当前节点范围内
        { // if 语句开始
            return false; // 插入失败
        } // if 语句结束
        if (objects.Count < capacity && !divided) // 如果当前节点还没满，并且还没分裂
        { // if 语句开始
            objects.Add(obj); // 直接把对象放进当前节点
            return true; // 插入成功
        } // if 语句结束
        if (!divided) // 如果当前节点还没有分裂
        { // if 语句开始
            Subdivide(); // 把当前节点切成四个子节点
        } // if 语句结束
        if (northWest.Insert(obj)) // 尝试插入左上子节点
        { // if 语句开始
            return true; // 如果插入成功，返回 true
        } // if 语句结束
        if (northEast.Insert(obj)) // 尝试插入右上子节点
        { // if 语句开始
            return true; // 如果插入成功，返回 true
        } // if 语句结束
        if (southWest.Insert(obj)) // 尝试插入左下子节点
        { // if 语句开始
            return true; // 如果插入成功，返回 true
        } // if 语句结束
        return southEast.Insert(obj); // 最后尝试插入右下子节点，并返回结果
    } // Insert 函数结束
    public void Query(Rect2D range, List<PointObject> result) // 定义范围查询函数
    { // Query 函数开始
        if (!boundary.Intersects(range)) // 如果查询范围和当前节点区域不相交
        { // if 语句开始
            return; // 当前节点整块都不用查，直接返回
        } // if 语句结束
        for (int i = 0; i < objects.Count; i++) // 遍历当前节点直接保存的对象
        { // for 循环开始
            if (range.Contains(objects[i])) // 如果对象在查询范围内
            { // if 语句开始
                result.Add(objects[i]); // 把对象加入查询结果
            } // if 语句结束
        } // for 循环结束
        if (!divided) // 如果当前节点没有子节点
        { // if 语句开始
            return; // 没有更多区域需要查询，直接返回
        } // if 语句结束
        northWest.Query(range, result); // 查询左上子节点
        northEast.Query(range, result); // 查询右上子节点
        southWest.Query(range, result); // 查询左下子节点
        southEast.Query(range, result); // 查询右下子节点
    } // Query 函数结束
    private void Subdivide() // 定义节点分裂函数
    { // Subdivide 函数开始
        float x = boundary.X; // 获取当前区域 X 坐标
        float y = boundary.Y; // 获取当前区域 Y 坐标
        float halfW = boundary.Width * 0.5f; // 计算子区域宽度
        float halfH = boundary.Height * 0.5f; // 计算子区域高度
        northWest = new QuadTree(new Rect2D(x, y + halfH, halfW, halfH), capacity); // 创建左上子节点
        northEast = new QuadTree(new Rect2D(x + halfW, y + halfH, halfW, halfH), capacity); // 创建右上子节点
        southWest = new QuadTree(new Rect2D(x, y, halfW, halfH), capacity); // 创建左下子节点
        southEast = new QuadTree(new Rect2D(x + halfW, y, halfW, halfH), capacity); // 创建右下子节点
        divided = true; // 标记当前节点已经分裂
    } // Subdivide 函数结束
} // QuadTree 类结束

怎么使用？

QuadTree tree = new QuadTree(new Rect2D(0f, 0f, 100f, 100f), 4); // 创建一个覆盖 100x100 区域、每节点最多存 4 个对象的四叉树
tree.Insert(new PointObject(1, 10f, 20f)); // 插入编号 1 的对象
tree.Insert(new PointObject(2, 15f, 25f)); // 插入编号 2 的对象
tree.Insert(new PointObject(3, 80f, 80f)); // 插入编号 3 的对象
List<PointObject> result = new List<PointObject>(); // 创建查询结果列表
tree.Query(new Rect2D(0f, 0f, 30f, 30f), result); // 查询左下角 30x30 范围内的对象

四叉树和八叉树怎么选？

如果是 2D 游戏：

地图是平面
角色只在 XY 或 XZ 平面移动
范围技能是圆形或矩形

一般用：

四叉树

如果是 3D 游戏：

对象分布在三维空间
需要考虑高度
场景有上下层
飞行单位、子弹、空间物体很多

可以考虑：

八叉树

面试高分回答

NOTE

四叉树和八叉树都是空间划分结构，用来加速空间查询。四叉树用于二维空间，每个节点把区域划分成 4 个子区域；八叉树用于三维空间，每个节点把空间划分成 8 个子空间。它们的核心作用是避免遍历全场对象，只查询和目标范围相交的空间节点，从而快速找到附近对象。常见用途包括碰撞检测 broad phase、范围技能查询、视野检测候选目标筛选、可见性剔除、LOD 管理和大场景对象管理。实际项目中要注意动态对象移动后的更新、节点容量、最大深度、大对象跨区域处理，以及对象分布不均导致树不平衡的问题。

BVH 是什么？

BVH 是什么？BVH 全称是：

Bounding Volume Hierarchy

中文一般叫：

包围体层次结构

一句话理解：

BVH 是一棵树，树上的每个节点都是一个包围盒，用来快速排除不可能碰撞或不可能命中的对象。

它常用于：

碰撞检测 broad phase
射线检测
渲染剔除
光线追踪
复杂模型三角形加速查询

为什么需要 BVH？

假设场景里有很多物体：

10000 个物体

如果每次查询都遍历所有物体：

太慢

BVH 的思路是：

先把相近的物体包成一个大盒子。
再把多个大盒子继续包成更大的盒子。
最后形成一棵树。

查询时，如果一个查询范围和某个大盒子都不相交，那么：

这个大盒子下面的所有物体都不用查。

这就是 BVH 的核心价值：

整棵子树剪枝。

BVH 的结构

BVH 通常是一棵二叉树。

叶子节点：

保存真实物体

内部节点：

保存左右子节点的合并包围盒

比如：

Root
├── Left Bounds
│   ├── Object A
│   └── Object B
└── Right Bounds
    ├── Object C
    └── Object D

如果查询范围只碰到 Right Bounds，那么 Left Bounds 整棵子树都可以跳过。

BVH 和四叉树 / 八叉树区别

四叉树 / 八叉树是：

把空间固定切成 4 份或 8 份

BVH 是：

根据物体分布来组织包围盒

所以 BVH 不一定固定切空间。

对比一下：

四叉树：空间驱动
八叉树：空间驱动
BVH：对象驱动

如果对象大小差异很大、分布不均，BVH 通常会比固定网格或四叉树更灵活。

C# 基础 BVH 示例

下面写一个简单 2D AABB BVH。 它支持：

构建 BVH
查询和某个范围相交的物体
using System; // 引入 System 命名空间，用来使用 Math
using System.Collections.Generic; // 引入集合命名空间，用来使用 List
public struct Aabb2D // 定义 2D AABB 包围盒结构体
{ // Aabb2D 结构体开始
    public float MinX; // 包围盒最小 X 坐标
    public float MinY; // 包围盒最小 Y 坐标
    public float MaxX; // 包围盒最大 X 坐标
    public float MaxY; // 包围盒最大 Y 坐标
    public Aabb2D(float minX, float minY, float maxX, float maxY) // 定义 AABB 构造函数
    { // 构造函数开始
        MinX = minX; // 保存最小 X 坐标
        MinY = minY; // 保存最小 Y 坐标
        MaxX = maxX; // 保存最大 X 坐标
        MaxY = maxY; // 保存最大 Y 坐标
    } // 构造函数结束
    public bool Intersects(Aabb2D other) // 判断两个 AABB 是否相交
    { // Intersects 函数开始
        bool separated = MaxX < other.MinX || MinX > other.MaxX || MaxY < other.MinY || MinY > other.MaxY; // 判断两个盒子是否完全分离
        return !separated; // 如果没有完全分离，就说明相交
    } // Intersects 函数结束
    public static Aabb2D Merge(Aabb2D a, Aabb2D b) // 合并两个 AABB，得到能包住它们的大 AABB
    { // Merge 函数开始
        float minX = Math.Min(a.MinX, b.MinX); // 取两个盒子的最小 X
        float minY = Math.Min(a.MinY, b.MinY); // 取两个盒子的最小 Y
        float maxX = Math.Max(a.MaxX, b.MaxX); // 取两个盒子的最大 X
        float maxY = Math.Max(a.MaxY, b.MaxY); // 取两个盒子的最大 Y
        return new Aabb2D(minX, minY, maxX, maxY); // 返回合并后的包围盒
    } // Merge 函数结束
    public float CenterX() // 获取包围盒中心 X
    { // CenterX 函数开始
        return (MinX + MaxX) * 0.5f; // 返回最小 X 和最大 X 的平均值
    } // CenterX 函数结束
    public float CenterY() // 获取包围盒中心 Y
    { // CenterY 函数开始
        return (MinY + MaxY) * 0.5f; // 返回最小 Y 和最大 Y 的平均值
    } // CenterY 函数结束
} // Aabb2D 结构体结束
public class BvhObject // 定义 BVH 中保存的物体类
{ // BvhObject 类开始
    public int Id; // 物体唯一编号
    public Aabb2D Bounds; // 物体自己的 AABB 包围盒
    public BvhObject(int id, Aabb2D bounds) // 定义物体构造函数
    { // 构造函数开始
        Id = id; // 保存物体编号
        Bounds = bounds; // 保存物体包围盒
    } // 构造函数结束
} // BvhObject 类结束
public class BvhNode // 定义 BVH 节点类
{ // BvhNode 类开始
    public Aabb2D Bounds; // 当前节点的总包围盒
    public BvhNode Left; // 当前节点的左子节点
    public BvhNode Right; // 当前节点的右子节点
    public BvhObject Object; // 当前节点保存的物体，只有叶子节点才有
    public bool IsLeaf => Object != null; // 判断当前节点是否是叶子节点
} // BvhNode 类结束
public class BvhTree // 定义 BVH 树类
{ // BvhTree 类开始
    private BvhNode root; // 保存 BVH 根节点
    public BvhTree(List<BvhObject> objects) // 定义 BVH 构造函数
    { // 构造函数开始
        root = Build(objects, 0, objects.Count); // 用所有物体构建 BVH 树
    } // 构造函数结束
    public List<BvhObject> Query(Aabb2D range) // 定义范围查询函数
    { // Query 函数开始
        List<BvhObject> result = new List<BvhObject>(); // 创建查询结果列表
        QueryNode(root, range, result); // 从根节点开始查询
        return result; // 返回所有和查询范围相交的物体
    } // Query 函数结束
    private BvhNode Build(List<BvhObject> objects, int start, int count) // 定义递归构建 BVH 的函数
    { // Build 函数开始
        if (count <= 0) // 如果没有物体
        { // if 语句开始
            return null; // 返回空节点
        } // if 语句结束
        if (count == 1) // 如果只有一个物体
        { // if 语句开始
            BvhObject obj = objects[start]; // 取出这个物体
            return new BvhNode { Bounds = obj.Bounds, Object = obj }; // 创建叶子节点并返回
        } // if 语句结束
        Aabb2D bounds = objects[start].Bounds; // 先用第一个物体的包围盒初始化总包围盒
        for (int i = start + 1; i < start + count; i++) // 遍历当前范围内的其他物体
        { // for 循环开始
            bounds = Aabb2D.Merge(bounds, objects[i].Bounds); // 把每个物体的包围盒合并进总包围盒
        } // for 循环结束
        bool splitByX = (bounds.MaxX - bounds.MinX) >= (bounds.MaxY - bounds.MinY); // 如果 X 方向更长，就按 X 排序，否则按 Y 排序
        objects.Sort(start, count, Comparer<BvhObject>.Create((a, b) => splitByX ? a.Bounds.CenterX().CompareTo(b.Bounds.CenterX()) : a.Bounds.CenterY().CompareTo(b.Bounds.CenterY()))); // 按中心点排序，让空间上接近的物体更容易分到一起
        int leftCount = count / 2; // 左子树物体数量取一半
        int rightCount = count - leftCount; // 右子树物体数量是剩下的一半
        BvhNode left = Build(objects, start, leftCount); // 递归构建左子树
        BvhNode right = Build(objects, start + leftCount, rightCount); // 递归构建右子树
        Aabb2D merged = Aabb2D.Merge(left.Bounds, right.Bounds); // 合并左右子树包围盒
        return new BvhNode { Bounds = merged, Left = left, Right = right }; // 创建内部节点并返回
    } // Build 函数结束
    private void QueryNode(BvhNode node, Aabb2D range, List<BvhObject> result) // 定义递归查询节点函数
    { // QueryNode 函数开始
        if (node == null) // 如果节点为空
        { // if 语句开始
            return; // 直接返回
        } // if 语句结束
        if (!node.Bounds.Intersects(range)) // 如果查询范围和当前节点包围盒不相交
        { // if 语句开始
            return; // 整个子树都不可能命中，直接剪枝
        } // if 语句结束
        if (node.IsLeaf) // 如果当前节点是叶子节点
        { // if 语句开始
            result.Add(node.Object); // 把叶子节点里的物体加入结果
            return; // 叶子节点没有子节点，直接返回
        } // if 语句结束
        QueryNode(node.Left, range, result); // 递归查询左子树
        QueryNode(node.Right, range, result); // 递归查询右子树
    } // QueryNode 函数结束
} // BvhTree 类结束

怎么使用？

List<BvhObject> objects = new List<BvhObject>(); // 创建物体列表
objects.Add(new BvhObject(1, new Aabb2D(0f, 0f, 1f, 1f))); // 添加编号 1 的物体
objects.Add(new BvhObject(2, new Aabb2D(2f, 0f, 3f, 1f))); // 添加编号 2 的物体
objects.Add(new BvhObject(3, new Aabb2D(10f, 10f, 12f, 12f))); // 添加编号 3 的物体
BvhTree tree = new BvhTree(objects); // 用物体列表构建 BVH 树
List<BvhObject> hits = tree.Query(new Aabb2D(0f, 0f, 4f, 2f)); // 查询和这个范围相交的物体

BVH 的查询为什么快？

关键在这里：

如果查询范围和某个节点的 Bounds 不相交
这个节点下面的所有对象都不用看

比如一个节点下面有 500 个物体。 只要查询范围不碰这个节点的包围盒，就能一次跳过 500 个物体。

这就是：

剪枝

BVH 的构建方式

常见构建方式有：

按最长轴排序后切一半
按对象中心点排序
SAH 表面积启发式
自底向上合并
动态 AABB Tree

面试基础回答里，说：

按最长轴排序后切一半

就已经够清楚。

意思是：

如果当前包围盒 X 方向更长，就按 X 中心排序。
如果 Y 方向更长，就按 Y 中心排序。
然后一半给左子树，一半给右子树。

BVH 和四叉树 / 八叉树怎么选？

如果你是规则地图、大量大小差不多的单位：

Uniform Grid 或四叉树很好用

如果对象大小差异大、形状复杂、分布不均：

BVH 更灵活

如果是复杂模型的三角形射线检测：

BVH 很常见

比如光线追踪里，射线不可能每次和所有三角形求交。 它会先和 BVH 的大包围盒测试，逐层向下，只访问可能命中的三角形。

动态对象要注意什么？

静态对象：

构建一次 BVH
反复查询

非常划算。

动态对象：

对象一直移动
包围盒会变
树可能需要更新

这时要考虑：

每帧重建是否太贵
局部 refit 包围盒
动态 AABB Tree
静态 BVH + 动态对象单独管理

面试高分回答

IMPORTANT

BVH 是包围体层次结构，本质是一棵空间加速树。叶子节点保存真实对象或三角形，内部节点保存左右子树的合并包围盒。查询时先判断查询范围或射线是否和节点包围盒相交，如果不相交，就可以跳过整个子树；如果相交，再继续向下递归。BVH 的核心价值是通过层次包围盒做剪枝，避免遍历所有对象。它常用于碰撞检测 broad phase、射线检测、渲染剔除和光线追踪。和四叉树、八叉树相比，BVH 更偏对象驱动，不是固定切空间，所以对物体大小差异大、分布不均或复杂模型三角形查询更灵活。

如何做随机掉落权重？

随机掉落权重是什么？ 随机掉落权重就是：每个奖励配置一个 weight，权重越大，被抽中的概率越高。

比如：

金币 weight = 50
稀有装备 weight = 30
史诗装备 weight = 15
传说装备 weight = 5

总权重是：

50 + 30 + 15 + 5 = 100

所以概率大概是：

金币：50%
稀有装备：30%
史诗装备：15%
传说装备：5%

核心原理

不是直接随机一个物品，而是先把权重变成一段段区间：

金币：      [0, 50)
稀有装备：  [50, 80)
史诗装备：  [80, 95)
传说装备：  [95, 100)

然后随机一个数：

roll = 73

因为 73 落在：

[50, 80)

所以掉落：

稀有装备

C# 基础代码

using System; // 引入 System 命名空间，用来使用 Random
using System.Collections.Generic; // 引入集合命名空间，用来使用 List
public class DropItem // 定义掉落物品类
{ // DropItem 类开始
    public string Name; // 掉落物名字
    public int Weight; // 掉落物权重
    public DropItem(string name, int weight) // 定义构造函数，用来创建掉落物
    { // 构造函数开始
        Name = name; // 保存掉落物名字
        Weight = weight; // 保存掉落物权重
    } // 构造函数结束
} // DropItem 类结束
public class WeightedDropTable // 定义权重掉落表
{ // WeightedDropTable 类开始
    private List<DropItem> items = new List<DropItem>(); // 保存所有掉落物
    private Random random = new Random(); // 创建随机数对象
    public void AddItem(string name, int weight) // 定义添加掉落物函数
    { // AddItem 函数开始
        if (weight <= 0) // 如果权重小于等于 0
        { // if 语句开始
            return; // 无效权重不加入掉落表
        } // if 语句结束
        items.Add(new DropItem(name, weight)); // 把掉落物加入列表
    } // AddItem 函数结束
    public DropItem Roll() // 定义随机掉落函数
    { // Roll 函数开始
        int totalWeight = 0; // 创建总权重变量
        for (int i = 0; i < items.Count; i++) // 遍历所有掉落物
        { // for 循环开始
            totalWeight += items[i].Weight; // 把当前物品权重累加到总权重
        } // for 循环结束
        if (totalWeight <= 0) // 如果总权重无效
        { // if 语句开始
            return null; // 没有可掉落物，返回 null
        } // if 语句结束
        int roll = random.Next(0, totalWeight); // 随机一个数，范围是 0 到 totalWeight - 1
        int currentWeight = 0; // 创建当前累计权重
        for (int i = 0; i < items.Count; i++) // 再次遍历所有掉落物
        { // for 循环开始
            currentWeight += items[i].Weight; // 累加当前物品权重，形成区间右边界
            if (roll < currentWeight) // 如果随机数落在当前物品的权重区间内
            { // if 语句开始
                return items[i]; // 返回当前掉落物
            } // if 语句结束
        } // for 循环结束
        return null; // 理论上不会走到这里，作为安全兜底
    } // Roll 函数结束
} // WeightedDropTable 类结束

怎么使用？

WeightedDropTable table = new WeightedDropTable(); // 创建一个权重掉落表
table.AddItem("金币", 50); // 添加金币，权重是 50
table.AddItem("稀有装备", 30); // 添加稀有装备，权重是 30
table.AddItem("史诗装备", 15); // 添加史诗装备，权重是 15
table.AddItem("传说装备", 5); // 添加传说装备，权重是 5
DropItem item = table.Roll(); // 执行一次随机掉落
Console.WriteLine(item.Name); // 输出本次掉落物名字

面试要点

权重不是百分比，而是相对值。

比如：

A = 1
B = 3

意思是：

B 的概率大约是 A 的 3 倍

如果总权重是 4：

A 概率 = 1 / 4 = 25%
B 概率 = 3 / 4 = 75%

常见坑

权重为 0 的物品：

不会被抽中

权重为负数：

通常应该禁止配置

大规模掉落表：

可以用前缀和 + 二分查找优化

线上游戏掉落：

要记录掉落日志，方便排查玩家投诉和概率问题

面试高分回答

NOTE

随机掉落权重的核心是累计权重。先计算所有奖励的总权重，然后生成一个 [0, totalWeight) 范围内的随机数，再从头累加每个奖励的权重。随机数落在哪个累计区间，就返回哪个奖励。权重越大，占据的区间越长，被抽中的概率越高。普通掉落表用一次遍历就够了，如果掉落表很大，可以预先构建前缀和数组，再用二分查找提升查询效率。实际项目中还要注意权重合法性、随机种子、掉落日志、保底机制和服务器权威计算。

如何做洗牌算法？

洗牌算法是什么？ 洗牌算法就是把一个数组随机打乱，比如：

[1, 2, 3, 4, 5]

打乱后可能变成：

[3, 1, 5, 2, 4]

但真正好的洗牌算法要满足一个要求：

每一种排列出现的概率都一样。

最经典、最常考的洗牌算法叫：

Fisher-Yates Shuffle

核心思路

从数组最后一个位置开始：

i = n - 1

每次在：

[0, i]

范围里随机选一个下标：

j

然后交换：

nums[i] 和 nums[j]

接着 i--，继续处理前面的元素。

举个例子

原数组：

[1, 2, 3, 4, 5]

第一轮：

i = 4
随机 j = 2
交换 nums[4] 和 nums[2]

变成：

[1, 2, 5, 4, 3]

这时最后一个位置已经随机确定了。

下一轮只在前面 [0, 3] 里继续随机。

C# 泛型洗牌代码

using System; // 引入 System 命名空间，用来使用 Random
using System.Collections.Generic; // 引入集合命名空间，用来使用 IList
public static class ShuffleUtility // 定义洗牌工具类
{ // ShuffleUtility 类开始
    private static readonly Random RandomGenerator = new Random(); // 创建全局随机数生成器，避免频繁 new Random 导致随机效果不好
    public static void Shuffle<T>(IList<T> list) // 定义泛型洗牌函数，可以打乱 int、string、对象等任意列表
    { // Shuffle 函数开始
        if (list == null) // 如果传入的列表为空
        { // if 语句开始
            return; // 空列表不能洗牌，直接返回
        } // if 语句结束
        for (int i = list.Count - 1; i > 0; i--) // 从最后一个位置开始，依次向前固定每个位置
        { // for 循环开始
            int j = RandomGenerator.Next(0, i + 1); // 在 [0, i] 范围内随机一个下标，注意 Next 的右边界不包含
            T temp = list[i]; // 临时保存 i 位置的元素
            list[i] = list[j]; // 把 j 位置的元素放到 i 位置
            list[j] = temp; // 把原来 i 位置的元素放到 j 位置，完成交换
        } // for 循环结束
    } // Shuffle 函数结束
} // ShuffleUtility 类结束

怎么使用？

List<int> cards = new List<int>() { 1, 2, 3, 4, 5 }; // 创建一个待洗牌的列表
ShuffleUtility.Shuffle(cards); // 调用洗牌函数，把 cards 原地打乱

为什么 Random.Next(0, i + 1)？

C# 的 Random.Next(min, max) 是：

包含 min
不包含 max

所以：

Random.Next(0, i + 1)

实际随机范围是：

0 到 i

这正好符合 Fisher-Yates 的要求。

如果你写成：

Random.Next(0, i)

那就取不到 i 本身，概率就错了。

为什么不能用随机排序？

有些人会写：

OrderBy(x => random.Next())

这个做法不推荐。

原因是：

1. 排序是 O(n log n)，Fisher-Yates 是 O(n)
2. 随机排序不一定能保证每种排列概率完全一致
3. 比较器或随机 key 处理不好时可能产生偏差

洗牌面试里最好直接说：

用 Fisher-Yates，不用随机排序。

Unity 版本

如果你在 Unity 里，也可以用 UnityEngine.Random.Range。

using System.Collections.Generic; // 引入集合命名空间，用来使用 IList
using UnityEngine; // 引入 UnityEngine 命名空间，用来使用 Random.Range
public static class UnityShuffleUtility // 定义 Unity 洗牌工具类
{ // UnityShuffleUtility 类开始
    public static void Shuffle<T>(IList<T> list) // 定义泛型洗牌函数
    { // Shuffle 函数开始
        if (list == null) // 如果列表为空
        { // if 语句开始
            return; // 直接返回
        } // if 语句结束
        for (int i = list.Count - 1; i > 0; i--) // 从最后一个元素开始往前遍历
        { // for 循环开始
            int j = Random.Range(0, i + 1); // Unity 整数版 Range 右边界不包含，所以这里也是 [0, i]
            T temp = list[i]; // 临时保存当前位置元素
            list[i] = list[j]; // 把随机位置的元素放到当前位置
            list[j] = temp; // 把原当前位置的元素放到随机位置
        } // for 循环结束
    } // Shuffle 函数结束
} // UnityShuffleUtility 类结束

复杂度

Fisher-Yates 洗牌：

时间复杂度：O(n)
空间复杂度：O(1)

因为它只遍历一次数组，并且原地交换。

面试高分回答

NOTE

洗牌算法推荐使用 Fisher-Yates。它从数组末尾开始，每一轮在 [0, i] 范围内随机选择一个下标 j，然后交换 list[i] 和 list[j]，再把 i 向前移动。这样每个位置都会从剩余未固定元素中等概率选择一个元素，因此可以保证所有排列出现的概率相同。它是原地算法，时间复杂度是 O(n)，空间复杂度是 O(1)。不推荐用随机排序，因为性能更差，而且可能产生概率偏差。

如何做技能目标筛选？

技能目标筛选是什么？ 技能目标筛选就是：释放一个技能时，从场景里的很多单位中，找出真正应该被这个技能命中的目标。

比如一个扇形攻击技能，不能随便命中所有人，它通常要满足：

目标是敌人
目标还活着
目标在技能范围内
目标在技能角度内
目标没有被墙挡住
目标数量没有超过技能上限

常见筛选流程

一般不要一上来就精确判断所有单位，而是分层筛：

1. 先用 OverlapSphere 找附近候选目标
2. 过滤死亡、友军、无敌、免疫单位
3. 根据技能形状过滤，比如圆形、扇形、矩形
4. 用 Raycast 检查中间有没有墙
5. 按距离、血量、仇恨、优先级排序
6. 取前 N 个目标

这叫：

先粗筛，再精筛，最后排序。

Unity C# 示例：扇形技能筛选

下面代码实现一个常见的扇形技能目标筛选。

using System.Collections.Generic; // 引入集合命名空间，用来使用 List
using UnityEngine; // 引入 UnityEngine 命名空间，用来使用 MonoBehaviour、Transform、Physics 等
public enum Camp // 定义阵营枚举
{ // Camp 枚举开始
    Player, // 玩家阵营
    Enemy // 敌人阵营
} // Camp 枚举结束
public class TargetUnit : MonoBehaviour // 定义可被技能选中的单位组件
{ // TargetUnit 类开始
    public Camp Camp; // 当前单位所属阵营
    public bool IsAlive = true; // 当前单位是否存活
    public bool IsInvincible = false; // 当前单位是否无敌
    public int Hp = 100; // 当前单位血量
    public int Priority = 0; // 当前单位优先级，数值越高越优先
} // TargetUnit 类结束
public class SkillTargetSelector : MonoBehaviour // 定义技能目标筛选器
{ // SkillTargetSelector 类开始
    public Camp CasterCamp = Camp.Player; // 施法者阵营
    public float Radius = 6f; // 技能搜索半径
    public float Angle = 90f; // 技能扇形角度
    public int MaxTargetCount = 3; // 最多选中几个目标
    public LayerMask TargetMask; // 目标所在层
    public LayerMask ObstacleMask; // 障碍物所在层
    public float EyeHeight = 1.2f; // 射线检测高度，避免从脚底发射
    public List<TargetUnit> SelectTargets() // 定义筛选目标函数
    { // SelectTargets 函数开始
        List<TargetUnit> result = new List<TargetUnit>(); // 创建结果列表，用来保存最终目标
        Vector3 origin = transform.position; // 获取施法者当前位置
        Vector3 eyePosition = origin + Vector3.up * EyeHeight; // 计算射线起点位置
        Collider[] colliders = Physics.OverlapSphere(origin, Radius, TargetMask); // 在半径内查找所有候选目标
        for (int i = 0; i < colliders.Length; i++) // 遍历所有候选碰撞体
        { // for 循环开始
            TargetUnit target = colliders[i].GetComponent<TargetUnit>(); // 尝试从碰撞体上获取 TargetUnit 组件
            if (target == null) // 如果候选对象没有 TargetUnit 组件
            { // if 语句开始
                continue; // 不是合法目标，跳过
            } // if 语句结束
            if (!target.IsAlive) // 如果目标已经死亡
            { // if 语句开始
                continue; // 死亡目标不能被选中，跳过
            } // if 语句结束
            if (target.IsInvincible) // 如果目标处于无敌状态
            { // if 语句开始
                continue; // 无敌目标不能被选中，跳过
            } // if 语句结束
            if (target.Camp == CasterCamp) // 如果目标和施法者是同一阵营
            { // if 语句开始
                continue; // 友军不能被敌对技能选中，跳过
            } // if 语句结束
            Vector3 targetPosition = target.transform.position + Vector3.up * EyeHeight; // 计算目标检测点位置
            Vector3 direction = targetPosition - eyePosition; // 计算施法者到目标的方向向量
            float distance = direction.magnitude; // 计算施法者到目标的距离
            Vector3 normalizedDirection = direction.normalized; // 把方向向量归一化
            float halfAngle = Angle * 0.5f; // 计算扇形半角
            float angleToTarget = Vector3.Angle(transform.forward, normalizedDirection); // 计算施法者前方向和目标方向的夹角
            if (angleToTarget > halfAngle) // 如果目标不在扇形角度内
            { // if 语句开始
                continue; // 角度不满足，跳过
            } // if 语句结束
            bool blocked = Physics.Raycast(eyePosition, normalizedDirection, distance, ObstacleMask); // 发射射线检测中间是否有障碍物
            if (blocked) // 如果中间有障碍物
            { // if 语句开始
                continue; // 被墙挡住，跳过
            } // if 语句结束
            result.Add(target); // 所有条件都满足，把目标加入结果列表
        } // for 循环结束
        result.Sort(CompareTarget); // 按优先级和距离排序
        if (result.Count > MaxTargetCount) // 如果目标数量超过技能上限
        { // if 语句开始
            result.RemoveRange(MaxTargetCount, result.Count - MaxTargetCount); // 移除多余目标，只保留前 MaxTargetCount 个
        } // if 语句结束
        return result; // 返回最终筛选出的目标
    } // SelectTargets 函数结束
    private int CompareTarget(TargetUnit a, TargetUnit b) // 定义目标排序函数
    { // CompareTarget 函数开始
        if (a.Priority != b.Priority) // 如果两个目标优先级不同
        { // if 语句开始
            return b.Priority.CompareTo(a.Priority); // 优先级高的排前面
        } // if 语句结束
        float distanceA = Vector3.Distance(transform.position, a.transform.position); // 计算目标 a 和施法者的距离
        float distanceB = Vector3.Distance(transform.position, b.transform.position); // 计算目标 b 和施法者的距离
        return distanceA.CompareTo(distanceB); // 距离更近的排前面
    } // CompareTarget 函数结束
} // SkillTargetSelector 类结束

为什么要先用 OverlapSphere？

因为场景里可能有很多单位。

如果每次放技能都遍历所有单位：

1000 个怪物都检查一遍

会比较浪费。

OverlapSphere 的作用是：

先找半径范围内的候选目标

这一步是粗筛。

后面再做：

阵营
死亡
角度
遮挡
排序

这些是精筛。

不同技能怎么筛？

圆形技能：

只判断距离 <= radius

扇形技能：

距离 <= radius
角度 <= angle / 2

矩形技能：

把目标转换到施法者本地坐标
判断 x、z 是否落在矩形范围内

单体锁定技能：

判断目标是否合法
判断是否在释放距离内
判断是否有遮挡

链式闪电：

先找最近目标
再从当前目标附近继续找下一个
并且避免重复命中

面试高分回答

IMPORTANT

技能目标筛选一般分为粗筛、精筛和排序。粗筛阶段用 OverlapSphere、空间网格、四叉树等方式先找到附近候选目标，避免全场遍历。精筛阶段根据技能规则过滤目标，比如阵营、是否存活、是否无敌、距离、扇形角度、矩形范围、障碍遮挡等。最后根据技能需求排序，比如距离最近、血量最低、优先级最高、仇恨最高，并限制最大命中数量。实际项目中，不同技能可以抽象成不同的筛选器或组合条件，例如圆形筛选、扇形筛选、矩形筛选、射线筛选和排序策略，这样技能系统会更容易扩展。