Алгоритм поиска путей?

Question

[grindel]

Здравствуйте.

Есть такая игра


Цель — соединить, одинаковые цвета не оставив пустых клеток.


Мне стало интересно каким образом можно реализовать генерацию и решение таких уровней.

Я совершенное не имею понятия куда копать. Подскажите пожалуйста, что гуглить.

Answer 1

[moonsly]

Если планы уровней точно такие же по содержанию, как приведенная картинка (т.е. связные, не содержат диагональных поворотов и нет других скрытых условий), то алгоритм поиска пути:
1) тыкаем в случайную точку, ее цвет — желтый, добавляем ее к области Желтая1
2) ищем в окрестности точку желтого цвета, если найдены 1 или 2 новых точки (еще не записанных в Желтая) — цикл далее повторяем с ними, ищем следующие окрестные точки
3) прекращаем поиск Желтых, когда достигнуты оба конца Желтой области
4) тыкаем новую случайную точку, ее цвет Красный — повторяем с 1)
5) когда все клетки поля оказались в наборах Желтая1, Желтая2, Красная1 итд — стоп.
Также можно почитать про ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_A* и другие алгоритмы поиска пути
ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D1%83%D1%82%D0%B8

Генерация уровня — берем случайный цвет Синий, случайно определяем его первую точку, добавляем ее в Синий1, далее случайно определяем шаг — по горизонтали или вертикали, добавляем каждую новую Синюю точку в Синий1 + в использованные, на каждом шаге случайно решаем — завершить цвет Синий или перейти к Красному. Повторяем — пока все поле не будет в использованных. Получаем похожий уровень.

Comments

[grindel]

Спассибо за ответ!
Если я правильно вас понял, то к сожалению этот алгоритм не подходит, потому что кратчайший путь не всегда верный, например бывают такие уровни

Answer 2

[T-D-K]

Можно не выделять компоненты связности, а просто считать что переходов между ячейками разного цвета нету. В этом графе строить Гамильтонов цикл для каждой компоненты связности.
Ещё почитать можно здесь: e-maxx.ru/algo/

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

Answer 3

[SabMakc]

Поиск решения:
Для классических обходов в глубину / ширину нам надо представить данную задачу как "дойти из А в Б". Для этого предлагаю рассматривать следующее решение:
1. Пронумеруем цвета. Пусть будет 1- Синий, 2 - Желтый ... 5 - Зеленый.
2. Для каждого цвета выбираем "точку начала" и "точку финиша".
3. Теперь за точку А берем начало 1го цвета, за точку Б берем финиш последнего.
4. Условимся, что из клетки можно сделать ход по следующим правилам:
* Из точки начала делается ход только в пустые точки или в точку финиша этого же цвета.
* Из обычной точки делается ход только в пустые точки или в точку финиша этого же цвета.
* Из Финиша мы "телепортируемся" в точку начала следующего цвета. При телепорте текущий цвет меняется.
* Если мы достигли точки Б (и обошли все точки поля), то обход закончен, решение найдено.
5. На каждом шаге красим точку текущим цветом.
6. Обходим получившийся граф в глубину или ширину классическими методами (я бы сделал рекурсивный обход в глубину).

Генерация карты:
Вариант 1 - ставим точки случайным образом и ищем решение. Нашли решение? Вот и новая карта.
Вариант 2 - обходим все поле 1 линией со случайными поворотами. В точке начала - начало 1го цвета. В точке конца - финиш последнего цвета. Выбираем 4 места (чтобы получить 5 отрезков) на данной линии (с расстоянием между ними не менее 2х клеток), ставим по 2 маркера в выбранных местах: конец предыдущего цвета (по обходу) и начало следующего.

Что гуглить: теорию графов, алгоритмы поиска пути.

P.S. кто захочет поиграть - ключевые слова для поиска "Flow".