Czego używać do tworzenia losowych poziomów gry flow free?

Najprostszym sposobem na stworzenie takiego poziomu jest znalezienie sposobu na jego rozwiązanie. W ten sposób można w zasadzie wygenerować dowolną losową konfigurację początkową i określić, czy jest to prawidłowy poziom, próbując go rozwiązać. To wygeneruje najbardziej zróżnicowane poziomy.

I nawet jeśli znajdziesz sposób na wygenerowanie poziomów w inny sposób, nadal będziesz chciał zastosować ten algorytm rozwiązywania, aby udowodnić, że wygenerowany poziom jest dobry;) {]}

Wyliczanie Brute-force

Jeśli plansza ma rozmiar komórek NxN, a dostępne są również N kolorów, brute-force wylicza wszystkie możliwe konfiguracje (niezależnie od szerokości tworzą rzeczywiste ścieżki między węzłami początkowymi i końcowymi): {]}

• N^2 komórki razem
• komórki 2N zajęte już węzłami początkowymi i końcowymi
• komórki N^2 - 2N, dla których kolor nie został jeszcze określony
• Dostępne kolory.
• N^(N^2 - 2N) możliwe kombinacje.

Więc,

• dla N=5 oznacza to 5^15 = 30517578125 kombinacji.
• dla N = 6 oznacza to 6^24 = 4738381338321616896 kombinacje.

Innymi słowy, liczba możliwych kombinacji jest dość wysoka na początek, ale także rośnie śmiesznie szybko, gdy zaczniesz zwiększać planszę.

Ograniczenie liczby komórek na kolor

Oczywiście powinniśmy starać się zmniejszyć liczbę konfiguracji tak bardzo, jak możliwe. Jednym ze sposobów jest rozważenie minimalnej odległości ("dMin") między komórką początkową i końcową każdego koloru - wiemy, że powinno być przynajmniej tyle komórek o tym kolorze. Obliczanie minimalnej odległości można wykonać za pomocą prostego wypełnienia powodziowego lub algorytmu Dijkstry. (Uwaga: cała następna sekcja omawia tylko liczbę komórek, ale nie mówi nic o ich lokalizacjach )

W twoim przykładzie oznacza to (nie licząc początku i komórki końcowe)

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

Oznacza to, że z 15 komórek, dla których kolor nie został jeszcze określony, musi być co najmniej 1 pomarańczowa, 1 czerwona, 5 Zielona, 3 żółte i 5 niebieskich komórek, co daje łącznie 15 komórek. W tym konkretnym przykładzie oznacza to, że połączenie komórki początku i końca każdego koloru (jedną z) najkrótszych ścieżek wypełnia całą planszę - tzn. po wypełnieniu planszy najkrótszymi ścieżkami nie pozostają żadne niebarwione komórki. (Należy to uznać za "szczęście", a nie każde uruchomienie konfiguracji tablicy spowoduje, że tak się stanie).

Zwykle po tym kroku mamy liczbę komórek, która może być dowolnie kolorowana, nazwijmy ją liczbą U. dla N=5,

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

Ponieważ komórki te mogą przyjmować dowolny kolor, możemy również określić maksymalną liczbę komórek, które mogą mieć określony kolor:

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

(w tym konkretnym przykładzie U=0, więc minimalna liczba komórek na kolor jest również maksymalna).

Path-finding using the distance ograniczenia

Gdybyśmy mieli brute force wyliczyć wszystkie możliwe kombinacje przy użyciu tych ograniczeń kolorów, mielibyśmy o wiele mniej kombinacji martwić. Dokładniej, w tym konkretnym przykładzie mamy:

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

To jednak wciąż nie daje nam rzeczywistych ścieżek. tak więc lepszym pomysłem byłoby wyszukiwanie cofania, gdzie przetwarzamy każdy kolor po kolei i próbujemy znaleźć wszystkie ścieżki, które: {]}

• nie przekracza już kolorowego komórka
• nie jest krótszy niż dmin(kolor) i nie dłuższy niż DMAX (kolor).

Drugie kryterium zmniejszy liczbę ścieżek zgłaszanych na kolor, co spowoduje znaczne zmniejszenie całkowitej liczby ścieżek (ze względu na efekt kombinatoryczny).

W pseudo-kodzie:

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

To pozostawia tylko FindAllPaths (board, colour, startCell, endCell, minDistance, maxDistance) do zaimplementowania. Najtrudniejsze jest to, że jesteśmy nie szukając najkrótszych ścieżek, ale wszelkich ścieżek, które mieszczą się w zakresie określonym przez minDistance i maxDistance. Dlatego nie możemy po prostu używać Dijkstry lub A*, ponieważ będą one rejestrować tylko najkrótszą ścieżkę do każdej komórki, a nie ewentualne objazdy.

Jednym ze sposobów znalezienia tych ścieżek byłoby użycie wielowymiarowej tablicy dla planszy, gdzie każda komórka jest w stanie przechowywać wiele waypointów, a punkt waypoint jest zdefiniowany jako para (poprzedni punkt waypoint, odległość do pochodzenie). Poprzedni waypoint jest potrzebny, aby móc odtworzyć całą ścieżkę po dotarciu do celu i odległości do źródła zapobiega przekroczeniu maksymalnej odległości.

Znalezienie wszystkich ścieżek może być wykonane za pomocą flood-fill jak eksploracja z komórki startowej na zewnątrz, gdzie dla danej komórki, każda niebarwiona lub taka sama jak obecna, kolorowa okolica jest rekurencyjnie badana (z wyjątkiem tych, które tworzą naszą bieżącą ścieżkę do źródła), dopóki nie osiągniemy albo endCell lub przekroczyć maksymalną odporność.

Ulepszeniem tej strategii jest to, że nie badamy od startCell Na zewnątrz do endCell, ale badamy zarówno od startCell, jak i endCell Na Zewnątrz równolegle, używając podłogi (maxDistance / 2) i sufitu (maxDistance / 2) jako odpowiednich maksymalnych odległości. W przypadku dużych wartości maxDistance, powinno to zmniejszyć liczbę zbadanych komórek z 2 * maxDistance^2 do maxDistance^2.

Zaimplementowałem następujący algorytm w moim numberlink solver i generator . In stosuje zasadę, że ścieżka nigdy nie może się dotknąć, co jest normalne w większości "hardcorowych" aplikacji numberlink i łamigłówek

1. najpierw plansza jest wyłożona Domino 2x1 w prosty, deterministyczny sposób. Jeśli nie jest to możliwe (na nieparzystym papierze), w prawym dolnym rogu znajduje się pozostawiony jako singleton.
2. Następnie Domino są losowo tasowane przez obracające się losowe pary sąsiedzi. Nie jest to wykonywane w przypadku szerokości lub wysokości równej 1.
3. teraz, w przypadku nieparzystego papieru obszarowego, prawy dolny róg jest przymocowany do jeden z sąsiadów Domino. Zawsze będzie to możliwe.
4. wreszcie możemy zacząć szukać losowych ścieżek przez Domino, łącząc je jak przejdziemy. Szczególną uwagę należy zwrócić na to, aby nie łączyć" co stworzy łamigłówki, które "dublują się".
5. zanim puzzle zostaną wydrukowane we "Kompaktowy" zakres użytych kolorów, w miarę możliwości.
6. układanka jest drukowana przez zastąpienie wszystkich pozycji, które nie są flow-heads przez .

Mój format numberlink używa znaków ascii zamiast liczb. Oto przykład:

$ 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>>.*.?......@
.[..[....]........:..........?..^..
..._.._.f...,......-.`..`.7.^......
{{......].....|....|....7.......@..

I tutaj przepuszczam to przez mojego solvera (ten sam seed):

$ 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└─────┘@─┘

Przetestowałem zastąpienie step (4) funkcją, która iteracyjnie, losowo łączy dwie sąsiednie ścieżki. Jednak gra znacznie gęstsze zagadki, i już myślę, że powyżej jest prawie zbyt gęsty, aby być trudne.

Oto lista problemów, które wygenerowałem o różnej wielkości: https://github.com/thomasahle/numberlink/blob/master/puzzles/inputs3

Myślę, że będziesz chciał to zrobić w dwóch krokach. Krok 1) Znajdź zestaw nie przecinających się ścieżek, które łączą wszystkie punkty, a następnie 2) rozwijaj/przesuń te ścieżki, aby wypełnić całą planszę

Moje myśli na Krok 1 są zasadniczo wykonać Dijkstra jak algorytm na wszystkich punktach jednocześnie, rosnąc razem ścieżki. Podobnie jak Dijkstra, myślę, że będziesz chciał zalać-wypełnić z każdego z twoich punktów, wybierając, który węzeł szukać dalej, używając jakiegoś heurystycznego (moje przeczucie mówi o wyborze punktów z najmniejszym stopniem swobody najpierw, potem na odległość, może być dobry). Bardzo inaczej niż Dijkstra choć myślę, że możemy utknąć z konieczności cofania, gdy mamy wiele ścieżek próbujących rosnąć w tym samym węźle. (To oczywiście może być dość problematyczne na większych mapach, ale może nie być wielkim problemem na małych mapach, takich jak ta, którą masz powyżej.)

Możesz również rozwiązać kilka łatwiejszych ścieżek przed uruchomieniem powyższego algorytmu, głównie w celu zmniejszenia liczby backtracks potrzebne. W szczególności, jeśli możesz prześledzić między punktami wzdłuż krawędzi planszy, możesz zagwarantować, że połączenie tych dwóch punktów w ten sposób nigdy nie będzie kolidować z innymi ścieżkami, więc możesz po prostu wypełnić te i usunąć tych facetów z równania. Możesz następnie dalej to powtarzać, aż wszystkie te" szybkie i łatwe " Ścieżki zostaną znalezione przez śledzenie wzdłuż granic planszy lub granic istniejących ścieżek. Algorytm ten faktycznie całkowicie rozwiązałby powyżej przykładowa tablica, ale bez wątpienia zawiodłaby gdzie indziej .. mimo to byłoby to bardzo tanie w wykonaniu i skróciłoby czas wyszukiwania dla poprzedniego algorytmu.

alternatywnie

Można po prostu zrobić prawdziwy algorytm Dijkstry pomiędzy każdym zestawem punktów, wybierając najbliższe punkty jako pierwsze(lub wypróbowując je w kilku losowych kolejnościach). To prawdopodobnie zadziała w sporej liczbie przypadków, a gdy się nie powiedzie, po prostu wyrzuć mapę i wygeneruj nowy jeden.

Po rozwiązaniu kroku 1, Krok 2 powinien być łatwiejszy, choć niekoniecznie trywialny. Aby rozwijać swoje ścieżki, myślę, że będziesz chciał rozwijać swoje ścieżki na zewnątrz (więc ścieżki najbliżej ścian najpierw, rosnące w kierunku ścian, potem inne wewnętrzne ścieżki na zewnątrz, itp.). Aby rosnąć, myślę, że będziesz miał dwie podstawowe operacje, przerzucanie rogów i rozszerzanie się na sąsiednie pary pustych kwadratów.. to znaczy, jeśli masz linię jak

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

Najpierw będziesz chciał przewrócić rogi do wypełnij swoje przestrzenie krawędzi

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

Następnie będziesz chciał rozszerzyć się na sąsiednie pary otwartej przestrzeni

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

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

Itd..

Zauważ, że to, co opisałem, nie gwarantuje rozwiązania, jeśli takie istnieje, ale myślę, że powinieneś być w stanie znaleźć takie rozwiązanie przez większość czasu, jeśli takie istnieje, a następnie w przypadkach, gdy mapa nie ma rozwiązania lub algorytm go nie znajdzie, po prostu wyrzuć mapę i spróbuj innego:)]}

Masz dwa wyjścia:

1. Napisz Niestandardowy solver
Brutalna siła.

Użyłem opcji (2) do generowania tablic typu Boggle i jest to bardzo udane. Jeśli wybierzesz opcję (2), to tak to zrobisz:

Potrzebne narzędzia:

• Napisz a * solver.
• Napisz losowego twórcę planszy

Do rozwiązania:

1. Wygeneruj losową planszę składającą się tylko z punktów końcowych
2. while board is not solved:
   • get two punkty końcowe najbliżej siebie, które nie zostały jeszcze rozwiązane
   • Uruchom*, aby wygenerować ścieżkę
   • zaktualizuj planszę, aby next a * znał nowy układ planszy z nową ścieżką oznaczoną jako nie do przejścia.
3. przy wyjściu pętli, sprawdź success/fail (czy cała płyta jest używana / etc) i uruchom ponownie w razie potrzeby

A* na 10x10 powinno działać w setnych częściach sekundy. Prawdopodobnie możesz rozwiązać 1K + deski / sekundę. Tak więc 10-sekundowy bieg powinien dać ci kilka "użytecznych" desek.

Bonus punkty:

• podczas generowania poziomów dla pakietu poziomów IAP (w zakupie aplikacji), pamiętaj, aby sprawdzić lusterka / obroty / odbicia / itp.
• wymyśl metrykę, która zorientuje się, czy dwie tablice są "podobne", a jeśli tak, porzuć jedną z nich.