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

Все мы любим rogue-like-игры со случайно генерируемыми подземельями (или космосом). Один из читателей Gamasutra подробно объясняет, как именно работает алгоритм генерации:

Сначала внутри заданного круга создаются команты со случайной шириной и высотой. Разные соотношения ширины/высоты приводят к разному виду подземелий:

Чтобы комнаты не сбивались в кучу и не накладывались друг на друга, используется симуляция каждой комнаты как твердого физического тела:

Затем нужно определить, какие комнаты будут главными/ключевыми для игры. Скажем, все команты с шириной и высотой больше 30 назначаются главными:

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

Подземелье не должно напоминать планировкой жилую квартиру, но и удаленных комнат-островов в нем быть не должно:

В последнюю очередь в подземелье добавляются коридоры. Сначала они выстраиваются между точками графика главных комнат. Затем на «скелет» из коридоров накладываются оставшиеся комнаты:

И все, ваше подземелье закончено. Можно выходить навстречу perma-death!