Mathematical Area Position Number Radius Spread

Question

I'm working on a video game written in C++, and I'm trying to create monster spawns based on a given radius, let's say I define a position like this:

Position ( X, Y, Z ) Amount ( Value )

What that code does is the start point is Position, and I want to place (Amount) monsters around the start point (X = X-Amount, Y = Y-Amount, X = X+Amount, Y = Y+Amount), there's a maximum of 9 monsters per spawn.

The code I'm using right now is pretty noobish:

// 1000 tries because I'm using random numbers
for (int i = 0; i < 1000; i++)
{
    toPlace = centerPos;

    toPlace.x = uniform_random(centerPos.x-monsterAmount, centerPos.x+monsterAmount);
    toPlace.y = uniform_random(centerPos.y-monsterAmount, centerPos.y+monsterAmount);

    if (Monster->CanSpawnAt(toPlace))
    {
        Monster->Spawn();
        break;
    }
}

Position calculation is using monsterAmount (amount of monsters defined by user), so if there are 3 monsters, then it's -3 behind and +3 positions in front.

It's bad because I'm using a random value, hence why I'm inside a for loop of 1000, because sometimes the monster can't spawn on the given position.

Also sometimes monsters spawn next to each other, and I really don't want that. I'm wondering if you guys could help me by telling me what is the mathematical algorithm I should use for this type of task?

Answer 1

If you have a set of discrete eligible spawn positions (which I'm guessing you do, given that you are adding and subtracting small integers from the center position), then you could use an algorithm like this:

1. Make a list A of all the eligible spawn positions, with a list of adjacent eligible spawn positions for each position in that list.
2. Select a spawn position randomly from the list A.
3. Remove the selected spawn position and all of its adjacent positions from list A. (This will prevent monsters spawning in positions adjacent to any previously-spawned monster)
4. Repeat from step 2 until all monsters have spawned or until there are no remaining eligible spawn positions (i.e. the length of list A is zero).

This is a form of reservoir sampling. It avoids a trial-and-error approach to finding the spawn position by doing some pre-computation first. Thus, whether to use trial-and-error or this method (or some other method) will depend on how satisfactory or unsatisfactory the trial-and-error approach is.