Webゲームのスパース(疑似)無限グリッドデータ構造

私は基本的に無限のグリッド上で行われるゲームを作ろうと考えています。

  • グリッドは非常にまばらです。比較的高密度の特定の小さな領域。相対的に少数の分離された空でないセル。
  • 使用しているグリッドの量は大きすぎるため、ネイティブに実装することはできませんが、
    “ビッグデータ”標準(インターネットなどのマッピングはしていません)によって小さくなる可能性があります。
  • これは持続するのが簡単である必要があります。

このグリッド上で(妥当に効率的に)実行したい操作は次のとおりです。

  • 小さな矩形のセルとそのすべてのコンテンツ(プレーヤーの現在の周辺)をリクエストします。
  • 個々のセルを設定するか、小さな領域を分割する(プレーヤーは移動している)
  • いくつかのより大きな矩形領域の大まかな形や輪郭/シルエット(世界地図または地域プレビュー)を求めます。
  • 特定の密度のある地域を特定する(プレーヤーのスポーン場所)
  • ホップごとにいくつかの小さな一定の空きスペースのギャップを通る最短経路です(誤った近似であることはよくありますが、間違った方向を探し続けることはできません)。
  • 地域の凸包近似

ここにキャッチがあります:私はWebアプリケーションでこれをやりたいつまり、既存のデータストレージ(おそらくリレーショナルデータベースの形式)と外部依存性(比較的永続的なプロセスの必要性を避けることが望ましい)を使用することを好むでしょう。

皆さん、実際にこれを実装する際に私にどのようなアドバイスをお願いできますか?ウェブアプリの制限がない場合はどうすればよいですか?もしあなたがそれを修正すればどうですか?

ありがとうございます、誰もが!

ベストアンサー

私はクアッドツリーを使って、他の人が示唆しているように、そしておそらくいくつかの追加のデータ構造を使ってすべてを行うことができると思います。もう少し詳しく説明します:

  • Asking for cell contents, setting cell contents: these are the
    basic quadtree operations.
  • Rough shape/outline: Given a rectangle, go down sufficiently
    many steps within the quadtree that most cells are empty, and make
    the nonempty subcells at that level black, the others white.
  • Region with approximately given density: if the density you’re
    looking for is high, then I would maintain a separate index of all
    objects in your map. Take a random object and check the density
    around that object in the quadtree. Most objects will be near high
    density areas, simply because high-density areas have many objects.
    If the density near the object you picked is not the one you were
    looking for, pick another one.

    If you’re looking for low-density, then just pick random
    locations on the map – given that it’s a sparse map, that should
    typically give you low density spots. Again, if it doesn’t work
    right try again.

  • Approximate shortest path: if this is a not-too-frequent
    operation, then create a rough graph of the area “between” the
    starting point A and end point B, for some suitable definition of
    between (maybe the square containing the circle with the midpoint
    of AB as center and 1.5*AB as diameter, except if that diameter is
    less than a certain minimum, in which case… experiment). Make the
    same type of grid that you would use for the rough shape/outline,
    then create (say) a Delaunay triangulation of the black points. Do
    a shortest path on this graph, then overlay that on the actual map
    and refine the path to one that makes sense given the actual map.
    You may have to redo this at a few different levels of refinement –
    start with a very rough graph, then “zoom in” taking two points
    that you got from the higher level as start and end point, and
    iterate.

    If you need to do this very frequently, you’ll want to maintain
    this type of graph for the entire map instead of reconstructing it
    every time. This could be expensive, though.

  • Approx convex hull: again start from something like the rough
    shape, then take the convex hull of the black points in that.

リレーショナルデータベースに入れるのが簡単かどうかはわかりません。ファイルベースのストレージが機能するかもしれませんが、書き込み操作を他のものと並行させることは実用的ではありません。もしこれが合理的な数のプレーヤー(世界/マップごとに複数の世界/地図です)。私はその場合、おそらく別のプロセスを生かしておくのが最良だと思っています…そして、それでもこれを適切に尊重することは、マルチスレッド化が頭痛になることになります。

コメントする

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です