Vector3位置生成方法未满足最小间距要求，求问题排查

我实现了一个按平面区域权重生成指定数量Vector3的方法，要求生成的位置间距不小于设定值，但实例化对象后仍存在间距小于指定值的情况。相关代码如下：

// Generate random point based on plane area
public List<Vector3> GeneratePositions(int numberOfPositions, float minDistanceBetweenPositions)
{
    float entireArea = 0f;
    List<AreasWeight> areasWeights = new List<AreasWeight>();
    List<Vector3> positions = new List<Vector3>();

    foreach (GeneratorPlane plane in GeneratorPlanes.GetCollectionAsList())
    {
        entireArea += plane.GetArea();
    }
    foreach (GeneratorPlane plane in GeneratorPlanes.GetCollectionAsList())
    {
        float weight = plane.GetArea() / entireArea;
        int numOfPositionsInArea = Mathf.RoundToInt(numberOfPositions * weight);
        areasWeights.Add(new(plane, weight, numOfPositionsInArea));
    }

    foreach (AreasWeight areaWeight in areasWeights)
    {
        for (int i = 0; i < areaWeight.NumOfPointsInArea; i++)
        {
            Vector3 generatedPoint = areaWeight.Plane.GetRandomPointOnPlane();

            foreach (Vector3 position in positions)
            {
                int attempts = 1;

                while ((position - generatedPoint).magnitude < minDistanceBetweenPositions)
                {
                    generatedPoint = areaWeight.Plane.GetRandomPointOnPlane();
                    attempts++;

                    if (attempts > 2000)
                    {
                        Debug.Log("Can't generate all positions.");
                        break;
                    }
                }

            }
            positions.Add(generatedPoint);
        }
    }

    return positions;
}

随机点生成方法：

public Vector3 GetRandomPointOnPlane()
{
    float xPosition = Random.Range(Mathf.Min(DownPoint.x, DownPointHelper.x), Mathf.Max(DownPoint.x, DownPointHelper.x));
    float zPosition = Random.Range(Mathf.Min(DownPoint.z, UpPointHelper.z), Mathf.Max(DownPoint.z, UpPointHelper.z));

    return new(xPosition, DownPoint.y + 0.002f, zPosition);
}

错误原因分析 #

• 间距检查逻辑漏洞：当前遍历每个已存在点时，仅针对单个点重新生成新坐标，但新生成的坐标只通过了当前单个点的间距校验，没有重新检查所有已存在点。比如新点满足和点A的间距要求，但可能和点B的间距仍不达标，却直接被加入列表。
• 尝试次数变量作用域错误：attempts变量放在foreach (Vector3 position in positions)循环内部，每次遍历一个已存在点都会重置尝试次数，导致实际总尝试次数被分散，即使累计尝试远超2000次也无法触发终止逻辑，甚至可能生成不符合要求的点。

修正后的代码 #

// Generate random point based on plane area
public List<Vector3> GeneratePositions(int numberOfPositions, float minDistanceBetweenPositions)
{
    float entireArea = 0f;
    List<AreasWeight> areasWeights = new List<AreasWeight>();
    List<Vector3> positions = new List<Vector3>();

    foreach (GeneratorPlane plane in GeneratorPlanes.GetCollectionAsList())
    {
        entireArea += plane.GetArea();
    }
    foreach (GeneratorPlane plane in GeneratorPlanes.GetCollectionAsList())
    {
        float weight = plane.GetArea() / entireArea;
        int numOfPositionsInArea = Mathf.RoundToInt(numberOfPositions * weight);
        areasWeights.Add(new(plane, weight, numOfPositionsInArea));
    }

    foreach (AreasWeight areaWeight in areasWeights)
    {
        for (int i = 0; i < areaWeight.NumOfPointsInArea; i++)
        {
            Vector3 generatedPoint;
            int attempts = 0;
            bool isPointValid;

            do
            {
                attempts++;
                generatedPoint = areaWeight.Plane.GetRandomPointOnPlane();
                // 校验新点与所有已存在点的间距
                isPointValid = true;
                foreach (Vector3 position in positions)
                {
                    if ((position - generatedPoint).magnitude < minDistanceBetweenPositions)
                    {
                        isPointValid = false;
                        break;
                    }
                }

                if (attempts > 2000)
                {
                    Debug.Log("Can't generate all positions.");
                    break;
                }
            } while (!isPointValid);

            // 仅添加有效点
            if (isPointValid)
            {
                positions.Add(generatedPoint);
            }
            else
            {
                // 无法生成有效点时可选择终止或跳过
                break;
            }
        }
    }

    return positions;
}

额外优化建议 #

• 提前校验可行性：先估算所有平面的总可容纳点数（每个点所需最小面积为π*(minDistanceBetweenPositions/2)²），如果需求点数超过可容纳上限，直接提前提示，避免无效尝试。
• 优化间距检查效率：若生成点数较多，遍历所有点检查间距会降低性能，可使用网格分区、四叉树等数据结构，仅检查同区域或相邻区域的点，提升校验速度。

内容的提问来源于stack exchange，提问作者Mylo