Random Spawn Optimisation

This topic is 923 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hey everyone,

I am currently in the process of developping a game with a circular "arena" and I'm closing in to the actual spawning of my enemies but I was wondering what the best way to determine spawn locations at random was, efficiency wise. (Since I am planning to port this to mobile, any improvement counts)

My idea was something along these lines:

-Determine a random position in X and Z.

-Normalize the vector

-Multiply by the size of my arena.

Would there be a more efficient way of doing it? (EDIT: I intend to only spawn on the edge of the circle of my arena.)

~Volvary

Edited by Volvary

Share on other sites
I can't imagine picking a random point in a circle can possibly be a bottleneck, even in a mobile platform.

The easiest way to pick a random point in a circle uniformly is to pick a random point in a containing square repeatedly until the point happens to be inside the circle.

  do {
p.x = uniform_random(-1.0f, +1.0f);
p.y = uniform_random(-1.0f, +1.0f);
} while (p.x*p.x + p.y*p.y > 1.0f);


Share on other sites

My idea was something along these lines:

-Determine a random position in X and Z.
-Normalize the vector
-Multiply by the size of my arena.
This means enemies are always at the border of the circle? (normalized * size == size, after all).

You could just generate an angle, or an angle and a distance, but it may not be worth the trouble, you'd have to measure performance first if you want to know.

Share on other sites

That would work except for two issues: The first is that you're not going to get an even distribution around the edges because there will be a slight bias towards the corners. You can fix that by ensuring your random positions fall within a circle, not the square X-Z plane. The other problem is that there is a minuscule chance your random position would be (0, 0) which will cause a division by zero error when you try to normalize the vector. You can fix that by ensuring the position you generate is some minimum distance away from the center.

To generate a random evenly distributed direction, follow this algorithm:

1. Generate random x and y coordinates between -1 and +1
2. Calculate the squared length of the vector (using Pythagoras: lengthSquared = x*x + y*y).
3. If the squared length is greater than or equal to 1, or less than some small (but non-zero) minimum then discard those coordinates and return to step 1
4. Normalize the vector and return it.

Once you have the direction the rest of your algorithm is correct. Multiply the vector by the arena's radius and add its center position to get a random position along the edge.

Share on other sites

The easiest way to pick a random point in a circle uniformly is to pick a random point in a containing square repeatedly until the point happens to be inside the circle.

  do {
p.x = uniform_random(-1.0f, +1.0f);
p.y = uniform_random(-1.0f, +1.0f);
} while (p.x*p.x + p.y*p.y > 1.0f);


You should exclude points that are exactly on the edge or you'll get a very small bias in the result. Most PRNGs generate numbers between 0 inclusive and 1 exclusive, so they might generate a point like (0.6, 0.8) but never (0.0, 1.0) or (1.0, 0.0).

Share on other sites

I should have mentioned at first that yes, I intend to only spawn on the edge of the circle since I am using a heavy fog and want every enemy to spawn at the same distance. (I'll edit the OP to clarify things.)

Share on other sites

I think generating a random radian angle and converting that to a position would be relatively quick, even on mobile.  Yes, you have to call sincos, but that's not all that expensive.  How many things are you going to spawn every frame?  Are you worried about overlap?

Share on other sites

Create an array of something like 1000 locations around the circle. Put spawns in a random location and eventually mark as occupied also nearby locations to avoid duplicate spawns. If density of enemies is not too much you are done by generating in loop new random locations until you find a free spot, otherwise you just have to move at the end of the array occupied places (swap 2 numbers) and generate a random number between 0 and the last free location.

Share on other sites

The easiest way to pick a random point in a circle uniformly is to pick a random point in a containing square repeatedly until the point happens to be inside the circle.

  do {
p.x = uniform_random(-1.0f, +1.0f);
p.y = uniform_random(-1.0f, +1.0f);
} while (p.x*p.x + p.y*p.y > 1.0f);


You should exclude points that are exactly on the edge or you'll get a very small bias in the result. Most PRNGs generate numbers between 0 inclusive and 1 exclusive, so they might generate a point like (0.6, 0.8) but never (0.0, 1.0) or (1.0, 0.0).

That depends on the particular semantics of `uniform_random', which I haven't specified. In any case, I don't usually worry about things with probability zero. If I give you my algorithm in a black box, how long would you have to test it before you can decide with some statistical significance that my algorithm is biased?

Share on other sites

Would you be doing each enemy by itself or will you be using "waves" of enemies?

I just wonder this because if you are using waves you could buffer a fixed amount of enemy slots and allocate them while showing "Wave # Incoming" type of message and hide a slight lag as the group is set up.  This would allow you to use a slightly less efficient method and not have to worry so much.

Of course if your circle is a fixed has radius/diameter, you could simply pre calculate a group of starting points (say 60 or 90 points on a circle) and then you would simply need to randomly generate an integer for which fixed position each enemy started at, which could be even more efficient than on the fly calculations.

1. 1
Rutin
24
2. 2
3. 3
JoeJ
20
4. 4
5. 5

• 9
• 46
• 41
• 23
• 13
• Forum Statistics

• Total Topics
631749
• Total Posts
3002040
×