Алгоритмы генерации карт

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

Рис. 10.13. Окно программы D3D_MapEditorGeneration

Обратите внимание на уже ставшие привычными элементы рисунка. Здесь есть панель инструментов, область редактирования и мини-карта. Новым элементом является появившаяся на панели инструментов кнопка Generate. Она очищает всю карту, заполняя ее водой, и создает случайно расположенные участки суши. Кроме того, вы можете заметить, что я увеличил размер мини-карты. Я сделал это для того, чтобы вы более ясно увидели эффект генерации случайной карты. Есть и еще одно изменение, которое нельзя заметить на рис. 10.13. Если вы запустите программу D3D_MapEditorGeneration, то увидите красный прямоугольник на мини-карте. Он показывает, какой именно фрагмент большой карты отображается в окне просмотра и помогает понять что именно вы сейчас редактируете.

Теперь загрузите проект D3D_MapEditorGeneration и следуйте за мной, а я буду рассказывать вам о коде программы.

Функция vGenerateMap()

Структура этой программы редактирования карт практически полностью повторяет структуру предыдущего примера. Главные отличия сконцентрированы в функции генерации карты. Ее цель — генерировать случайно расположенные участки суши, базируясь на передаваемом в качестве параметра номере используемого алгоритма. В рассматриваемом примере я реализовал только один тип алгоритма генерации карты, но ничто не мешает вам добавить и другие! Вот как выглядит код функции:

void vGenerateMap(int iType)
{
   int iRandDirection;
   int iSeedPos[32];
   int i, j;
   int iNumSeeds     = 32;
   int iNumUpdates   = 800;

   // -- ТИП 0 -- Случайные семена
   if(iType == 0) {
      // Очиска карты
      vInitMap();
      // Создание случайно расположенных начальных семян
      for(i = 0; i < iNumSeeds; i++) {
         // Установка начальной позиции семени
         iSeedPos[i] = rand() % (g_iMapHeight * g_iMapWidth);
         // Помещаем в позицию семени блок с изображением травы
         g_iTileMap[iSeedPos[i]] = 17;
      }
      // Перемещение семени
      for(i = 0; i < iNumUpdates; i++) {
         for(j = 0; j < iNumSeeds; j++) {
            iRandDirection = rand()%4;

            // перемещаем семя вверх
            if(iRandDirection == 0) {
               iSeedPos[j] -= g_iMapWidth;
            }
            // Перемещаем семя вправо
            else if(iRandDirection == 1) {
               iSeedPos[j]++;
            }
            // Перемещаем семя вниз
            else if(iRandDirection == 2) {
               iSeedPos[j] += g_iMapWidth;
            }
            // Перемещаем семя влево
            else if(iRandDirection == 3) {
               iSeedPos[j]--;
            }

            // Если семя вышло за пределы карты,
            // помещаем его в случайную позицию
            if(iSeedPos[j] < 0 ||
               iSeedPos[j] >= (g_iMapHeight * g_iMapWidth))
            {
               iSeedPos[j] =
                  rand() % (g_iMapHeight * g_iMapWidth);
            }
            // Помещаем в позицию семени блок с изображением травы
            g_iTileMap[iSeedPos[j]] = 17;
         }
      }
   }
   // Отображение мини-карты
   vRenderMinimap();
   // Воспроизведение звука, сообщающего о завершении операции
   PlaySound("bleep.wav",NULL,SND_FILENAME|SND_ASYNC);
}

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

Рис. 10.14. Ход выполнения функции vGenerateMap()

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

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

Есть еще пара вещей, отсутствующих на иллюстрации. Во-первых, перед началом создания ландшафта я вызываю функцию vInitMap() для очистки карты. Это требуется для того, чтобы перед созданием случайно расположенных блоков с изображением травы массив карты был приведен в исходное состояние. Во-вторых, на иллюстрации отсутствует проверка, гарантирующая, что семя не будет блуждать за пределами карты. Если семя выходит за границы карты, оно помещается в случайную позицию внутри карты и продолжает формировать изображение суши в новом месте. И последняя отсутствующая вещь — вызов функции отображения миникарты, показывающей обновленный ландшафт.

Методы генерации карт

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

Рис. 10.15. Использование шаблонов для генерации случайного ландшафта

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