What can you think of an algorithm for generating random non-repeating coordinates on a width and height grid of size, with a range — the distance between them and the count number? That is, the result should be approximately as follows: height = 10, width = 9 count = 3 range = 2

  или ......... ......... ......... ......... ....C.... ......... ......... ......... ......... ......... .C....... ......... ......... .......C. .......C. ....C.... ......... ......... ......... ......C..
  • You come up with a function to calculate the distance between points, generate random coordinates and check them with each of the existing points so that the distance is as needed. And so until the required number of points. What is the problem? - Vladimir Martyanov
  • checking with each one is a very laborious process, if there is a field of 10000x10000 - the generation will be long, you need to not immediately repeat - Herrgott
  • Then the function of finding the coordinates at a distance X from the given one and check that there is no point in any of them. - Vladimir Martyanov
  • one
    This should be checked in a circle, and plus my main fear is that with a small field there can be an infinite cycle. If there is no free space to set the point - Herrgott
  • Teeth to be afraid ... Make a separate check that the number of permissible points is greater than the number required. In general, I do not see any serious problems. - Vladimir Martyanov

2 answers 2

A two-dimensional grid can be pulled out into a one-dimensional array:

 x = i * width + j

and accordingly return to the two-dimensional grid:

 i = floor(x / width) j = x - width * i

That is, the task is reduced to the generation of non-repeating indices from 0 to width*height-1 :

  1. Create an array of x length N = width*height , fill it with numbers from 0 to width*height-1 .
  2. Take a random number n in the range from 0 to N-1
  3. x [n] turn into a pair (i,j)
  4. Put x[n] at the end of the array (swap it with x[N-1] )
  5. Reduce N by 1.
  6. Repeat from step 2.
  • I've almost done, thanks. And thanks for the translation formulas from one-dimensional to two-dimensional, I did not know. I also need to have a distance between them. I made it so that when generating, it takes count range parameters. In a week there will be a ready code - Herrgott
  • And what does the floor variable mean by the way? - Herrgott
  • @Hergott, floor - the integer part of a number - Taras
  • And for sure - a function, I forgot completely - Herrgott

I thought, thought and finally came up with and debugged the algorithm. I checked the distance on the diamond principle

range = 3

....o....
...ooo...
..ooooo..
.oooXooo.
..ooooo..
...ooo...
....o....

  1. Create a one-dimensional boolean array.
  2. We hammer in an array with true values ​​(If true , then the place is free)
  3. Create a random coordinate within the field (For coordinates, I used my Coordinate class. In it, I defined only two fields. X and Y)
  4. Check if the coordinate is available. (I used the GetAddress function)
    • If available ( true ), we generate coordinates around this point (I used the GetDiamondAreaCoordinates function GetDiamondAreaCoordinates , but any other of yours is possible. For example, a square area or a round one) and check with an iterator whether points are valid.
    • If not available, return to step 3.
  5. If each point of the area is not outside the field, in the boolean array through the GetAddress function we GetAddress false.
    • If outside, then continue the cycle.
 public Coordinate[] GetDiamondAreaCoordinates(Coordinate coordinate, int range) { ArrayList<Coordinate> coordinates = new ArrayList<>(); int offsetHeight = 0, offsetWidth = range; int currentX = coordinate.getLeft(); int currentY = coordinate.getTop(); int localIterator = 0; for (int i = currentX-range; i < currentX+range+1; i++) { for (int j = currentY-offsetHeight; j < currentY+offsetHeight+1; j++) { coordinates.add(new Coordinate(i, j)); } offsetWidth --; offsetHeight += (currentX-offsetWidth <= currentX)? 1 : -1; } Coordinate[] resultCoords = coordinates.toArray(new Coordinate[coordinates.size()]); return resultCoords; } 
 private int getAddress(int top, int left) { int index = top*width+left; if (index >= 0 && index < width*height) return index; return -1; }