在最小值/最大值范围内计算概率值

Question

考虑一个二维网格，比如1000x1000个单元格的大小，作为游戏中一关卡的地图。此地图在运行时动态填充了游戏对象。现在我们需要计算将新对象放置到该网格中给定x/y位置的概率。

已经有一个int数组，它保存了靠近x/y位置的游戏对象数量。该数组的索引表示到给定单元格的距离，数组中的每个值告诉该距离处网格上的游戏对象数。例如，该数组可能如下所示：

0, 0, 1, 2, 0, 3, 1, 0, 4, 0, 1

这意味着在x/y格子中没有0个对象，相邻的格子中也没有0个对象，与两个单元格距离的单元格中有1个对象，在三个单元格距离的单元格中有2个对象，以此类推。以下图示说明此示例：

任务现在是根据该数组中的值计算在x/y处放置新对象的可能性。算法应该是这样的：

- 如果至少有一个对象比min更近，则概率必须为0.0 - 否则，如果没有对象在max距离内，则概率必须为1.0 - 否则，概率取决于有多少对象靠近x/y，以及有多少个对象。

换句话说：如果已经有至少一个游戏对象非常接近，我们不想要一个新的对象。另一方面，如果没有对象在max半径内，我们无论如何都想要一个新对象。否则，我们希望根据靠近x/y的其他对象数量以及它们的距离来放置一个新对象——越靠近的对象越多，距离越近，我们就越不希望放置一个新对象。

希望我的描述清楚易懂。您能想到一个优雅的算法或公式来计算这个概率吗？

PS：对于这个问题的标题，我很抱歉，我不知道如何更好地概括我的问题。

- Matthias

---

你能解释一下第三种情况中如何计算概率吗？另外，这些概率是用于接受所选点的吗？例如：“我在网格上选择一个随机点。我以p的概率接受它，否则拒绝并选择一个新的。”？还是你正在生成一个未归一化的似然分布，然后从中采样单元格？ - Carsten

@Carsten：我不会一次性生成这些对象。相反，在运行时，我只是获取一个网格单元的x/y坐标和上述描述的数组。对于你的第一个问题：正如所说，越靠近x/y的对象越多，它们越接近，我就越不想创建新的对象。没有更多或更具体的要求。 - Matthias

那么，您是否满意于在首先计算的单元格中生成更多的对象？如果您的网格具有边缘（即左上角单元格的计数不包括来自右下角的对象），则会在角落和边缘获得更多的对象。 - Aprillion

@deathApril：是的，我想至少对于第一个版本来说这应该是可以的。但是当然：最后对象分布越均匀，就越好 :) - Matthias

Answer 1

我建议考虑一种方法，为该方格计算“人口密度”。人口密度越低，放置物品的概率就越高。

正如您所说，如果在（x,y）处有物品，那么您无法在那里放置物品。因此，将其视为1.0的人口密度。

在外面的下一个层级上，有8个可能的相邻区域。该层级的人口密度将是n/8，其中n是那个层级上的物品数量。因此，如果有3个与（x，y）相邻的对象，则该级别的密度为3/8。再除以(distance+1)。

对于所有级别都做同样的处理。即计算每个层的密度，除以(distance+1)，并求和。每个级别的除数是(distance*8)。因此，您的除数为8、16、24等。

计算结果后，您可能需要稍微调整一下数字来调整概率。也就是说，如果您得出了0.5的总和，那么该空间很可能相当拥挤。您不想使用(1-density)作为生成物品的概率。但是我上面提到的方法应该会给您一个单一的数字，这应该可以简化问题。

因此，算法看起来像这样：

total_density = 0;
for i = 0; i < max; ++i
    if (i == 0)
        local_density = counts[i]
    else
        local_density = counts[i]/(i*8);  // density at that level
    total_density = total_density + (local_density/(i+1))

如果将本地密度除以 (i+1) ，会夸大距离的影响，考虑使用 log(i+1) 或者 sqrt(i+1)。我发现在其他距离是一个因素但不是线性的情况下，这些方法非常有用。

- Jim Mischel

---

谢谢您详细的回答，听起来是一种有趣的方法。不过我有一个问题：您是怎么得出 ((distance+2)^2)-1 作为除数的呢？这听起来很合理，但背后的思路是什么？ - Matthias

哦，是的，我现在明白了。非常感谢！ - Matthias

下投票者：通常需要提供下投票的原因。你具体不同意这里的什么？ - Jim Mischel

但是在距离2的地方有16个单元格。对于距离大于0，正确的单元格数量为distance*8（当距离=0时为1，但如果单元格本身被占用，则无需计算此值）。 - Aprillion

@deathApril：感谢您的纠正。我已经编辑了答案。 - Jim Mischel

Answer 2

假设您的数组名称为distances。

double getProbability()
{
    for(int i=0 ; i<min ; i++)
    {
        if(distances[i]!=0) return 0;
    }

    int s = 0;
    bool b = true;
    for(int i=min ; i<max ; i++)
    {
        b = b && (distances[i]==0)
        s+= distances[i]/(i+1);
    }
    if(b) return 1;

    for(int i=0 ; i<distances.Count() ; i++)
    {
        s+= distances[i]/(i+1);
    }
    else return (float)s/totalObjectNum;
}

- Sachamora

---

谢谢，但我认为你的解决方案没有考虑到其他物体有多接近。正如所说的一个要求是：一个物体离x/y越近，放置新物体的可能性就越小。因此，我们必须尊重周围物体的距离，而不仅仅是它们的数量。 - Matthias

@Matthias，请查看新的编辑。 - Sachamora

Answer 3

这种方法计算距离大于min且小于等于max的对象的加权和。 同时计算一个上限（称为normWeight），该上限仅取决于max。

如果至少有一个对象距离大于min且小于等于max，则最接近1的概率将是1-（1/normWeight），对于外环上的1个对象。 最小概率将是1-（（normWeight-1）/ normWeight）。例如，对于外环上的max-1个对象。

通过计算变量delta的不同值来修改加权和的计算。

float calculateProbabilty()
{
    vector<int> numObjects; // [i] := number of objects in a distance i
    fill numObjects ....

    // given:
    int min = ...;
    int max = ...; // must be >= min


    bool anyObjectCloserThanMin = false;
    bool anyObjectCloserThanMax = false;

    // calculate a weighted sum

    float sumOfWeights  = 0.0;
    float normWeight    = 0.0;

    for (int distance=0; distance <= max; distance++)
    {
        // calculate a delta-value for increasing sumOfWeights depending on distance
        // the closer the object the higher the delta
        // e.g.: 
        float delta = (float)(max + 1 - distance);
        normWeight += delta;

        if (numObjects[distance] > 0 && distance < min)
        {
            anyObjectCloserThanMin = true;
            break;
        }

        if (numObjects[distance] > 0)
        {
            anyObjectCloserThanMax = true;
            sumOfWeights += (float)numObjects[distance] * delta;
        }
    }

    float probability = 0.0;

    if (anyObjectCloserThanMin)
    {
        // if at least one object is already closer than min, then the probability must be 0.0
        probability = 0.0;
    }
    else if (!anyObjectCloserThanMax)
    {
        //  if no object is within a distance of max, then the probability must be 1.0
        probability = 1.0;
    }
    else
    {
        // else the probability depends on how many objects are close to x/y

        // in this scenario normWeight defines an upper limited beyond that 
        // the probability becomes 0
        if (sumOfWeights >= normWeight)
        {
            probability = 0.0;
        }
        else
        {
            probability = 1. - (sumOfWeights / normWeight);
            // The probability closest to 1 would be 1-(1/normWeight) for 1 object on the outer ring.
            // The minimal probability would be 1-((normWeight-1)/normWeight). E.g. for
            // max-1 objects on the outer ring.
        }
    }

    return probability;
}

- n-o-d

Answer 4

一个简单的方法可能是：

1 /（在[min,max]范围内所有邻居距离x/y加1的权重之和）。

通过加权，我指的是到x/y距离更近的邻居的数量乘以比不那么接近的邻居更大的因子。作为权重，您可以采取（max + 1）-距离。

- ma0ho

Answer 5

请注意，一旦计算出对象密度（请参见前面答案中的“人口密度”或“距离内这些对象的加权和”），您仍需要将该值转换为插入新对象的概率（在其他答案中没有得到很好的解释）。

概率函数（PDF）需要针对所有可能的对象密度定义，即在闭区间[0, 1]上，但是它可以朝着任何您所需的目标进行形状化（请参见插图），例如：

• 将当前对象密度移向期望的最大对象密度
• 在考虑本地对象密度的情况下，保持插入总体概率不变

如果您想尝试各种目标（PDF函数形状-线性、二次、双曲线、圆截面等），您可能希望看看工厂方法模式，这样您可以在调用相同的方法名称时切换实现，但是我想在我的示例中保持简单，因此我仅实现了第一个目标（用Python）：

def object_density(objects, min, max):
    # choose your favourite algorithm, e.g.:
    #  Compute the density for each level of distance
    #  and then averages the levels, i.e. distance 2 object is
    #  exactly 8 times less significant from distance 1 object.
    #  Returns float between 0 and 1 (inclusive) for valid inputs.
    levels = [objects[d] / (d * 8) for d in range(min, max + 1)]
    return sum(levels) / len(levels)

def probability_from_density(desired_max_density, density):
    # play with PDF functions, e.g.
    #  a simple linear function
    #   f(x) = a*x + b
    #  where we know 2 points [0, 1] and [desired_max_density, 0], so:
    #      1 = 0 + b
    #      0 = a*desired_max_density + b
    #  Returns float betwen 0 and 1 (inclusive) for valid inputs.
    if density >= desired_max_density:
      return 0.0
    a = -1 / desired_max_density
    b = 1
    return a * density + b

def main():
    # distance 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
    objects = [0, 0, 1, 2, 0, 3, 1, 0, 4, 0, 1]
    min = 2
    max = 5
    desired_max_density = 0.1

    if sum(objects[:min]):  # when an object is below min distance
      return 0.0 
    density = object_density(objects, min, max)  # 0,0552
    probability = probability_from_density(desired_max_density, density)  # 0,4479
    return probability

print(main())

- Aprillion

---

请注意，以下Python代码实际上是可执行的，如果有人想要尝试，请点击此链接（http://www.compileonline.com/execute_python3_online.php）。但在Python 2.7中，需要添加“from future import division”语句。 - Aprillion