Генерация лабиринтов по ключу

@iRomul · Регистрация: 17.10.2012

Студворк — интернет-сервис помощи студентам

Добрый день! Появилась такая задача - есть квадратное поле с фиксированной размерностью NxN. Как создать лабиринт я примерно понимаю, но перед нами встала другая задача - нужно сгенерировать лабиринт по заданному ключу. Т.е. каждый раз, подставляя этот ключ, я бы получал абсолютно одинаковые лабиринты. Что-то похожее есть в Minecraft, только там поле генерируется бесконечно. Одно из условий - всегда должен быть вход\выход (это значит, что нет по 1 ячейки на краю карты) и между ними всегда должен быть путь.
Подскажите, пожалуйста, как можно попробовать решить эту задачу. У меня пока есть пара мыслей, но я пока не проверял их.

@Qwertiy · 02.10.2013, 12:25

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

@iRomul · 02.10.2013, 12:27 **[ТС]**

Qwertiy, можно и число, только вот как генерировать случайные значения с заданным зерном?

@Qwertiy · 02.10.2013, 12:37

От языка зависит. Например, в Си/Си++ srand(x), в C# new Random(x).

@iRomul · 02.10.2013, 12:50 **[ТС]**

А есть ли какой-нибудь алгоритмический способ генерации? Мы пишем на JS, там нет аналога srand(), к сожалению.

@Qwertiy · 02.10.2013, 13:16

Ну вроде гуглятся всякие генераторы...

@Mysterious Light · 02.10.2013, 13:55

Есть один безотказный вариант, но он может Вам не подойти.

Все поля NxN можно закодировать N^2 битами, очевидно. По-другому, длинным числом. Например, поле 8x8 можно закодировать массивом bite[8].
Однако, не все такие коды будут соответствовать лабиринтам. Поэтому нужно выбрать только те длинные числа, которые являются лабиринтами. Их можно упорядочить лексикографически и использовать полученную таблицу два перевода из последовательных (1,2,3,4,...) чисел в числа-коды.

С одной стороны, можно использовать число-код как ключ. Но для его хранения понадобится N*N бит. Из этих N*N вариантов вычеркнуть нелабиринты и тогда для кранения номера в этой таблице потребуется количество бит, равное логарифму от числа лабиринтов на таком поле. Кстати, меньше Вы не сможете использовать ключ, потому что тогда некоторые лабиринты не будут соотв. никакому ключу.

Выше описывался метод, когда лабиринт есть поле, где каждая клетка либо свободна, либо занята препятствием. Бывают лабиринты, где препятствия располагаются между двумя соседними клеточками. В этом случае понадобится 2*(N+1)^2 бит, потому что нужно кодировать сетку горизонтальных черточек и вертикальных отдельно. Ужать можно тем же способом, вычеркнув все нелабиринты.

@Qwertiy · 02.10.2013, 14:11

Mysterious Light, а после ужимания всё множество лабиринтов включить в страницу, чтобы она загружалась несколько часов?

Добавлено через 36 секунд
И вообще, генерировать лабиринты это никак не поможет.

@iRomul · 02.10.2013, 14:12 **[ТС]**

Mysterious Light, спасибо за исчерпывающий ответ. Я может неправильно понял, но получается, что алгоритм выглядит так:
1) Генерируем лабиринт NxN
2) Создаём массив store[n]
3) В каждой строке (i)
3.1) На каждой ячейке (j)
3.1.1) Записываем бит в store[i]
3.1.2) Сдвигаем маску
так?

@Qwertiy · 02.10.2013, 14:17

iRomul, значение n какое?
Мне кажется, сохранять все лабиринты в любом случае не очень хорошая идея.

Не по теме:

JavaScript
1
2
3
4
5
6
7
var x=Math.random(), n;
 
for(n=0; x!==Math.random(); ++n)
  if(!(n&65535))
    console.log(n);
 
console.log("done", n);

done 1254442900

@iRomul · 02.10.2013, 14:20 **[ТС]**

Qwertiy, меньше 53

@Qwertiy · 02.10.2013, 15:58

На всякий случай напоминаю, что в js нет int64...

@iRomul · 02.10.2013, 16:02 **[ТС]**

Я по этому посту определил.

@Qwertiy · 02.10.2013, 16:09

Только битовые операции всё равно работают только с int32. Всё остальное - исключительно дробное.

Новые блоги и статьи Все статьи Все блоги /
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а привычная функция main(). . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/

@iRomul 163 / 104 / 14 Регистрация: 17.10.2012 Сообщений: 488

	Генерация лабиринтов по ключу 02.10.2013, 11:19. Показов 3203. Ответов 13 Метки нет (Все метки) Добрый день! Появилась такая задача - есть квадратное поле с фиксированной размерностью NxN. Как создать лабиринт я примерно понимаю, но перед нами встала другая задача - нужно сгенерировать лабиринт по заданному ключу. Т.е. каждый раз, подставляя этот ключ, я бы получал абсолютно одинаковые лабиринты. Что-то похожее есть в Minecraft, только там поле генерируется бесконечно. Одно из условий - всегда должен быть вход\выход (это значит, что нет по 1 ячейки на краю карты) и между ними всегда должен быть путь. Подскажите, пожалуйста, как можно попробовать решить эту задачу. У меня пока есть пара мыслей, но я пока не проверял их. 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	02.10.2013, 12:25
	Если ключ - это число, то можно использовать его в качестве зерна генератора случайных чисел. Если нужно нечто более сложное, то надо думать конкретно исходя из того что требуется и какие ограничения на ключ. 0

@iRomul 163 / 104 / 14 Регистрация: 17.10.2012 Сообщений: 488
	02.10.2013, 12:27 [ТС]
	Qwertiy, можно и число, только вот как генерировать случайные значения с заданным зерном? 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	02.10.2013, 12:37
	От языка зависит. Например, в Си/Си++ srand(x), в C# new Random(x). 1

@iRomul 163 / 104 / 14 Регистрация: 17.10.2012 Сообщений: 488
	02.10.2013, 12:50 [ТС]
	А есть ли какой-нибудь алгоритмический способ генерации? Мы пишем на JS, там нет аналога srand(), к сожалению. 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	02.10.2013, 13:16
	Ну вроде гуглятся всякие генераторы... 0

@Mysterious Light $Эксперт по математике/физике$ 4313 / 2105 / 431 Регистрация: 19.07.2009 Сообщений: 3,204 Записей в блоге: 24
	02.10.2013, 13:55
	Есть один безотказный вариант, но он может Вам не подойти. Все поля NxN можно закодировать N^2 битами, очевидно. По-другому, длинным числом. Например, поле 8x8 можно закодировать массивом bite[8]. Однако, не все такие коды будут соответствовать лабиринтам. Поэтому нужно выбрать только те длинные числа, которые являются лабиринтами. Их можно упорядочить лексикографически и использовать полученную таблицу два перевода из последовательных (1,2,3,4,...) чисел в числа-коды. С одной стороны, можно использовать число-код как ключ. Но для его хранения понадобится NN бит. Из этих NN вариантов вычеркнуть нелабиринты и тогда для кранения номера в этой таблице потребуется количество бит, равное логарифму от числа лабиринтов на таком поле. Кстати, меньше Вы не сможете использовать ключ, потому что тогда некоторые лабиринты не будут соотв. никакому ключу. Выше описывался метод, когда лабиринт есть поле, где каждая клетка либо свободна, либо занята препятствием. Бывают лабиринты, где препятствия располагаются между двумя соседними клеточками. В этом случае понадобится 2*(N+1)^2 бит, потому что нужно кодировать сетку горизонтальных черточек и вертикальных отдельно. Ужать можно тем же способом, вычеркнув все нелабиринты. 1

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	02.10.2013, 14:11
	Mysterious Light, а после ужимания всё множество лабиринтов включить в страницу, чтобы она загружалась несколько часов? Добавлено через 36 секунд И вообще, генерировать лабиринты это никак не поможет. 0

@iRomul 163 / 104 / 14 Регистрация: 17.10.2012 Сообщений: 488
	02.10.2013, 14:12 [ТС]
	Mysterious Light, спасибо за исчерпывающий ответ. Я может неправильно понял, но получается, что алгоритм выглядит так: 1) Генерируем лабиринт NxN 2) Создаём массив store[n] 3) В каждой строке (i) 3.1) На каждой ячейке (j) 3.1.1) Записываем бит в store[i] 3.1.2) Сдвигаем маску так? 0

@iRomul 163 / 104 / 14 Регистрация: 17.10.2012 Сообщений: 488
	02.10.2013, 14:20 [ТС]
	Qwertiy, меньше 53 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	02.10.2013, 15:58
	На всякий случай напоминаю, что в js нет int64... 0

@iRomul 163 / 104 / 14 Регистрация: 17.10.2012 Сообщений: 488
	02.10.2013, 16:02 [ТС]
	Я по этому посту определил. 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	02.10.2013, 16:09
	Только битовые операции всё равно работают только с int32. Всё остальное - исключительно дробное. 0