游戏 AI / 系统课时

NPC 距离过滤怎么避免无效计算

NPC 距离过滤怎么避免无效计算

NPC 每次决策如果都对场景中的全部对象做可见性、阵营、路径等检查,成本会随候选数量迅速放大。更稳妥的做法是先用搜索半径和平方距离完成廉价过滤,把昂贵判断留给少量近邻候选。

学习目标

  • 用搜索半径和平方距离快速缩小候选集
  • 理解过滤顺序为什么会直接影响单次决策成本
  • 能为距离边界和候选数量设计可验证的检查

先用便宜条件缩小候选集

候选过滤应遵循一个原则:越便宜、淘汰率越高的条件越靠前。距离通常只需要坐标减法和乘加,比射线检测、寻路查询或复杂规则评分便宜,因此适合放在过滤链前段。

假设 NPC 周围有 1000 个潜在对象,半径过滤后只剩 25 个,那么后续可见性检查最多处理这 25 个对象,而不是对全部 1000 个对象发起射线检测。

距离过滤先于昂贵空间检查的候选收缩流程

如果引擎已经提供空间索引,应优先使用物理世界查询、四叉树、八叉树、网格或其他空间结构先取得附近对象。不要先遍历全场对象,再靠距离表达式“补救”,因为这样仍然支付了全量遍历成本。

用平方距离避免不必要的开方

只比较“是否位于半径内”时,不需要真正计算欧氏距离。二维情况下可以比较平方距离:

d2=(x1−x2)2+(y1−y2)2d^2 = (x_1-x_2)^2 + (y_1-y_2)^2

当 d2d^2 不大于 r2r^2 时,目标就在搜索半径内。这样可以避免为每个候选执行平方根运算,同时保持半径判定结果一致。

下面的 C# 示例完整演示先按平方距离过滤,再把近邻交给后续步骤的过程。

csharp
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

public sealed record Candidate(string Id, Vector2 Position);

public static class Program
{
    public static void Main()
    {
        Vector2 npcPosition = new(0, 0);
        float searchRadius = 10f;

        var candidates = new List<Candidate>
        {
            new("A", new Vector2(3, 4)),
            new("B", new Vector2(10, 0)),
            new("C", new Vector2(8, 8)),
            new("D", new Vector2(20, 1))
        };

        float radiusSquared = searchRadius * searchRadius;

        var nearby = candidates
            .Where(candidate =>
                Vector2.DistanceSquared(npcPosition, candidate.Position) <= radiusSquared)
            .Select(candidate => candidate.Id)
            .ToList();

        Console.WriteLine(string.Join(", ", nearby));
    }
}

预期输出:

text
A, B

B 正好位于半径边界上,因此使用 <= 时会被保留;C 的平方距离为 128,已经超过半径平方 100。

过滤顺序决定昂贵操作执行次数

距离过滤不是唯一条件。真实目标选择常见顺序可以是:对象有效性检查、阵营或标签过滤、距离过滤、可见性检查、路径可达性,最后再做评分。顺序不应机械固定,而要同时考虑单次成本和淘汰率。

例如,阵营字段比较几乎没有成本,而且能淘汰大量友军,就可以放在距离之前;相反,路径查询通常很贵,应该尽量等候选已经很少时再执行。

给搜索半径留下明确边界

半径太大会让过滤失去意义,太小又可能漏掉本应进入决策的目标。实践中应把“感知范围”和“攻击范围”分开:前者决定谁有资格进入候选集,后者只是后续动作条件,不要用攻击距离替代感知距离。

还要明确边界语义。若设计要求“刚好 10 米也算被感知”,代码就应使用 <=;若要求严格小于,则使用 <。边界定义不一致会让位于临界位置的目标反复进出候选集。

用计数器验证优化是否生效

验证距离过滤时,不只看最终选中了谁,还应记录每一层剩余候选数量,例如“空间查询返回 80 个、距离过滤剩 24 个、可见性检查执行 24 次、最终有效 6 个”。如果过滤后数量没有明显下降,就应重新检查搜索半径、空间索引范围或对象分组策略。

距离过滤真正的价值不是单独省下一次平方根,而是让射线、寻路和评分等昂贵决策只面对真正可能成为目标的少量对象。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

NPC 距离过滤怎么避免无效计算

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通