Отделяем свет от тьмы 2
Пути видимые и невидимые
Важные ответы
Мое желание пропустить предисловия в первой части породило множество вопросов. Сейчас попробую на них ответить.
А что это такое?
Это генератор карт. Он генерирует карты.
А зачем?
Ни за чем, просто мне нравится его писать.
Это вторая часть. А где первая?
То есть ты делаешь свою “Цивилизацию”?
Нет, это не игра. Это скорее исследовательский проект, так как в процессе узнаю много нового и неожиданного.
А на чем пишешь?
Я пишу на C++. Это мой первый проект на этом языке.
И что, все это ты сам?
Смотря что “все”. Я использую сторонние библиотеки для рисования, генерирования диаграммы Вороного, шума Перлина, поиска путей и для интерфейса. Остальное — да, сам.
Ну так больше ничего и не осталось!
Да, не так и много, но, вообще-то это около 3х тысяч строк в свободное время чуть более чем за месяц. Это софт, которые работает под линукс и винду и его не стыдно показать другим. Так что судите сами, но я доволен прогрессом.
Ну так покажи!
- Версия для винды
- Исходники
- Видео выше
Ладно, погнали.
Любому, кто хоть раз сталкивался с разработкой игр при словосочетании “нахождение пути” в голову приходит ответ: “А-звездочка”. Я не исключение, поэтому сейчас расскажу что это и зачем.
При взгляде на картинку выше сразу понятны основные сложности этой задачи:
- Нельзя просто переть напрямую
- Глупо ехать через горы, если можно близко обойти
- Зачем обходить города, если куда лучше идти через них
- По морю иногда нужно плыть, но для этого нужен порт
- Никто не будет прокладывать новую дорогу параллельно уже существующей
- И прочее, менее очевидное
Попробуем взглянуть на эту задачу глазами первопроходца. Есть очевидные установки:
- Идем в направлении места назначения
- Если перед нами что-то непроходимое — обходим
Если дороге много лет, то она “оптимизируется”. Начинает заходить в “точки интереса” и выбирает более “дешевые” пути. То есть, для выбора куда мы хотим идти, у нас есть два параметра: насколько мы стали ближе к цели и насколько “дорого” нам идти именно через эту точку. В простом случае и то и другое сводится только к расстоянию и проходимости. Только что вы прочли очень упрощенное описание алгоритма А*.
Это один из лучших и, вероятно, наиболее используемый из алгоритмов нахождения пути. Самому поиграться с ним можно, например, здесь. Естественно, есть множество его реализаций под множество языков. Однако, мне нужна была особая: такая, которая позволила бы написать свою эвристику для подсчета “цены” перемещения. Мне повезло, и таковая нашлась, что сэкономило мне порядочно времени.
Гермес, тот который Флэш
По сути, нам нужно определить только две функции: нахождение списка возможных перемещений и подсчет стоимости перемещения.
Непроходимы у нас только озера. Ну для простоты. Условно непроходима у нас вода, если мы на суше, но не в порту и суша, но не порт, если мы на море. Так у нас есть два “режима” перемещения: по суше и по воде. Очевидно, что и стоимость у них считается по-разному.
Дистанцию я, как и все, считаю между “центральными” точками регионов. То есть тех, по которым строилась диаграмма Вороного (см. первую часть статьи). Это и будет нашей базовой ценой. Если мы сейчас в море, то цена будет 80% от базовой, так как плыть легче чем ехать. Здесь и далее цифры взяты с потолка и эмпирически откорректированы на атмосферные флуктуации.
С движением по земле все чуточку хитрее. Для начала введем штраф на подъем в гору. Но, скинем немного, если там город. Это позволит не проходить мимо городов. Затем накинем штраф за пересечение границы (всегда лучше по своей территории идти, чем по чужой) и дадим маленькие бонусы за продвижение вдоль рек и уже существующих дорог. Поиграв с величинами этих поправок можно получить картинку, которая размещена выше.
Так как бонус за проход по существующим дорогам не очень большой (а также из-за небольшой магии, о которой ниже), случаются внезапные “отходы”, которые можно объяснить неотмеченными на карте поселениями, стоянками или колодцами. Также там есть и совсем не оптимальная дорога через снежную вершину к некой пещере. Но я решил, что а) дальнейший тюнинг алгоритма слабо улучшит картину б) так возникает ощущение, что мир на самом деле более живой и учитывает вещи, которых нет на карте. Например факт того, что к этой пещере только один путь. В горах такое запросто.
Небольшое техническое отступление. Так как мне нужно найти пути из каждого города в каждый, обычно получается порядка трех-четырех тысяч дорог. Однако втупую решить эту проблему за приемлемое время не получится. Для начала отметим слово “уникальных”. Очевидно, что нет нужды пересчитывать дорогу в обратную сторону, если она уже найдена. Для этого мы, проходя по городам начинаем внутренний цикл каждый раз с позиции N+1, где N — индекс города, из которого строим пути. Казалось бы, очевидно, но когда напряженно думаешь в одном направлении, мозг с трудом находит простые решения.
Вторая трудность — время выполнения. Даже уникальные дороги если их делать по порядку занимают не менее пары минут. Но ведь эти расчеты почти не зависят друг от друга. Почти, так как на самом деле я учитываю, есть ли дорога в целевом регионе. Если две дороги считаются “одновременно” и проходят по одному региону, в котором еще нет дорог, то они не учитывают друг друга. Но если не считать этой “магии”, их можно создавать в разных потоках. Я сделал это очень плохо и знаю, что если переиспользовать потоки и “солверы”, которые считают дороги, будет еще быстрее, но и так я догнал время просчета дорог с “ну нафиг дожидаться” до “ладно, уже немного осталось”.
Гермес, тот который продал кифару Аполлону
Перед тем как перейти к рассказу про экономику, зацепим немного тему отрисовки дорог на карте. Ну и проблем, которые у меня с ними есть и пока не решены.
Так как я отрисовываю дороги сплайном (как и реки, см. первую часть), у каждой дороги есть возможность определять цвет, толщину и прозрачность (технически, это входит в состав цвета). Изначально дорога имеет белый цвет с достаточно высокой прозрачностью. Да, на картинке вы этого не увидете, так как в зависимости от того, проходит дорога по земле или воде, ее цвет “умножается” на коричневый или синий соответственно. Так мы получаем цвет.
Прозрачность на самом деле всегда остается одинаковой. Сейчас расскажу, почему на карте они совершенно непрозрачные. Я храню дороги целиком, от начала и до конца, даже если она на 99% совпадает с другими. Это очень удобно для расчетов, но, во-первых, рисует лишние пиксели, а во-вторых, я вынужден рисовать дороги целиком, а значит не могу спрятать морские пути, так как они являются частью сухопутной дороги. Но вернемся к прозрачности. Как я уже сказал, я много раз рисую дороги по одному и тому же месту, что означает, что если где-то проходит только один путь, то он остается полупрозрачным, а если много, то они накладываются и становятся сплошными.
Ширина же рисуемой дороги зависит именно от того, сколько дорог проходит по данному региону. Поэтому есть узенькие дороги побочные дороги и широкие “магистрали”.
Гермес, тот который купец
Раз в этой части мы говорим про влияние “человека” на карту, то, очевидно, основой этого влияния является экономика. Хотя дороги — тоже продукт стремления продать свою продукцию соседу, симуляцию мы начнем с уже основанными городами и установившейся сетью дорог. Однако, у меня есть желание сделать развитие начинающееся с нескольких поселений и разрастающееся до полноценного государства.
Конечно, следовало бы делать по уму — то есть составить какую-то модель, похожую на реальную, прогнать ее несколько тысяч раз, подогнать коэффициенты… Но я делал не так. Я просто постепенно вводил параметры, которые, как мне кажется, должны влиять на экономику. Так получилась некая модель, которая экспоненциально увеличивает население и линейно — богатство городов. Затем я подогнал цифры и количество итераций так, чтобы результат не вырастал до совсем огромных чисел и напоминал ситуацию в компьютерных играх, где проходят века, а технологии и население почти не меняется.
Сейчас результаты симуляции влияют только на то, какой город будет объявлен столицей. Но у меня в работе система градации городов по размеру и богатству, о которой я расскажу как-нибудь потом. А сейчас к экономической модели.
В общем виде все крайне просто: мы делаем 50 циклов-десятилетий, каждую итерацию делая “тик” экономики и “тик” роста населения.
Шаг экономического развития начинается с создания “общего рынка”. Это список товаров, которые все города готовы продать. Товары собраны в “пакеты”, которые имеют объем и цену, которая будет рассчитываться для каждого покупателя индивидуально. Пакеты производятся так:
- Если это земледельческий город, умножаем параметр “комфорта климата” (см первую часть) на коэффициент “овощей за лето” на население и на коэффициент “человек выращивает столько-то помидоров”
- Если это шахта, то похожий расчет, но на основании “богатства полезными ископаемыми”
- Портовые города ничего не производят. Что не мешает быть им самыми богатыми. Но об этом позже.
Затем мы перемешиваем города. Моя “модель” основывается на постоянном дефиците, то есть сумма потребности всех городов больше суммы производимых товаров. Можно было бы симулировать торговлю в реальном времени, чтобы возможность купить определялась не только наличием товара, но и тем, что его не купил кто-то раньше и тем, что он уже доехал и так далее. Но это сложно и все еще далеко от реальности. Поэтому я поступил проще: мы пробегаем по городам и покупаем покуда есть нужда. Затем переходим к следующему городу. Очевидно, что всем не хватит. Но кому именно решает рандом, который перемешивает города. Хотя, пока я это писал, мне подумалось, что стоит все-таки делать покупки в несколько заходов.
Итак, покупки. Потребность в каком-то из ресурсов все также определяется произведением населения на некий коэффициент “потребности в ресурсе”, который корректируется на производство этого ресурса в этом городе. Так очень богатым одним ресурсом городам может быть вовсе не нужно докупать его.
Потом доступные товары сортируются по цене. Как уже говорилось, цена для каждого покупателя отличается. Ценой является “стоимость” пути от продавца до покупателя. Эти стоимости мы считали на этапе прокладки дорог. И домножаем на полтора, если покупатель и продавец в разных странах. Конечно, тут можно ввести еще кучу факторов, но вряд ли они будут оказывать существенное влияние на результат симуляции.
Выбранные товары покупаются. То есть мы вычитаем у покупателя богатства равное цене, деленной на его население. Продавец получает точно так же. Но помимо этого, каждый портовый город на пути от продавца к покупателю получает свой процент от цены пакета. Я не стал вычитать эту “мзду” из прибыли продавца, отнеся это на счет эффекта мультипликации, то есть роста экономики за счет оборота денежных средств.
Когда город не может удовлетворить свою потребность, из его богатства вычитается некий штраф, также зависящий от населения и уровня оставшейся потребности в каждом ресурсе. UPD: сейчас я его отключил. Вероятно, я даже заменю его на обратный, который увеличивает богатство города в зависимости от доли удовлетворенной потребности.
Да, вряд ли эта “модель” хоть сколько-нибудь похожа на реальное положение вещей, но она н достаточно сложна, чтобы быть интересной и увеличивать нужные мне показатели. Хотя пока мы поговорили только о богатстве.
Население увеличивается на постоянный коэффициент, который корректируется на уровень богатства города. Сейчас, кажется, я подправил числа так, что богатство как и население всегда увеличивается, но это скорее ошибка, чем намерение.
Кстати, еще у меня есть планы на “фазу бедствий”, когда его величество рандом будет устраивать пожары, эпидемии, падения метеоритов и извержения вулканов. Ну и не забыть войны, которые будут влиять не только на население, но и границы, торговые отношения и потребление ресурсов.
Акела промахнулся. Или это из другой оперы?
Пока я готовился к записи видео для этой статьи я обнаружил досадный баг в экономической модели. Особенно досаден он тем, что его починка напрочь ломает весь баланс симуляции. Ошибка проста и в чем-то даже злободневна: города покупали ресурсы пока не удволетворят свою потребность в них. Вроде разумно, но ведь покупать = платить, а я совсем не учитывал это. В итоге получалось, что покупатели загоняли себя в банкротство, а продавцы все равно отгружали товар, вне зависимости от платежеспособности покупателя, ведь я все равно им платил (у меня-то инфляции нет, могу брать деньги из воздуха).
Естественно, введение “покупательской разумности” выявило ряд проблем: слишком высокие цены и слишком низкий экономический рост. Это приводило к тому, что города быстро банкротились и последующие итерации просто ничего не покупали. Я смог относительно быстро вернуть “какой-то” баланс, но мне явно нужно еще поработать над этим, вероятно, введя еще какие-то новые механики развития.
Аид, Гефест и все-все-все
Также в фазу симуляции генератор делает и другие вещи:
- В случайной точке горы создает “локации”-пещеры
- Удаляет портовые города, через которые не идет путей в другие поселения. Затем подчищает “висячие” дороги, оставшиеся от удаленных городов.
- Расставляет маяки. Для этого рядом с регионом должен проходить достаточно нагруженный морской путь. Так как маяк нужен только в опасном месте, например, мысе, я выбираю только те точки, где минимум три соседних региона имеют торговый путь. Так отбираются “выступающие” области.
- Прокладывает дороги до пещер и маяков
- На часто используемых дорогах, которые пересекают границу между государствами размещает город-”форт”. Пока это еще очень недоработанный алгоритм, но лучше пусть крепости будут, чем нет.
В следующих сериях
Еще осталась не охваченной огромная область, связанная с визуальной частью программы. Я сейчас планирую сильно переработать эту часть, поэтому постораюсь параллельно писать о нюансах.
Надеюсь, и это будет не последняя статья, так как у меня еще полно идей и незаконченных фич. Помимо этого я обдумываю возможности скомпилировать одну более техническую статью, чтобы опубликовать ее на Хабре, а затем перевести и выложить на Реддит. Но это уже из разряда наполеоновских планов. А пока прощаюсь с вами, спасибо, что прочли.
