3
\$\begingroup\$

I have a 2D grid map that is relatively large. I'd like to pick some semi-random points all over it (say N points). The rule I want to ensure here, though, is that any selected points are at least M distance from every other selected point but no more than L distance from at least one other point.

Is there a fairly elegant way of doing this without having every new point's distance calculated for every existing point (being less computationally expensive as well)?

I imagine the rules could be met by something like partitioning the map out into rectangular segments and just kind of flood-fill randomly from one inner segment outwards, but I'm having a little trouble visualizing that where my L, M, and N values are randomly chosen (L is of course greater than or equal to M, but not entirely sure what the rules will be for M or N or even the size of the map).

The reason for this whole thing is a procedural waypoint system that I can then build a 2D dungeon crawler type map by using a path finding system to create tiles from waypoint to waypoint essentially.

If this is too vague or any other issues, just let me know and I'll happily try to explain further.

Edit: To give some hard numbers as an example, say the full grid is 2,000 by 1,000 total possible points. Assume you want 5,000 total waypoints spread fairly randomly across the map. Each of the 4,000 points need to be (euclidean distance) greater than 20 from every other point and less than 30 away from at least one other point.

\$\endgroup\$
3
  • \$\begingroup\$ Ok so you goal is to generate all the points so they are at a specific distance from one another? \$\endgroup\$ Mar 13, 2015 at 21:49
  • \$\begingroup\$ I'm guessing poisson discs will be useful for this. You can use a quad tree or sorted range data structure to help find the closest point to your new proposed point. Jason Davies has a demo of an efficient algorithm but it only handles M and not your L condition. Still might be a good starting point. \$\endgroup\$
    – amitp
    Mar 14, 2015 at 15:42
  • \$\begingroup\$ I'm not sure understand correctly: Do A) have a grid and want to select points in it that match the criteria. Or B) create a grid with just points that match the criteria? \$\endgroup\$
    – Felsir
    Jul 20, 2015 at 7:59

3 Answers 3

3
\$\begingroup\$

Every point must be greater then 20 and less then 30 away from each other.

Red    is the Point.
Purple is the radius 20 from point. If any point is placed here it means it is inside the radius of another point.
Green  is radius 30 from point.
White  is out side. No points should be placed here because it means that point will be 30 units away from any other point.

enter image description here

Next simply add a point randomly in a green space and fill in its neighbors. enter image description here Each point is now greater then 20 and less then 30 from every other point.

Im guessing you will store your grid of points as a object that contains the state of the square.

There is also this method maybe this is what you were looking for in the first place :D

\$\endgroup\$
2
  • \$\begingroup\$ You've illustrated exactly what I'm going for, but I still don't know quite how to achieve it. I could do a filled circle algorithm working outwards from a radius of 0 to 20 and then 20 to 30, ignore points already seen, and in the 20 to 30 range add them to a "green" list to choose my next point from, but that wouldn't scale very well if I wanted a map with say inner radius 30 and outer radius 400 as an example. Sorry if I didn't explain well, but I'm hoping to have this scale very well so I could set semi-random numbers for my map size, point count, minimum radius, and maximum radius. \$\endgroup\$
    – Mythics
    Mar 14, 2015 at 0:31
  • \$\begingroup\$ I cant seem to find better then O(N^2). How about a pseudo random algorithm? Will that be good enough? There will be some predictability. \$\endgroup\$ Mar 14, 2015 at 10:02
1
\$\begingroup\$

Your point selection rules can be satisfied by a Poisson-Disk sampling distribution & can be solved in O(n) with Bridson's algorithm. Basically, the algorithm divides the output region into a grid of cells sized relative to the minimum allowable distance, such that only one point can appear in each cell. Then, when you consider adding a new point, you only need to check a disk shaped collection of neighboring cells as opposed to the entire list of points. With respect to your problem, the cell & neighborhood size will account for your M parameter, the disk radii will account for your M parameter. Your N parameter is handled by terminating when enough points have been generated.

Mike Bostock has a nice animation showing the algorithm in progress.

The standard implementation is only concerned with a fixed minimal distance between points. amitp mentioned Herman Tulleken's Poisson Disk sampling article; it includes an adaptation to for varying the minimum distance across the resulting image/map which may make it better suited for your problem. It also includes source code.

\$\endgroup\$
0
\$\begingroup\$

Here's an idea of how it might go. Keep in mind the more points you create the less random their placing will be.

For(int i=0; i<3999; i++){
    array.add(new Point(random.int(x);
    random.int(y));
}

For(int i=0; i<3999; i++){
    int dist = Point.calcDistance(array.get(i),array.get(i++)); 
    //distance formula between two points: sqrt((x2-x1)^2+(y2-y1)^2))

    if(dist < 20 && dist> 30){
        array.remove(i++); //or create another one
    }
}
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .