Создание редактора карт в стратегиях типа WarCraft

Довелось мне как-то озадачиться идеей написать редактор карт для моей новой игры. Скажу сразу, что задача эта не из простых. Приступим сразу к делу. Как правило, в двумерных стратегических играх типа Warcraft, Heroes of Might and Magic, Z и т. д. карты строятся из ячеек. Иными словами, карта - это матрица с некоторыми числовыми значениями внутри ячеек. Эти значения есть номера текстур (растровых картинок с изображениями земли, воды, камней и т. д., из которых и будет склеиваться Ваш уникальный ландшафт).

Рисунок 1

На рисунке изображена ну очень маленькая карта с размером матрицы 3х3. Для создания подобной карты задается двумерный массив ( Map : Array[3, 3] of Byte ), записываются, каким-либо образом, в каждую ячейку порядковые номера текстур и при выводе карты на экран эти номера читаются из массива. Ну например: ...
For i := 0 to 2 do
For j := 0 to 2 do
Begin
Number := Map[i, j];
X := J * TextureWidth;
Y := i * TextureHeight;
DrawTexture(X, Y, Number);
End;
... Number - номер текстуры,
Х - координата текстуры на экране,
Y - то же самое,
DrawTexture - некая процедура вывода текстуры на экран.

Совет!!!
Если Вам заранее не известно из какого количества ячеек будет состоять Ваша карта, не используйте Tlist в Tlist'e для ее создания. Советую воспользоваться PByteArray. GetMem(PbyteArray, MapWidth*MapHeight*SizeOf(Тип ячейки));

Тип ячейки в нашем случае - Byte. Обращение в этом случае будет таким: Number := PbyteArray[Y*MapWidth + X];Где X, Y - координаты нужной ячейки в матрице.
Все что мы рассмотрели выше подходит для карт на основе только лишь одного типа земли. Взгляните на рисунок расположенный выше. Вы увидите, что поскольку все текстуры разные - карта как-бы состоит из квадратиков. Кому она такая нужна? Хочется чтобы эти текстуры плавно перетекали друг в друга. Отсюда есть три выхода:
Создавать карту из текстур мало отличающихся друг от друга и при рисовании карты выбирать их случайным образом.
Налепить целю кучу "пересекающихся" между собой текстур и класть их на карту вручную.
Так же налепить ту же кучу текстур и написать программу позволяющую автоматически распределять их на карте.
Первый способ не очень интересен. Он скорее подходит для создания ролевых игр. Где, как правило, присутствует базовый тип земли, а все остальное, такое как вода, камни, травка представляется объектами. Второй способ легок по реализации, но очень утомительно будет потом создавать карты в таком редакторе.
Посмотрите на рисунок.

Рисунок 2

Если у Вас вся карта состоит из текстур с травой, а Вам надо добавить участок воды, то мы видим, что для того чтобы добиться плавного перетекания Вам придется добавить еще 8 промежуточных текстур окружающих текстуру с водой. Если делать это вручную( по второму способу ), то это займет слишком много времени и сил. Поэтому нам второй способ тоже не подходит. Мы остановимся на третьем способе и будем создавать карту подобно тому, как это происходит в WarCraft'e. При добавлении текстуры на карту( фактически - записи номера текстуры в определенную ячейку матрицы ), окружающие ее текстуры будут рассчитываться автоматически. Как этого добиться?

Я достаточно долго ломал голову над этой проблемой. Я пытался найти какой-нибудь способ позволяющий не утруждать компьютер громоздкими вычислениями и работать максимально быстро и эффективно. Один раз я даже вывел формулу, по которой рассчитывались новые значения ячеек, но она увы имела ограниченное действие( только 2 типа земли ) и плохо подходила для создания карт, где требуется максимальное разнообразие. Но достаточно лирики, давайте вернемся к нашим баранам.

Прежде всего необходимо выяснить - какое количество переходных текстур нам понадобится для обеспечения плавного перетекания между двумя типами земель. Здесь есть свои тонкости.

Представим, что у нас имеется два типа земли: ВОДА и ЗЕМЛЯ, тогда: Во-первых нам понадобятся две базовых текстуры , это текстуры полностью заполненные водой или землей.

Рисунок 3

Во вторых нам понадобятся промежуточные текстуры. Сколько их нужно мы сейчас посчитаем.

Рисунок 4

Оказалось, что для плавного перетекания двух земель друг в друга надо 14 промежуточных текстур, плюс две базовых. Итого 16. Всякий программист знает, что это хорошая цифра.

Возможно кто-то спросит: А зачем так много? Не достаточно ли 8 текстур, как на рисунке 2 - где трава пересекается с водой? Нет не достаточно. Ведь ситуации бывают разные. Окружающие ячейки могут быть не полностью забиты травой ( в данном случае землей ), и тогда понадобятся дополнительные текстуры.

Тогда может последовать другой вопрос: Почему так мало текстур? Где например текстуры когда вода с трех сторон окружена землей, и с четырех, и другие? Не следует ли предусмотреть все случаи?

И это правильный вопрос, но здесь все зависит от конкретной реализации алгоритма автоматического вычисления необходимой текстуры. В моем примере он реализован так, что остальные текстуры не нужны. Объясню наглядно:

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

Рисунок 5

2. Текстуры воды окруженные с двух уголков на одной стороне превращаются в текстуры полностью окруженные землей с одной стороны.( если уголки с трех сторон, то вода оказывается окружена полностью с двух сторон, если уголков 4, то вода превращается в землю совсем).

Теперь, я надеюсь, все ясно. С помощью применения подобной техники количество промежуточных текстур удалось уменьшить ровно в два раза! Это существенная экономия памяти, особенно если учесть, что типов земель будет больше. Кстати в WarCraft'e, если я не ошибаюсь, используется такой же набор текстур.

Ну хорошо, теперь давайте еще посчитаем. Для "слияния" двух земель нам понадобилось 16 текстур. Но если к земле и воде добавить еще траву, то придется создавать также переходные текстуры для трава-земля и трава-вода. Это еще 32 текстуры. Добавим еще каменистую почву( надо же сделать карту разнообразнее). Еще 48 текстур. И так далее и так далее. А если мы хотим сделать несколько видов одной и той же текстуры( опять таки для разнообразия )? Количество текстур растет как на дрожжах. Что делать?

Но тут на помощь пришел опять-таки старый, добрый, затертый до дыр мышкой WarCraft. Никогда не замечали, что если в WarCraft'e, вернее в War Editor'e, "кладешь" воду на траву, то между травой и водой появляется прослойка земли? Вот и я заметил.

Рисунок 6а Рисунок 6б

Посмотрите на эти два рисунка. Из них видно, что вода граничит только с землей, трава тоже граничит только с землей. Земля в данном случае является "переходным" типом земли. Достаточно создать текстуры вода-земля, трава-земля, камни-земля, песок-земля и т. д. По 16 штук на каждую землю и все. Можно больше не беспокоится. Земли будут соединяться между собой через "переходный" тип земли. Спасибо WarCraft'у.

Итак, с количеством текстур и тем какими они должны быть мы разобрались, и вот наконец-то мы приступаем к самой реализации данной задачи.

Условимся, что:

1. Ячейку с номером 12 я буду называть активной или текущей.
2. Землю которой мы рисуем я также буду называть активной или текущей.
3. Землю которая была прежде была в ячейке 12 я буду называть прежней.
4. Ячейки под номерами 6, 7, 8, 11, 13, 16, 17, 18 я буду называть первым кругом.
5. Ячейки под номером 0, 1, 2, 3, 4, 5, 9, 10, 14, 15, 19, 20, 21, 22, 23, 24 я буду называть вторым кругом.
6. Все текстуры имеющие в себе участок некоторого типа кроме переходного есть эта земля. То есть, к примеру, ячейки в первом круге - это вода.(см. Рисунок 6б)

Пусть для данного примера у нас будет три типа земли: ВОДА, ТРАВА, КАМНИ. Плюс переходный тип - ЗЕМЛЯ. Нам понадобится 48 текстур. Почему 48, а не 64? - спросите вы, - ведь типов-то 4. Потому, что переходный тип и так есть в каждом из трех первых типов, в промежуточных текстурах.

Допустим, что текстуры у Вас будут храниться в компоненте ImageList, для нашего случая это удобнее всего. Разместим мы их следующим образом: за номером 0 будет располагаться цельная текстура воды, номера 1 - 14 займут промежуточные текстуры ВОДА-ЗЕМЛЯ (как на Рисунке 4), номер 15 займет цельная текстура ЗЕМЛИ. Следующий элемент ТРАВА займет номера 16 - 31 по тому же принципу, элемент КАМНИ займет номера с 32 - 47. Как Вы наверное заметили, номера 15, 31, 47 оказываются заняты одинаковыми цельными текстурами земли. Их можно сделать немного отличающимися друг от друга для обеспечения большего разнообразия, а затем выбирать случайным образом.

Введем базовые индексы типов земель. Пусть базовый индекс воды равен 0, базовый индекс травы равен 1, камней - 2. Тогда, узнав порядковый номер текстуры, мы можем выяснить какому типу земли она принадлежит, достаточно разделить целочисленным делением (Div) порядковый номер текстуры на 16. Если же мы разделим этот номер делением по остатку (Mod) на 16, то узнаем смещение или номер промежуточной текстуры внутри интервала номеров принадлежащего данному типу земли. Например, мы обратились к ячейке и получили номер 23. Поделив этот номер целочисленным делением на 16 получим 1. Это тип земли - ТРАВА. Поделив делением по модулю остатка на 16 получим 7. Это номер промежуточной текстуры.(См. Рисунок 4, только в данном случае была бы трава с землей) Заметьте, если бы вместо 7 мы получили 0, это означало бы цельную текстуру данной земли, 15 означало бы цельную текстуру переходного типа - ЗЕМЛЯ.