diamond square algorithm で地形生成

rcursion（再帰プログラム）の練習のためにjavaで地形生成するプログラムを書いています。

2Dの配列にランダムで生成した値を入れる段階で苦戦しています。

ダイアモンドスクエアアルゴリズムという方法を使いたいのですが、全くわかりません。

プログラムの構造なのですが、ユーザーに四隅の値（地形の高さ）を入力させます。（画像で左端の段階）
そのあと、四隅の平均の値が真ん中。（画像で左から2番目の段階）
両端の平均の値が４辺の中心の値。（画像で左から3番目の段階）
という風に値が決まっていきます。

この時点で小さい正方形がもう一度できたので、同じことを繰り返す。

というようなプログラムを書きたいのです。

java
1getTopLeft(), getTopRight(),getBottomLeft(), getBottomRight()

は、それぞれ四隅の値を所得するメソッドで

java
1private HeightShifter shift;

は、配列に高さを入れるためのクラスのオブジェクトで、

java
1public double randShift(double origVal)

というメソッドを持っています。

今の所、recursionを使用する箇所のプログラムはこんな感じです↓

java
1public boolean generateTerrain()
2	{
3		return generateTerrainHelper(getTopLeft(), getTopRight(),
4				getBottomLeft(), getBottomRight(), 0);
5	}
6
7public boolean generateTerrainHelper(double topLeft, double topRight,
8			double bottomLeft, double bottomRight, int counter)
9	{
10		//Base Case (Arrayのindexが隣同士)
11		
12		//General Case1  (四角の値をとる場合)
13		//Middle
14		shift.randShift(map[(counter + map.length) / 2][(counter + map.length) / 2] 
15				= (topLeft + topRight + bottomLeft + bottomRight) / 4);
16	
17		//General Case2 （2つの間の値をとる場合）　
18		return false;
19	}

常に四隅の値を返したりする事でどうにかできないかなぁ、と考えたりしたのですが、良い方法が浮かびませんでした。

お力添えをお願いします。

行動規範の内容に同意します

回答1件

以下のようなコードで実現できます。解説については、コード内のコメントをご参照ください。

Java
1import java.util.*;
2
3public class Main {
4
5    public static void main(String[] args) throws Exception {
6
7        //生成
8        double[][] map = generateTerrain(getTopLeft(),
9                                         getTopRight(),
10                                         getBottomLeft(),
11                                         getBottomRight(),
12                                         5);
13        
14        //出力
15        for(int x = 0; x < map.length; x++){
16            for(int y = 0; y < map.length; y++){
17                System.out.printf("%.2f\t", map[y][x]);
18            }
19            System.out.print("\n");
20        }
21        
22    }
23    
24    private static double getTopLeft(){
25        return 350.0;
26    }
27    
28    private static double getTopRight(){
29        return 120.0;
30    }
31    
32    private static double getBottomLeft(){
33        return 100.0;
34    }
35    
36    private static double getBottomRight(){
37        return 200.0;
38    }
39    
40    public static double[][] generateTerrain(double topLeftValue,
41                                          double topRightValue,
42                                          double bottomLeftValue,
43                                          double bottomRightValue,
44                                          int length){
45        //length*lengthの2次元配列を生成する
46        double[][] map = new double[length][length];
47        
48        //4つの頂点の値を設定する
49        map[0][0] = topLeftValue;
50        map[0][length - 1] = topRightValue;
51        map[length - 1][0] = bottomLeftValue;
52        map[length - 1][length - 1] = bottomRightValue;
53        
54        //再帰処理により、各点の値を求める
55        generateTerrainHelper(0, length - 1, 0, length - 1, map);
56        
57        return map;
58    }
59    
60    
61    private static void generateTerrainHelper(int leftIndex,
62                                              int rightIndex,
63                                              int topIndex,
64                                              int bottomIndex,
65                                              double[][] map){
66                                                  
67                                                  
68        //4つの頂点の値を取得する
69        double topLeftValue = map[topIndex][leftIndex];         //左上の頂点の値
70        double topRightValue = map[topIndex][rightIndex];       //右上の頂点の値
71        double bottomLeftValue = map[bottomIndex][leftIndex];   //左下の頂点の値
72        double bottomRightValue = map[bottomIndex][rightIndex]; //右下の頂点の値
73        
74        //正方形の中心の値を設定する
75        int centerXIndex = (leftIndex + rightIndex) / 2;
76        int centerYIndex = (topIndex + bottomIndex) / 2;
77        double centerValue = (topLeftValue + topRightValue + bottomLeftValue + bottomRightValue) / 4;
78        
79        map[centerYIndex][centerXIndex] = centerValue;
80        
81        //4辺の中心値を設定する
82        //上辺中心
83        double topSideValue = (topLeftValue + topRightValue) / 2.0;
84        map[topIndex][centerXIndex] = topSideValue;
85        
86        //左辺中心
87        double leftSideValue = (topLeftValue + bottomLeftValue) / 2.0;
88        map[centerYIndex][leftIndex] = leftSideValue;
89        
90        //右辺中心
91        double rightSideValue = (topRightValue + bottomRightValue) / 2.0;
92        map[centerYIndex][rightIndex] = rightSideValue;
93        
94        //下辺中心
95        double bottomSideValue = (bottomLeftValue + bottomRightValue) / 2.0;
96        map[bottomIndex][centerXIndex] = bottomSideValue;
97        
98        
99        //現在の四角形の大きさを取得する
100        int squareSize = rightIndex - leftIndex;
101        
102        //一回り小さい四角形の一辺の長さを取得する
103        int innerSquareSize = squareSize / 2;
104        
105        //もし一回り小さい四角形の大きさが1（点4つからなる四角形）なら、処理を中断する
106        if(innerSquareSize <= 1){
107            return;
108        }
109        
110        //現在処理している四角形より
111        //一回り小さい4つの四角形に対して、同様の処理を行う
112        for(int x = 0; x < 2; x++){
113            for(int y = 0; y < 2; y++){
114                int innerLeftIndex = leftIndex + innerSquareSize * x;
115                int innerRightIndex = leftIndex + innerSquareSize * (x + 1);
116                int innerTopIndex = topIndex + innerSquareSize * y;
117                int innerBottomIndex = topIndex + innerSquareSize * (y + 1);
118                generateTerrainHelper(innerLeftIndex,
119                                      innerRightIndex,
120                                      innerTopIndex,
121                                      innerBottomIndex,
122                                      map);
123            }
124        }
125        
126    }
127    
128}

//出力結果
350.00	287.50	225.00	162.50	100.00	
292.50	250.63	208.75	166.88	125.00	
235.00	213.75	192.50	171.25	150.00	
177.50	176.88	176.25	175.63	175.00	
120.00	140.00	160.00	180.00	200.00

補足

質問文中では、配列に高さを設定するHeightShifterクラスを作成していましたが、これはダイアモンドスクエアアルゴリズムと本質的には関係ないため、省いています。
上記コードのgenerateTerrain()のlengthには、2^N+1 （N:自然数）が設定されることを想定しています。（lengthが2^N+1でないと、中心をとる操作が途中でできなくなるため。）
今回、再帰処理をやめる判定は、現在処理している四角形の大きさで行っています。予め、generateTerrain()のlengthから再帰処理を行う回数を計算することにより、質問文にあるような、カウンターを用いた判定を行うこともできます。

投稿2018/10/22 15:29