Генерация шума: "Room Noise"

Question

Генерация шума: "Room Noise"

В последние недели я разрабатывал генератор мира (для мода Minecraft). Тем не менее, я искал не просто шум Перлина, а что-то, основанное на шуме клетки. Я хочу создать своего рода подземную лабораторию, состоящую из нескольких комнат разных размеров.

Чтобы объяснить проблему, я использую 2D-примеры.

Генератор шума занимает положение ячейки сетки (int x, int y) и возвращает объект с этой структурой:

boolean top;
boolean right;
boolean down;
boolean left;

int roomType;

4 логических значения представляют стены, которые включены или отключены:

roomType представляет тип комнаты соответственно.

Окончательный результат должен быть примерно таким:
Здесь фоновый рисунок шахматной доски представляет базовую сетку, а черные линии представляют стены. Это просто простой пример, который можно сгенерировать, но в реальном случае сетка бесконечна как в x, так и в y направлениях.

Проблема, которую я получаю сейчас, состоит в том, что генератор шума принимает только координаты x и y, которые являются координатами ячейки сетки, которую он должен генерировать. Есть семя, из которого я могу генерировать больше случайных семян для хеш-функций:

long seed = 0x75fd239de48;

Random r = new Random(seed);
int seed1 = r.nextInt();
int seed2 = r.nextInt();
// etc.

Я мог бы использовать хэш-функцию: Hash.hash2D(int seed, int x, int y), который возвращает случайный double для координаты, согласно семени.

Это даст возможность генерировать информацию для окружающих клеток.

Чтобы легко генерировать большие комнаты, вы можете установить максимальный размер комнаты и проверить область для комнат, которые пытаются быть больше, чем 1x1. Если они есть и будут охватывать текущую комнату, эта комната будет продолжением другой комнаты. Однако проверка того, будет ли комната расширяться, требует проверки того, не расширяется ли она (в противном случае нежелательные расширения комнаты появляются в базах комнат, которые расширяют другую), что приводит к бесконечному циклу.

В моем случае есть таблица типов комнат, их размеров и веса. Пример:

name:   size [weight]
room-1: 1x1  [128]
room-2: 1x1  [128]
room-3: 2x1  [16]
room-4: 1x2  [16]
room-5: 2x2  [8]
room-6: 3x1  [4]
room-7: 1x3  [4]

Есть много других, с размерами до 5x5, но я использую этот список примеров для моего вопроса. Максимальный размер в этом примере - 3x3 (только max-width по max-height).

Здесь у меня есть пример класса некоторых основных настроек в Java:

public class RoomNoise {
    private final long seed;
    private final Random rand;
    public RoomNoise( long seed ) {
        this.seed = seed;
        this.rand = new Random( seed );
    }

    public enum RoomTypes {
        ROOM1( 1, 1, 128 ),
        ROOM2( 1, 1, 128 ),
        ROOM3( 2, 1, 16 ),
        ROOM4( 1, 2, 16 ),
        ROOM5( 2, 2, 8 ),
        ROOM6( 1, 3, 4 ),
        ROOM7( 3, 1, 4 );

        public final int width;
        public final int height;
        public final int weight;
        private RoomTypes( int w, int h, int weight ) {
            width = w;
            height = h;
            this.weight = weight;
        }
    }

    public static class Output {
        public final RoomTypes roomType;
        public final boolean upWall;
        public final boolean rightWall;
        public final boolean downWall;
        public final boolean leftWall;
        public Output( RoomTypes type, boolean u, boolean r, boolean d, boolean l ) {
            roomType = type;
            upWall = u;
            rightWall = r;
            downWall = d;
            leftWall = l;
        }
    }

    public Output generate( int x, int y ) {
        // What should be here
    }
}

Я ищу содержание generate метод, для которого я пробовал много вещей, но каждый раз я превращался в бесконечный цикл, или он не работал.

Есть ли способ генерировать этот шум в O(N) с N меньше бесконечности? И если есть способ, то какой это путь и как я могу его реализовать? Я искал в Интернете и перепробовал много вещей (уже 3 недели) и до сих пор не нашел решения.

Я использую Java 1.8, но я предпочитаю любой язык в стиле C.

Опять же, у меня есть эта хеш-функция:

Hash.hash2D( int seed, int x, int y );

Редактировать:

Ожидаемый результат:

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

Замечания:

Я не могу загружать и удалять чанки (ячейки сетки) вручную, базовый API (Minecraft) делает это для меня. Это только дает мне координату (которая зависит от взаимодействия игрока), и я должен вернуть (часть a) комнату, которая соответствует куску по этой координате. Я также знаю, что как только порция генерируется, она не генерируется снова.

7

java noise-generator

Источник

user5555016 07 май '18 в 19:12

2 ответа

Другие вопросы по тегам java noise-generator

user7859515 07 май '18 в 19:31 2018-05-07 19:31 · Answer 1 · 2018-05-07 19:31

Я не уверен, что прекрасно понимаю проблему, которую вы пытаетесь решить, поэтому, пожалуйста, не стесняйтесь комментировать, если это не соответствует цели:

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

Создайте "достаточно большую" сетку. Это может быть время / пространство, но если есть верхняя граница того, сколько вам может понадобиться, и выполнимо сделать все сразу, это самый простой вариант. Например, если пользователь не может сделать это на расстоянии более 1000 квадратов от центра, генерируйте 2000x2000.

ИЛИ ЖЕ:

Используйте ленивую оценку. Это означает, что ничего не генерировать, пока вам это не нужно. Если пользователь приближается к области, которая еще не была сгенерирована, сгенерируйте ее тогда. С другой стороны, вы также можете выбросить старые детали, к которым пользователь вряд ли вернется, если вам необходимо освободить ресурсы. Например: разрезайте свою область на квадраты (например, 20x20 или 1000x1000) и генерируйте дополнительные смежные квадраты, когда игрок приближается к ним, или карта перемещается в этом направлении и т. Д., По мере необходимости.

user5555016 09 май '18 в 08:45 2018-05-09 08:45 · Answer 2 · 2018-05-09 08:45

Хорошо, я думаю, что решил это сам.

Это решетка, не бесконечная здесь, но это может быть.

В этой сетке есть несколько ячеек, которые нужно расширить. Это напрямую определяется хеш-функцией:

Однако некоторые расширения перекрывают другие. Это то, чего мы на самом деле не знаем.

Возьмите для каждой ячейки приоритет. Вы можете сделать это несколькими способами:

Просто используйте хеш-функцию, чтобы дать им случайный приоритет
Присвойте каждому возможному типу / размеру номера приоритет (например, большие номера имеют более высокий приоритет).

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

Тогда у нас есть входная координата, которая является синей ячейкой:

Хорошо, зная это, вы должны сделать несколько шагов. Мы знаем, что максимальный размер 3х3.

Если входная ячейка не хочет расширяться

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

В этом случае оно существует.
Зная это, мы должны проверить, может ли одна из найденных ячеек распространиться на эту ячейку. Чтобы проверить это, проверьте, хочет ли это, чтобы эта ячейка была расширением, затем выполните шаги ниже и возьмите ячейку проверки в качестве входной координаты. В этом примере расширяющаяся ячейка может расширяться. Мы также знаем, что расширяющаяся ячейка будет расширять входную ячейку, поэтому входная ячейка является расширением.
Теперь мы можем легко проверить, какие стены существуют, а какие нет. В этом случае каждая стена исчезла, потому что это центр этой расширяющейся комнаты:

Некоторые другие примеры:

Входные координаты. Никто из них не хочет продления

Проверьте регионы:

Как видите, одна ячейка нашла комнату расширения, но эта комната расширения не расширяет эту входную ячейку. Это делает все эти комнаты 1х1 комнатой:

Если входная ячейка хочет расширить

И как проверить, может ли клетка расширяться?

Сделайте жесткую проверку. Тщательная проверка проверяет область размера расширения (в данном случае 3x3) прямо под входной ячейкой для других ячеек, пытающихся расширить. Если он есть, проверьте, можно ли его расширить. Если это возможно, входная ячейка не может расширяться и выполнять шаги для нерасширяющихся ячеек в вашей входной ячейке. Чтобы сэкономить память и время, вы можете пропустить проверку, могут ли найденные ячейки расширяться (возможно, это приведет к бесконечному циклу), и просто взять ячейку 1x1 напрямую (без расширения ячеек шаги не нужны).
Это область расширения / область жесткого контроля в этом случае. Здесь нет расширяющейся клетки, чтобы она могла расширяться.
Теперь сделайте мягкую проверку. Мягкая проверка проверяет расширение ячеек в области максимального размера слева и справа над ячейкой:

Также здесь вы можете проверить, расширяются ли они, но это занимает много памяти и времени.
Для каждой найденной ячейки, проверьте в их области расширения прямо под ними, распространятся ли они на любую из ячеек расширения, которые расширит входная ячейка. Эта проверка перекрывает две зоны расширения. Если они этого не делают, ваша ячейка может расширяться, и вы можете пропустить шаг 3 и перейти к шагу 4. Если они это сделают, перейдите к шагу 3. В этом случае обнаружено перекрытие:

Здесь желтая ячейка с красным контуром является найденным перекрытием.
Вы нашли совпадение. Здесь приоритет будет играть роль. Возьмите приоритет ячейки расширения, какая область перекрывает область входной ячейки. Также возьмите приоритет самой входной ячейки. Сравните их. Если приоритет входной ячейки больше, чем другой приоритет, входная ячейка может расширяться, и вы можете перейти к шагу 4. Если входная ячейка имеет более низкий приоритет, она не может быть расширена, и вы можете сделать ее комнатой 1x1 (или Вы могли бы выполнить нерасширяющиеся шаги ячеек, что необходимо, если вы проверили найденные ячейки в строгой проверке). Если приоритеты равны, возьмите ячейку с наивысшей координатой X или Y или что-то еще.
В моем примере входная ячейка имеет самый высокий приоритет, потому что она больше.
Последний шаг. Ячейка гарантированно расширяется. Вы можете рассчитать, какие стены существуют. Обратите внимание, что левая и верхняя стенки всегда существуют, поскольку ячейки расширения всегда находятся в верхнем левом углу.
Наша ячейка может расширяться, и мы получаем такой результат:

Другой пример

Ячейка ввода:

Сделайте жесткую проверку:

О, он нашел один, поэтому он не мог расширяться и превращался в комнату 1х1:

Вот и все, на самом деле. Я надеюсь, что я достаточно ясно Вместо того, чтобы использовать квадраты, вы также можете использовать прямоугольники или более сложные формы, такие как L-образные комнаты.

И это конечный результат моего примера: