[Алгоритм] генерация случайной квадратной 2D карты из N стран

Question

[KingOfNothing]

Не могу придумать алгоритм генерации случайной квадратной 2D карты из N стран таким образом, чтобы площадь каждой страны была одинаковой.

Допустим, есть карта 100 х 100 - двухмерный массив. Есть 10 стран - от 0 до 9. Когда-то ячейка на карте не занята, она равна -1. Нужно сделать так, чтобы территория была поделена между всеми странами равным образом. Территория должна быть цельной, то есть страна не может состоять из двух кусков не соединенных друг с другом. При каждой генерации результат должен быть немного разным (по внешнему виду, то есть форма стран каждый раз разная).

Я начал делать следующим образом:
1) для каждой страны выбрал точку в различных частях карты
2) потом для каждой страны, отталкиваясь от начальной точки, ищу соседние свободные точки и присоединяю их к территории страны.
3) и так пока все страны не наберут равную территорию

Проблема в том, что из-за случайности выбора точки и направления присоединения иногда получается что одна страна блокирует доступ другой стране к незанятым соседним точкам. И тогда всё - бесконечный цикл. Так как блокирующая страна набрала территорию, а блокируемая нет, но и точек она достичь не может.

Поэтому две просьбы:
1) если знаете название алгоритма решающего эту проблему, напишите пожалуйста.
2) если есть идеи как решить проблему, тоже напишите.

Comments

[wyfinger]

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

[KingOfNothing]

Да, страны должны соседствовать. Я боюсь, что даже если заполнять страны по одной и начать с центра, могут образоваться куски карты, которые невозможно будет соединить в одну страну.
Допустим, 4 х 4 и площадь страны должна быть 2.
XX1X
XX12
XXX2
XXXX

Тут страны 1 и 2 образовали пустое место в правом верхнем углу, и туда страну не получится поставить.

Answer 1

[Глеб]

Интересная задачка, если решать в лоб, то может быть требовательна к ресурсам.
Можно к вашему алгоритму добавить:

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

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

Самым оптимальным мне кажется предложение @wyfinger о выходе из центра карты к краям.
Потом можно предложить остальным совершить N число обменов с соседями, по каким-то правилам. Этот способ съест конечное рассчитываемое число ресурсов и при этом можно задавать какие-либо правила обмена (стремиться к центру или краю итд)

Comments

[KingOfNothing]

Видимо, нужно делать возможность перевыбора клетки, но я боюсь что может возникнуть ситуация, когда страны бесконечно перезабирают друг у друга одну и ту же клетку. Но я попробую этот способ, думаю, что можно легко ограничить кол-во обменов

Answer 2

[xanep]

1. Считаем какой должна быть площадь стран - размер_карты / количество_стран, или заданный заранее.
2. Выбираем случайную точку на карте из незанятых, присоединяем к ней случайным образом соседние, пока не будет нужный размер страны (посчитанный в 1.)
3. N раз повторяем пункт 2.

Comments

[KingOfNothing]

Это и есть мой алгоритм, и у него такая же проблема. Из-за случайности может так случиться, что последняя страна, например, не сможет занять нужную площадь

Answer 3

[ntkt]

Вспомните формулу Пика (площадь многоугольника на плоскости, чьи вершины лежат в узлах координатной сетки). Вот подборка задачек для разминки: zaba.ru/cgi-bin/tasks.cgi?tour=books.sms700.fpika&solution=1
Исходя из формулы Пика формулируем инвариант (площадь любых двух стран в любой момент времени равна). Любое преобразование границ должно сохранять инвариант. Начальное разбиение строим случайным образом, исходя из максимальной или минимальной возможной длины границ между странами.

Comments

[KingOfNothing]

Можно пожалуйста по-подробней, как предлагаете строить начальное разбиение?

[ntkt]

Например, рекурсивно.
Сначала остановимся на числе стран = 2^N. Была одна страна, будет две. Проверяем, можно ли ее разрезать на две равные части прямой линией. Режем. Так режем, пока не достигнем нужного числа стран. А потом каждую прямую линию, кроме рамки, режем пополам и рекурсивно "мутируем", проверяя инвариант стран по обе ее стороны.
Если число стран не степень двойки, то надо свести задачу к этому. Возьмем и разрежем прямыми линиями исходный прямоугольник на будущие блоки стран по 2^k стран в каждом блоке (исходя из площади). Потом каждый блок рекурсивно разрежем и мутируем границы.
Что еще можно принять во внимание:
все возможные (с точностью до симметрии) сочетания стран вокруг одного узла сетки:
00 10 00 12 12
00 00 11 00 34

[ntkt]

Идея задать инвариант тут только для того, чтобы на любом шаге был корректный результат.

А еще есть идея, как можно вырезать в прямоугольнике разные многоугольники нужной площади. Вспомним игру qix (en.wikipedia.org/wiki/Qix). Вылетаем "змейкой" по прямой, из любой точки рамки, а дальше на каждом шаге считаем максимально возможную площадь фигуры по правую сторону "головы", учитывая пройденный и оставшийся путь до рамки. Из формулы Пика у нашей змейки, получается, есть запас "топлива", и мы на каждом шаге можем найти точку невозврата, из которой мы сможем замкнуть контур только по прямой до ближайшей сетки.

[KingOfNothing]

Не совсем понял про "змейку". Если мы начинаем двигаться по прямой из случайной точки на рамке, может же случиться так, что фигура справа не будет достаточной площади?

С делением на блоки вроде понятно всё. А вот какие есть алгоритмы мутирования границ? Идея понятна. Но как это может выглядеть, пока не представляю. Изучал ли кто-то эту проблему? Может есть готовые эффективные алгоритмы?

[ntkt]

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