Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 58
извините, я читаю это в 5 утра, и, возможно, напишу чушь, но правильно ли я понял, что мы можем нагенерить небольшой кусок ландшафта, и затем, по мере необходимости, динамически достраивать его при сдвигании окна? тогда, это ведь шикарно, мы можем заселить юзеров на карту и позволить им исследовать огромный мир, динамически создаваемый находу, пока у нас хватает памяти.
Собственно — Minecraft именно это и предлагает… Огромный мир, который генерируется по ходу движения игроков…
Только там ещё и нагружено пещерами разнообразными…
Только там ещё и нагружено пещерами разнообразными…
думаю, девелоперам мморпг стоит уже присмотреться к этому подходу, понятно, что генерить квесты и ключевых мобов таким методом как-то странно, но можно сделать те же самые пещеры под землей со всякими вкусностями или еще что-то
Нечто подобное, насколько знаю, применялось в серии TES. В TES3:Morrowind многочисленные дома и подземелья были сгенерированы автоматически.
И далеко не всем это пришлось по вкусу. Почему? Да потому что игрок рубится с монстрами, зачищает немаленькое подземелье, а что в конце? Сундук с зельями. На пятом подземелье становится откровенно скучно. Игрокам нужна награда. Слишком частые и весомые награды могут сделать дальнейшую игру слишком легкой.
Критика была учтена и в следующей части серии автоматически генерировались только леса и прочие мелкие детали ландшафта. Впрочем, это тоже не всем понравилось и возник замечательный проект Unique Landscapes, который заменяет скучный однообразные ландшафты, сделанные генератором на созданные вручную и добавляет всяческие водопады, пустыни, особенные леса.
Так что автогенерация есть, но пока что она далека от совершенства. И чтобы довести ее до этого самого совершенства нужен титанический труд разработчиков.
PS. Карта в приведенных выше играх была сгенерирована еще на этапе разработки, а не во время начала новой игры. Просто привел пример того, что большие пространства, сделанные генераторами, это здорово, но этого явно недостаточно.
И далеко не всем это пришлось по вкусу. Почему? Да потому что игрок рубится с монстрами, зачищает немаленькое подземелье, а что в конце? Сундук с зельями. На пятом подземелье становится откровенно скучно. Игрокам нужна награда. Слишком частые и весомые награды могут сделать дальнейшую игру слишком легкой.
Критика была учтена и в следующей части серии автоматически генерировались только леса и прочие мелкие детали ландшафта. Впрочем, это тоже не всем понравилось и возник замечательный проект Unique Landscapes, который заменяет скучный однообразные ландшафты, сделанные генератором на созданные вручную и добавляет всяческие водопады, пустыни, особенные леса.
Так что автогенерация есть, но пока что она далека от совершенства. И чтобы довести ее до этого самого совершенства нужен титанический труд разработчиков.
PS. Карта в приведенных выше играх была сгенерирована еще на этапе разработки, а не во время начала новой игры. Просто привел пример того, что большие пространства, сделанные генераторами, это здорово, но этого явно недостаточно.
Не путайте Morrowind и Daggerfall, пожалуйста. В моровинде как раз все локации были зашиты в ресурсы, а местами даже сделаны вручную.
Игр с генерируемыми подземельями довольно много — с ходу могу вспомнить «Сферу», Диабло и ещё два десятка с псевдографикой…
Собственно ситуация "… а в конце — сундук с зельями" — недоработка разработчиков: как минимум в результате должен быть достаточно ценный предмет, на ценность которого влияют параметры «Размеры подземелья», «Число и уровень мобов» и т.п.
Т.е. — если весь дандж «три поворота и один тупик», а монстров в охране — маленькая мышка — награда тоже не велика, но для нуба, на которого рассчитан квест — вполне существенна.
А если группа игроков с трудом прорывается сквозь крутых боссов и кучу монстров — то и награда будет вполне приличная для их уровня. Но с другой стороны — спустя несколько уровней они смогут зачистить тот-же уровень и в одиночку, но и награда им уже не будет казаться такой «вкусной».
Собственно ситуация "… а в конце — сундук с зельями" — недоработка разработчиков: как минимум в результате должен быть достаточно ценный предмет, на ценность которого влияют параметры «Размеры подземелья», «Число и уровень мобов» и т.п.
Т.е. — если весь дандж «три поворота и один тупик», а монстров в охране — маленькая мышка — награда тоже не велика, но для нуба, на которого рассчитан квест — вполне существенна.
А если группа игроков с трудом прорывается сквозь крутых боссов и кучу монстров — то и награда будет вполне приличная для их уровня. Но с другой стороны — спустя несколько уровней они смогут зачистить тот-же уровень и в одиночку, но и награда им уже не будет казаться такой «вкусной».
Первая (да и вторая) Диабла тоже генерировала свои подземелья случайным образом. Пусть не идеально, но все же со случайными подземельями игра вышла интересней, чем со статикой. Так что критиковать стоит не столько концепцию случайно генерированных карт сколько конкретную реализацию алгоритма в морровинде, ПМСМ.
Это действительно вопрос, понравится пользователям автогенерация ландшафта или нет.
М какой она должна, быть чтобы игрокам понравилось и было интересно?
М какой она должна, быть чтобы игрокам понравилось и было интересно?
В Celestia такую штуку надо встроить, чтобы планеты более реальными казались.
Совершенно верно.
У меня была идея реализовать клон Minecraft, но я решил, что не осилю, и ограничился этим топиком :)
У меня была идея реализовать клон Minecraft, но я решил, что не осилю, и ограничился этим топиком :)
Молодца! Хорошая подборка!
Это великолепно, мои геймдевовские корешки шевелятся и лезут на поверхность :)
Браво. Отличная статья, спасибо, прочитал без отрыва.
Редко сейчас встретишь в «Алгоритмах» настолько качественный материал.
Редко сейчас встретишь в «Алгоритмах» настолько качественный материал.
Фракталы отлично справляются подобными задачами, особенно хорошо тем, что можно спокойно масштабировать, так же очень не плохо и различные другие объекты генерируются, будь то растительность, камни и т.д. Взять к примеру стариннейшую игру Elite, весь мир описан 6ю байтами, изменив которые в исполняемом файле получали совершенно иной мир. А статья хороша.
хм, а генетический алгоритм сюда можно применить? делать много раз heights[i][j] += random(), где random() возвращает какую-нибудь маленькую величину (как положительную, так и отрицательную)
Спасибо за отличную статью?
Почему бы не отказаться от размера и прегенерации карты? Давайте генерировать только то, что нам нужно. Берем тайл, небольшого размера, скажем, в два раза больший, чем (дальность зрения игрок*2). Если игрок видит на 16 клеток, то пусть это будет 16*2*2 = 64 пикселя, генерируем блок 64*64 и ставим пользователя в середину. Когда пользователь подойдёт к краю — догенерируем следующий блок на базе предыдущего. К примеру, на картинке ниже у нового блока есть три точки, случайно выбираем четвертую и погнали простым алгоритмом.
Итак, подход таков: пусть наш ландшафт изначально задуман гигантских размеров (например, 16777216x16777216 пикселей, хотя это далеко не предел).
Почему бы не отказаться от размера и прегенерации карты? Давайте генерировать только то, что нам нужно. Берем тайл, небольшого размера, скажем, в два раза больший, чем (дальность зрения игрок*2). Если игрок видит на 16 клеток, то пусть это будет 16*2*2 = 64 пикселя, генерируем блок 64*64 и ставим пользователя в середину. Когда пользователь подойдёт к краю — догенерируем следующий блок на базе предыдущего. К примеру, на картинке ниже у нового блока есть три точки, случайно выбираем четвертую и погнали простым алгоритмом.
простите, не тот знак. правильно так:
Спасибо за отличную статью!!!
Спасибо за отличную статью!!!
Дело в том, что у нас получится тогда не часть цельного ландшафта, а новый маленький подландшафтик (к тому же при его создании нам понядобятся высоты в еще не построенных блоках ниже и правее нового — и откуда их брать, не совсем ясно).
почему бы не сгенерить (только) ключевые точки при прегенерации, а потом догенерировать детали?
А что такое «ключевые точки»? Там каждая вторая точка будет получаться «ключевой», от неё будут другие точки зависеть.
каждая 64-ая точка, например?
Да в общем-то ничего не мешает как угодно поступать — хоть всю карту прегенерировать, хоть каждую N-ую точку, хоть вообще ничего.
Просто следует понимать, что имея, например, точки (64, 64), (127, 64), (64, 127) и (127, 127) — корректно заполнить только по ним все внутренние точки в квадрате (64, 64) — (127, 127) не выйдет: на этапах «diamond» нам часто будут нужны точки «снаружи», из соседних квадратов.
Просто следует понимать, что имея, например, точки (64, 64), (127, 64), (64, 127) и (127, 127) — корректно заполнить только по ним все внутренние точки в квадрате (64, 64) — (127, 127) не выйдет: на этапах «diamond» нам часто будут нужны точки «снаружи», из соседних квадратов.
а можно как-то так? то есть генерить клетки+ дополнительные данные. просто время генерации карты сейчас не очень радует. плюс делается дофига ненужной работы. плюс карта ограниченная.
Мне кажется, вы не до конца разобрались в том приеме, который я предложил.
Его особенность как раз в том, чтобы делать минимум ненужной работы. От ограниченности карты, кстати, никуда не деться, но в моем алгоритме можно дешево задавать очень большим её общий размер.
А что до времени отрисовки — я думаю, здесь меня подвел попиксельный доступ к canvas. Если не выводить значение каждой точки на экран, будет гораздо быстрее.
Его особенность как раз в том, чтобы делать минимум ненужной работы. От ограниченности карты, кстати, никуда не деться, но в моем алгоритме можно дешево задавать очень большим её общий размер.
А что до времени отрисовки — я думаю, здесь меня подвел попиксельный доступ к canvas. Если не выводить значение каждой точки на экран, будет гораздо быстрее.
а представьте, если бы огромная карта генерировалась заранее. включил, ушёл на полчаса.
сейчас, при относительно небольшом размере в 2к*2к у меня фокс висит, а что если необходим размер больше?
сейчас, при относительно небольшом размере в 2к*2к у меня фокс висит, а что если необходим размер больше?
Ну, в статье я как раз и описываю подход, в котором нет надобности генерировать сразу всю карту.
Высота в каждой точке может определяться в любой момент, и даже в худшем случае число операций, которые на это уйдут, будет порядка двоичного логарифма от размера карты.
Высота в каждой точке может определяться в любой момент, и даже в худшем случае число операций, которые на это уйдут, будет порядка двоичного логарифма от размера карты.
dwarf fortress :3
У него общий случай. Нотч тоже, хоть и уверяет, что карта бесконечная, на практике называет цифру, на которой она кончается таки. ;)
В Майнкрафте приняты блоки-«чанки» размером 16 на 16 на 128, при этом видимость — этак на 64 клетки, примерно…
В Майнкрафте приняты блоки-«чанки» размером 16 на 16 на 128, при этом видимость — этак на 64 клетки, примерно…
Спасибо, очень интересная и качественная статья.
Скажите, а не пробовали ли, хотя бы грубо, моделировать взаимодействие тектонических плит с последующей эрозией и почвообразованием, чтобы получать ландшафт? Ведь, все-таки представленные методы генерирования являются чисто математическими, без учета реального строения, то есть попыткой подобрать математическую модель, визуально похожую на то, что мы можем наблюдать.
Скажите, а не пробовали ли, хотя бы грубо, моделировать взаимодействие тектонических плит с последующей эрозией и почвообразованием, чтобы получать ландшафт? Ведь, все-таки представленные методы генерирования являются чисто математическими, без учета реального строения, то есть попыткой подобрать математическую модель, визуально похожую на то, что мы можем наблюдать.
Нет, я, в общем-то, даже эрозию толком не изучал.
А такую вещь, как взаимодействие тектонических плит, думается, будет весьма проблематично промоделировать — этому, по крайней мере, нужно посвящать целое отдельное исследование. В любом случае понадобятся серьезные упрощения модели (мы же не станем рассматривать взаимодействие каждой пары песчинок), и они вполне могут отдалить результат от реальности значительно более, чем то, что получается искусственным фрактальным путем.
А такую вещь, как взаимодействие тектонических плит, думается, будет весьма проблематично промоделировать — этому, по крайней мере, нужно посвящать целое отдельное исследование. В любом случае понадобятся серьезные упрощения модели (мы же не станем рассматривать взаимодействие каждой пары песчинок), и они вполне могут отдалить результат от реальности значительно более, чем то, что получается искусственным фрактальным путем.
Любому из этих способов генерации нехватает водной эрозии чтобы выглядеть правдоподобно. Горы без ущелий в реальном мире никогда не встречаются.
Превосходный материал, огромное спасибо!
Давно слежу за ходом разработки игры от ребят, которые выкатили Дарвинию и Дефкон ( www.introversion.co.uk/blog/archive.php, советую начинать с архива блога ), там исходная идея была в генерации огромного города, видео-материалы впечатляли даже пару лет назад. Правда за время разработки идея менялась, ну не суть важно :)
Очень интересен подобный алгоритм (генерация урбанистических ландшафтов), но с упором на инфраструктуру и специализацию районов (а не просто от ориентации на сетку дорог и ландшафт).
Задача достаточно амбициозная, мне кажется, этапу генерации должен предшествовать этап вычислений социальных и экономических взаимодействий в неком городе или агломерации с учетом эпохи действия, доступности строительных технологий и общего уровня технологии (например, наличие канализации, системы водопроводов, транспортных систем и т.д.) Плюс, еще со времен древних симсити в голове сидят критерии вроде «Земля вокруг мусоросжигательных заводов не самая престижная».
Кто-нибудь сталкивался с чем-то подобным?
Давно слежу за ходом разработки игры от ребят, которые выкатили Дарвинию и Дефкон ( www.introversion.co.uk/blog/archive.php, советую начинать с архива блога ), там исходная идея была в генерации огромного города, видео-материалы впечатляли даже пару лет назад. Правда за время разработки идея менялась, ну не суть важно :)
Очень интересен подобный алгоритм (генерация урбанистических ландшафтов), но с упором на инфраструктуру и специализацию районов (а не просто от ориентации на сетку дорог и ландшафт).
Задача достаточно амбициозная, мне кажется, этапу генерации должен предшествовать этап вычислений социальных и экономических взаимодействий в неком городе или агломерации с учетом эпохи действия, доступности строительных технологий и общего уровня технологии (например, наличие канализации, системы водопроводов, транспортных систем и т.д.) Плюс, еще со времен древних симсити в голове сидят критерии вроде «Земля вокруг мусоросжигательных заводов не самая престижная».
Кто-нибудь сталкивался с чем-то подобным?
Ссылка для ленивых на одно из первых видео процесса www.introversion.co.uk/blog/roadgen/roadgen-all.avi
forums.introversion.co.uk/introversion/viewtopic.php?t=586
forums.introversion.co.uk/introversion/viewtopic.php?t=586
Функция randFromPair(x, y) — очень заинтересовала.
Да, идёт генерация псевдослучайного числа на основе «состояния» {x,y}. Всё в лучших добрых традициях ГПСЧ — простые числа, остатки от деления и последующие математические операции.
Но позвольте спросить, — откуда взяты именно такие простые числа?
А именно, 7; 13; 1301081 для X, и 8461; 105467; 105943 для Y?
Чем обусловлен выбор именно этих чисел и именно по три штуки?
Вопрос про 80-1 проездов напильником по результату также остаётся открытым.
Да, идёт генерация псевдослучайного числа на основе «состояния» {x,y}. Всё в лучших добрых традициях ГПСЧ — простые числа, остатки от деления и последующие математические операции.
Но позвольте спросить, — откуда взяты именно такие простые числа?
А именно, 7; 13; 1301081 для X, и 8461; 105467; 105943 для Y?
Чем обусловлен выбор именно этих чисел и именно по три штуки?
Вопрос про 80-1 проездов напильником по результату также остаётся открытым.
Честно говоря, все бралось практически с потолка в попытках избежать видимых глазу закономерностей в генерируемых ландшафтах. Как оказалось, при небольшом числе итераций в данной функции, практически всегда оказывается заметна зависимость от входных координат. Подобное «перемешивание» остатков дало наиболее приемлемый результат.
К сожалению, не удалось нигде найти способов решения задачи быстрого получения достаточно «хорошего» псевдослучайного числа на основе заданного зерна. Все известные мне алгоритмы предполагают задание зерна единожды чтобы получить быстро генерируемую последовательность ПСЧ. Их время задержки перед выдачей первого элемента последовательности оказалось слишком большим для моих нужд, пришлось выкручиваться.
Буду очень рад, если укажете на более эффективный подход к этой задаче.
К сожалению, не удалось нигде найти способов решения задачи быстрого получения достаточно «хорошего» псевдослучайного числа на основе заданного зерна. Все известные мне алгоритмы предполагают задание зерна единожды чтобы получить быстро генерируемую последовательность ПСЧ. Их время задержки перед выдачей первого элемента последовательности оказалось слишком большим для моих нужд, пришлось выкручиваться.
Буду очень рад, если укажете на более эффективный подход к этой задаче.
Поэкспериментировал, и предлагаю такой вариант функции:
Скорость работы (в моём хроме) поднялась почти в два раза.
Каких-либо артефактов или закономерностей я не заметил, результат выглядит столь же неплохо.
К сожалению, метод такой же — простые числа 1972854929, 2971902361, 3572953751 взяты "с потолка", математическое доказательство или исследование «подходящести» данного способа генерации ПСЧ на основе зерна {x,y,seed} — также открытая задача.
Возможно другие простые числа могут вести себя лучше.
s = 0x6C078965 * s;// & 0xFFFFFFFF; и далее
— взято из всеми любимого Вихря Мерсенна.
Закомментированный блок битового перемешивания — отключен поскольку он не производил видимых улучшений результирующей картины. (так и незачем его считать, для наших целей)
Сама строка «s = 0x6C...» оставлена по той же причине — без неё не происходит минимально необходимого перемешивания данных исходной тройки {x,y,seed}
Попробовать сейчас твой фрактальный ландшафт с моим вариантом функции можно здесь.
Я тоже буду рад помощи в доведении данного вопроса {x1,x2,...,xn} => PRN до итогового результата.
Причём даже больший интерес представляет расширенная задача, где исходные данные x1,...,xn — вещественные числа, и накладывается требование непрерывности построенного по ним поля PRN.
function randFromPair(x, y) {
var s = seed * 1972854929;
s ^= (x * 2971902361) ^ (y * 3572953751);
s = 0x6C078965 * s;// & 0xFFFFFFFF;
/*
s ^= s >> 11;
s ^= (s << 7) & 0x9D2C5680;
s ^= (s << 15) & 0xEFC60000;
s ^= s >> 18;
*/
return (s & 0x7FFFFFFF) * 4.656612875245796924105750827168e-10; //(1./2147483647.);;
}
Скорость работы (в моём хроме) поднялась почти в два раза.
Каких-либо артефактов или закономерностей я не заметил, результат выглядит столь же неплохо.
К сожалению, метод такой же — простые числа 1972854929, 2971902361, 3572953751 взяты "с потолка", математическое доказательство или исследование «подходящести» данного способа генерации ПСЧ на основе зерна {x,y,seed} — также открытая задача.
Возможно другие простые числа могут вести себя лучше.
s = 0x6C078965 * s;// & 0xFFFFFFFF; и далее
— взято из всеми любимого Вихря Мерсенна.
Закомментированный блок битового перемешивания — отключен поскольку он не производил видимых улучшений результирующей картины. (так и незачем его считать, для наших целей)
Сама строка «s = 0x6C...» оставлена по той же причине — без неё не происходит минимально необходимого перемешивания данных исходной тройки {x,y,seed}
Попробовать сейчас твой фрактальный ландшафт с моим вариантом функции можно здесь.
Я тоже буду рад помощи в доведении данного вопроса {x1,x2,...,xn} => PRN до итогового результата.
Причём даже больший интерес представляет расширенная задача, где исходные данные x1,...,xn — вещественные числа, и накладывается требование непрерывности построенного по ним поля PRN.
В результате более охватывающего тестирования к сожалению было выявлено, что предложенный мной способ вычисления PRN(x1,...,xn) для существенно больших размеров карты ведёт себя неприемлимо — начинают проявляться артефакты: диагональная симметрия и периодичность «островков» карты.
Это происходит при ширине квадрата карты примерно от 128М и более (смотрел до 4Г, т.е. до карт шириной и высотой по 4*1024^3 клеток).
Между тем, deNull, твой метод выдаёт результат ничем не хуже, чем для карт малых размеров.
В результате приходится продолжить поиск более совершенного алгоритма, который с одной стороны работал бы быстро и выглядел красиво (что характерно для элегантных и эффективных решений), и с другой не давал бы никаких заметных артефактов вплоть до размеров используемой при вычислениях разрядности (в нашем случае 2^32).
Пока что экспериментирование с различными операциями и вариациями на тему дополнительных перемешиваний почти не принесло видимых результатов.
Что же касается предложенного выше алгоритма randFromPair — его вполне успешно можно использовать для не очень больших карт (до 100млн х 100млн), получая при этом заметный выигрыш производительности. Для экстремально больших карт же пока остаётся актуальным только метод автора статьи.
/ Большой респект за хорошую статью! /
Продолжаю поиски грааля.
Это происходит при ширине квадрата карты примерно от 128М и более (смотрел до 4Г, т.е. до карт шириной и высотой по 4*1024^3 клеток).
Между тем, deNull, твой метод выдаёт результат ничем не хуже, чем для карт малых размеров.
В результате приходится продолжить поиск более совершенного алгоритма, который с одной стороны работал бы быстро и выглядел красиво (что характерно для элегантных и эффективных решений), и с другой не давал бы никаких заметных артефактов вплоть до размеров используемой при вычислениях разрядности (в нашем случае 2^32).
Пока что экспериментирование с различными операциями и вариациями на тему дополнительных перемешиваний почти не принесло видимых результатов.
Что же касается предложенного выше алгоритма randFromPair — его вполне успешно можно использовать для не очень больших карт (до 100млн х 100млн), получая при этом заметный выигрыш производительности. Для экстремально больших карт же пока остаётся актуальным только метод автора статьи.
/ Большой респект за хорошую статью! /
Продолжаю поиски грааля.
Реализовал оба варианта на С++, поэкспериментировал.
На мой взгляд, 80 прогонов у тебя избыточны, хватает 32 раз. Соответственно время генерации существенно уменьшается. (грубо говоря в 2 раза)
Также примечательное свойство данного генератора ландшафтов (в целом генератора) — отображаемая карта (512х512) просчитывается практически за константное время, вне зависимости от размеров «полной карты». *
При размерах от 512 и до 1.073.741.824 время генерации отстаётся неизменным в пределах погрешностей.
Имеется ввиду как раз первичный просчёт, когда в «кэше» нет ни одного элемента и необходимо считать все.
_____________
* Данное поведение проявилось в реализации на С++, с использованием stl::map, в качестве ключа взята структура {dword x; dword y;}, вместо предлагаемого в оригинале строкового ключа «x+'_'+y». Однако же в браузерном исполнении JS-варианта прослеживается заметное увеличение времени генерации при росте «размера карты».
На мой взгляд, 80 прогонов у тебя избыточны, хватает 32 раз. Соответственно время генерации существенно уменьшается. (грубо говоря в 2 раза)
Также примечательное свойство данного генератора ландшафтов (в целом генератора) — отображаемая карта (512х512) просчитывается практически за константное время, вне зависимости от размеров «полной карты». *
При размерах от 512 и до 1.073.741.824 время генерации отстаётся неизменным в пределах погрешностей.
Имеется ввиду как раз первичный просчёт, когда в «кэше» нет ни одного элемента и необходимо считать все.
_____________
* Данное поведение проявилось в реализации на С++, с использованием stl::map, в качестве ключа взята структура {dword x; dword y;}, вместо предлагаемого в оригинале строкового ключа «x+'_'+y». Однако же в браузерном исполнении JS-варианта прослеживается заметное увеличение времени генерации при росте «размера карты».
Взял нормальное распределение гаусса функцию вместо randFromPair, сигмачку и мю поднастроил. Ускорил алгоритм на порядки. Правда написал на питоне. Но я думаю можно и ручками функцию запрогать.
О спасибо, а то я от лени просто рандомом высоту наращивал — не просто каждой точке, а какой-то случайной точке на карте с указанным разбросом по X и Y, и таких точек 50 штук на карте. Каждый раз когда на точку выпадает кон — её высота увеличивается на 5, начальная высота -100. Рандом не простой а Гауссовый из библиотеки d3js — он больше ближе к середине выдаёт (с простым квадраты получались). Чёрные — это гоные пики типа. Примерно так выходило (10 сек для карты 150х150, AthX2 1.9G, Linux, Chrome).
Большое спасибо за статью, очень помогла!
@deNULL После некоторых размышлений я пришел к выводу, что быстрого способа преобразовать две координаты в число, которое было бы мало скоррелировано с ними, в принципе невозможно. В итоге я остановился на такой функции, которая дает приемлимые результаты из-за многократного взятия чисел по простым модулям
Делал нечто подобное и столкнулся с той же проблемой. Гдето на зарубежном форуме нашел такое решение (привожу переработанный мной пример так как исходника и ссылки на оригинал не сохранилось)
Объект с функциями генерации псевдослучайных последовательностей по seed
function rerandom(seed) {
// всякая инициализационная хрень
if (this instanceof rerandom === false) {
return new rerandom(seed);
}
var self = this;
this.p1 = 2654435761;
this.p2 = 2246822519;
this.p3 = 3266489917;
this.p4 = 668265263;
this.p5 = 374761393;
this.p=[this.p1,this.p2,this.p3,this.p4,this.p5];
this.cut = 2097151;
this.seed = seed;
}
rerandom.prototype.GetXzHash = function(x, y) {
if(!y) y=0;
for (var i = 0; i < 80; i++) {
var xm7 = x % 7;
var xm13 = x % 13;
var xm1301081 = x % 1301081;
var ym8461 = y % 8461;
var ym105467 = y % 105467;
var ym105943 = y % 105943;
y = x + this.seed;
x += (xm7 + xm13 + xm1301081 + ym8461 + ym105467 + ym105943);
}
return (xm7 + xm13 + xm1301081 + ym8461 + ym105467 + ym105943) & this.cut;
};
rerandom.prototype.GetXxHash = function() {
let buf = arguments
let h32;
let index = 0;
let len = buf.length;
if (len >= 4) {
let limit = len - 4;
let v1 = this.seed + this.p1 + this.p2;
let v2 = this.seed + this.p2;
let v3 = this.seed + 0;
let v4 = this.seed - this.p1;
while (index <= limit) {
v1 = this.CalcSubHash (v1, buf[index]);
index++;
v2 = this.CalcSubHash (v2, buf[index]);
index++;
v3 = this.CalcSubHash (v3, buf[index]);
index++;
v4 = this.CalcSubHash (v4, buf[index]);
index++;
}
h32 = this.RotateLeft (v1, 1) + this.RotateLeft (v2, 7) + this.RotateLeft (v3, 12) + this.RotateLeft (v4, 18);
}
else {
h32 = this.seed + this.p5;
}
h32 += len * 4;
while (index < len) {
h32 += buf[index] * this.p3;
h32 = this.RotateLeft (h32, 17) * this.p4;
index++;
}
h32 ^= h32 >> 15;
h32 *= this.p2;
h32 ^= h32 >> 13;
h32 *= this.p3;
h32 ^= h32 >> 16;
return h32&this.cut;
};
rerandom.prototype.RotateLeft = function(value, count) {
return (value << count) | (value >> (32 - count));
}
rerandom.prototype.CalcSubHash = function(value, read_value) {
value += read_value * this.p2;
value = this.RotateLeft (value, 13);
value *= this.p1;
return value;
}
rerandom.prototype.rnd = rerandom.prototype.GetXxHash;
//rerandom.prototype.rnd = rerandom.prototype.GetXzHash;
в коде представленна ваша функция под именем GetXzHash
и функция GetXxHash которая делает тоже самое
скорость работы
- GetXxHash. при генерации 2^24 (16777216) значений на моем стареньком ноутбуке отрабатывает за 6625 мс
- GetXzHash. подсчитать время работы не удалось (через пол часа нажиманий в браузере кнопки [продолжить] на запрос «скрипт замедляет работу браузера» я сдался )
равномерность распределения
- GetXxHash. представленна на картинке
- GetZxHash. не представленна по той же причине что и скорость выполнения.
Вывод
Операции деления по модулю катастрофически увеличивают время расчетов.
ЗЫ:
работу генератора карт можно посмотреть по адресу
ЗЫЗЫ:
буду рад всем желающим поучаствовать в разработке открытого движка генератора карт. Обращайтесь в ЛС.
варианты генератора карт:
С вашего позволения подправлю ссылки из моего предыдущего коментария.
- game.lastuniverse.ru/v.3d — самый древний вариант, тонок и сложен в настройках, убог интерфейсом. После загрузки страницы необходимо нажать кнопку «отобразить карту». карта кликабельная (ЛКМ приближает карту. кнопка «отобразить карту» сбрасывает приближение. Игровое окно (то что с человечком) отрисовывает текущие координаты на карте, кликабельно. Кнопка «тест FPS через setTimeout» пирокручивает кусок игрового окна)
- game.lastuniverse.ru/v.00 — промежуточный вариант
- game.lastuniverse.ru/v.01 — шаманство :)
- game.lastuniverse.ru/v.02 — шаманство :)
- game.lastuniverse.ru/v.03 — реализация на основе алгоритма из статьи. Карта кликабельна (двойной клик ЛКМ — приближает точку клика), так же добавлены слои освещенности, температуры, оледенения (включаются/выключаются в панели «отображаемые слои», после внесения изменений нажми кнопку «перерисовать карту»)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм «diamond-square» для построения фрактальных ландшафтов