Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Programming

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

by
Difficulty:IntermediateLength:LongLanguages:

Russian (Pусский) translation by Marat Amerov (you can also view the original English article)

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

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

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

Демо-проект

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

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

Screenshot from Demo program - Generating the Random Map
Генерирование случайной карты. (Нажмите для загрузки демо.)

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

Screenshot from Demo program - Playing the Map
Играем на карте. (Нажмите для загрузки демо.)

Используйте клавиши со стрелками для перемещения.


Что такое BSP?

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

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

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


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

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

Благодаря BSP можно гарантировать создание более равномерно распределённых комнат и обеспечить их соединение.


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

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

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

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

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

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

Sample of an area divided by Leafs
Пример области, разделённой на листья

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

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

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

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

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

Sample of Leafs with random room inside each one
Пример листьев со случайными комнатами внутри каждого.

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

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

Sample of Leafs with a room inside each one separator lines removed
Пример Leafs с комнатами внутри без разделительных линий.

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

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

Мы возьмём Leaf, рассмотрим каждый из его дочерних Leafs, пройдём до каждого из дочерних, пока не дойдём до Leaf с комнатой, а затем соединим комнаты. Мы можем делать это одновременно с генерированием комнат.

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

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

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

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

Sample of Leafs filled with random rooms connected via hallways
Пример Leafs, заполненных случайными комнатами и соединёнными коридорами.

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


Заключение

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

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

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

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.