При заполнении области объектами (например, комнатами в подземелье) в случайном порядке вы рискуете тем, что всё будет слишком случайным. Результат может оказаться абсолютно бесполезным хаосом. В этом туториале я покажу, как использовать для решения этой проблемы двоичное разбиение пространства (Binary Space Partitioning, BSP).
Я подробно и по этапам расскажу об использовании BSP для создания простой двухмерной карты, к примеру, схемы подземелья. Я покажу, как создать простой объект Leaf
, который мы используем для разделения области на маленькие сегменты. Затем мы займёмся генерированием в каждом Leaf
случайной комнаты. И, наконец, узнаем, как соединить все комнаты коридорами.
Примечание: хоть код примеров и написан на AS3, концепцию можно использовать практически в любом другом языке.
Leaf
, а затем отрисовывает их в объекте BitmapData
, после чего тот отображается на экране (с увеличением масштаба для заполнения экрана).Bitmap
объекту FlxTilemap
, который генерирует играбельную тайловую карту и отображает её на экране. По ней можно побродить с помощью стрелок:Leaf
), и разделяем её, вертикально или горизонтально, на два меньших листа, а затем повторяем процесс с меньшими областями, снова и снова, пока каждая область не станет меньше или равной заданному максимальному значению.Leaf
, с которыми можно делать всё, что угодно. В трёхмерной графике 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
, который можно использовать для генерирования дерева разделённых листьев, создали случайные комнаты в каждом из листьев и соединили комнаты коридорами.К сожалению, не доступен сервер mySQL