Как я могу сделать алгоритм, который будет случайным образом помещать 1 в массив 2d, при этом убедитесь, что есть путь от нижнего левого до верхнего правого пространства? - PullRequest
Новая
       30

Как я могу сделать алгоритм, который будет случайным образом помещать 1 в массив 2d, при этом убедитесь, что есть путь от нижнего левого до верхнего правого пространства?

0 голосов
/ 27 мая 2018

Я пытаюсь сделать простую Java-игру, в которой игрок не может видеть мир (двумерный массив) и должен ввести «вправо», «влево», «вверх» или «вниз».Игрок должен пройти из левого нижнего угла в верхний правый через определенное время.Массив будет заполнен нулями, а единицы будут назначаться случайным образом, при этом убедитесь, что между началом и концом есть путь.Вот что у меня есть: 

public class PathMaker {

    private int [][]arr;

    public PathMaker(int Difficulty){
        if (Difficulty == 1)
            arr = new int[5][5];
        if (Difficulty == 2)
            arr = new int[5][5];
        if (Difficulty == 3)
            arr = new int[5][5];
        Pathset(arr);
    }

    private static void Pathset(int [][]arr){
        int length = arr.length;
        int trees = (length-1)*2;
        int a, b;
        int check = 0;
        arr[0][0] = 1;
        for (int i = 0; i < trees; i++){
            a = (int)((Math.random()*length)+1);
            b = (int)((Math.random()*length)+1);
            while(check == 0){
                if (((arr[a+1][b] == 0) && (arr[a][b+1] == 0)) || a == 1 || b == 1)
                    check = 1;
                a = (int)((Math.random()*length)+1);
                b = (int)((Math.random()*length)+1);
            }
            arr[a][b] = 1;
        }
    }
}

Я новичок, поэтому, пожалуйста, объясните мне, как это сделать, спасибо.

1 Ответ

0 голосов
/ 04 июня 2018

Полагаю, вам нужен результат, который выглядит как случайно разбросанные деревья вместо лабиринта, но при этом гарантируется, что через него будет проходить путь.

Там будет путь к нижнему левому квадрату дляверхний правый квадрат, если нет цепочки деревьев, соединяющей верхнюю или левую сторону с нижней или правой стороной.

Это можно решить с помощью структуры данных union-find: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

  1. Сделайте набор для верхней + левой сторон и набор для нижней + правой сторон.Во время алгоритма вы также добавите наборы для всех деревьев, которые вы добавляете.
  2. Перебирайте квадраты в случайном порядке и попробуйте добавить дерево для каждого, как показано ниже.
  3. Комупроверить квадрат, найти все наборы, к которым он подключается.Это включает в себя верхний левый набор и / или нижний правый набор, если он находится на стене, и все наборы для деревьев в соседних квадратах.Если включены как верхний левый, так и нижний правый наборы, вы не можете добавить дерево в этот квадрат, поэтому переходите к следующему.
  4. Если квадрат проходит, добавьте дерево.Создайте новый набор для дерева и объедините его со всеми наборами, которые он соединяет с тем, что вы нашли в (3).
  5. Остановитесь, когда у вас будет достаточно деревьев.
...