2Dグリッドグリッドを小さなグリッドに分割するアルゴリズム

Question

私は、JavaのArrayListsを使用して2Dグリッドを構築しており、グリッドを所定の数の小さなグリッドに分割したいと考えています。

私が取り組んでいる作業は、複数のサーバーにゲームマップを配布するためのシミュレータを開発することです。そのため、小さなマップをサーバーに分割する必要があります。

私は実際には2つの質問を持っていますが、最初にXでY矩形（マップ）とNに分割する部分が与えられます、どのようにNを小さく（しかし、長方形。

第2に、上記の方法論を2Dアーリーリストの観点でどのように実装するかについての提案がありがたいです。

Answer 1

nが正方形である場合は、各方向のsqrt（n）スライスに切断してグリッドを分割できます。さもなければ、水平な縞模様がうまくいくでしょう（もし作品全体の形が似ていないということが問題でないならば）。シェイプを合理的に保つことが重要ですが、グリッド全体から開始し、必要な数のピースが得られるまで最大のピースを半分に分割し続けるアルゴリズムを検討してください。

グリッドのスライスを切り捨てる場合、2D ArrayListとすれば、List<List<?>>を意味します。ここで、list.get(x).get(y)は（x、y）の項目です。次に、あなただけの両方向にsubList()を使用することができます。

List<List<?>> split(List<List<?>> in, int x1, int y1, int x2, int y2) { 
    List<List<?>> out = new ArrayList<List<?>>(w); 
    for(List<?> column : in.sublist(x1, x2)) { 
     out.add(column.subList(y1, y2)); 
    } 
    return out; 
} 

List<List<List<?>>> partitionEqualAspect(List<List<?>> grid, int n) { 
    int w = grid.size(); 
    int h = grid.get(0).size(); 
    int cols = (int)(sqrt(n) + .5); 

    // This many columns have (cols - 1) rows 
    int shortCols = Math.max(0, cols * cols - n); 
    // This many columns have (cols + 1) rows 
    int longCols = Math.max(0, n - cols * cols); 

    List<List<List<?>>> tiles = new ArrayList<List<List<?>>>(); 
    for(int c = 0; c < cols; ++c) { 
     int rows = cols + (c < shortCols ? -1 : c >= cols - longCols ? 1 : 0); 
     for(int r = 0; r < rows; ++r) { 
     tiles.add(split(grid, 
         w * c/cols, h * r/rows, 
         w * (c + 1)/cols, h * (r + 1)/rows)); 
     } 
    } 
    return tiles; 
} 

注ここで作成したグリッド・スライスが元のグリッドへの参照やスライスへの変更は、フルグリッドに反映されること。代わりに、これを避けたい場合は、すべてのコピーを作成することができます。同じ面積のN小さな長方形にX-によって-Yの四角形を分割する上で最初の質問に答える

Answer 2

...

私は最善のアプローチは、それぞれ維持するN個のサブrectsで四角形を分割することだと思いますメインのrectと同じアスペクト比。

NはSQRT（N）は積分答えが得られるようなものであるべきである（例えばN = 36を、SQRT（N）= 6）。したがって、X-Yは、sqrt（N） -by-sqrt（N）サブレールに細分されています。サブRECTサイズ（XS、イースは）それほどのように計算されます。

のX = X/SQRT（N）

イース= Y/SQRT（N）が

このアプローチは常にあなたを与えるだろうN sqrt（N）が整数値である限り、同等の部分矩形です。 Nの値に応じて、整数の切り捨て誤差を補正する必要があるかもしれません。これは、いくつかのサブレットを少し大きくしてメインの長方形全体を完全に覆うようにします。

メイン矩形の面積をNで除算し、その結果の平方根をM-by-Mとすると、それよりも粗い上記のアプローチ。