Bagaimana saya bisa menemukan kata-kata yang valid dalam kotak karakter?

Saya membuat game yang mirip dengan Tetris, dengan dua perbedaan utama: layar sudah mulai dipenuhi ubin (seperti dalam Puzzle Quest untuk Nintendo DS dan PC) dan setiap ubin individu memiliki huruf di dalamnya. Tujuan pemain adalah menghilangkan ubin dengan membentuk kata-kata yang valid dengannya. Kata-kata dibentuk dengan menempatkan huruf-huruf di samping satu sama lain, ke segala arah, kecuali secara diagonal.

Pemain dapat memindahkan seluruh baris ubin ke kiri atau ke kanan atau seluruh kolom ubin ke atas atau ke bawah, untuk sebanyak mungkin ruang yang diinginkan (jika pergerakan baris / kolom melampaui batas papan, maka huruf yang melewati batas akan "siklus", muncul di ujung baris / kolom). Setelah aksi pemain, permainan harus memeriksa seluruh papan untuk mencari kata yang valid dan menghapus huruf yang membentuk kata-kata itu dari papan. Huruf-huruf di atas yang telah dihapus akan jatuh di tempat surat-surat yang dihapus dan surat-surat baru akan jatuh dari bagian atas layar sampai papan diisi kembali.

Saya sudah menulis algoritma linier yang, diberi urutan karakter, menentukan apakah itu kata bahasa Inggris yang valid. Masalah yang saya alami adalah: bagaimana saya bisa memeriksa kata-kata yang valid di papan tulis? Apakah kekuatan kasar satu-satunya cara? Menguji semua kemungkinan kombinasi dari papan untuk melihat apakah mereka valid sangat lambat, bahkan untuk papan kecil (5x5). Bantuan apa pun akan sangat dihargai, terima kasih!

Kekerasan bukan satu-satunya cara.

Memecahkan papan permainan Anda mirip dengan memecahkan papan Boggle , kecuali lebih sederhana. Anda ingin memeriksa setiap ubin di papan, mencari untuk melihat apakah ada kata yang dapat dibuat di sepanjang arah yang sesuai.

Anda masih ingin mempersempit ruang pencarian Anda lebih jauh sehingga Anda tidak perlu repot mencari arah jika Anda tahu Anda tidak dapat membuat kata. Misalnya, jika Anda menemukan dua qs berturut-turut, Anda harus membatalkan. Untuk itu, Anda ingin beberapa jenis struktur data yang memungkinkan Anda untuk mengetahui apakah serangkaian karakter yang diberikan adalah awalan dari kata yang valid. Untuk ini, Anda bisa menggunakan trie , atau pohon awalan; struktur data yang berguna saat memecahkan masalah seperti ini.

Pohon awalan adalah struktur berbasis simpul hierarkis, di mana setiap simpul mewakili beberapa awalan anak-anaknya, dan simpul daun (umumnya) mewakili nilai akhir. Misalnya, jika kamus Anda berisi kata-kata yang valid berisi "cat," "car," dan "cell," sebuah trie akan terlihat seperti:

    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

Jadi, mulailah dengan mengisi pohon awalan dengan setiap kata yang valid di gim Anda.

Proses aktual untuk menemukan kata-kata yang valid di papan tulis pada waktu tertentu akan melibatkan memulai pencarian rekursif dari setiap ubin di papan tulis. Karena setiap pencarian melalui ruang papan dimulai pada beberapa ubin yang diberikan adalah independen, ini dapat diparalelkan jika diperlukan. Saat Anda mencari, Anda "mengikuti" pohon awalan berdasarkan nilai huruf ke arah yang Anda cari.

Anda akhirnya akan mencapai titik di mana tidak ada huruf di sekitarnya adalah anak-anak dari simpul pohon awalan Anda saat ini. Ketika Anda mencapai titik itu, jika memang benar bahwa simpul saat ini adalah daun, Anda telah menemukan kata yang valid. Jika tidak, Anda belum menemukan kata yang valid dan Anda dapat membatalkan pencarian.

Contoh kode dan diskusi tentang teknik ini (dan lainnya, seperti solusi pemrograman dinamis yang bahkan bisa lebih cepat dengan "membalikkan" ruang pencarian setelah mode) dapat ditemukan di blog orang ini di sini ; ia membahas pemecahan Boggle, tetapi mengadaptasi solusi untuk gim Anda kurang lebih adalah masalah mengubah arah yang memungkinkan Anda mencari.

Anda mungkin sudah mencoba ini, sudah menerapkan ini, mungkin lebih baik disertai dengan jawaban lain, dll. Tapi saya belum melihat mereka disebutkan (belum), jadi ini dia:

Anda dapat membuang banyak cek dengan melacak apa yang berubah dan apa yang tidak. Sebagai contoh:

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.

atau, dalam kode 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)
}

Dan pertanyaan sepele:

Apakah Anda memiliki optimisasi kecepatan kompiler yang ditetapkan? (jika Anda menggunakan satu)

Dapatkah algoritma pencarian kata Anda dioptimalkan sama sekali? Dengan cara apapun?

Ingat bahwa setiap karakter adalah nilai. Jadi gunakan itu untuk keuntungan Anda. Ada beberapa fungsi hash yang dapat dihitung dengan cepat saat iterasi pada substring. Sebagai contoh, katakanlah kita memberi setiap huruf kode 5 bit (lakukan saja c - 'a' + 1dalam C):

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

Daripada Anda bisa dengan cepat menabrak semua substring dengan ukuran tertentu:

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

Kita dapat memeriksa substring hingga 12 huruf dengan cara ini pada arsitektur paling umum saat ini.

Jika kode hash ada di kamus Anda, Anda dapat menarik kata dari sana dengan cepat karena kode hash seperti ini unik. Saat Anda mencapai maksimal 12 huruf, Anda mungkin ingin menambahkan struktur data lain untuk kata-kata yang dimulai dengan 12 huruf itu. Jika Anda menemukan kata yang dimulai dengan 12 huruf spesifik daripada hanya membuat daftar atau tabel hash kecil untuk akhiran setiap kata yang dimulai dengan awalan itu.

Menyimpan kamus dari semua kode kata yang ada tidak boleh lebih dari beberapa megabyte memori.

Apakah Anda hanya terbatas pada bentuk Tetris klasik ketika membentuk kata-kata, atau akankah formasi apa pun melakukannya? Bisakah kata-kata dibengkokkan tanpa batas atau hanya sekali? Bisakah sebuah kata sepanjang yang diinginkan? Cara ini cukup rumit jika Anda bisa melakukan banyak tikungan sesuka hati, efektif membuat kata-kata terpanjang sepanjang 25 karakter. Saya menganggap Anda memiliki daftar kata yang diterima. Atas asumsi itu saya sarankan Anda mencoba sesuatu seperti ini:

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

Ini akan membuat peta pada setiap ubin dengan informasi bagaimana ubin ini terhubung dengan kata-kata di sekitarnya dalam kisi. Ketika kolom atau baris dipindahkan periksa semua ubin yang telah, atau berdekatan dengan gerakan dan hitung ulang informasinya. Ketika Anda menemukan kata, dan tidak ada ubin lagi dapat ditambahkan ke kata itu; Singkirkan. Saya tidak yakin apakah ini akan lebih cepat, itu benar-benar bermuara pada berapa banyak kata yang setengah dibuat. Manfaat untuk ini adalah bahwa pengguna kemungkinan besar mencoba membuat kata dari kata setengah lengkap di papan tulis. Dengan menyimpan semua kata ini tersimpan, mudah untuk memeriksa apakah suatu kata telah selesai.