• Advertisement
Sign in to follow this  

Random Spawn Optimisation

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

If you intended to correct an error in the post then please contact us.

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

 

Thanks in advance to any help you guys can send my way,

~Volvary

Edited by Volvary

Share this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement