前言

前几天发生了如下这么一段对话。

策划：我想给咱们Boss加一个新技能…..
程序：不，你不想(╯▔皿▔)╯。
策划: 是这样的，这个boss不是水母吗，我想给这个boss增加一个使用触须攻击玩家的范围性技能，触须是在玩家附近连续快速生成，类似地刺一样，生成前会有一定的延迟预警效果。
程序：所以这是一个区域限制性的技能，目标是给玩家施加一些走位的压力？
策划：是的。
程序：触须的位置选择规则是怎样的？
策划：是随机的。
程序：怎么个随机法，能不能描述的具体点？
策划：额，要不我整个演示视频你看下？
（策划花了点时间整了个演示PPT）

策划：你看下这个效果演示？
程序：嗷（恍然大悟状），所以这是在玩家附近的一个矩形区域内均匀地选取随机点，然后依次延迟一段时间后造成一个个小型范围AOE，对吧？
策划：对的。
程序：了解了，那么你需要AI里可以控制哪些参数，按我理解的话，应该是有区域的长宽、地刺的大小、数量以及地刺之间的间距以及….(巴拉巴拉一些其他参数，不赘述）。
策划：只需要区域长宽、地刺数量以及地刺间的距离就行了，大小咱们改预制体就好了。
程序：行，需求确定好了就开搞。
（之后又对了一些AI相关的问题）

尝试与分析

确定好了策划的需求，那么就开始分析实现。

这个需求的核心难点在于，如何均匀地选取随机点。

最开始想到了将矩形区域均匀分割成等大小的方格，然后先选择离玩家最近的那个方格做多次BFS，达到指定数量的方格后，然后在方格里再随机选择一个坐标点（类似下图这样生成7个绿色的随机点）

但是这样会导致一个问题:相邻的两个方格内的随机点有可能过近

或者过远。

思考了半天, 最后不得不求助万能的谷歌, 搜索关键字Evenly distributed random point。

最后发现泊松盘采样算法(Poisson Disk Sampling)是个不错的选择。

算法思路如下：

1.输入点之间的最小间距r, 采样所在空间的维度d，比如二维平面d = 2
2.初始化一个Grid，在Grid内生成均匀大小的方格，一般方格大小为 r / sqrt(d)。
3.输入一个起始点，然后创建两个点集合，一个是处理集合，一个是结果集合，把起始点放入这两个集合中。
4.如果处理集合不为空，从中随机选取一个点a移除掉，进行第5步操作，否则终止算法输出结果集合。
5.设置到a的最小距离为r，最大距离为2r。设定最大采样次数k，对第4步选取的点a进行圆环采样。
- I. 圆环采样：以点a为中心生成一个圆环，在这个圆环中生成一个随机采样点b，并对b进行有效性检测。如果检测通过就将该点b放入结果结合当中，否则舍弃这个点b，尝试进行第n(n <= k)次随机点采样。采样达到k次后返回第4步继续循环。
- II. 有效性判断逻辑
  - 判断其是否超出限定区域
  - 判断其所在的周围8个网格是否存在与其相邻过近的点, 如下图所示。

代码实现

实现的代码逻辑如下，注意泊松盘采样原算法是会将整个区域铺满的，这里为了优化，当采样点数量达到指定大小(selectPointCount)时，会提前终止采样。

/// <summary>
/// 泊松盘采样等距离坐标点
/// </summary>
/// <param name="width">采样区域宽度</param>
/// <param name="height">采样区域高度</param>
/// <param name="minDistance">采样点之间最小间隔</param>
/// <param name="selectPointCount">采样点数量</param>
/// <param name="firstPoint">采样起始点</param>
/// <param name="k">单次采样迭代次数</param>
/// <returns>采样点列表</returns>
public static List<Vector2> PossionDiskSample(float width, float height, float minDistance, int selectPointCount, Vector2 firstPoint = default, int k = 10)
{
    var results = new List<Vector2>(selectPointCount);
    var processPoints = new List<Vector2>();
    float cellSize = minDistance / (float)Math.Sqrt(2);

    int col = Mathf.CeilToInt(width / cellSize);
    int row = Mathf.CeilToInt(height / cellSize);
    
    var grid = new Vector2[col, row];

    results.Add(firstPoint);
    processPoints.Add(firstPoint);
    var xy = Point2ColRow(firstPoint, cellSize);
    grid[xy.col, xy.row] = firstPoint;

    while(processPoints.Count > 0 && results.Count < selectPointCount)
    {
        var curPoint = processPoints.PickRandomElement();
        for(int i = 0;i < k; ++i)
        {
            var newPoint = NextRandomPoint(curPoint, minDistance);
            if(IsValidPossionPoint(newPoint, grid, cellSize, minDistance))
            {
                results.Add(newPoint);
                processPoints.Add(newPoint);
                var col_row = Point2ColRow(newPoint, cellSize);
                grid[col_row.col, col_row.row] = newPoint;
                if (results.Count >= selectPointCount)
                    break;
            }
        }
    }
    return results;
}

//坐标位置转换为网格索引
private static (int col, int row) Point2ColRow(Vector2 point, float cellSize)
{
    int col = Mathf.FloorToInt(point.x / cellSize);
    int row = Mathf.FloorToInt(point.y / cellSize);
    return (col, row);
}

private static Vector2 NextRandomPoint(Vector2 curPoint, float minDistance)
{
    float angle = GameRand.InclusiveRange(0, 360);
    float radius = GameRand.Range(minDistance, 2 * minDistance);
    float x = curPoint.x + radius * Mathf.Cos(angle);
    float y = curPoint.y + radius * Mathf.Sin(angle);
    return new Vector2(x, y);
}

private static bool IsValidPossionPoint(Vector2 point, Vector2[,] grid, float cellSize, float radius)
{
    var xy = Point2ColRow(point, cellSize);
    int xmax = grid.GetLength(0);
    int yMax = grid.GetLength(1);
    //不在范围内
    if (xy.col < 0 || xy.row < 0 || xy.col >= xmax || xy.row >= yMax)
        return false;
    //与邻近点过近
    for (int i = xy.col - 1; i <= xy.col + 1; ++i)
    {
        for (int j = xy.row - 1; j <= xy.row + 1; ++j)
        {
            if (i < 0 || j < 0 || i >= xmax || j >= yMax)
                continue;
            if (grid[i, j] == Vector2.zero)
                continue;
            if (Vector2.Distance(point, grid[i, j]) < radius)
                return false;
        }
    }
    return true;
}

public static T PickRandomElement<T>(this ICollection<T> elementSet, bool removePicked = true, System.Random rand = null)
{
    T res = default(T);
    if (elementSet == null || elementSet.Count == 0)
    {
        Debug.LogError("Null or Empty Collections");
        return res;
    }
    var randomIdx = -1;
    if (rand == null)
        randomIdx = UnityEngine.Random.Range(0, elementSet.Count);
    else
        randomIdx = rand.Next(0, elementSet.Count);
    res = elementSet.ElementAt(randomIdx);
    if (removePicked)
    {
        elementSet.Remove(res);
    }
    return res;
}

结果

最后表现如下图。

做完后的小插曲

程序：怎么样？是不是你想要的技能效果？
策划：嗯，机制上来说是这样的，不过怎么变闪电打击了？
程序：我觉得水母也能放电的嘛，这不河里吗？
策划：是挺合理的，但是…
程序: 其实还有一个更重要的原因。
策划：什么原因？
程序：咱们有美术和动画大佬来做表现吗？我画画贼烂，要不你试下？

策划：…………..好像是这么个问题。
程序：咱还是先临时用免费资源处理吧，等找到美术大佬了再来改下动画表现。
策划：OKOK。

总结

沟通时，确定对齐好双方的目标往往能够快速理解对方的意图。
如果表达不好，或者对方无法理解文字描述的问题时，那么最好用画图、演示的方式来辅助自己传达意图，一图胜千言。
以需求目的以及实践来驱动的算法学习，就个人而言其效率比纯刷题要高得多。

小咸鱼

使用泊松盘采样实现技能目标区域随机点选取

前言

尝试与分析

代码实现

结果

做完后的小插曲

总结