1

プレイヤーをゲームに参加させるための効率的なアルゴリズムを考えています。膨大な数のプレーヤーが存在するため、アルゴリズムは非同期にする必要があります (つまり、クラスター内の任意の数のマシンに拡張できます)。詳細があります: 無向グラフがあると想像してください (各ノードはプレーヤーです)。プレイヤー間の各エッジは、プレイヤーが同じゲームに参加できることを意味し、エッジがなければ参加できないことを意味します。次の基準でプレーヤーをグループ化するアルゴリズムを実装する必要があります。

  • 各プレイヤーには、「ゲーム待機中」または「ゲーム中」という状態があります。待機中のプレイヤーのみをゲームにグループ化する必要があります
  • 各ゲームには最小人数と最大人数のプレイヤーがいます

実装に関する私の考え: グラフは、NoSQL データベースを介して (クラスター内のさまざまなマシンから) 格納およびアクセスされます。特定のスキーマはまだありません (提案はありますか?)。また、個々のプレーヤーへのアクセスをロックする (ペシミスティック ロックとも呼ばれる) ことは、同じプレーヤーにアクセス/収集しようとする他のプロセスの速度を低下させる潜在的なボトルネックになるため、オプションではありません。

私の質問は、そのようなアルゴリズムを実装した人はいますか? 助言がありますか？

PS: 私はすでに未加工のアイデアを持っていますが、最初に議論したい/人々が提案するものを確認したいです.

ありがとう！

EDIT1: Thomas Jungblut への回答: ゲーム スロットの使用は興味深いアイデアですが、(正しく理解し次第) 場合によっては機能しない可能性があります。Fox の例: 各ゲームには正確に 3 人のプレイヤーが必要です。新しい 6 人のプレーヤー (ABCDEF と呼びましょう。例 1 を参照) は、A、B、E、F、C、D の順序で 1 つずつグラフ/キューに入ります。

例 1

その結果、1 つのゲーム (A、B、C) と、空のスロットを持つ 2 つのゲーム (D) および (E、F) のみが作成されます。しかし、最適なのは (A, C, D) と (B, E, F) の 2 つのゲームですよね?

4

1 に答える 1

3

ビジネス要件について十分に検討していないのではないかと思います。

任意の条件を持つ「最適なマッチング」のようなフレーズは、私には NP 完全なにおいがします。大規模なデータ セットを持つこれらの 1 つに対する効率的な正確な解を見つけることはできません。合理的な近似にすぎません。

そして、準最適な一致のコストはいくらですか? 誰かが遊んでいるのを見つけるために、少し長く待たなければならなくなります。特に問題ありません。

このような単純なものを実装します。セットアップ中のゲームのキューを用意します。参加する各人は、最初のゲームに参加しようとし、2 番目のゲームに失敗し、3 番目のゲームに失敗し、というように続きます。何も見つからない場合は、キューの最後に新しいゲームを作成します。ゲームは、最大サイズに達したとき、または最小サイズに達してから一定時間後に開始されます。ゲームが開始されると、キューの先頭から削除されます。

それが決定されたのに、なぜ 100 万人のアクティブ プレイヤーがいると思いますか?

もしあなたが大きな夢を持ったスタートアップだからであるなら、既知の問題をできるだけ効率的に解決することに集中する必要があることを強くお勧めします。万一成功した場合 (真剣に、統計を見たことがありますか?)、後でスケーリングできます。そして、実際の問題を解決するだけで、恐ろしいものから単に貧弱なものまで、成功の可能性が大幅に向上します。(落胆させるつもりはありません。しかし、スタートアップの夢とは、非常識なリターンが得られる可能性が非常に低いことです。あなたが行うすべての行動は、可能性を改善することに向けられるべきです。)

あなたが確立されたゲーム会社であり、これらの数字を達成できると信じる十分な理由がある場合は、読み進めてください.

言及する必要のない明白な注意点は、パフォーマンスに重要なビットを比較的高速な言語で実装する必要があるということです。たとえば、ほとんど Python で書いている場合、これは Java、Go、または C++ で書くのに適しています。

次に、スケーリングしない最初のものはプレーヤー情報です。だからそれを配布してください。これを行うと、「プレーヤーがゲームに適合できるか」チェックが遅くなります。したがって、ゲームごとのロックを追加し、その計算を非同期に分散します。あきらめて新しいゲームを作成する前に、ゲームに参加しようとする努力を制限してください。

次のボトルネックは、ゲームのマッチング計算です。では、「新しいゲームはこちら」を複数のマシンに配布する作業に進みます。ここでプレイヤーが現れ、チェックするゲームの集中リストを取得し、それらのチェックを開始します。ボトルネックを避けるために、プレーヤーは待機中のゲームのリストをランダムに並べ替える必要があります。

ネットのボトルネックはそのリストを求めています。リストはほとんどが読み取り専用であるため、Redis のレプリケートされたインスタンスのみを使用できます。書き込み (新しいゲーム、および開始されたゲームのマーキング) はマスターに送信でき、読み取りは必要な数のマシンに分散できます。プレイヤーは Redis のランダムなコピーをヒットし、リストを取得してランダムに並べ替えます。

このレベルのスケールに到達すると、私はショックを受けるでしょう。それを超える場合は、Redis のシャーディングなどの次の手順をお任せします。

ランダムメモ。これはまともなタイプのインタビューの質問です. 「このシンプルなものを設計してください。スケールさせてください。さらにスケールさせてください。さらにスケールさせてください。」分散パフォーマンスを理解している人を実際に探しているのであれば、それは良いテストです。(ただし、インタビュアーが良い回答と悪い回答を区別できる場合に限ります。)

于 2013-06-28T17:40:50.667 に答える