Как стать автором
Обновить

Комментарии 22

Вместо этого на этапе разбиения пространства я строю структуру двусвязного списка рёбер


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

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

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

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

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

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

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

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

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


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


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

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

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


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

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

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


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

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

Разбиение пространства напомнило работы Пита Мондриана:
image
Генерацию подобных картин я когда-то делал с помощью Wolfram Mathematica. Для более равномерного разбиения я тогда использовал бета-распределение.
А можете выложить код в свободный доступ? Интересно посмотреть, почитать…
это же перевод) надо идти на источник и там вопрошать
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.