Использование BSP-деревьев для создания игровых карт

При заполнении области объектами (например, комнатами в подземелье) в случайном порядке вы рискуете тем, что всё будет слишком случайным. Результат может оказаться абсолютно бесполезным хаосом. В этом туториале я покажу, как использовать для решения этой проблемы двоичное разбиение пространства (Binary Space Partitioning, BSP).

Я подробно и по этапам расскажу об использовании BSP для создания простой двухмерной карты, к примеру, схемы подземелья. Я покажу, как создать простой объект Leaf, который мы используем для разделения области на маленькие сегменты. Затем мы займёмся генерированием в каждом Leaf случайной комнаты. И, наконец, узнаем, как соединить все комнаты коридорами.

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

---

Демо-проект

Я создал демо, показывающую часть возможностей BSP. Демо написано с помощью свободной библиотеки AS3 Flixel с открытым исходным кодом.

При нажатии на кнопку Generate демо выполняет код для генерирования нескольких Leaf, а затем отрисовывает их в объекте BitmapData, после чего тот отображается на экране (с увеличением масштаба для заполнения экрана).

Генерирование случайной карты. (Нажмите для загрузки демо.)

При нажатии на кнопку Play программа передаёт сгенерированную карту Bitmap объекту FlxTilemap, который генерирует играбельную тайловую карту и отображает её на экране. По ней можно побродить с помощью стрелок:

Играем на карте. (Нажмите для загрузки демо.)

---

Что такое BSP?

Двоичное разбиение пространства — это способ разделения области на более мелкие части.

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

После завершения процесса у нас получится иерархия разбитых Leaf, с которыми можно делать всё, что угодно. В трёхмерной графике BSP можно использовать для сортировки видимых для игрока объектов или для распознавания коллизий в ещё меньших частях.

---

Зачем использовать BSP для генерирования карт?

Существует множество разных способов генерирования случайной карты. Можно написать простую логику для создания прямоугольников случайного размера в случайных местах, но в результате получатся карты, заполненные пересекающимися, скученными или странно расположенными комнатами. Кроме того, немного сложнее соединить все комнаты друг с другом и сделать так, чтобы не осталось изолированных комнат. Благодаря BSP можно гарантировать создание более равномерно распределённых комнат и обеспечить их соединение.

---

Создание листьев

Первое, что нам нужно создать в коде — класс Leaf. В сущности, наш Leaf будет прямоугольником с некоторыми дополнительными возможностями. Каждый Leaf будет содержать либо пару дочерних Leaf, либо пару комнат Room, а также один или два коридора.

Вот как выглядит код Leaf:

public class Leaf {  	private const MIN_LEAF_SIZE:uint = 6;  	public var y:int, x:int, width:int, height:int; // положение и размер этого листа  	public var leftChild:Leaf; // левый дочерний Leaf нашего листа 	public var rightChild:Leaf; // правый дочерний Leaf нашего листа 	public var room:Rectangle; // комната, находящаяся внутри листа 	public var halls:Vector.; // коридоры, соединяющие этот лист с другими листьями  	public function Leaf(X:int, Y:int, Width:int, Height:int) 	{ 		// инициализация листа 		x = X; 		y = Y; 		width = Width; 		height = Height; 	}  	public function split():Boolean 	{ 		// начинаем разрезать лист на два дочерних листа 		if (leftChild != null || rightChild != null) 			return false; // мы уже его разрезали! прекращаем!  		// определяем направление разрезания 		// если ширина более чем на 25% больше высоты, то разрезаем вертикально 		// если высота более чем на 25% больше ширины, то разрезаем горизонтально 		// иначе выбираем направление разрезания случайным образом 		var splitH:Boolean = FlxG.random() > 0.5; 		if (width > height && width / height >= 1.25) 			splitH = false; 		else if (height > width && height / width >= 1.25) 			splitH = true;  		var max:int = (splitH ? height : width) - MIN_LEAF_SIZE; // определяем максимальную высоту или ширину 		if (max <= MIN_LEAF_SIZE) 			return false; // область слишком мала, больше её делить нельзя...  		var split:int = Registry.randomNumber(MIN_LEAF_SIZE, max); // определяемся, где будем разрезать  		// создаём левый и правый дочерние листы на основании направления разрезания 		if (splitH) 		{ 			leftChild = new Leaf(x, y, width, split); 			rightChild = new Leaf(x, y + split, width, height - split); 		} 		else 		{ 			leftChild = new Leaf(x, y, split, height); 			rightChild = new Leaf(x + split, y, width - split, height); 		} 		return true; // разрезание выполнено! 	} }

Теперь нам нужно создать Leaf:

const MAX_LEAF_SIZE:uint = 20;  var _leafs:Vector<Leaf> = new Vector<Leaf>;  var l:Leaf; // вспомогательный лист  // сначала создаём лист, который будет "корнем" для всех остальных листьев. var root:Leaf = new Leaf(0, 0, _sprMap.width, _sprMap.height); _leafs.push(root);  var did_split:Boolean = true; // циклически снова и снова проходим по каждому листу в нашем Vector, пока больше не останется листьев, которые можно разрезать. while (did_split) { 	did_split = false; 	for each (l in _leafs) 	{ 		if (l.leftChild == null && l.rightChild == null) // если лист ещё не разрезан... 		{ 			// если этот лист слишком велик, или есть вероятность 75%... 			if (l.width > MAX_LEAF_SIZE || l.height > MAX_LEAF_SIZE || FlxG.random() > 0.25) 			{ 				if (l.split()) // разрезаем лист! 				{ 					// если мы выполнили разрезание, передаём дочерние листья в Vector, чтобы в дальнейшем можно было в цикле обойти и их 					_leafs.push(l.leftChild); 					_leafs.push(l.rightChild); 					did_split = true; 				} 			} 		} 	} }

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

Вот пример с листьями, разделёнными линиями:


Пример области, разделённой на листья

---

Создание комнат

Мы определились с листьями, теперь нужно создать комнаты. Мы хотим реализовать своеобразный эффект «перетекания»: начнём с самого большого, «корневого» Leaf и спустимся до самых маленьких Leaf, у которых нет дочерних листьев, а затем создадим в каждом из них комнату.

Поэтому добавим в класс Leaf эту функцию:

public function createRooms():void { 	// эта функция генерирует все комнаты и коридоры для этого листа и всех его дочерних листьев. 	if (leftChild != null || rightChild != null) 	{ 		// этот лист был разрезан, поэтому переходим к его дочерним листьям 		if (leftChild != null) 		{ 			leftChild.createRooms(); 		} 		if (rightChild != null) 		{ 			rightChild.createRooms(); 		} 	} 	else 	{ 		// этот лист готов к созданию комнаты 		var roomSize:Point; 		var roomPos:Point; 		// размер комнаты может находиться в промежутке от 3 x 3 тайла до размера листа - 2. 		roomSize = new Point(Registry.randomNumber(3, width - 2), Registry.randomNumber(3, height - 2)); 		// располагаем комнату внутри листа, но не помещаем её прямо  		// рядом со стороной листа (иначе комнаты сольются) 		roomPos = new Point(Registry.randomNumber(1, width - roomSize.x - 1), Registry.randomNumber(1, height - roomSize.y - 1)); 		room = new Rectangle(x + roomPos.x, y + roomPos.y, roomSize.x, roomSize.y); 	} }

Теперь, когда мы создали Vector из листьев, вызовем нашу новую функцию из корневого листа:

_leafs = new Vector<Leaf>;  var l:Leaf; // вспомогательный лист  // сначала создаём лист, который будет "корнем" всех листьев. var root:Leaf = new Leaf(0, 0, _sprMap.width, _sprMap.height); _leafs.push(root);  var did_split:Boolean = true; // циклически проходим по каждому листу в Vector, снова и снова, пока не останется неразрезанных листьев. while (did_split) { 	did_split = false; 	for each (l in _leafs) 	{ 		if (l.leftChild == null && l.rightChild == null) // если этот лист ещё не разрезан... 		{ 			// если этот лист слишком большой, или есть вероятность 75%... 			if (l.width > MAX_LEAF_SIZE || l.height > MAX_LEAF_SIZE || FlxG.random() > 0.25) 			{ 				if (l.split()) // разрезаем лист! 				{ 					// если мы выполнили разрезание, передаём дочерние листья в Vector, чтобы в дальнейшем можно было в цикле обойти и их 					_leafs.push(l.leftChild); 					_leafs.push(l.rightChild); 					did_split = true; 				} 			} 		} 	} }  // затем итеративно проходим по каждому листу и создаём в каждом комнату. root.createRooms();

Вот пример нескольких сгенерированных листьев с комнатами внутри:


Пример листьев со случайными комнатами внутри каждого.

Как вы видите, каждый лист содержит одну комнату случайного размера и со случайным расположением. Можно поэкспериментировать со значениями минимального и максимального размера листа, изменять размер и положение каждой комнаты, чтобы научиться получать разные эффекты.

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


Пример листьев с комнатами внутри без разделительных линий.

---

Соединение листьев

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

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

public function getRoom():Rectangle { 	// итеративно проходим весь путь по этим листьям, чтобы найти комнату, если она существует. 	if (room != null) 		return room; 	else 	{ 		var lRoom:Rectangle; 		var rRoom:Rectangle; 		if (leftChild != null) 		{ 			lRoom = leftChild.getRoom(); 		} 		if (rightChild != null) 		{ 			rRoom = rightChild.getRoom(); 		} 		if (lRoom == null && rRoom == null) 			return null; 		else if (rRoom == null) 			return lRoom; 		else if (lRoom == null) 			return rRoom; 		else if (FlxG.random() > .5) 			return lRoom; 		else 			return rRoom; 	} }

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

public function createHall(l:Rectangle, r:Rectangle):void { 	// теперь мы соединяем эти две комнаты коридорами. 	// выглядит довольно сложно, но здесь мы просто выясняем, где какая точка находится, а затем отрисовываем прямую линию или пару линий, чтобы создать правильный угол для их соединения. 	// при желании можно добавить логику, делающую коридоры более извилистыми, или реализующую другое сложное поведение.  	halls = new Vector<Rectangle>;  	var point1:Point = new Point(Registry.randomNumber(l.left + 1, l.right - 2), Registry.randomNumber(l.top + 1, l.bottom - 2)); 	var point2:Point = new Point(Registry.randomNumber(r.left + 1, r.right - 2), Registry.randomNumber(r.top + 1, r.bottom - 2));  	var w:Number = point2.x - point1.x; 	var h:Number = point2.y - point1.y;  	if (w < 0) 	{ 		if (h < 0) 		{ 			if (FlxG.random() < 0.5) 			{ 				halls.push(new Rectangle(point2.x, point1.y, Math.abs(w), 1)); 				halls.push(new Rectangle(point2.x, point2.y, 1, Math.abs(h))); 			} 			else 			{ 				halls.push(new Rectangle(point2.x, point2.y, Math.abs(w), 1)); 				halls.push(new Rectangle(point1.x, point2.y, 1, Math.abs(h))); 			} 		} 		else if (h > 0) 		{ 			if (FlxG.random() < 0.5) 			{ 				halls.push(new Rectangle(point2.x, point1.y, Math.abs(w), 1)); 				halls.push(new Rectangle(point2.x, point1.y, 1, Math.abs(h))); 			} 			else 			{ 				halls.push(new Rectangle(point2.x, point2.y, Math.abs(w), 1)); 				halls.push(new Rectangle(point1.x, point1.y, 1, Math.abs(h))); 			} 		} 		else // если (h == 0) 		{ 			halls.push(new Rectangle(point2.x, point2.y, Math.abs(w), 1)); 		} 	} 	else if (w > 0) 	{ 		if (h < 0) 		{ 			if (FlxG.random() < 0.5) 			{ 				halls.push(new Rectangle(point1.x, point2.y, Math.abs(w), 1)); 				halls.push(new Rectangle(point1.x, point2.y, 1, Math.abs(h))); 			} 			else 			{ 				halls.push(new Rectangle(point1.x, point1.y, Math.abs(w), 1)); 				halls.push(new Rectangle(point2.x, point2.y, 1, Math.abs(h))); 			} 		} 		else if (h > 0) 		{ 			if (FlxG.random() < 0.5) 			{ 				halls.push(new Rectangle(point1.x, point1.y, Math.abs(w), 1)); 				halls.push(new Rectangle(point2.x, point1.y, 1, Math.abs(h))); 			} 			else 			{ 				halls.push(new Rectangle(point1.x, point2.y, Math.abs(w), 1)); 				halls.push(new Rectangle(point1.x, point1.y, 1, Math.abs(h))); 			} 		} 		else // если (h == 0) 		{ 			halls.push(new Rectangle(point1.x, point1.y, Math.abs(w), 1)); 		} 	} 	else // если (w == 0) 	{ 		if (h < 0) 		{ 			halls.push(new Rectangle(point2.x, point2.y, 1, Math.abs(h))); 		} 		else if (h > 0) 		{ 			halls.push(new Rectangle(point1.x, point1.y, 1, Math.abs(h))); 		} 	} }

Наконец, мы изменим функцию createRooms(), чтобы она вызывала функцию createHall() для каждого листа, имеющего пару дочерних листьев:

public function createRooms():void { 	// эта функция генерирует все комнаты и коридоры для этого листа и всех его дочерних листьев. 	if (leftChild != null || rightChild != null) 	{ 		// этот лист был разрезан, поэтому переходим к его дочерним листьям 		if (leftChild != null) 		{ 			leftChild.createRooms(); 		} 		if (rightChild != null) 		{ 			rightChild.createRooms(); 		}  		// если у этого листа есть и левый, и правый дочерние листья, то создаём между ними коридор 		if (leftChild != null && rightChild != null) 		{ 			createHall(leftChild.getRoom(), rightChild.getRoom()); 		}  	} 	else 	{ 		// этот лист готов к созданию комнаты 		var roomSize:Point; 		var roomPos:Point; 		// размер комнаты может находиться в промежутке от 3 x 3 тайла до размера листа - 2. 		roomSize = new Point(Registry.randomNumber(3, width - 2), Registry.randomNumber(3, height - 2)); 		// располагаем комнату внутри листа, но не помещаем её прямо рядом со стороной листа (иначе комнаты сольются) 		roomPos = new Point(Registry.randomNumber(1, width - roomSize.x - 1), Registry.randomNumber(1, height - roomSize.y - 1)); 		room = new Rectangle(x + roomPos.x, y + roomPos.y, roomSize.x, roomSize.y); 	} }

Получившиеся комнаты и коридоры должны выглядеть примерно так:


Пример листьев, заполненных случайными комнатами и соединёнными коридорами.

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

---

Подводим итог

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

На данном этапе все созданные нами объекты являются прямоугольниками, но при необходимости им можно придать любую форму.

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