Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/9: Рейтинг темы: голосов - 9, средняя оценка - 4.67
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
1

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

02.10.2013, 11:19. Просмотров 1714. Ответов 13
Метки нет (Все метки)

Добрый день! Появилась такая задача - есть квадратное поле с фиксированной размерностью NxN. Как создать лабиринт я примерно понимаю, но перед нами встала другая задача - нужно сгенерировать лабиринт по заданному ключу. Т.е. каждый раз, подставляя этот ключ, я бы получал абсолютно одинаковые лабиринты. Что-то похожее есть в Minecraft, только там поле генерируется бесконечно. Одно из условий - всегда должен быть вход\выход (это значит, что нет по 1 ячейки на краю карты) и между ними всегда должен быть путь.
Подскажите, пожалуйста, как можно попробовать решить эту задачу. У меня пока есть пара мыслей, но я пока не проверял их.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.10.2013, 11:19
Ответы с готовыми решениями:

Создание лабиринтов
Мне нужно написать программу, которая создает алгоритм размером N*N которые я...

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

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

Генерация лабиринтов в двухмерном массиве
Нужно реализовать рандомный генератор лабиринтов в своей игре. Есть двухмерный...

Генерация лабиринтов с автоматическим созданием стен
Не знаю понятно ли выразился в заголовке, но суть вопроса в следующем. Есть ли...

13
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
02.10.2013, 12:25 2
Если ключ - это число, то можно использовать его в качестве зерна генератора случайных чисел.
Если нужно нечто более сложное, то надо думать конкретно исходя из того что требуется и какие ограничения на ключ.
0
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
02.10.2013, 12:27  [ТС] 3
Qwertiy, можно и число, только вот как генерировать случайные значения с заданным зерном?
0
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
02.10.2013, 12:37 4
От языка зависит. Например, в Си/Си++ srand(x), в C# new Random(x).
1
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
02.10.2013, 12:50  [ТС] 5
А есть ли какой-нибудь алгоритмический способ генерации? Мы пишем на JS, там нет аналога srand(), к сожалению.
0
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
02.10.2013, 13:16 6
Ну вроде гуглятся всякие генераторы...
0
Mysterious Light
Эксперт по математике/физике
3998 / 1962 / 399
Регистрация: 19.07.2009
Сообщений: 2,986
Записей в блоге: 21
02.10.2013, 13:55 7
Есть один безотказный вариант, но он может Вам не подойти.

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

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

Выше описывался метод, когда лабиринт есть поле, где каждая клетка либо свободна, либо занята препятствием. Бывают лабиринты, где препятствия располагаются между двумя соседними клеточками. В этом случае понадобится 2*(N+1)^2 бит, потому что нужно кодировать сетку горизонтальных черточек и вертикальных отдельно. Ужать можно тем же способом, вычеркнув все нелабиринты.
1
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
02.10.2013, 14:11 8
Mysterious Light, а после ужимания всё множество лабиринтов включить в страницу, чтобы она загружалась несколько часов?

Добавлено через 36 секунд
И вообще, генерировать лабиринты это никак не поможет.
0
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
02.10.2013, 14:12  [ТС] 9
Mysterious Light, спасибо за исчерпывающий ответ. Я может неправильно понял, но получается, что алгоритм выглядит так:
1) Генерируем лабиринт NxN
2) Создаём массив store[n]
3) В каждой строке (i)
3.1) На каждой ячейке (j)
3.1.1) Записываем бит в store[i]
3.1.2) Сдвигаем маску
так?
0
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
02.10.2013, 14:17 10
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

0
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
02.10.2013, 14:20  [ТС] 11
Qwertiy, меньше 53
0
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
02.10.2013, 15:58 12
На всякий случай напоминаю, что в js нет int64...
0
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
02.10.2013, 16:02  [ТС] 13
Я по этому посту определил.
0
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
02.10.2013, 16:09 14
Только битовые операции всё равно работают только с int32. Всё остальное - исключительно дробное.
0
02.10.2013, 16:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.10.2013, 16:09

Как реализуется генерация лабиринтов в игре "Сокобан"
Как реализуется генерация лабиринтов кто-нибудь мб подскажет? Вот пример...

Генерация HMAC (SHA256) по ключу
Помогите организовать генерацию используя две строки (строка которую шифруем и...

Генерация массива по Алгоритму Плейфера по ключу
public void button6_Click(object sender, EventArgs e) // Генерация...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru