Jak znaleźć prawidłowe słowa w siatce znaków?

Tworzę grę podobną do Tetris, z dwiema głównymi różnicami: ekran już zaczyna się wypełniać kafelkami (jak w Puzzle Quest na Nintendo DS i PC), a każda płytka ma literę. Celem gracza jest eliminacja płytek, tworząc z nimi prawidłowe słowa. Słowa są tworzone przez umieszczanie liter obok siebie, w dowolnym kierunku, z wyjątkiem ukośnych.

Gracz może przesunąć cały rząd płytek w lewo lub w prawo lub całą kolumnę płytek w górę lub w dół, na tyle pól, ile chce (jeśli ruch rzędu / kolumny przekracza granice planszy, litera przekraczająca limit będzie „cyklować”, pojawiając się na drugim końcu wiersza / kolumny). Po akcji gracza gra powinna sprawdzić całą planszę w celu znalezienia prawidłowych słów i usunąć litery tworzące te słowa z planszy. Litery powyżej tych, które zostały usunięte, spadną w miejsce tych, które zostały usunięte, a nowe litery spadną z góry ekranu, aż tablica zostanie ponownie wypełniona.

Napisałem już algorytm liniowy, który na podstawie sekwencji znaków określa, czy jest to poprawne angielskie słowo. Mam problem: jak mogę sprawdzić poprawność słów na tablicy? Czy brutalna siła jest jedynym sposobem? Testowanie wszystkich możliwych kombinacji z planszy, aby sprawdzić, czy są poprawne, jest bardzo powolne, nawet dla małej (5x5) planszy. Każda pomoc będzie bardzo mile widziana, dzięki!

Brutalna siła to nie jedyny sposób.

Układanie planszy jest podobne do układania planszy Boggle , z wyjątkiem prostszych. Chcesz sprawdzić każdy kafelek na planszy, sprawdzając, czy są jakieś słowa, które można ułożyć we właściwych kierunkach.

Nadal chcesz uściślić swoją przestrzeń wyszukiwania, abyś nie zawracał sobie głowy szukaniem kierunku, jeśli wiesz, że nie możesz napisać słowa. Na przykład, jeśli znajdziesz dwa qs z rzędu, powinieneś przerwać. W tym celu potrzebujesz struktury danych, która pozwala stwierdzić, czy dany zestaw znaków jest prefiksem prawidłowego słowa. W tym celu możesz użyć drzewa trie lub prefiksu; przydatna struktura danych przy rozwiązywaniu takich problemów.

Drzewo prefiksów to hierarchiczna struktura oparta na węzłach, w której każdy węzeł reprezentuje jakiś prefiks swoich elementów podrzędnych, a węzły liści (ogólnie) reprezentują wartości końcowe. Na przykład, jeśli słownik prawidłowych słów zawiera „kot”, „samochód” i „komórka”, trie może wyglądać następująco:

    0        The root of the trie is the empty string here, although you 
    |        can implement the structure differently if you want.
    c
   / \ 
  a   e
 / \   \
t  r    l
         \
          l

Dlatego zacznij od wypełnienia drzewa przedrostków każdym prawidłowym słowem w grze.

Rzeczywisty proces znajdowania prawidłowych słów na planszy w danym momencie będzie wymagał rozpoczęcia wyszukiwania rekurencyjnego z każdego kafelka na planszy. Ponieważ każde przeszukiwanie przestrzeni planszowej rozpoczynającej się od danego kafelka jest niezależne, w razie potrzeby można je zrównoleglić. Podczas wyszukiwania „podążasz” za drzewem prefiksów na podstawie wartości litery w kierunku, w którym szukasz.

W końcu dojdziesz do punktu, w którym żadna z otaczających liter nie jest potomkami twojego obecnego węzła drzewa prefiksów. Po osiągnięciu tego punktu, jeśli prawdą jest również to, że bieżący węzeł jest liściem, znaleziono prawidłowe słowo. W przeciwnym razie nie znalazłeś prawidłowego słowa i możesz przerwać wyszukiwanie.

Przykładowy kod i omówienie tej techniki (i innych, takich jak rozwiązanie do programowania dynamicznego, które może być jeszcze szybsze poprzez „odwracanie” przestrzeni wyszukiwania po modzie) można znaleźć na blogu tego faceta ; omawia rozwiązywanie problemu Boggle, ale dostosowanie rozwiązań do gry jest mniej więcej kwestią zmiany kierunku, w którym możesz szukać.

Być może próbowałeś tego, już to zaimplementowałeś, może lepiej dołączyć inną odpowiedź itp. Ale nie widziałem ich (jeszcze) wspomnianych, więc oto:

Możesz odrzucić wiele czeków, śledząc, co się zmieniło, a co nie. Na przykład:

On a 5x5 field, A vertical word is found on base of the third column,
All the rows change. However, the first, second, fourth, and fifth,
columns do not change, so you dont need to worry about them (the third did change.)

On a 5x5 field, A 3 letter word is found horizontally on row 2, column 3, to column 5.
So you need to check row 1 and 2 (row 1 because the words on that one
fell down and where replaced), as-well as columns 3, 4, and 5.

lub w kodzie psudo

// update the board

// and check
if (vertical_word)
{
    check(updated_column)

    for (i in range 0 to updated_row_base)
        check(i)
}
else // horizontal word
{
    for (i in range 0 to updated_row)
        check(i)

    for (i in range 0 to updated_column_start)
        check(i)

    for (i in range updated_column_end+1 to final_column)
        check(i)
}

I trywialne pytania:

Czy masz ustawione optymalizacje prędkości kompilatorów? (jeśli używasz jednego)

Czy w ogóle można zoptymalizować algorytm wyszukiwania słów? W jakikolwiek sposób?

Pamiętaj, że każda postać jest wartością. Wykorzystaj to na swoją korzyść. Istnieje kilka funkcji skrótu, które można szybko obliczyć podczas iteracji na podciągach. Na przykład, powiedzmy, że każdemu listowi nadajemy 5-bitowy kod (po prostu zrób c - 'a' + 1w C):

space = 00000;
a = 00001;
c = 00011;
e = 00101;
t = 01100;

Następnie możesz szybko przejechać wszystkie podciągi określonego rozmiaru:

a b [c a t] e t h e = 00011 00001 01100;
//Now we just remove the 5 msb and shfit the rest 5 bits left and add the new character.
a b  c [a t e] t h e = (([c a t] & 0xffff) << 5) | e; // == a t e

W ten sposób możemy sprawdzać podciągi do 12 liter w większości popularnych obecnie architektur.

Jeśli w słowniku znajduje się kod skrótu, możesz go szybko pobrać, ponieważ takie kody skrótu są unikalne. Po osiągnięciu maks. 12 liter możesz dodać kolejne struktury danych dla słów zaczynających się od tych 12 liter. Jeśli znajdziesz słowo, które zaczyna się od 12 liter, po prostu utwórz listę lub inną małą tablicę skrótów dla sufiksów każdego słowa, które zaczyna się od tego prefiksu.

Przechowywanie słownika wszystkich istniejących kodów słownych nie powinno zająć więcej niż kilka megabajtów pamięci.

Czy przy formowaniu słów ograniczasz się tylko do klasycznych kształtów Tetris, czy zrobi to jakakolwiek formacja? Czy słowa mogą zginać się w nieskończoność lub tylko raz? Czy słowo może być tak długie, jak chce? Jest to dość skomplikowane, jeśli możesz wykonać tyle zakrętów, ile chcesz, tworząc najdłuższe możliwe słowa o długości 25 znaków. Zakładam, że masz listę zaakceptowanych słów. Przy takim założeniu sugeruję wypróbowanie czegoś takiego:

At the start of the game:
  Iterate tiles:
    Use tile as starting letter
      Store previous tile
      Check the four adjacent tiles
      If a tile can continue a word started by the previous tile, carry on
      Store the next tile
      Move check to next tile

Spowoduje to utworzenie mapy na każdym kafelku z informacją o tym, jak ten kafelek jest połączony ze słowami wokół niego w siatce. Po przesunięciu kolumny lub wiersza sprawdź wszystkie płytki, które były lub sąsiadują z ruchem i ponownie oblicz informacje. Kiedy znajdziesz słowo, a do tego słowa nie będzie można dodać kolejnych kafelków; usunąć to. Nie jestem pewien, czy będzie to szybsze, tak naprawdę sprowadza się do tego, ile słów jest w połowie stworzonych. Zaletą tego jest to, że użytkownik najprawdopodobniej próbuje utworzyć słowo z półpełnego słowa na tablicy. Przechowując wszystkie te słowa w pamięci, łatwo jest sprawdzić, czy słowo zostało uzupełnione.