2

Ruzzleというゲームで使われているアルゴリズムについてしばらく考えていました。ゲームの目的は、特定のグリッド内の任意の単語の存在を見つけることです。単語は、上下、上下、左右、左右、対角線の上下など、任意の方向に一致させることができます。

簡単にしましょう。一致する制約 (方向) が同じである 2 次元グリッド内の特定の単語を検索します。可能な限り最高の時間複雑度を持つアルゴリズムは何ですか?

たとえば、FOREVER はこのグリッドにあります。

H OF ER

L RE TO

SN V O R

PQT E N

4

2 に答える 2

1

Trieデータ構造を使用して、さらに最適化できます。すべての英語の単語 (または別の言語) を構造に入力すると、O(1) で、特定の隣人の文字を調べる必要があるかどうかを確認できます。

この時点で、ストレージを時間と交換していることに注意してください。Trie 全体を格納するにはおそらくより多くの RAM が必要になりますが、単語の順序付きリストをチェックインするよりも高速にクエリを実行できます。

ゲームの背後にあるアーキテクチャに関しては、専用のサーバーを使用していると思います。このサーバーは、新しいゲーム (マトリックス) と許容される単語のリストを DB に保存するためにフルタイムで動作します。ゲーム中、デバイスは ID を受け取り、マトリックスと許容される単語のリストをダウンロードします。これで十分にプレイできます。各ゲームの終了時にすべてが削除され、最終スコア (整数のみ) がサーバーに送信され、プロファイルが更新されます。実際のゲームでは、バッジや統計情報も含まれているため、さらに何かがあります (ただし、収集するのは些細なことです)。これは、私が設計および開発する方法にすぎないことを覚えておいてください。

どう思いますか?もっとうまくやれるだろうか?

于 2014-06-19T07:28:16.327 に答える
-2

Unity でラズル ゲームの仕組みを作成するコースを作成しました。チェックしてみてください。正確な答えが見つかります。

https://www.udemy.com/word-game-unity/?couponCode=wordgamecourse

于 2015-05-22T11:49:23.457 に答える