46

私はPHPでのコーディングに慣れていますが、Javaに精通しておらず、これはしばらくの間問題になっています。かなり簡単な解決策になると思いますが、どのように検索しても良いサンプルコードが見つからないので、次のようにします。

私は、タイルベースのマップ上で2Dランダムに生成された無限の世界で行われるゲームをプログラミングしています（ニッチピッキング：それが本当に無限ではないことはわかっています。世界はかなり大きいと思います）。map [x] [y]多次元配列の通常のアプローチは基本的な考え方として始まりましたが、JavaはPHPのように非整数（つまり負の）配列キーシェナニガンの方法を提供しないため、適切に（- x、+ x、-y、+ y）配列キーを使用した座標系。

特定のx、y座標でタイル上のオブジェクトを検索できるようにする必要があります。また、特定のタイルの「隣接するタイル」を検索できる必要があります。（getObjectAt（x、y）、get（x + 1、y）などができれば自明です）

四分木やR木などについて読んだことがあります。コンセプトはエキサイティングですが、Javaでの優れた単純な実装例は見たことがありません。それに加えて、それが私が正確に必要としているものであるかどうかは本当にわかりません。

アドバイスは大歓迎です

ありがとうございました

4

11 に答える 11

7

Map<Integer, Map<Integer, Tile>>1）配列の代わりに、またはを使用できますMap<Point, Tile>。これにより、もちろん負のインデックスが可能になります。

2）最初から世界の次元を知っている場合は、ゲッターを変更して、APIがネガティブを受け入れ、[線形]ポジティブに変換できるようにすることができます。たとえば、世界が100x1000タイルで、（-5、-100）が必要な場合、どちらが（45,400）にWorldMap.getTile(-5,-100)変換されるかがわかります。return tileArray[x+mapWidth/2][y+mapHeight/2];

于 2011-03-07T22:44:15.170 に答える
5

私は同じ問題でこのスレッドに来ましたが、私の解決策はMap/HashMapsを使用することでしたが、これらは 1 次元です。

これを克服するために、マップ内でマップを使用する代わりに (これは面倒で非常に非効率的です)、一般的なPairクラスを使用しました (ストック Java ライブラリにあるものではありません)。ただし、これを Position クラスに置き換えることもできます。 (実質的に同じコードですが、一般的ではなく、整数または浮動小数点数です)。

したがって、マップを定義するとき:Map<Pair, Tile> tiles = new HashMap<Pair, Tile>;

私が使用したマップにタイルオブジェクトを配置しtiles.put(new Pair(x, y), new GrassTile());、オブジェクトを取得するためtiles.get(new Pair(x, y));。

[x/y は、配置したい任意の座標になります (これにより、混乱することなく負の座標を使用できます!)、「new GrassTile()」は、マップの作成中に特定のタイプのタイルを配置する例にすぎません。明らかに - 前に述べたように - Pair クラスは交換可能です。]

あなたが尋ねるかもしれないArrayListsではないのはなぜですか？配列リストはマッピングよりもはるかに直線的であり、私の意見では、特に 2 次元ではタイルの追加と取得がより難しいためです。

アップデート：

なぜ Java に Pair() クラスがないのか疑問に思っている人のために、ここに説明があります。

于 2012-06-07T15:50:10.010 に答える
3

木、四分木、二分木、赤木と黒木、その他すべての種類の木は役に立ちません (巨大な森のあるマップを計画している場合を除きます)。

特殊なデータ構造には、特定の用途があります。ゲームに空間インデックスが必要な正当な理由がない限り、作成しないでください。典型的なシナリオが「可視領域を反復処理し、各正方形でどのタイルが表示されているかを見つける」である場合、特定のキーの下に格納されている値にすばやくランダムにアクセスできる構造が必要です。そのような構造は HashMap です (PHP が使用するのは一種の LinkedHashMap ですが、おそらく「リンクされた」部分は使用していません)。

あなたは xephox のアドバイスに従う必要があります (そして彼にクレジットを与えます)。それは:

  • 場所を説明するクラスを作成します (ペア、場所、ポイントなど)。
  • すべてのフィールド (おそらく x と y) を final にします。場所自体は変更できないことが重要です (これにより、作業が非常に楽になります)。
  • equals メソッドと hashcode メソッドを生成します (すべての IDE がこれを支援します。実装では x と y の両方を使用する必要があることに注意してください。IDE のウィザードが役立ちます)。
  • マップは次のようになります。 Map map = new HashMap();

最良のこと: マップ インターフェイスを使用し続けると、ロックアウトされることはなく、多くの改善を行うことができます。いくつかのアルゴリズム技術を使用してマップの一部を作成するオブジェクトに HashMap をラップするようなものです。

于 2012-06-07T16:29:28.477 に答える
2

私はゲーム プログラミングの専門家ではありませんが、配列に問題がなければ、座標を (-x, +x) から (0, 2x) に変換するだけで済みます (y 軸も同様です)。

または、PHP のような連想配列に慣れている場合は、Java で対応する構造体を使用します。これは Map (HashMap で問題ありません) です。Coordinate適切な equals メソッドと hashCode メソッドを使用してクラスを定義し、HashMap<Coordinate>. Coordinate を不変にすると、コードがより堅牢になり、hashCode をキャッシュできるようになります。

于 2011-03-07T22:40:52.940 に答える
2

QuadTree を試すことができます (ここに良い例があります: http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/ )

于 2011-09-16T11:58:26.433 に答える
1

マップをチャンクに分割するのはどうですか (はい、Minecraft のファンです。これがどこで使用されているか知っています :P)。したがって、同じ原点を持つ 2 つの座標系があります。

  • x/y座標
  • c1/c2チャンク座標

チャンクは常に、実世界の座標の固定サイズ (128x128 など) です。Chunk次に、すべてのピクセルのすべての情報を含む固定配列 (128x128) を持つクラスがあります。Map<ChunkCoordinates, Chunk>そして、他の人がすでに説明したように、チャンクをに保存します。をお勧めしHashMapます。

プレーヤーが特定の地域にいるときはいつでも、必要なチャンクがマップから読み込まれ、そこにある固定サイズの配列にアクセスできます。チャンクがx/y座標のどこに配置されているかを知っている場合、Pixel Chunk#getPixel(long x, long y)またはそのようなサポート機能を使用することもできます...

ところで: これにより、世界全体の生成を本当に必要になるまで延期する簡単な方法も提供されますChunk。それから。または、それが簡単な場合は、起動時にいっぱいにすることもできます。(疑似無限であっても、無限の世界を埋めるには長い時間がかかります)

于 2012-11-13T11:09:55.327 に答える
1

私は Java でいくつかの実験的なスペア データ構造を作成しました。

最も興味深いのはOctreapで、これはTreapとOctreeの間のまったく新しいクロスであると私は信じています。これには次の機能がありました。

  • 60 ビット世界座標 (約 1,000,000 * 1,000,000 * 1,000,000 グリッド)
  • 負の座標をサポート
  • 空のスペースはストレージを必要としません (非常にまばらな世界をサポートします)
  • 同一のセルのボリュームを圧縮します (たとえば、同じ材料の大きなブロックが効率的に保存されます)。
  • 読み取りと書き込みの O(log n)
于 2012-03-09T06:48:10.927 に答える
0

おそらく Map の実装を使用したいと思うでしょう。HashMap、SortedMap などは、保存するデータの量とアクセス パターンに応じて異なります (Sorted Map はシーケンシャル アクセスに非常に適していますが、HashMap はランダム アクセスに適しています)。

2 次元マップを使用するか、2 次元インデックスを 1 次元マップのキーに変更することができます。

于 2011-03-07T22:42:23.827 に答える
0

これは、負の配列インデックスをシミュレートして「無限」マップを作成する方法と、タイルを効率的に格納する方法の 2 つの個別の問題です。

最初の質問では、1 つのハックは、各象限に 1 つずつ、4 つの個別のマトリックス (マトリックス?) を維持することです。次に、すべてのインデックスが正になる可能性があります。

2 番目の質問では、スパース マップが必要です。あまり効率的でない方法の 1 つは、ハッシュマップのハッシュマップを使用することです。実際、これで最初の問題も解決できます。

HashMap<String, HashMap> x = new HashMap()
HashMap<String, Tile> y = new HashMap()

// get the tile at coordinates 1,2
Tile myTile = x.get("1").get("2");

// this would work as well
myTile = x.get("-1").get("-2");

整数をキーとして取り、はるかに効率的な独自の Map 実装を行うことができます。

于 2011-03-07T22:48:01.220 に答える
0

本当に高速でスケーラブルになりたい場合は、間違いなく Sparse Octree を使用してください。

http://en.wikipedia.org/wiki/Octree

Java での実装については知りませんが、些細なことです。ノードが現在リンクされているビットフィールドを 1 バイトで格納し、リンクされたリストを使用してそれらの参照を保持します (オクツリー ノードごとに、最大 8 エントリの個別のリスト)。

于 2011-03-07T22:49:27.300 に答える