Calculation of the probability value in the range with the min / max boundaries

Question

Think of a two-dimensional grid, for example. 1000x1000 cells in size, which is used as a level map in the game. This map is dynamically populated with game objects at runtime. Now we need to calculate the probability of placing a new object at a given position x / y in this grid.

That I already have an array int, it keeps the number of game objects at a close distance from the cell in x / y. The index of this array represents the distance of the cell to the given cell, and each value in the array reports the number of game objects in the grid at that distance. So, for example, an array might look like this:

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

This would mean that 0 objects are in the grid cell along x / y itself, 0 objects are in the cells of the direct neighbor, 1 object is in the cell with a distance of two cells, 2 objects are in the cells the distance of three cells, etc. The following figure shows this example:

Now the task is to calculate how likely it is to place the new object in x / y based on the values ​​in this array. The algorithm should be something like this:

• if at least one object is already closer than min, then the probability should be 0.0
• else, if the object is not at a distance max, then the probability should be 1.0
• otherwise the probability depends on how many objects are close to x / y and how many.

, : , , . , , , . , x/y - , , .

, .
?

PS: , , .

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). , , , .

Answer 2

, - .

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;
}

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;
}

Answer 4

:

1/( [min, max], x/y + 1).

, , x/y , , . (max + 1) -distance.

Answer 5

, (. "" " ), ( ).

(PDF) , [0, 1], (. ), :

• ,

If you want to experiment with different goals (PDF function forms are linear, quadratic, hyperbolas, circles, ...), you can take a look at the factory so you can switch between implementations when calling the same method name, but I wanted to simplify my example, so I implemented only the first goal (in 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())