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

Материал из Клуб любителей рогаликов
Перейти к: навигация, поиск

Создание карты

При создании roguelike игры (отсюда и далее - RL), есть несколько моментов, требующих внимания. Одна из первых проблем, с которыми Вы, вероятно, столкнетесь - проблема генерации пригодного уровня темниц. Фактически, мало того, что Вы нуждаетесь в уровне, Вы нуждаетесь и в значительно бесконечной генерации случайных уровней заполненных монстрами, сокровищами, ловушками и всякой всячиной.

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

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

Этот алгоритм будет основан на взятии большого куска скалы, скажем, 256x256 и вырезание темниц из него, комнат и проходов. Мы будем вначале упрощать насколько возможно, хотя этот алгоритм может быть расширен, чтобы произвести много различных типов темницы от пещер до замков, с довольно незначительными изменениями основного кода.

Так мы начинаем с 256x256 тайлов, заполненных камнем. Для нашего основного генератора темниц мы будем также нуждаться в двух функциях:

MakeRoom(), которая генерирует случайную комнату и затем вызывает: MakeHall(), которая генерирует холл случайной длины.

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

Скажем, используя всевдокод мы имеем:

  • StartX и StartY будут целые числа, определяющие местоположение каждой комнаты и холла;
  • Direction будет целое число, определяющее направление комнаты или холла;
  • RecurseDepth будет использоваться для прекращения рекурсии на некоторой глубине;

Первым мы определим MakeRoom.

void MakeRoom( StartX, StartY, Direction, RecurseDepth )
{
        integer X1,Y1,X2,Y2; // расположение комнаты

        // ограничитель рекурсии до некоторой глубины
        if( RecurseDepth > MAXRECURSEDEPTH ) return;

        DetermineExtents();
/*      Мы должны определить направление, когда определяем 
        расположение...
        ... Для примера:
        ( '#' = скала '.' = открытое пространство)

        ##########
        ##########
        ##########
        #####X.... <--- Коридор вызывает MakeRoom.
        ##########
        ##########
        ##########

        В этой ситуации мы определяем расположение:
        a = x1,y1
        b = x2,y2
        ##########
        ##########
        #a****####
        #****X....
        #****b####
        ##########
        ##########
        Это хорошо...

        ##########
        ##########
        ###a****##
        ###**X....
        ###****b##
        ##########
        ##########
        Это плохо...
*/

        CreateTheRoom();

        for( x = x1 to x2 )
         for( y = y1 to y2 )
          Dungeon[x,y] = OpenSpace;

        integer R = Random(0,4); // определение направления.

        for( x = 0 to R )
        {
                int hx,hy,hd;

                DetermineLocationOfHall();
                // Выберем точку на одной из стен
                // Затем определим направление
                // (North, South, East или West) относительно 
                // выбранной стены.

                MakeHall( hx,hy,hd, RecurseDepth+1 );
        }
}

Сейчас, MakeHall которая сравнительно проста:

void MakeHall( StartX, StartY, Direction, RecurseDepth )
{
        // ограничитель рекурсии...
        if( RecurseDepth > MAXRECURSEDEPTH ) return;

        integer x1,y1;
        x1 = StartX;
        y1 = StartY;

        for( x = 1 to RandomLength )
        {
                if( x1 or y1 is out of bounds ) return;

                Dungeon[x1,y1] = OpenSpace;

                // Заметьте:
                // Для удобства прохода в направлении, которое мы
                // будем определять, два массива содержат X и Y 
                // смещения каждого направления
                x1 += DirectionXDelta[Direction];
                y1 += DirectionYDelta[Direction];
        }

        RandomChoice = Random(1,3);

        if( RandomChoice == 1 ) return;

        if( RandomChoice == 2 )
         for( x = 1 to Random(0,3) )
          MakeHall( x1,y1, RandomDirection, RecurseDepth+1 );

        if( RandomChoice == 3 )
         MakeRoom( x1,y1, Direction, RecurseDepth+1 );
}

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



Автор: Brian Bucklew.
Источник: Creating A Dungeon.
Перевел: Сергей В. Ждановских [Alchemist], 10.04.2005.