Calculating a probability value in range with min / max bounds

Question

Think of a 2D grid, e.g. in the size of 1000x1000 cells, which is used as the map of a level in a game. This map is dynamically filled with game objects during runtime. Now we need to calculate the probability of placing a new object into the a given x/y position in this grid.

What I have already is an int array the holds the number of game objects in close distance to the cell at x/y. The index of this array represents the cell distance to the given cell, and each value in the array tells the number of game objects in the grid at that distance. So for example the array could 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 at x/y itself, 0 objects are in the direct neighbour cells, 1 object is in a cell with a distance of two cells, 2 objects are in the cells of a distance of three cells, and so on. The following figure illustrates this example:

The task now is to calculate how likely it is to place a new object at 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 must be 0.0
• else if no object is within a distance of max, then the probability must be 1.0
• else the probability depends on how many objects are close to x/y, and how many.

So in other words: if there is at least one game object already very close, we don't want a new one. On the other hand if there is no object within a max radius, we want a new object in any case. Or else we want to place a new object with a probability depending on how many other objects there are close to x/y -- the more objects are close, and the closer they are, the less likely we want to place a new object.

I hope my description was understandable.
Can you think of an elegent algorithm or formula to calculate this probability?

PS: Sorry for the title of this question, I don't know how to summarize my question better.

Answer 1

One approach I'd consider is to compute a "population density" for that square. The lower the population density, the higher the probability that you would place an item there.

As you say, if there is an item at (x,y), then you can't place an item there. So consider that a population density of 1.0.

At the next level out there are 8 possible neighbors. The population density for that level would be n/8, where n is the number of items at that level. So if there are 3 objects that are adjacent to (x,y), then the density of that level is 3/8. Divide that by (distance+1).

Do the same for all levels. That is, compute the density of each level, divide by (distance+1), and sum the results. The divisor at each level is (distance*8). So your divisors are 8, 16, 24, etc.

Once you compute the results, you'll probably want to play with the numbers a bit to adjust the probabilities. That is, if you come up with a sum of 0.5, that space is likely pretty crowded. You wouldn't want to use (1-density) as your probability for generating an item. But the method I outline above should give you a single number to play with, which should simplify the problem.

So the algorithm looks something like:

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

If dividing the local density by (i+1) over-exaggerates the effect of distance, consider using something like log(i+1) or sqrt(i+1). I've found that to be useful in other situations where the distance is a factor, but not linearly.