Как разделить карту на заданное количество областей?

#алгоритм #разработка_игр #генерация_случайных_данных

пишу игру Dice War, но застрял в самом начале - на генерации карты.

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

1 1 2 2 3 3 3 3 3 3
1 1 1 2 2 3 3 4 4 4
1 1 1 1 2 3 3 5 5 4
8 8 8 8 2 2 2 5 5 4
8 8 8 7 7 2 2 5 5 4
0 0 8 8 7 7 5 5 5 4
0 0 0 8 9 7 5 4 4 4
9 0 0 0 9 7 7 7 6 6
9 0 0 0 9 6 7 7 6 6
9 9 9 9 9 6 6 6 6 6

    

Ответы

Ответ 1

Можно сделать следующим образом. Сначала кидаем случайно центры областей с равномерным
распределением, потом все элементы связываем с ближайшими центрами областей. В прошлом
делал генератор текстур на этом алгоритме, получаются такие пазлы:



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

Update. Усреднять размеры областей можно разными времени написания и времени выполнения
способами:


Глобальный подход. Ищем пары ближайших областей с избытком и недостатком клеток,
переносим элементы между ними. Пример: 1 1 1 2 2 3 => 1 1 2 2 3 3.
Методы тыка. Все области с площадью больше средней отдают клетки другим областям
без переизбытка площади, а все со слишком малой площадью забирают клетки у областей
без недостатка. Затратно по времени, но если карты генерируются редко, то может подойти.
Эвристический подход. Любые идеи, средние по сложности и качеству между двумя предыдущими.
Например, те же случайные перемещения клеток, но только в те области, в которых перемещений
ещё не было.


Ответ 2

Построение одной области можно сделать так: 


занять случайную пустую клетку;
из соседних 4 клеток выбрать одну случайно, с учётом весов. Вес клетки расчитывается
как сумма числа занятых соседей или стен. Пустая клетка посреди поля имеет нулевой
вес. Клетка со всеми 4 соседями, или 3 соседями и у стены, или 2 соседями и в углу
имеет макс. вес 4. Напр. при наличие двух свободных клеток рядом, у одной вес 1, у
другой 4, берётся случайное от 0 до 1, и если оно попадает в диапазон 0 .. 0.2, то
выбирается первая клетка, если 0.2 .. 1 – вторая.
далее аналогично выбирается новая клетка, только из вариантов всей «колонии», а не
только одной последней клетки. Алгоритм тот же.


Демо – построение одной области:



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

Upd. Оказалось, просто бросать случайные точки и растить область от каждой – не очень
эффективно. Даже если начинать с чертырёх углов, чаще всего остаются «дыры». Стало
лучше, когда при наличие среди вариантов глухой дыры с весом 4 (клетка уже закрыта
со всех сторон), однозначно выбирается она, без случайностей. Даже иногда получаются
100% варианты заполнения:



Гарантии от мёртвых зон, отрезанных у стены, нет – есть только вероятностный механизм.
Надо внести коррективы. Случайно отбирать только в начале построения области, а чем
ближе к концу, тем «строже» следовать макс. весу в ущерб случайности.

Либо добавлять клетки в каждую из областей по очереди. Всем по 1-й клетке, затем
всем по 2-й, и т.д. до N-й?.. Чувствую, задача сводится к моделированию поведения жидкостей : )

"use strict"; // пришлось добавить ради ссылки на jsFiddle


Ответ 3

Самое простое при маленьком поле нарисовать штук 100 карт или на сколько хватит терпения,
поворотами, отражениями получить еще кучу.  

При большом поле вариант генерации: реализовать разрезание фигуры по клеточкам на
две части в определенном соотношении по площади (1:1, 2:3, 1:2).


Выбираем рандомно точку на границе фигуры.
В каждой точке сетки мы можем двигаться в нескольких направлениях. Направлений может
быть от нуля до трех (ноль - разрез закончен).
Выбираем рандомно направление. 
3.1. Проверяем можем ли резать в данном направлении. Главное, чтобы дойдя до границы
получили нужную площадь.
3.2. Если поле большое, можно резать не по одной клетке, а больше, тоже рандомно.
3.3. Направление можно попытаться скорректировать, продлив разрез до границы и проверить
площадь полученных фигур. Направление, в котором отклонение от необходимой площади
минимально, можно выбирать с некоторым большим весом, тогда разрезы будут более ровными.
Если веса распределять по-другому могут быть довольно причудливые формы.
Разрезав фигуру до конца, получим две фигуры, для каждой из них, если надо повторяем
с п.1.


Сложно, но реализуемо...