3

I need some clever and rather simple solution to my problem - province shape generation. Suppose that map is matrix NxM. Each cell is represented by natural number. 0 means that tile does not belong to any province. numbers 1 means that it belongs to province nr 1, nr 2 means that cell belongs to province nr 2... etc.

Consider this map, which is 4x4:

0000
0000
0000
0000

This map represents 16 tiles that do not belong to any province.

This is map containing 1 province:

0010
0111
0100
0000

this is province of size 5, and id = 1. It has no neighbours.

Consider 3 provinces:

1133
2100
2200
2000

So province 1 is neighbour of 2 and 3. Province 3 is only neighbour of 1 and province 2 is only neighbour of 1. There are also 7 not associated tiles.

My problem is: I want to generate k provinces on map NxN. There are also few simple rules:

  • there is max size of province and min size of province (for example min = 2, max = 10)
  • all tiles of province should be connected (by vertical or horizontal, but not corners)

Example of invalid province (it's not connected):

1100
0000
0011
0000
  • there should not be enclaves (province inside province)
  • shapes should be random

I was trying to implement it by flood fill modification but it has some disadvantages. I'll be glad to hear some ideas or any help. Map's can be 300x300 with 200 provinces or more so it should be also some clever algorithm.

4

3 に答える 3

5

ボロノイ図の使用

これは可能なすべてのマップを生成するわけではありませんが、ほとんどの「合理的な」マップを生成すると思います。

ボロノイ図は、選択した点への近さに応じて平面を分割することで構成されます。タイトルのウィキペディアのリンクで例を見ることができます。

アルゴリズム：

1) 希望するプロヴィンス数以上のランダム ポイントのセットを選択します。必要以上に生成すると、空のスペースが保証されます。

代替テキスト

2) ボロノイ アルゴリズムを実行します (興味があれば説明しますが、Web で簡単に見つけることができます)。

代替テキスト

3) 結果のポリゴンの面積を計算する

4) 十分な表面積があることを確認してください > (必要な最小面積)。そうでない場合は、1 へ

5) 必要以上のランダム ポイントを生成した場合は、面積 > (最小面積) のポリゴンから各州を構成するポリゴンのセットをランダムに選択します。

6) ポリゴンの面積が < (最大面積) かどうかを確認します。そうでない場合は、それらを減らす必要があります。

7) 各ポリゴンの面積を小さくするには

  • 一方面積 > (最大面積)
    • ポリゴン境界を見つける
    • ポリゴン境界からランダム ポイントを削除する

ところで、上記のグラフを取得するためにMathematicaでこのプログラムを作成しました。

 Clear["Global`*"];
 Needs["ComputationalGeometry`"];
 data2D = Table[{RandomReal[16], RandomReal[16]}, {10}]
 convexhull = ConvexHull[data2D]
 (delval = DelaunayTriangulation[data2D]) // Shallow[#, {5, 6}] &
 b1 = {{0, 0}, {16, 0}, {16, 16}, {0, 16}};
 {diagvert1, diagval1} = BoundedDiagram[b1, data2D, delval, convexhull];
 Show[{Graphics[Join[{PointSize[Large]}, {Point@data2D}], Frame -> True]}]
 Show[{Graphics@Point[data2D],   DiagramPlot[data2D, diagvert1, diagval1]}]

適切なツールを使用してアルゴリズムを簡単に実装できることを示すために、コードを含めます。

注：アルゴリズムの説明では、領域が正方形で構成されているとは言及されていません...

HTH

于 2010-11-01T15:08:14.960 に答える
2

時間はほとんどありませんが、良いアイデアは、最初に左から右に、次に右から左に州を追加することです。好き

 1111222
 3333322
 3344555        
 0000665

乱数を書きました。正しいですか？

void insert(Matrix matrix){
    lastProvince=0;
    missingProvince=MIN;
    if(matrix.dimensio<MIN*K) throw new RuntimeException("Matrix too small");
    for(y=0;y<matrix.height;y++){
        if(y%2==0){
            for(x=0;x<matrix.width;x++){
                matrix[x][y]=lastProvince;
                missingProvince--;
                if(missingProvince==0) {
                    lastProvince++;
                    missingProvince=MIN;
                }
                if(lastProvince==k) return;
            }
        }else{
            for(x=matrix.width;x>=0;x--){// is -- not ++
                matrix[x][y]=lastProvince;
                missingProvince--;
                if(missingProvince==0) {
                    lastProvince++;
                    missingProvince=MIN;
                }
                if(lastProvince==k) return;
            }
         }
   }
}

テストされていませんが、それがアイデアです。

于 2010-11-01T12:53:47.507 に答える
2

頭のてっぺんから：

  1. 必要なプロヴィンスごとに「シード」を生成します。マップと L 個の州がNxMあり、範囲内で L 個の一意の乱数を生成するだけです[0-(N*M-1)]。X,Y番号付きのシードの座標PはP/MとP%Mです。

  2. すべてのプロヴィンスが最小サイズよりも大きく、最大サイズよりも小さくなるまで:

    を。まだ成長できるランダムなプロヴィンスを選択します (サイズが最大より小さい、他のプロヴィンスに完全に囲まれていない)

    b. どのプロヴィンスにも属さないランダムな隣接セルをそのプロヴィンスに追加します。

この手法ではエンクレーブが発生する可能性はわずかですが、非常に低いです。ステップ b を拡張してそれらをチェックし、成長によって作成される場合は成長しないようにすることができます。

プロヴィンス自体が十分に大きくなる前に、他のプロヴィンスに完全に囲まれてしまうと、プロヴィンスが小さすぎるままになる可能性もあります。ステップ 2 が完了した後で、それを確認して調整できます。

于 2010-11-01T13:26:42.967 に答える