Create random points with a given minimum and maximum distance

Question

I need algorithmic ideas for creating points in a 2D space with given minimum and maximum possible distances between points.

Bassicaly, I want to find a good way to insert a point in a 2D space filled with points, so that the point has a random location, but also more MINIMUM_DISTANCE_NUM and less than MAXIMUM_DISTANCE_NUM far from the nearest points.

I need this for the game, so it should be fast and independent of random probability.

Answer 1

You can use a 2D regular grid of points (P0, P1, P2, P3, ..., P (m * n) when m is the width and n is the height of this grid)

Each point is associated with 1) a Boolean statement that this grid point was used or not, and 2) a “shift” from this grid position to avoid too much regularity. (or you can put the point + shear coordinates in your allready grid)

Then, when you need a new point, just select a random point on your grid that has not been used, select that point as “used” and use the Point + shift in your game.

Depending on the n, m, width / height of your 2D space and the number of points you are going to use, this might just be great.

Answer 2

Save the point set in the Kd tree. Create a new point at random, then explore its nearest neighbors, which can be quickly found in the Kd tree. If the point is accepted (i.e. MIN_DIST <nearest neighbor <MAX_DIST), add it to the tree.

It should be noted that this will work best in conditions where the points are not too densely packed, that is, MIN * N <L, where N is the number of points, and L is the size of the field into which you insert them. If this is not the case, then most new points will be rejected. But think about it, in this limit you pack marble into a box, and the arrangement cannot be very “random” at all above a certain density.

Answer 3

How many points are you talking about? If you have an upper limit on the number of points, you can generate (pre-calculate) an array of points and store them in an array. Take this array and save them in a file.

You will have all the complex computational processing before loading the map (so you can use any random point generation algorithm), and then you have a good quick way to get your points.

Thus, you can create a ton of different cards, and then randomly select one of the cards to create your points.

This only works if you have an upper limit, and you can pre-calculate points before the game loads