PatientZero Jul 24 2019 at 17:27

Генерация подземелий и пещер для моей игры

4 min

26K

Algorithms*Game design*Game development*

Translation

+63

Comments 26

UFO just landed and posted this here

Brightori Jul 24 2019 at 18:04

Нужны канешн ), просто про деревья обычно спрашивают на собеде всякие штуки которые давным давно читал в учебнике, плюс придираются к формулировкам. А вакансия вообще про UI ), где большую часть времени надо старые префабы переделывать.

По теме статьи — генерация контента очень прикольная и интересная тема ), результат у автора на первый взгляд ничошный такой.

Zibx Jul 24 2019 at 18:22

Тут использовались базовые структуры. Они, тригонометрия и линейка радостно вылезают при касании программистом геймдева. С другой стороны можно обойтись без какой-либо математики, но тогда будут решаться другие задачи или другими способами. Умение выбрать подходящую структуру и реализовать её (после чего, возможно, выкинуть свою реализацию и взять готовую) — чертовски ценно и именно оно требуется программистам. На собеседованиях же могут спросить нюансы вращения B+tree с размером указателей в ребёнке перевалившим за размер сектора диска. Когда мне попадалось такое — я уходил. Сам когда искал людей — таким не страдал.

ledocool Jul 25 2019 at 10:43

А я скажу так:
Для программирования математика не нужна. Программирование вообще сугубо гуманитарная дисциплина. Это ведь в первую очередь язык и умение им пользоваться. Вы ведь разговор/письмо на английском не считаете тех. дисциплиной? Конечно, я понимаю, что в основном на этом языке говорят о теоремах и выражениях, но все же. Да и посмотрите на языки высокого уровня — мы всячески идем к тому, чтобы в свободной форме изложить компу задачу, а как ее делать он решал сам.)

Другое дело, если разговор заходит о графах и деревьях.

В тех тредах абсолютно правы — там собираются веб программисты. Для веба мозгов не надо. Представьте, если вы пришли устраиваться кассиром в Ашан, а вас просят деревьями повертеть. (Поэтому веб-комьюнити радостно ищет идолов во всяких SOLID'ах. А то иначе тру от нетру не отличить.)

Так вот, математика нужна когда начинаешь делать крутые вещи, а не копипастить REST контроллеры со stack overflow.

alloky Jul 25 2019 at 14:59

Это ведь в первую очередь язык и умение им пользоваться

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

movl Jul 25 2019 at 18:04

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

ledocool Jul 26 2019 at 15:28

Вот у меня так не получается. Почему-то веб никак не выходит считать серьезной дисциплиной. И оттого особенно грустно, что в общем-то дальше веба мне никуда не уползти.

knotri Jul 25 2019 at 14:54

Вы плохо тут статью прочитали — там жаловались на то что вопросы были НЕ СВЯЗАННЫЕ С РАБОТОЙ.

Если бы после собеседования про графы, математику и генерацию пещер вас бы взяли на работу ВНЕЗАПНО делать графы и генерировать пещеры — все супер.

Проблема когда вас после математических вопросов берут перекрашивать кнопку из синего в красный, а потом это по ФТП на прод заливать

Ckpyt Jul 26 2019 at 05:42

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

ledocool Jul 26 2019 at 05:51

А никто заранее не знает чем будет заниматься разработчик в команде.

Вот так придешь на разраба, а тебе кофе заваривать поручат. XD

Mishootk Jul 24 2019 at 18:08

Глядя на результат генерации пещер из комнат интуитивно подставился алгоритм двумерного шума. При генерации шума можно задать уровни комнат и стен такими значениями, чтобы любые шумовые отклонения не выводили их за пороговое значение. Тогда в конце получившийся «рельеф» заливается по уровню «водой» и получаем примерно такой же результат в виде связаных пещер или островов и каналов (для разных игр можно трактовать по разному). Я бы выбрал этот алгоритм как более контролируемый.

SadOcean Jul 24 2019 at 22:26

Ну базовый алгоритм будет тот же, просто вместо клеточного автомата можно использовать шум.

shaman4d Jul 24 2019 at 21:19

«Следующий шаг — генерация коридоров из выбранных рёбер. Наверно, это самая хитрая часть генератора» и она такая хитрая что автор о ней решил просто промолчать. Прекрасно зачем тогда было писать статью…

nightrain912 Jul 25 2019 at 12:39

А чего там хитрого? Там видно же, как он сделал.
Для каждого соединения:

Взять две соединенные комнаты
Получить дельту позиций комнат и выбрать максимальный по модулую компонент (x или y).
Так мы понимаем, горизонтальный или вертикальный коридор и с какой стороны
Получить минимальную и максимальную позицию коридора (для y:
minY = Max(firstRoom.y, secondRoom.y)
maxY = Min(firstRoom.y + firstRoom.height, secondRoom.y + secondRoom.height)
Min и Max не перепутаны)
Если min > max, тоннель нужно "сломать" посередине
Выбрать позицию из указанного интервала: tunnelY = Random.Range(minY, maxY — tunnelHeight)
Нарисовать тоннель

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

IntActment Jul 25 2019 at 12:06

Возможно, я просто придираюсь, но мне не очень нравится результат самой первой итерации дробления пространства: из-за деления «от одной стенки до противоположной — одной прямой линией» сразу бросается в глаза строгая граница, делящая лабиринт пополам, и это свойство алгоритма проявляется в любом варианте генерации. Да, позже добавленные коридоры немного ослабляют эффект, но все же.

CryptoPirate Jul 25 2019 at 12:56

Следующий шаг — генерация коридоров из выбранных рёбер. Наверно, это самая хитрая часть генератора, потому что мне нужно быть аккуратным, чтобы ни один коридор не пересекался с другим.

А зачем запрет на пересекание? Было бы больше всяких ветвистых коридоров с перекрёстками.

trapwalker Jul 25 2019 at 14:31

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

CryptoPirate Jul 25 2019 at 15:43

В примерах есть ветвления, но они идут через другие комнаты (например маленькая комната в центре на первом рисунке). Тут не описано что должен быть один путь через все комнаты в определённом порядке (хотя, я мог пропустить). Выходит, монстров, босов, закрытые двери итд всё равно нужно руками расставлять.

trapwalker Jul 26 2019 at 08:27

В том-то и дело, что нет. В описанном варианте у нас сначала строится граф связности, а потом на его основе все рисуется. Руками ничего расставлять не нужно, все можно автоматизировать.
Проблема не в том, что будет два пути или один, а в том, чтобы иметь возможность этим управлять. Если допустить чрезмерную эрозию стен, то могут появиться незапланированные и не описанные исходным графом дыры. Их придётся детектировать, учитывать, отбраковывать лабиринты с неудобными подходами… Лучше чтобы сразу все по порядку шло предсказуемо и по плану.

ybeltukov Jul 25 2019 at 19:25

Разбиение пространства напомнило работы Пита Мондриана:

Генерацию подобных картин я когда-то делал с помощью Wolfram Mathematica. Для более равномерного разбиения я тогда использовал бета-распределение.

Ckpyt Jul 26 2019 at 05:38

А можете выложить код в свободный доступ? Интересно посмотреть, почитать…

Brightori Jul 26 2019 at 11:56

это же перевод) надо идти на источник и там вопрошать

Mem0 Oct 14 2022 at 17:30

хотелось бы увидеть, конечно, хоть немного кода в такой статье.

Orijana Oct 14 2022 at 17:30

Игра называется Ragnarok?

AlexWolfGod Oct 14 2022 at 17:30

«Следующий шаг — генерация коридоров из выбранных рёбер. Наверно, это самая хитрая часть генератора, потому что мне нужно быть аккуратным, чтобы ни один коридор не пересекался с другим.» — рассказывать про реализацию я, конечно же, не стану))

nurdauletm Oct 14 2022 at 17:30

Круто