Да, теперь понятно. Ни один из рукавов, по-отдельности, не запрещает появление прямого участка. А на самом деле он может соединить эти рукава "встречь".
Ну и точно так же возможно соединение встречь двух рек.
Так что, без указания направления течения не обойтись. Но это увеличит число тайлов с реками. Так вместо одного тайла с Т-образным слиянием/разделением рек (4 тайла с учетом поворотов) появятся 4 тайла с разными направлениями течения. А с учетом поворотов и отражений - 24.
На карте с расположенными объектами строится сеть Штейнера. Вернее, её подобие. Потому что настоящая сеть Штейнера строится на непрерывной поверхности с Евклидовой метрикой, а нам придется работать на дискретной гексагональной метрике. Да еще в условиях переменной стоимости прокладки дорог.
Первое обстоятельство, само по себе, не сильно усложняет проблему нахождения перекрёстков. Просто найти тайл, включающий точку Торричелли (если такая есть) и уточнить его симплекс-методом.
Но вот второе обстоятельство, в условиях сложного ландшафта, делает эту задачу нетривиальной:
Найденный тайл может содержать реку. Построить Т-образный мост на картинке можно, но на практике это лишено всякого смысла.
Найденный тайл может находиться в заливе или озере. Тогда никакой симплекс-метод не улучшит суммарную стоимость прокладки дорог. Да и где виданы дорожные развязки над водой?
Найденный тайл может находиться в окружении такого сложного ландшафта, что симплекс-метод, в лучшем случае, поможет слегка улучшить стоимость прокладки дорог (локальный минимум), но не найдет наилучшего способа (глобальный минимум).
Навскидку, пример для последнего случая:
Точка Торричелли находится в лесу внутри подковообразного хребта. Симплекс-метод определяет, что выбор тайла у основания подковы позволит укоротить два пути по лесу за счет удлинения одного пути по лесу. Но оптимальный способ прокладки дорог может заключаться в огибании хребта с внешней стороны подковы. Потому что там нет лесов вообще - одни равнины. Да и через горы прорубаться не надо. Пути получатся длиннее, но дешевле.
Можно было бы просто для всех тайлов внутри треугольника городов рассчитать суммарную стоимость дорог до этих трёх городов. Но дело в том, что ландшафт может быть таким сложным, что перекрёсток выгоднее расположить вообще за пределами треугольника городов. А это значит, что на него окажут влияние другие дороги и перекрёстки.
Но это еще не учитывает, что стоимость самих дорог может зависить не только от ландшафта, но и от качества. Например, к руинам дороги можно не прокладывать специально. Либо протоптать тропинку, стоимость которой околонулевая, а скорость передвижения - низкая (но выше, чем по бездорожью).
Если начинать генерацию реки с истока (якорный тайл), то закольцовки не будет. Собственно, направление, даже если его явно не задавать, уже будет реализовано при этом.
Разделяться на рукава река может. Только, ненадолго. Вот это уже сложнее реализовать. И в устье реки, обычно, разбиваются на множество рукавов.
А еще есть старицы - тупиковые застойные участки на месте бывшего русла.
Для реки это может быть исток или затока. Или залив моря.
У дороги это может быть участок, непосредственно примыкающий к поселению или каким-либо руинам. Не рисовать же на самих тайлах построек различные способы подведения дорог. Тем более, что деревья и постройки не помещаются тайлами, а помещаются поверх них следующим слоем. Т.е. на этом огрызке дороги может сверху располагаться куча щебня, бывшая храмом местного божка.
Города, руины, дороги, сложные ландшафты. Влияние ландшафта на характеристики юнитов.
И очень похожие на сгенерированные WFC карты. Хотя, быть такого не может. Игрушка старая - ей более 30 лет. А WFC получил распространение несколько лет назад.
Вероятность на то и вероятность, что вероятно всё, даже самое невероятное :)
Как используя процедурную тайловую генерацию объединить три города дорогами по схеме "звезда"?
Тут, скорее, надо с другой стороны танцевать:
Сначала сгенерить крупнокалиберную географию - моря, реки, хребты, отроги.
Затем сгенерить карты высот на основе удаления от гор-морей (и учитывать, что реки должны течь с уменьшением высоты или по равнине). Зашумить карты высот хоть Перлином, хоть еще как. Лишь бы рядом с реками не находились более низкие участки.
Потом сгенерить ландшафты и биомы на свободных клетках с учетом высот и удалений от гор/рек/морей. Т.е. это та же самая тайловая генерация, но высота будет играть роль регулятора вероятности.
Потом поставить города недалеко от рек и морей. Шахты у гор и в болотах, капища в лесах и холмах, руины везде.
Соединить города дорогами. Но не напрямую, в через систему перекрестков между ними (почти по Торричелли - выбирается некая точка между тремя городами и соединяется с городами, потом ищется вариант подешевле). Стоимость дорог учитывает ландшафт (на равнине дёшево, в лесах, холмах и болотах дорого, в горах крайне дорого). Это делается уже не тайловой генерацией, а поверх готового поля. Самые дорогие дороги можно исключить, но так, чтобы на нарушить связности.
Тема генерации тайловых карт не раскрыта в плане приближения к реальным ландшафтам:
Как обеспечить, что горы не будут группироваться в сплошные массивы, а будут образовывать хребты и отроги?
Как обеспечить, что реки будут стекать с гор и возвышенностей (водоразделов), а не пересекать их?
Как обеспечить, что реки будут сливаться, а не разделяться? Но возможно образование рукавов и стариц.
Как обеспечить, что реки будут впадать в моря (можно и в озера, но при этом должны и вытекать из них), а не прерываться или заканчиваться в чистом поле?
Как обеспечить, что дороги будут соединять города/посёлки/святилища/шахты и т.д., а не обрываться и не закольцовываться?
Как обеспечить более-менее оптимальную схему дорог с учетом проходимости ландшафта?
Он должен поддерживаться на всех коммутаторах сети.
Он должен быть настроен (по умолчанию, обычно, DHSP-трафик разрешен на всех портах).
И если второй пункт - не проблема, то с первым не всё так просто, если в сети хотя бы пара десятков коммутаторов разных производителей и разной давности.
Всё равно не находит. Надо вспомнить, как работает репликация DHCP. Похоже, резервный сервер никак себя не проявляет, пока работает основной. Только синхронизируется с основным.
При генерации пещерных лабиринтов используют схожую идею:
Поле разбивается на прямоугольники иррегулярным способом. При этом существуют ограничения, которые не позволяют прямоугольникам иметь слишком разный размер и слишком разное соотношение сторон.
В некоторых общих участках делаются проходы (собственно, генерация лабиринта, только не на регулярном поле, а на иррегулярном.).
В получившиеся прямоугольники вписываются комнаты тоже случайного размера и положения.
Эти комнаты соединяются между собой через проходы коридорами.
Форма пещер модифицируется - углы сглаживаются, коридоры расширяются, стены делаются неровными. Только надо следить, чтобы при этом комнаты и коридоры не налезли друг на друга.
В классическом прямоугольном лабиринте каждая клетка может быть связана рёбрами с четырьмя окружающими. В плетёном лабиринте - с восемью (по 2 с каждой стороны) или даже с двенадцатью-шестнадцатью.
Так что, тут никаких особых заморочек нет. Но, как я уже ранее писал, при таком подходе возможны моменты, снижающие наглядность алгоритма:
Допустим по горизонтали есть подряд 4 клетки A, B, C и D. A соединена с C, а B с D. Таким образом, между B и C есть участок, полностью скрытый под другим участком. Его не будет видно, что скажется на визуальном восприятии лабиринта.
Если тупик будет заканчиваться над перпендикулярным коридором, то будет казаться, что он его разрывает. А если завести тупик под мост, то тоже будет выглядеть неаккуратно.
Можно немного модифицировать алгоритм. Например, ограничить длину моста/туннеля одним пролетом. Не включать в список кандидатов на присоединение те клетки, путь к которым ведет над поворотами/разветвлениями/тупиками (если не модифицированный, а упрощенный алгоритм Прима, то не включать рёбра, проходящие над такими клетками). Но не совсем ясно, не приведет ли это к образованию недостижимых зон.
Как я понял, WFC может использоваться для генерации тайловых карт (в т.ч. и лабиринтов с переплетениями), но при этом не гарантирует построение идеального лабиринта.
Искал на просторах Инета. По-буржуйски такие лабиринты называются "Layered Pipe Maze" (Лабиринт из слоёв труб), но толкового описания алгоритма генерации не нашел. Вернее, пока что не нашел вообще никакого.
Вот, лежу придумываю свой. В принципе, можно использовать даже алгоритм Прима, если в кандидаты на присоединение к новой комнате брать не только граничащие с присоединяемой клеткой пока не обработанные клетки, но и более дальние кандидаты (первый еще не присоединенный кандидат в нужном направлении). Но есть ограничения:
На разных уровнях должны находится только пересечения, а не коридоры, идущие в одном направлении.
Тупики не должны находится под/над другим коридором.
Иначе лабиринт станет не наглядным и трудным для восприятия.
Да, теперь понятно. Ни один из рукавов, по-отдельности, не запрещает появление прямого участка. А на самом деле он может соединить эти рукава "встречь".
Ну и точно так же возможно соединение встречь двух рек.
Так что, без указания направления течения не обойтись. Но это увеличит число тайлов с реками. Так вместо одного тайла с Т-образным слиянием/разделением рек (4 тайла с учетом поворотов) появятся 4 тайла с разными направлениями течения. А с учетом поворотов и отражений - 24.
Я тут немного освежил память по поводу п.5:
На карте с расположенными объектами строится сеть Штейнера. Вернее, её подобие. Потому что настоящая сеть Штейнера строится на непрерывной поверхности с Евклидовой метрикой, а нам придется работать на дискретной гексагональной метрике. Да еще в условиях переменной стоимости прокладки дорог.
Первое обстоятельство, само по себе, не сильно усложняет проблему нахождения перекрёстков. Просто найти тайл, включающий точку Торричелли (если такая есть) и уточнить его симплекс-методом.
Но вот второе обстоятельство, в условиях сложного ландшафта, делает эту задачу нетривиальной:
Найденный тайл может содержать реку. Построить Т-образный мост на картинке можно, но на практике это лишено всякого смысла.
Найденный тайл может находиться в заливе или озере. Тогда никакой симплекс-метод не улучшит суммарную стоимость прокладки дорог. Да и где виданы дорожные развязки над водой?
Найденный тайл может находиться в окружении такого сложного ландшафта, что симплекс-метод, в лучшем случае, поможет слегка улучшить стоимость прокладки дорог (локальный минимум), но не найдет наилучшего способа (глобальный минимум).
Навскидку, пример для последнего случая:
Точка Торричелли находится в лесу внутри подковообразного хребта. Симплекс-метод определяет, что выбор тайла у основания подковы позволит укоротить два пути по лесу за счет удлинения одного пути по лесу. Но оптимальный способ прокладки дорог может заключаться в огибании хребта с внешней стороны подковы. Потому что там нет лесов вообще - одни равнины. Да и через горы прорубаться не надо. Пути получатся длиннее, но дешевле.
Можно было бы просто для всех тайлов внутри треугольника городов рассчитать суммарную стоимость дорог до этих трёх городов. Но дело в том, что ландшафт может быть таким сложным, что перекрёсток выгоднее расположить вообще за пределами треугольника городов. А это значит, что на него окажут влияние другие дороги и перекрёстки.
Но это еще не учитывает, что стоимость самих дорог может зависить не только от ландшафта, но и от качества. Например, к руинам дороги можно не прокладывать специально. Либо протоптать тропинку, стоимость которой околонулевая, а скорость передвижения - низкая (но выше, чем по бездорожью).
Если начинать генерацию реки с истока (якорный тайл), то закольцовки не будет. Собственно, направление, даже если его явно не задавать, уже будет реализовано при этом.
Разделяться на рукава река может. Только, ненадолго. Вот это уже сложнее реализовать. И в устье реки, обычно, разбиваются на множество рукавов.
А еще есть старицы - тупиковые застойные участки на месте бывшего русла.
Да, направление - первое, что приходит на ум. Но вряд ли его одного будет достаточно.
Ну так это тайлы из предлагаемой реализации.
Для реки это может быть исток или затока. Или залив моря.
У дороги это может быть участок, непосредственно примыкающий к поселению или каким-либо руинам. Не рисовать же на самих тайлах построек различные способы подведения дорог. Тем более, что деревья и постройки не помещаются тайлами, а помещаются поверх них следующим слоем. Т.е. на этом огрызке дороги может сверху располагаться куча щебня, бывшая храмом местного божка.
Эх ... Даже в WarLords-2 захотелось поиграть :)
Города, руины, дороги, сложные ландшафты. Влияние ландшафта на характеристики юнитов.
И очень похожие на сгенерированные WFC карты. Хотя, быть такого не может. Игрушка старая - ей более 30 лет. А WFC получил распространение несколько лет назад.
Аналогичный случай. Кубик крутится, шарик вертится. А демка не открывается.
Еще как!
https://i.pinimg.com/originals/4c/14/ae/4c14aed15ad731fe5549063cabe3b6a0.jpg
Поясните, пожалуйста.
Вероятность на то и вероятность, что вероятно всё, даже самое невероятное :)
Как используя процедурную тайловую генерацию объединить три города дорогами по схеме "звезда"?
Тут, скорее, надо с другой стороны танцевать:
Сначала сгенерить крупнокалиберную географию - моря, реки, хребты, отроги.
Затем сгенерить карты высот на основе удаления от гор-морей (и учитывать, что реки должны течь с уменьшением высоты или по равнине). Зашумить карты высот хоть Перлином, хоть еще как. Лишь бы рядом с реками не находились более низкие участки.
Потом сгенерить ландшафты и биомы на свободных клетках с учетом высот и удалений от гор/рек/морей. Т.е. это та же самая тайловая генерация, но высота будет играть роль регулятора вероятности.
Потом поставить города недалеко от рек и морей. Шахты у гор и в болотах, капища в лесах и холмах, руины везде.
Соединить города дорогами. Но не напрямую, в через систему перекрестков между ними (почти по Торричелли - выбирается некая точка между тремя городами и соединяется с городами, потом ищется вариант подешевле). Стоимость дорог учитывает ландшафт (на равнине дёшево, в лесах, холмах и болотах дорого, в горах крайне дорого). Это делается уже не тайловой генерацией, а поверх готового поля. Самые дорогие дороги можно исключить, но так, чтобы на нарушить связности.
Вот как-то так.
У меня тоже ссылка не работает. Пишет, что устройство или браузер не соответствует требованиям.
Пробовал на разных браузерах. Но на работе у меня Win8.1ю Дома попробую на Win10.
Если у кого получилось зайти в демку - напишите, что требуется.
Я уже писал выше, что река не может "заканчиваться" иначе, чем впадением в море.
Так же как и дороги не могут прерываться, кроме как на объектах, которые они соединяют.
Петли дорог и рек на равнинах - тоже могут возникнуть в некоторых случаях.
Тема генерации тайловых карт не раскрыта в плане приближения к реальным ландшафтам:
Как обеспечить, что горы не будут группироваться в сплошные массивы, а будут образовывать хребты и отроги?
Как обеспечить, что реки будут стекать с гор и возвышенностей (водоразделов), а не пересекать их?
Как обеспечить, что реки будут сливаться, а не разделяться? Но возможно образование рукавов и стариц.
Как обеспечить, что реки будут впадать в моря (можно и в озера, но при этом должны и вытекать из них), а не прерываться или заканчиваться в чистом поле?
Как обеспечить, что дороги будут соединять города/посёлки/святилища/шахты и т.д., а не обрываться и не закольцовываться?
Как обеспечить более-менее оптимальную схему дорог с учетом проходимости ландшафта?
И т.д.
Для DHCP-snooping необходимо две маленькие вещи:
Он должен поддерживаться на всех коммутаторах сети.
Он должен быть настроен (по умолчанию, обычно, DHSP-трафик разрешен на всех портах).
И если второй пункт - не проблема, то с первым не всё так просто, если в сети хотя бы пара десятков коммутаторов разных производителей и разной давности.
Всё равно не находит. Надо вспомнить, как работает репликация DHCP. Похоже, резервный сервер никак себя не проявляет, пока работает основной. Только синхронизируется с основным.
Полезная утилита - сам пару раз случайно включал "левый DHCP". Потом удивлялся, почему сыплются сообщения о дублировании IP.
Скачал, запустил. Сообщило, что найден 1 DHCP-сервер. Но у нас их 2 с настроенной репликацией.
Буду разбираться. То ли второй не обнаруживается, потому что он резервный, то ли одно из двух ...
"Дикие ягодицы" - сегодня в каждом порнокинотеатре страны!
Байка ...
Еще в 80-е годы мы шутили, что, якобы, есть в округе какая-то забегаловка под названием "Голубая вода". Или на английском - "Blue Water".
При генерации пещерных лабиринтов используют схожую идею:
Поле разбивается на прямоугольники иррегулярным способом. При этом существуют ограничения, которые не позволяют прямоугольникам иметь слишком разный размер и слишком разное соотношение сторон.
В некоторых общих участках делаются проходы (собственно, генерация лабиринта, только не на регулярном поле, а на иррегулярном.).
В получившиеся прямоугольники вписываются комнаты тоже случайного размера и положения.
Эти комнаты соединяются между собой через проходы коридорами.
Форма пещер модифицируется - углы сглаживаются, коридоры расширяются, стены делаются неровными. Только надо следить, чтобы при этом комнаты и коридоры не налезли друг на друга.
По сути, меняются даже не рёбра, а их количество.
В классическом прямоугольном лабиринте каждая клетка может быть связана рёбрами с четырьмя окружающими. В плетёном лабиринте - с восемью (по 2 с каждой стороны) или даже с двенадцатью-шестнадцатью.
Так что, тут никаких особых заморочек нет. Но, как я уже ранее писал, при таком подходе возможны моменты, снижающие наглядность алгоритма:
Допустим по горизонтали есть подряд 4 клетки A, B, C и D. A соединена с C, а B с D. Таким образом, между B и C есть участок, полностью скрытый под другим участком. Его не будет видно, что скажется на визуальном восприятии лабиринта.
Если тупик будет заканчиваться над перпендикулярным коридором, то будет казаться, что он его разрывает. А если завести тупик под мост, то тоже будет выглядеть неаккуратно.
Можно немного модифицировать алгоритм. Например, ограничить длину моста/туннеля одним пролетом. Не включать в список кандидатов на присоединение те клетки, путь к которым ведет над поворотами/разветвлениями/тупиками (если не модифицированный, а упрощенный алгоритм Прима, то не включать рёбра, проходящие над такими клетками). Но не совсем ясно, не приведет ли это к образованию недостижимых зон.
Как я понял, WFC может использоваться для генерации тайловых карт (в т.ч. и лабиринтов с переплетениями), но при этом не гарантирует построение идеального лабиринта.
Искал на просторах Инета. По-буржуйски такие лабиринты называются "Layered Pipe Maze" (Лабиринт из слоёв труб), но толкового описания алгоритма генерации не нашел. Вернее, пока что не нашел вообще никакого.
Вот, лежу придумываю свой. В принципе, можно использовать даже алгоритм Прима, если в кандидаты на присоединение к новой комнате брать не только граничащие с присоединяемой клеткой пока не обработанные клетки, но и более дальние кандидаты (первый еще не присоединенный кандидат в нужном направлении). Но есть ограничения:
На разных уровнях должны находится только пересечения, а не коридоры, идущие в одном направлении.
Тупики не должны находится под/над другим коридором.
Иначе лабиринт станет не наглядным и трудным для восприятия.