CODEWITHSUNDEEP
algorithm
deloki
deloki

Reputation: 1771

Generating random points with defined minimum and maximum distance

I need algorithm ideas for generating points in 2D space with defined 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, in such manner that the point has random location, but is also more than MINIMUM_DISTANCE_NUM and less than MAXIMUM_DISTANCE_NUM away from nearest points.

I need it for a game, so it should be fast, and not depending on random probability.

Upvotes: 8

Views: 6215

Answers (4)

antonagestam
antonagestam

Reputation: 4789

A good option for this is to use Poisson-Disc sampling. The algorithm is efficient (O(n)) and "produces points that are tightly-packed, but no closer to each other than a specified minimum distance, resulting in a more natural pattern".

https://www.jasondavies.com/poisson-disc/

Upvotes: 2

gcbenison
gcbenison

Reputation: 11963

Store the set of points in a Kd tree. Generate a new point at random, then examine its nearest neighbors which can be looked up quickly in the Kd tree. If the point is accepted (i.e. MIN_DIST < nearest neighbor < MAX_DIST), then add it to the tree.

I should note that this will work best under conditions where the points are not too tightly packed, i.e. MIN * N << L where N is the number of points and L is the dimension of the box you are putting them in. If this is not true, then most new points will be rejected. But think about it, in this limit, you're packing marbles into a box, and the arrangement can't be very "random" at all above a certain density.

Upvotes: 7

GameAlchemist
GameAlchemist

Reputation: 19294

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

Each point is associated with 1) a boolean saying wether 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+shift coordinates in your grid allready)

Then when you need a new point, just pick a random point of your grid which was not used, state this point as 'used' and use the Point+shift in your game.

Depending on n, m, width/height of your 2D space, and the number of points you're gonna use, this could be just fine.

Upvotes: 4

joe_coolish
joe_coolish

Reputation: 7259

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

You'll have all the hard computational processing done before the map loads (so that way you can use any random point generating algorithm) and then you have a nice fast way to get your points.

That way you can generate a ton of different maps and then randomly select one of the maps to generate your points.

This only works if you have an upper limit and you can precomputer the points before the game loads

Upvotes: 0

Related Questions