Что нужно использовать для создания произвольно созданного игрового процесса с потоком?

Ответ 1

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

Первая часть, создающая простую предварительно разрешенную плату, тривиальна (если вы хотите, чтобы она была), если вы используете потоки n в сетке n x n:

• Для каждого потока...
  • Поместите головную точку в верхнюю часть первого открытого столбца.
  • Поместите хвостовую точку в нижней части этого столбца.

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

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

• Для некоторого количества итераций...
  • Выберите случайный поток f.
  • Если f находится на минимальной длине (скажем, 3 квадрата), перейдите к следующей итерации, потому что мы не можем сжимать f прямо сейчас.
  • Если головная точка f находится рядом с точкой из другого потока g (если выбрать более одного g, выберите один случайным образом)...
    • Переместите f голову на один квадрат вдоль его потока (т.е. проведите один квадрат к хвосту). f теперь на один квадрат короче и есть пустой квадрат. (Теперь головоломка не решена.)
    • Переместите соседнюю точку с g в пустой квадрат, освобожденный f. Теперь есть пустой квадрат, из которого g точка перемещается из.
    • Заполните это пустое место с потоком от g. Теперь g на один квадрат длиннее, чем в начале этой итерации. (Головоломка снова и снова решается.)
  • Повторите предыдущий шаг для f хвоста.

Подход в его нынешнем виде ограничен (точки всегда будут соседями), но его легко расширить:

• Добавьте шаг, чтобы перебрать поток потока f, ища более сложные способы обмена пространствами с другими потоками...
• Добавьте шаг, который предотвращает переход точки в старое местоположение...
• Добавьте любые другие идеи, которые вы придумали.

Общее решение здесь, вероятно, меньше идеального, к которому вы стремитесь, но теперь у вас есть два простых алгоритма, которые вы можете сформулировать дальше, чтобы служить роли одного большого, всеобъемлющего алгоритма. В конце концов, я думаю, что этот подход управляем, а не загадочен и легко поддается, и, если не что иное, хорошее место для начала.

Обновление: я закодировал концептуальную концепцию, основанную на вышеуказанных шагах. Начиная с первой сетки 5x5 ниже, процесс производил следующие 5 разных плат. Некоторые из них интересны, некоторые - нет, но они всегда действительны с одним известным решением.

Начальная точка

5 Случайные результаты (извините за несогласованные снимки экрана)

И случайный 8x8 для хорошей меры. Отправной точкой был такой же простой подход столбцов, как и выше.

Ответ 2

Самый простой способ создать такой уровень - найти способ его решения. Таким образом, вы можете в принципе генерировать любую случайную стартовую конфигурацию и определять, является ли она допустимым уровнем, пытаясь разрешить ее. Это создаст самые разные уровни.

И даже если вы найдете способ сгенерировать уровни каким-либо другим способом, вы все равно захотите применить этот алгоритм решения, чтобы доказать, что сгенерированный уровень хорош;)

Перечисление грубой силы

Если плата имеет размер NxN-ячеек и имеются также N цветов, грубая сила, перечисляющая все возможные конфигурации (независимо от того, будут ли они образовывать фактические пути между начальным и конечным узлами):

• Всего N ^ 2 ячеек
• 2N ячейки, уже занятые начальным и конечным узлами
• N ^ 2 - 2N ячейки, для которых цвет еще не определен
• Доступны N цветов.
• N ^ (N ^ 2 - 2N) возможных комбинаций.

Итак,

• При N = 5 это означает комбинации 5 ^ 15 = 30517578125.
• При N = 6 это означает 6 ^ 24 = 4738381338321616896 комбинаций.

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

Ограничение количества ячеек на цвет

Очевидно, что мы должны стараться максимально уменьшить количество конфигураций. Один из способов сделать это - рассмотреть минимальное расстояние ( "dMin" ) между каждой начальной и конечной ячейками цвета - мы знаем, что по крайней мере должно быть столько ячеек с этим цветом. Вычисление минимального расстояния может быть выполнено с помощью простой заливки или алгоритма Дейкстры. (N.B. Обратите внимание, что весь следующий раздел обсуждает только количество ячеек, но ничего не говорит об их местоположении)

В вашем примере это означает (не считая начальную и конечную ячейки)

dMin(orange) = 1
dMin(red) = 1
dMin(green) = 5
dMin(yellow) = 3
dMin(blue) = 5

Это означает, что из 15 клеток, для которых еще предстоит определить цвет, должны быть по крайней мере 1 оранжевый, 1 красный, 5 зеленых, 3 желтых и 5 синих клеток, а также в общей сложности 15 клеток, В этом конкретном примере это означает, что соединение каждой начальной и конечной ячейки цвета посредством (одного из) кратчайших путей заполняет всю доску, т.е. После заполнения доски самыми короткими путями никакие неизолированные ячейки остаются. (Это должно считаться "удачей", и не каждая начальная конфигурация платы приведет к тому, что это произойдет).

Обычно после этого шага у нас есть несколько ячеек, которые могут быть свободно окрашены, пусть назовем это число U. Для N = 5,

U = 15 - (dMin(orange) + dMin(red) + dMin(green) + dMin(yellow) + dMin(blue))

Поскольку эти ячейки могут принимать любой цвет, мы также можем определить максимальное количество ячеек, которые могут иметь определенный цвет:

dMax(orange) = dMin(orange) + U
dMax(red)    = dMin(red) + U
dMax(green)  = dMin(green) + U
dMax(yellow) = dMin(yellow) + U
dMax(blue)   = dMin(blue) + U

(В этом конкретном примере U = 0, поэтому минимальное количество ячеек на цвет также является максимальным).

Поиск путей с использованием ограничений расстояния

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

  15! / (1! * 1! * 5! * 3! * 5!)
= 1307674368000 / 86400
= 15135120 combinations left, about a factor 2000 less.

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

• не пересекает уже окрашенную ячейку
• Не короче dMin (цвет) и не длиннее dMax (цвет).

Второй критерий уменьшит количество путей, сообщаемых за цвет, что приводит к значительному уменьшению общего количества путей (из-за комбинаторного эффекта).

В псевдокоде:

function SolveLevel(initialBoard of size NxN)
{
    foreach(colour on initialBoard)
    {
        Find startCell(colour) and endCell(colour)
        minDistance(colour) = Length(ShortestPath(initialBoard, startCell(colour), endCell(colour)))
    }

    //Determine the number of uncoloured cells remaining after all shortest paths have been applied.
    U = N^(N^2 - 2N) - (Sum of all minDistances)

    firstColour = GetFirstColour(initialBoard)
    ExplorePathsForColour(
        initialBoard, 
        firstColour, 
        startCell(firstColour), 
        endCell(firstColour), 
        minDistance(firstColour), 
        U)
    }
}

function ExplorePathsForColour(board, colour, startCell, endCell, minDistance, nrOfUncolouredCells)
{
    maxDistance = minDistance + nrOfUncolouredCells
    paths = FindAllPaths(board, colour, startCell, endCell, minDistance, maxDistance)

    foreach(path in paths)
    {
        //Render all cells in 'path' on a copy of the board
        boardCopy = Copy(board)
        boardCopy = ApplyPath(boardCopy, path)

        uRemaining = nrOfUncolouredCells - (Length(path) - minDistance)

        //Recursively explore all paths for the next colour.
        nextColour = NextColour(board, colour)
        if(nextColour exists)
        {
            ExplorePathsForColour(
                boardCopy, 
                nextColour, 
                startCell(nextColour), 
                endCell(nextColour), 
                minDistance(nextColour), 
                uRemaining)
        }
        else
        {
            //No more colours remaining to draw
            if(uRemaining == 0)
            {
                //No more uncoloured cells remaining
                Report boardCopy as a result
            }
        }
    }
}

FindAllPaths

Это оставляет только FindAllPaths (плата, цвет, startCell, endCell, minDistance, maxDistance). Трудность здесь заключается в том, что мы не ищем кратчайшие пути, но для любых путей, которые попадают в диапазон, определяемый minDistance и maxDistance. Следовательно, мы не можем просто использовать Dijkstra или *, потому что они будут записывать только кратчайший путь к каждой ячейке, а не любые возможные обходные пути.

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

Затем поиск всех путей может быть выполнен с помощью заливки-заливки, такой как исследование, начиная с startCell наружу, где для данной ячейки каждая неокрашенная или ту же, что и текущая цветная соседка, рекурсивно исследуется (кроме те, которые формируют наш текущий путь к началу координат), пока мы не достигнем конца или не достигнем максимального сопротивления.

Улучшение этой стратегии заключается в том, что мы не исследуем с самого началаCell вне до концаCell, но что мы исследуем как из startCell, так и endCell наружу параллельно, используя Floor (maxDistance/2) и Ceil (maxDistance/2 ) как соответствующие максимальные расстояния. При больших значениях maxDistance это должно уменьшить количество исследованных ячеек от 2 * maxDistance ^ 2 до maxDistance ^ 2.

Ответ 3

Я выполнил следующий алгоритм в моем решателе и генераторе номерных ссылок. В принудительном порядке правило, что путь никогда не может коснуться самого себя, что является нормальным для большинства "хардкорных" приложений и головоломок номерной ссылки

• Сначала доска разбита на 2x1 домино простым, детерминированным способом. Если это невозможно (на бумаге нечетной области), нижний правый угол оставлен как одиночный.
• Затем домино случайным образом перетасовываются вращением случайных пар соседей. Это не делается в случае ширины или высоты, равной 1.
• Теперь, в случае бумаги с нечетной областью, нижний правый угол присоединен к один из его соседних домино. Это всегда будет возможно.
• Наконец, мы можем начать поиск случайных путей через домино, объединяя их как мы проходим. Особое внимание уделяется не связыванию "побочных потоков", который создавал бы головоломки, которые "удваивают обратно на себя".
• Перед тем, как головоломка будет напечатана, мы "максимально" максимально используем диапазон используемых цветов.
• Головоломка печатается путем замены всех позиций, которые не являются потоковыми головами с.

В моем формате номерной линии используются символы ascii вместо цифр. Вот пример:

$ bin/numberlink --generate=35x20
Warning: Including non-standard characters in puzzle

35 20
....bcd.......efg...i......i......j
.kka........l....hm.n....n.o.......
.b...q..q...l..r.....h.....t..uvvu.
....w.....d.e..xx....m.yy..t.......
..z.w.A....A....r.s....BB.....p....
.D.........E.F..F.G...H.........IC.
.z.D...JKL.......g....G..N.j.......
P...a....L.QQ.RR...N....s.....S.T..
U........K......V...............T..
WW...X.......Z0..M.................
1....X...23..Z0..........M....44...
5.......Y..Y....6.........C.......p
5...P...2..3..6..VH.......O.S..99.I
........E.!!......o...."....O..$$.%
.U..&&..J.\\.(.)......8...*.......+
..1.......,..-...(/:.."...;;.%+....
..c<<.==........)./..8>>.*[email protected]
.[..[....]........:..........?..^..
..._.._.f...,......-.`..`.7.^......
{{......].....|....|[email protected]

И здесь я запускаю его через своего решателя (одно и то же семя):

$ bin/numberlink --generate=35x20 | bin/numberlink --tubes
Found a solution!
┌──┐bcd───┐┌──efg┌─┐i──────i┌─────j
│kka│└───┐││l┌─┘│hm│n────n┌o│┌────┐
│b──┘q──q│││l│┌r└┐│└─h┌──┐│t││uvvu│
└──┐w┌───┘d└e││xx│└──m│yy││t││└──┘│
┌─z│w│A────A┌┘└─r│s───┘BB││┌┘└p┌─┐│
│D┐└┐│┌────E│F──F│G──┐H┐┌┘││┌──┘IC│
└z└D│││JKL┌─┘┌──┐g┌─┐└G││N│j│┌─┐└┐│
P──┐a││││L│QQ│RR└┐│N└──┘s││┌┘│S│T││
U─┐│┌┘││└K└─┐└─┐V││└─────┘││┌┘││T││
WW│││X││┌──┐│Z0││M│┌──────┘││┌┘└┐││
1┐│││X│││23││Z0│└┐││┌────M┌┘││44│││
5│││└┐││Y││Y│┌─┘6││││┌───┐C┌┘│┌─┘│p
5││└P│││2┘└3││6─┘VH│││┌─┐│O┘S┘│99└I
┌┘│┌─┘││E┐!!│└───┐o┘│││"│└─┐O─┘$$┌%
│U┘│&&│└J│\\│(┐)┐└──┘│8││┌*└┐┌───┘+
└─1└─┐└──┘,┐│-└┐│(/:┌┘"┘││;;│%+───┘
┌─c<<│==┌─┐││└┐│)│/││8>>│*┌?│┌───┐@
│[──[└─┐│]││└┐│└─┘:┘│└──┘┌┘┌┘?┌─^││
└─┐_──_│f││└,│└────-│`──`│7┘^─┘┌─┘│
{{└────┘]┘└──┘|────|└───7└─────┘@─┘

Я тестировал замену шага (4) функцией, которая итеративно, случайно объединяет два соседних пути. Однако в игре гораздо более плотные головоломки, и я уже думаю, что это слишком сложно, чтобы быть трудным.

Вот список проблем, которые я создал разного размера: https://github.com/thomasahle/numberlink/blob/master/puzzles/inputs3

Ответ 4

Думаю, вы захотите сделать это за два шага. Шаг 1) найдите набор непересекающихся путей, которые соединяют все ваши точки, затем 2) Увеличьте/сдвиньте эти пути, чтобы заполнить всю доску.

Мои мысли о шаге 1 состоят в том, чтобы по существу выполнять Dijkstra как алгоритм во всех точках одновременно, увеличивая вместе пути. Подобно Dijkstra, я думаю, вы захотите наполнить заливку из каждой точки, выбрав node для поиска следующего с использованием некоторой эвристики (Моя догадка говорит сначала о том, чтобы сначала набрать точки с наименьшими степенями свободы, затем по расстоянию, может быть хорошим). Совсем иначе, чем Dijkstra, хотя я думаю, что мы можем зациклиться на том, что нам нужно отступить, когда у нас есть несколько путей, пытающихся перерасти в один и тот же node. (Это может быть, конечно, довольно проблематично на больших картах, но может не быть большой проблемой на небольших картах, подобных тому, который у вас есть выше.)

Вы также можете решить некоторые из более простых путей, прежде чем запускать вышеуказанный алгоритм, главным образом, чтобы сократить количество требуемых backtracks. В частности, если вы можете сделать трассировку между точками вдоль края доски, вы можете гарантировать, что соединение этих двух точек в этом стиле никогда не будет мешать другим путям, поэтому вы можете просто заполнить их и вывести этих парней из уравнение. Затем вы можете продолжить эту операцию до тех пор, пока все эти "быстрые и легкие" пути не будут найдены путем прослеживания вдоль границ доски или границ существующих путей. Этот алгоритм фактически полностью разрешил вышеупомянутую доску, но, несомненно, потерпел бы неудачу в другом месте. Тем не менее, было бы очень дешево выполнять и сократить время поиска для предыдущего алгоритма.

В качестве альтернативы

Вы можете просто выполнить реальный алгоритм Дейкстры между каждым набором точек, сначала выбирая самые близкие точки (или несколько раз пытаясь их выполнить в некоторых случайных порядках). Это, вероятно, будет работать для целого ряда случаев, и когда он не удастся просто выбросить карту и создать новую.

Как только вы решите Шаг 1, Шаг 2 должен быть проще, хотя и не обязательно тривиальным. Чтобы вырастить ваши пути, я думаю, вы захотите развить свои пути наружу (так что пути, наиболее близкие к стенам, сначала, растущие к стенам, затем другие внутренние пути наружу и т.д.). Чтобы расти, я думаю, что у вас будут две основные операции, перевертывание углов и расширение на смежные пары пустых квадратов. То есть, если у вас есть строка типа

.v<<.
v<...
v....
v....

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

v<<<.
v....
v....
v....

Затем вы захотите перейти в соседние пары открытого пространства

v<<v.
v.^<.
v....
v....

v<<v.
>v^<.
v<...
v....

и т.д..

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

Ответ 5

У вас есть два варианта:

• Напишите пользовательский решатель
• Грубая сила.

Я использовал опцию (2) для создания плат типа Boggle, и она ОЧЕНЬ успешна. Если вы перейдете с опцией (2), вот как вы это сделаете:

Необходимые инструменты:

• Напишите решение A *.
• Создать произвольный создатель доски

Чтобы решить:

• Создайте случайную плату, состоящую только из конечных точек
• пока совет не решен:
  • получить две конечные точки, наиболее близкие друг другу, которые еще не решены.
  • запустить A * для генерации пути
  • плата обновления, следующая далее. A * знает новый макет платы с новым путем, обозначенным как непереходный.
• При выходе из цикла проверьте успех/сбой (используется вся доска /etc ) и снова запустите, если необходимо

A * на 10x10 должен выполняться через сотые доли секунды. Вы, вероятно, можете решить 1k + доски/секунду. Таким образом, за 10 секунд вы получите несколько "полезных" плат.

Бонусные баллы:

• При создании уровней для пакета уровня IAP (при покупке приложения) не забудьте проверить зеркала/вращения/отражения/etc, чтобы у вас не было одной платы с копией другого (что было просто хромой).
• Придумайте метрику, которая будет выяснять, являются ли две платы "одинаковыми", и если да, то один из них.