Маджонг — расставьте плитки так, чтобы обеспечить хотя бы один путь к победе, независимо от раскладки.
https://stackoverflow.com/questions/159547
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Независимо от раскладки, используемой для плиток, есть ли хороший способ разделить плитки, чтобы гарантировать пользователю, что в начале игры существует хотя бы один путь к завершению головоломки и победе в игре? ?
Очевидно, что в зависимости от ходов пользователя он может лишить себя возможности выиграть.Я просто хочу иметь возможность всегда говорить пользователю, что головоломку можно выиграть, если он сыграет хорошо.
Если вы случайным образом разместите плитки в начале игры, возможно, что пользователь сможет сделать несколько ходов и не сможет сделать больше.Знание того, что головоломка, по крайней мере, разрешима, должно сделать игру более увлекательной.
Решение
Разместите все плитки наоборот (т. е. разложите доску, начиная с середины, работая).
Чтобы еще больше дразнить игрока, вы можете делать это заметно, но на очень высокой скорости.
Другие советы
Сыграйте в игру наоборот.
Случайным образом разложите кусочки попарно, в местах, где их можно было бы сдвинуть в кучу.Вам понадобится способ знать где вам разрешено размещать кусочки так, чтобы в итоге получилась куча, соответствующая некоторому заданному шаблону, но вам это все равно понадобится.
Я знаю, что это старый вопрос, но я столкнулся с этим, когда сам решал проблему.Ни один из ответов здесь не является совершенным, и некоторые из них содержат сложные предостережения или не работают на патологических схемах.Вот мое решение:
Решите доску (вперед, а не назад) с немаркированными плитками.Удалите две свободные плитки за раз.Поместите каждую удаленную пару в стопку «совпадающих пар».Часто это все, что вам нужно сделать.
Если вы зашли в тупик (numFreeTiles == 1), просто перезагрузите генератор :) Я обнаружил, что обычно не захожу в тупики, и до сих пор у меня максимальное количество повторов составляло 3 для примерно 10 макеты, которые я пробовал.Как только я наберу 8 повторов, я сдаюсь и просто случайным образом распределяю остальные плитки.Это позволяет мне использовать один и тот же генератор как для настройки доски, так и для функции перемешивания, даже если игрок облажался и сделал 100% неразрешимое состояние.
Другое решение, когда вы зашли в тупик, — отступить (вытащить стопку, заменив плитки на доске), пока не сможете выбрать другой путь.Выберите другой путь, убедившись, что вы сопоставляете пары, которые удалят исходную блокирующую плитку.
К сожалению, в зависимости от платы, это может зацикливаться навсегда.Если в конечном итоге вы удалите пару, которая напоминает дорогу без выхода, где все последующие «дороги» являются тупиком и имеется несколько тупиков, ваш алгоритм никогда не завершится.Я не знаю, возможно ли спроектировать такую плату, но если да, то решение все же есть.
Чтобы решить эту более серьезную проблему, рассматривайте каждое возможное состояние платы как узел в DAG, причем каждая выбранная пара является ребром на этом графе.Выполняйте случайный обход, пока не найдете листовой узел на глубине 72.Следите за историей своего перемещения, чтобы никогда не повторять спуск.
Поскольку в использованных мной макетах тупики встречаются реже, чем решения с первой попытки, то на ум сразу приходит гибридное решение.Сначала попробуйте решить ее с минимальным объемом памяти (сохраните выбранные пары в своем стеке).Как только вы зайдете в первый тупик, перейдите к полной маркировке/генерации ребер при посещении каждого узла (где это возможно, ленивая оценка).
Однако я очень мало изучал теорию графов, так что, возможно, есть лучшее решение проблемы случайного обхода/поиска DAG :)
Редактировать:На самом деле вы можете использовать любое из моих решений с генерацией платы в обратном порядке, например, сообщение от 13 октября 2008 года.У вас все еще есть те же предостережения, потому что вы все равно можете оказаться в тупике.Однако создание доски в обратном порядке имеет более сложные правила.Например, вы гарантированно потерпите неудачу в настройке, если не начнете хотя бы НЕКОТОРЫЕ строки с первой части посередине, например, в макете с 1 длинным рядом.Выбор совершенно случайного (законного) первого хода в генераторе прямого решения с большей вероятностью приведет к разрешимой доске.
Единственное, что мне удалось придумать, это сложить плитки одинаковыми парами, как своего рода обратный пасьянс Маджонг.Таким образом, в любой момент размещения плиток доска должна выглядеть так, как будто она находится в середине реальной игры (т. е. никакие плитки не плавают на 3 слоя выше других плиток).
Если в обратной игре плитки расположены совпадающими парами, это всегда должно приводить к появлению хотя бы одного прямого пути для решения игры.
Я хотел бы услышать другие идеи.
Я считаю, что лучший ответ уже был предложен:создание набора путем его решения «обратно» - т.е.начиная с пустой доски, затем добавляя где-нибудь пару, добавляя еще пару в решаемой позиции и так далее...
Если вы предпочитаете подход «Большого взрыва» (сначала генерирующий весь набор случайным образом), это очень мачо разработчика или просто чувствуете себя мазохистом сегодня, вы можете представить все пары, которые вы можете извлечь из данного набора, и то, как они зависят друг от друга, с помощью ориентированного графа.
После этого вам нужно будет только получить транзитивное замыкание этого набора и определить, существует ли хотя бы один путь хотя бы из одной из начальных допустимых пар, который ведет к желаемому концу (пар плиток не осталось).
Реализация этого решения оставлена читателю в качестве упражнения :D
Вот правила, которые я использовал в своей реализации.
При построении кучи для каждого лада в паре отдельно найдите ячейки (места), которыми являются:
- все ячейки на нижних уровнях уже заполнены
- место для второго лада не перекрывает первый, учитывая, что первый лад уже установлен
- оба места находятся «по краям» уже построенной кучи:
- ЛИБО имеет хотя бы одного соседа слева или справа.
- ИЛИ это первый лад подряд (все ячейки справа и слева рекурсивно свободны)
Эти правила не гарантируют, что сборка всегда будет успешной - иногда она оставляет последние 2 свободных ячеек, и на практике следует пересмотреть (или, по крайней мере, последние лады), «Черепаха», построенная не более чем на 6 повторных.
Большинство существующих игр, похоже, ограничивают размещение первых ладов («первых в ряду») где-то посередине.Это приводит к более удобным конфигурациям, когда по краям очень длинных рядов нет ладов, которые остаются до тех пор, пока не двинется последний игрок.Однако «середина» разная для разных конфигураций.
Удачи :)
P.S.Если вы нашли алгоритм, который строит разрешимую кучу за один ход, дайте мне знать.
В игре 144 плитки, каждая из 144 плиток имеет список блоков.(верхний тайл в стеке имеет пустой список блоков)
Для всех допустимых ходов необходимо, чтобы их «current__vertical_Block_list» был пустым.это может быть матрица размером 144x144, то есть 20 КБ памяти плюс список блоков ЛЕВЫЙ и ПРАВЫЙ, также по 20 КБ каждый.
Создайте действительную таблицу перемещений из (remaning_tiles) AND ((пустой ТЕКУЩИЙ ВЕРТИКАЛЬНЫЙ BLOCK LIST) и ((пустой CURRENT LEFT BLOCK LIST) OR (пустой CURRENT RIGHT BLOCK LIST)))
Выберите 2 случайные плитки из допустимой таблицы перемещения, запишите их обновите (текущие таблицы Vert, слева и справа), запишите плитки, удаленные в стек.
Теперь у нас есть список ходов, которые составляют действительную игру.Назначьте соответствующие типы плиток каждому из 72 ходов.
в сложных играх отслеживайте, когда становится доступной каждая плитка.найдите наборы, в которых есть (рано рано рано поздно) и (поздно поздно поздно рано), поскольку он пуст, вы найдете 1 блок EE, 1 LL и 2 блока LE.в блоке 2 LE найдите РАННИЙ, который блокирует ЛЮБОЙ другой РАННИЙ, который (кроме правого блока левой боковой части)
Как только вы получите действительную игру, поиграйте с заказом.
Пасьянс?Это всего лишь предположение, но я предполагаю, что вашему компьютеру нужно будет пройти игру (или близко к ней), чтобы это определить.
Другой вариант — иметь несколько предустановленных макетов (которые позволяют выиграть, смешанные с вашим текущим уровнем).
В некоторой степени вы можете попытаться убедиться, что одна из 4 плиток находится не более чем на X слоев ниже другой X.
В большинстве игр, которые я вижу, есть команда «Перемешать», когда кто-то застревает.
Я бы попробовал сочетание вещей и посмотрел, что работает лучше всего.
