Алгоритм генерации случайных координат в двумерной плоскости

#алгоритм #случайные_числа #генерация_случайных_данных

Какой можно придумать алгоритм генерации случайных неповторяющихся координат на сетке
width и height размера, с range - расстоянием между ними и count количеством?
То есть чтобы результат был примерно следующим:
height = 10, width = 9 count = 3 range = 2

           или
.........      .........
.........      .........
....C....      .........
.........      .........
.........      .........
.C.......      .........
.........      .......C.
.......C.      ....C....
.........      .........
.........      ......C..

    

Ответы

Ответ 1

Двумерную сетку можно вытянуть в одномерный массив:

x = i * width + j


и соответственно вернуться к двумерной сетке:

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


То есть задача сводится к генерации не повторяющихся индексов от 0 до width*height-1:


Создаем массив x длиной N = width*height, заполняем его числами от 0 до width*height-1.
Берем случайное число n в диапазоне от 0 до N-1
x[n] превращаем в пару (i,j)
Ставим x[n] в конец массива (меняем его местами с x[N-1])
Уменьшаем N на 1.
Повторяем начиная с шага 2.


Ответ 2

Думал, думал и наконец придумал и отладил алгоритм.
У меня проверяется расстояние по ромбовидному принципу



range = 3

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




Создаем одномерный boolean массив.
Забиваем массив значениями true (Если true - то место свободно)
Создаем случайную координату в пределах поля (Для координат я использовал свой класс
Coordinate. В нем я определил лишь два поля. X и Y)
Проверяем, доступна ли координата. (Я использовал функцию GetAddress)


Если доступна (true), генерируем координаты вокруг этой точки (Тут я пользовался
функцией GetDiamondAreaCoordinates, но можно и любую другую вашу. Например квадратная
область или круглая) и проверяем итератором валидны ли точки.
Если не доступна возвращаемся к пункту 3.

Если каждая точка области не за пределами поля, в boolean массив через функцию GetAddress
забиваем false.


Если за пределами, то продолжаем цикл.  





public Coordinate[] GetDiamondAreaCoordinates(Coordinate coordinate, int range) {
    ArrayList 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;
}