Нарисуйте мне мир

Автор, как впрочем, и многие из вас, потратили немало времени на игру «Цивилизация». Одной из интересных особенностей этой игры является то, что карта мира на которой будет происходить действие игры строится каждый раз заново. При этом игрок в начале задает некоторые предпочтения к миру (больше лесов, равнин или гор и т.п.), а программа сама на основе этих предпочтений строит карту.

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

Автоматическое построение подобных карт имеет большое значение в различных типах стратегических(тактических) игр, как в пошаговых, так и в стратегиях реального времени.

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

Тема. Напишите программу, строящую уровни для игры типа «Цивилизация»(«Герои меча и магии», “WarCraft”, Command&Conquer” и т.п.). На вход должна поступать информация о возможных элементах, из которых может состоять уровень, средних статистических значениях, определяющих количество использованных элементов того или другого типа. Также на вход может подаваться информация о сложности уровня и дополнительных элементах, распределенных по карте (обратите внимание, как это реализовано в «Героях»).

Выходными данными является карта мира в виде матрицы тайлов с дополнительными элементами (это м.б. отдельные деревья, полезные ресурсы, ловушки и т.п.).

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

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

Еще одним возможным вариантом является затравочный – в середине карты выбирается некоторый элемент (возможно и не один), а дальше от него идет заполнение карты.

Инструментировка. Подойдет практически любой язык. Возможно предпочтение следует отдать языкам типа Python, Perl или Ruby, их гибкость и встроенные классы могут оказаться к месту.

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