Что делает крупный разработчик игр, когда ему нужно состряпать много помещений для игрового мира? Нанимает кучу художников. Что делает ленивый/бедный/одинокий разработчик игр в такой же ситуации? Пишет процедурный генератор, который выполняет за него всю грязную работу.
По процедурной генерации планов помещений есть много, очень много статей. Вот ещё пяток ссылок на статьи. Вот только исходников ни к одной из них нет.
В этой статье я расскажу о том, как я реализовал на Unity3d один простой метод генерации, который приводит к хорошим результатам и легко модифицируется. С картинками и исходниками.
Если хотите, то можете почитать оригинальную статью, но суть примерно следующая:
- Всё пространство разбито на клетки наподобие сетки в архитектурных планах.
- Внешние стены уже существуют и подаются на вход программе.
- Есть список комнат, которые нужно разместить на плане.
- Комнаты имеют параметр «желаемый размер» и коэффициенты притяжения друг к другу
- Точки рождения комнат раскидываются по плану случайным образом, возможно с помощью некоей примерной карты.
- Затем каждая точка начинает прямоугольно расти пока не достигнет определённых для неё размеров.
- Когда все прямоугольники выросли, комнаты начинают расти в форме буквы L до тех пор, пока это возможно.
- Оставшееся свободное место пристёгивается к соседям.
Комнаты растут по одной стенке за раз, чтобы избежать наползания стен и комнат друг на друга. Стенка выбирается из самых больших стен комнаты, если есть одинаковые — берётся случайная. Наибольшая стена берётся для того, чтобы рост площади комнат был максимальным, и они были «пухлыми».
Теперь про мою реализацию. Я не стал пока заморачиваться с реалистичностью планировки, коэффициентами и размерами комнат — это всё украшательства, я работал над основным алгоритмом, всё остальное можно быстро добавить. Также в статье говорится о специальных проверках, предотвращающих появление П-образных комнат, я не стал их делать, не вижу ничего плохого в таких комнатах. Также я не расставлял коридоры, двери и окна, это отдельная тема, и их расстановка может зависеть от генерации всего остального здания.
Самым сложным было выбрать принцип роста комнат и способ хранения данных о них и здании. Один и тот же результат можно получить с помощью клеточных автоматов или даже простого пробега по массиву. Я перепробовал несколько вариантов, мне хотелось всегда иметь представление о габаритах комнаты и точном положении её стен, поэтому я создал класс, в котором хранятся только углы комнаты, а стены автоматически создаются путём связывания двух соседних углов.
Связывание стен это по сути поиск оболочки полигона из набора точек. Задача нетривиальная и с кучей подвохов, если интересно, то советую заглянуть сюда. К счастью, я решил ограничиться прямыми углами между соседними стенами и смастерил простенький алгоритм:
- Находим минимальные и максимальные значения координат X и Y в наборе точек.
- Из точки (minX, minY) отправляемся наверх по игреку и поочерёдно ищем точку с такими координатами, если её там нет, то ищем справа, снизу и слева. Когда находим, вытаскиваем её из старого списка, переносим в новый список.
- От координат этой точки в старом списке ищем следующую точку выше по игреку, если нашли — переносим в новый список, удаляем из старого, запоминаем, что нашли стену, которая параллельна Y, значит следующая стена должна быть параллельна X.
- Ищем точку по иксу справа и слева, переносим в новый список, запоминаем ориентацию только что найденной стены, ищем дальше по аналогии.
- Последнюю точку в старом списке просто переносим в новый.
public GridVector SortCorners()
{
// Ищем границы комнаты
var minX = corners[0].x;
var maxX = corners[0].x;
var minY = corners[0].y;
var maxY = corners[0].y;
foreach (var corner in corners)
{
if (corner.x < minX) minX = corner.x;
if (corner.x > maxX) maxX = corner.x;
if (corner.y < minY) minY = corner.y;
if (corner.y > maxY) maxY = corner.y;
}
// Сортируем углы комнаты
var oldC = new List<GridVector>(corners);
var newC = new List<GridVector>();
bool parallelX = false;
while (oldC.Count > 1)
{
// Ищем первый угол
if (newC.Count == 0)
{
if (ScanUp(ref oldC, ref newC, minX, minY, maxY)) continue;
if (ScanRight(ref oldC, ref newC, minX, minY, maxX)) continue;
if (ScanDown(ref oldC, ref newC, minX, minY, minY)) continue;
if (!ScanLeft(ref oldC, ref newC, minX, minY, minX))
{
Debug.Log("Error on start");
return null;
}
}
// Ищем остальные углы
else
{
var last = newC[newC.Count - 1];
if (parallelX)
{
if (ScanRight(ref oldC, ref newC, last.x, last.y, maxX))
{
parallelX = false;
continue;
}
if (ScanLeft(ref oldC, ref newC, last.x, last.y, minX))
{
parallelX = false;
continue;
}
}
else
{
if (ScanUp(ref oldC, ref newC, last.x, last.y, maxY))
{
parallelX = true;
continue;
}
if (ScanDown(ref oldC, ref newC, last.x, last.y, minY))
{
parallelX = true;
continue;
}
}
Debug.Log("Error -------------------------------------------------");
Debug.Log("Corners: " + corners.Count);
Debug.Log("OldC: " + oldC.Count);
Debug.Log("NewC: " + newC.Count);
Debug.Log(last);
color = Color.red;
return last;
}
}
// Добавляем последний оставшийся угол
newC.Add(oldC[0]);
corners = newC;
return null;
}
bool ScanLeft(ref List<GridVector> oldC, ref List<GridVector> newC, int startX, int startY, int minX)
{
for (var x = startX; x >= minX; x--)
{
var index = oldC.FindIndex(gv => gv.x == x && gv.y == startY);
if (index > -1)
{
newC.Add(oldC[index]);
oldC.RemoveAt(index);
return true;
}
}
return false;
}
bool ScanUp(ref List<GridVector> oldC, ref List<GridVector> newC, int startX, int startY, int maxY)
{
for (var y = startY; y <= maxY; y++)
{
var index = oldC.FindIndex(gv => gv.x == startX && gv.y == y);
if (index > -1)
{
newC.Add(oldC[index]);
oldC.RemoveAt(index);
return true;
}
}
return false;
}
bool ScanRight(ref List<GridVector> oldC, ref List<GridVector> newC, int startX, int startY, int maxX)
{
for (var x = startX; x <= maxX; x++)
{
var index = oldC.FindIndex(gv => gv.x == x && gv.y == startY);
if (index > -1)
{
newC.Add(oldC[index]);
oldC.RemoveAt(index);
return true;
}
}
return false;
}
bool ScanDown(ref List<GridVector> oldC, ref List<GridVector> newC, int startX, int startY, int minY)
{
for (var y = startY; y >= minY; y--)
{
var index = oldC.FindIndex(gv => gv.x == startX && gv.y == y);
if (index > -1)
{
newC.Add(oldC[index]);
oldC.RemoveAt(index);
return true;
}
}
return false;
}
В конечном итоге, у нас получается список углов, отсортированных по часовой стрелке, из которого можно запросто вывести стены. Благодаря сортировке становится легко узнать ещё одну важную вещь — направление наружу от стены комнаты. Для того чтобы повернуть конец стены наружу, нужно поменять X и Y местами и инвертировать первую координату, чтобы получилось следующее: (-y, x).
Комнаты хранятся в виде точек, точки сортируются, стены строятся автоматически, направление наружу известно — всего этого достаточно, чтобы проверять свободное пространство на плане этажа и выращивать комнаты. Иногда правда приходится добавлять новые стены, когда старые уже во что-то упёрлись и не могут расти.
Для проверки доступности клеток и поиска возможных новых стен я использую одну функцию, которая собирает список доступных для роста участков подаваемой на вход стены. Потом я сортирую найденные сегменты со всей комнаты по категориям: цельные стены, кусочки у края стены, центральные сегменты. Выбираю самую большую стенку из доступных и отправляю в функцию роста комнаты, а она сама разбирается, есть у неё уже такая стенка, или нужно создать новую. Когда стенка есть, координаты её концов сдвигаются наружу, что приводит к автоматическому удлинению соседних стен.
List<RoomWall> FindSegments(RoomWall wall, Color freeColor, Color roomColor)
{
var moved = wall + wall.outwards.minimized;
BresenhamLine(moved, new Color(Random.value * 0.7f + 0.1f, Random.value * 0.7f + 0.1f, Random.value * 0.7f + 0.1f), segmentsTexture);
var x0 = moved.start.x;
var y0 = moved.start.y;
var x1 = moved.end.x;
var y1 = moved.end.y;
var segments = new List<RoomWall>();
GridVector start = null;
GridVector end = null;
bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
if (steep)
{
Swap(ref x0, ref y0);
Swap(ref x1, ref y1);
}
if (x0 > x1)
{
Swap(ref x0, ref x1);
Swap(ref y0, ref y1);
}
for (int x = x0; x <= x1; x++)
{
for (int y = y0; y <= y1; y++)
{
int coordX = steep ? y : x;
int coordY = steep ? x : y;
Color color = texture.GetPixel(coordX, coordY);
if (color != freeColor && color != roomColor)
{
if (end != null && start != null)
{
var segment = new RoomWall(start, end);
segment -= wall.outwards.minimized;
segments.Add(segment);
start = null;
end = null;
}
scanTexture.SetPixel(coordX, coordY, Color.red);
}
else
{
if (start == null)
{
start = new GridVector(coordX, coordY);
}
end = new GridVector(coordX, coordY);
scanTexture.SetPixel(coordX, coordY, Color.green);
}
}
}
if (end != null && start != null)
{
var segment = new RoomWall(start, end);
segment -= wall.outwards.minimized;
segments.Add(segment);
}
return segments;
}
Для отображения всех манипуляций с комнатами я использую текстуру, в пиксели которой заношу положения стен. Если не стирать старые стенки, то получаются заполненные области, как на gif-ке в начале статьи. Стены рисую с помощью линий Брезенхема, про которые я писал здесь. В случае возникновения проблем со склейкой стен, всё сразу становится видно. Вместо текстуры можно использовать двумерный массив или сразу оперировать трёхмерной моделью.
Внешние стены можно генерировать очень просто. Рисуем несколько чёрных прямоугольников произвольных размеров, а поверх них рисуем такие же только белые и на один пиксель меньше с каждой стороны. Получается много разных домиков. Ещё их можно сделать трёхмерными и покрыть крышей. Голосом Каневского: Впрочем, это уже совсем другая история.
По ссылкам ниже можете посмотреть бинарники и исходники готового проекта.
Unity Web Player | Windows | Linux | Mac | Исходники на GitHub
Shift — Создаёт случайные внешние стены со случайными комнатами
Ctrl — Загрузить тестовую текстуру со случайными комнатами
Enter — Убрать все комнаты и загрузить тестовую текстуру
Пробел — Остановить рост комнат
Единица на алфавитной клавиатуре — Включить визуализацию поиска свободных клеток
Левая кнопка мыши на свободной области — Добавить комнату
Esc — Выход
Для пользователей Linux: Сделайте файл ProceduralExperiments.x86 исполняемым с помощью «chmod +x ProceduralExperiments.x86» и запускайте.
Автор: BasmanovDaniil
