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?

Are you asking how to spread some amount of monsters around in a circle? There are 2*pi radians around the position. Divide that by 2*monsters+1 giving you the equal spread around the position. As far as them not being able spawn in certain areas I imagine you'll have to use collision detection and resolution for that. — ChiefTwoPencils, Oct 16 '13 at 03:41
A circle has 360 degrees or 2 times pi (3.14...) radians. I say radians because most trig functions rely on radians and not degrees. — ChiefTwoPencils, Oct 16 '13 at 04:03
The thing is I ain't using circles, I'm using multi shaped maps, squares, circles, etc ... It differs for every spawn (X, Y). — Raúl Sanpedro, Oct 16 '13 at 04:06
Oh, that's why I asked. You said you were trying to spawn around a certain radius. A radius is half the length across a circle. That's is why I was relating it to a circle. — ChiefTwoPencils, Oct 16 '13 at 04:09

score 0 · Accepted Answer · edited May 23 '17 at 12:05

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:

Make a list A of all the eligible spawn positions, with a list of adjacent eligible spawn positions for each position in that list.
Select a spawn position randomly from the list A.
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)
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.

I'm now getting a list of eligible positions for each of my monster spawns, however I do not know what's the simpliest way to get adjacent positions from a given position. — Raúl Sanpedro, Oct 16 '13 at 03:59
How to best find the adjacent positions would depend on your geometry but, given that you say `sometimes monsters spawn next to each other, and I really don't want that`, you seem able to determine what locations are `next to` other locations. Thus, the list of adjacent positions for each position would just be the list of positions that meet the `next to` criterion. — Simon, Oct 16 '13 at 05:01

Mathematical Area Position Number Radius Spread

1 Answers1