# How to spawn enemies within a minimum distance of each other randomly? 2D

So I'm making an 2D infinite runner. So I try to spawn obstacles randomly in x-coordinate, but these just spawn most of the time in the same position and too frequently. generationPoint is just a small Empty a medium distance from the camera that's where the obstacles spawn. Even if I make them spawn at a small random rate It's still impossible to play.

{

public GameObject thePlatform;
public Transform generationPoint;
public float distanceBetween;

private float platformWidth;

public ObjectPooler theObjectPool;

public float randomEnemyThreshold;
public ObjectPooler enemyPool;

public float randomReindeerThreshold;
public ObjectPooler ReindeerPool;

void Start () {
platformWidth = thePlatform.GetComponent<BoxCollider2D>().size.x;

}

void Update () {

if (transform.position.x < generationPoint.position.x)
{
transform.position = new Vector3 (transform.position.x + platformWidth + distanceBetween, transform.position.y, transform.position.z);

GameObject newPlatform = theObjectPool.GetPooledObject();

newPlatform.transform.position = transform.position;
newPlatform.transform.rotation = transform.rotation;
newPlatform.SetActive (true);

if (Random.Range (0f, 100f) < randomEnemyThreshold)
{
GameObject newEnemy = enemyPool.GetPooledObject();

Vector3 enemyPosition = new Vector3 (-10f, 0.5f, 0f);

newEnemy.transform.position = transform.position + enemyPosition;
newEnemy.transform.rotation = transform.rotation;
newEnemy.SetActive(true);

}

if (Random.Range (0f, 100f) < randomReindeerThreshold)
{

GameObject newDeer = ReindeerPool.GetPooledObject ();

Vector3 reindeerPosition = new Vector3 (5f, 0.5f, 0f);

newDeer.transform.position = transform.position + reindeerPosition;
newDeer.transform.rotation = transform.rotation;
newDeer.SetActive(true);
}
}

}

}


Poisson disc sampling places the samples (in your case spawn points) randomly, but does so in a way that ensures no two points are not too close & yields a uniform distribution.

Robert Bridson's algorithm is the most efficient way I know, with a performance of O(n). Basically, you divide your space with a grid & when placing a random point, you find its grid cell & check it & the nearby cells for previously placed points. This allows you to discard random placements that would be too close without needing to test all of the points generated so far.

This question/answer on Random enemy placement on a 2d grid has more details & links to tutorials.

Edit with 1D specific details, assuming that you're building things a screen width at a time:

double r;     // minimium distance between points
double width; // screen width
// set r & width
double sqrt2 = 1.41421356237;
double cellSize = r / sqrt2;
int dim = (int) Math.ceil(width / cellSize);
float[] array = new float[dim]


Now, when you generate a new potential point x, find the corresponding index for the cell of that point in the array as follows:

int baseIndex = (int)(x/cellSize);


Then loop & check for previously generated points from array[index-2] to array[index+2] (obviously, be careful not to go past the bounds of the array). If you don't have any points saved in that region, nothing is too close, so add the new point. If you do find something, check the distance between it & the new potential point. If anything is too close, you'll need to discard the new point & generate a new random point. If you find prior points, but none are too close, add the point.

I'm certain there are some ways you could optimize things by taking advantage of the fact that this is a 1D version of the problem, (E.G. tracking empty cells & only attempting to generate points for them).

• I only need a random placement on x coordinates. Can I use Poisson Disc-Sampling for that? – SleepySleeper May 16 '16 at 18:46
• Yes, the concept works across arbitrary dimensions - I'll edit my answer to to reflect a 1D specific use. – Pikalek May 16 '16 at 19:46
• Sorry. Too confusing. I'm a semi-beginner. – SleepySleeper May 17 '16 at 2:41

Here's a way to control the spacing of spawn points, but it requires you to build them in one direction; in this case I'll restrict them to only add new points of increasing value:

// lastX - holds the last X value you generated
// distanceMin - the minimum distance to allow between points
// distanceMax - the maximum distance to allow between points
public double getNextPointX(double lastX, double distanceMin, double distanceMax){
double diff = distanceMax - distanceMin;
return nextX = (Random.NextDouble() * diff) + distanceMin + lastX;
}


So, if you give the method the last x value generated, a min distance & a max distance, it will generate a new random x value that is at least distanceMin away & not more than distanceMax away from the last value.

The easiest way to solve this would be to generate more than new points instead of 1, and pick the one with the highest distance from the other points, and spawn an enemy at it.

This results in a random look, but with the enemies more uniformly spread across the game field.