Задача на генерацию спрайтов для формирования ландшафтного набора тайлов (tileset).
Дано некоторое количество базовых спрайтов, которые распределены по нескольким слоям. Для генерации одного тайла нам нужно взять по одному любому спрайту из каждого слоя и последовательно наложить их друг на друга.
Например:
1 слой: Море/Берег/Суша
2 слой: Скалы
3 слой: Вершина/плоскогорье
4 слой: Трава
5 слой: Декоративные элементы
Количество спрайтов в каждом слое произвольно, но может быть только в пределах [1..16]
Кол-во слоёв также произвольно, но в пределах [1..6]
Нужно получить 16 или меньше (если больше сгенерировать невозможно) уникальных тайлов, состоящих, из как можно более разнообразных комбинаций исходных спрайтов - т.е. чем меньше они или их комбинации будут повторяться для разный тайлов, тем лучше.
Пример:
spoiler
для
{{0, 1, 2}, - слой 1
{0, 1, 2}, - слой 2
{0, 1, 2}} - слой 3
Результат будет примерно таким:
0 0 0
1 1 1
2 2 2
0 1 2
1 2 0
2 0 1
0 2 1
1 0 2
2 1 0
0 0 1
1 1 2
2 2 0
0 1 0
1 2 1
2 0 2
0 0 2
Мне представляется 2 хода решения этой задачи:
1. Каждый слой, по сути, представляет собой одномерное множество. Для получения всех возможных комбинаций нам достаточно выполнить прямое(декартово) произведение этих множеств. И отсортировать получившиеся в результате множества по "разнообразию".
Но в этом случае есть 2 сложности:
- Комбинаций может быть довольно много (нам же надо только 16 из них).
- Сравнивать не только сами множества между собой но ещё и с уже отобранными, на предмет частоты повторения входящих в них комбинаций.
2. Сразу генерировать максимально разнообразные комбинации.
Вынужден признать, что я застрял на обоих вариантах - в первом на алгоритме сортировки, во втором на алгоритме генерации. Прошу помощи или подсказки.
Средний
Средний
