C++

Forum

 
Javascript to C++ function

vivienneanthony (73)
Hi

I'm trying to covert some code to the c++ equivalenet from java script.

I started the funcion in c++ as double PRH(unsigned int iterations,double x,double y) or should I make x,y unsigned integers.

Vivienne

The original code is below. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
//This function returns the same result for given values but should be somewhat random.
    function PRH(iterations,x,y) {
        var hash;
        x &= 0xFFF;
        y &= 0xFFF;
        iterations &= 0xFF;
        hash = (iterations << 24);
        hash |= (y << 12);
        hash |= x;
        var rem = hash & 3;
        var h = hash;

        switch (rem) {
            case 3:
                hash += h;
                hash ^= hash << 32;
                hash ^= h << 36;
                hash += hash >> 22;
                break;
            case 2:
                hash += h;
                hash ^= hash << 22;
                hash += hash >> 34;
                break;
            case 1:
                hash += h;
                hash ^= hash << 20;
                hash += hash >> 2;
        }
        hash ^= hash << 6;
        hash += hash >> 10;
        hash ^= hash << 8;
        hash += hash >> 34;
        hash ^= hash << 50;
        hash += hash >> 12;

        return (hash & 0xFFFF) / 0xFFFF;
    }
LB (13399)
Can you offer any more explanation about what that code is supposed to be doing? The comment, function name, parameters, and local variables are all completely unhelpful. The code actually looks obfuscated.
vivienneanthony (73)
I'm utilizing it http://stackoverflow.com/questions/4977946/making-the-diamond-square-fractal-algorithm-infinite

Trying to implement http://godsnotwheregodsnot.blogspot.com/2013/11/field-diamond-squared-fractal-terrain.html

The function uses a hash table or some type of calculated randomness which is fine. In my case I would love to use a 256 bit hash table (using x/y location to determine the xy has value to use for infinite terrains but for now).

Just getting the last function to work would be nice.

The full code is 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
///Headers
#include <vector>
#include <cstdio>
#include <cmath>
#include <iostream>

/// Terraub Functions
double * getFieldSquareTerrain(double x0,double y0, double x1, double y1, unsigned int interations);
double displace(unsigned int iterations,  double x, double y);
double getMaxDeviation(unsigned int iterations);
double PRH(unsigned int iterations, double x,double y);
double * getFieldDiamondSquaredMap(unsigned int x, unsigned int y, unsigned int width, unsigned int height, unsigned int iterations);


/// Main function
int main()
{
    return 1;
}

double * getFieldDiamondSquaredMap(unsigned int x, unsigned int y, unsigned int width, unsigned int height, unsigned int iterations)
{
    /// Allocate memory for final map
    double * map = new double(width*height);

    map = getFieldSquareTerrain(x, y, x+width, y+height, iterations);

    double maxdeviation = getMaxDeviation(iterations);

    for (unsigned int x = 0; x < width; x++)
    {
        for (unsigned int  y = 0; y < height; y++)
        {
            map[x*y] = map[x*y] / maxdeviation;
        }
    }
    return map;
}

double * getFieldSquareTerrain(double x0,double y0, double x1, double y1, unsigned int interations)
{
    /// Define final height and width
    double finalwidth  = x1 - x0;
    double finalheight = y1 - y0;

    /// Allocate memory for final map
    double * finalmap = new double(finalwidth*finalheight);

    /// Test interation
    if (interations == 0)
    {
        for (unsigned int x = 0; x < finalwidth; x++)
        {
            for (unsigned int y = 0; y < finalheight; y++)
            {
                finalmap[x*y] =  displace(interations,x0+x,y0+y) ;
            }
            return finalmap;
        }
    }

    /// Define upper height and width for upper maps
    double upper_x0=floor(x0/2) - 1;
    double upper_y0=floor(x0/2) - 1;
    double upper_x1=ceil(x1/2)+1;
    double upper_y1=ceil(x1/2)+1;

    double upper_xwidth= upper_x0-upper_x1;
    double upper_yheight= upper_y0-upper_y1;

    /// Allocate memory for upper map width and height

    double * uppermap = new double(upper_xwidth*upper_yheight);

    /// Pass another interation
    uppermap = getFieldSquareTerrain(upper_x0, upper_y0, upper_x1, upper_y1, interations-1);

    /// Define counter height and width
    double counterwidth = upper_xwidth*2-1;
    double counterheight = upper_yheight*2-1;

    /// Allocate memory for currentmap using counter height and width
    double * currentmap = new double(counterwidth*counterheight);

    /// Copy information to double map
    for (unsigned int x = 0; x < upper_xwidth; x++)
    {
        for (unsigned int y = 0; y< upper_yheight; y++)
        {
            currentmap[(x*2)*(y*2)] = uppermap[x*y];
        }
    }

    /// Copy actual information to returned map
    for (unsigned int x = 0; x < finalwidth; x++)
    {
        for (unsigned int y = 0; y < finalheight; y++)
        {
            finalmap[x*y] = currentmap[x*y];
        }
    }

    return finalmap;
}

/// Random function to offset
double displace(unsigned int  iterations, double x, double y)
{
    return (((PRH(iterations,x,y) - 0.5)*2)) / (iterations+1);
}

/// Get maximum deviations
double getMaxDeviation(unsigned int iterations)
{
    double dev = 0.5 / (iterations+1);
    if (iterations <= 0) return dev;
    return getMaxDeviation(iterations-1) + dev;
}

///This function returns the same result for given values but should be somewhat random.
double PRH(unsigned int iterations,double x,double y)
{
    /// work in progress
    return 1.0;
}
MiiNiPaa (8886)
s/var/unsigned long long
fix integer division at the end.
Done. http://ideone.com/Ldbp9i
Last edited on
vivienneanthony (73)
Thanks. I tweaked the code also and came out with a similiar fix. Now I have to test out the fuction.
Last edited on
MiiNiPaa (8886)
Please note that your hash and h variables have to be at least 64 bit in size. So if you are not using long long or (u)int64_t you might have hard to detect bugs.
vivienneanthony (73)
Ok
vivienneanthony (73)
Hi

This is the complete conversion of the code. Did I do the right conversion from Javascript?

The Java code is at http://stackoverflow.com/questions/4977946/making-the-diamond-square-fractal-algorithm-infinite.

Oddly. The bottom right looks closest to what the output should be overall.

http://tinypic.com/r/aaho3t/8

Vivienne

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
 
///Headers
#include <vector>
#include <cstdio>
#include <cmath>
#include <iostream>

#include <stdio.h>
#include <stdlib.h>

#include <png++/png.hpp>
#include <png++/image.hpp>
#include <png++/rgb_pixel.hpp>



using namespace std;

/// Terraub Functions
double * getFieldSquareTerrain(int x0,int y0, int x1, int y1, unsigned int iterations);
double displace(unsigned int iterations,int x, int y);
double getMaxDeviation(unsigned int iterations);
double PRH(unsigned iterations, int x, int y);
double * getFieldDiamondSquaredMap(int x, int y, int width, int height, unsigned int iterations);

//Size of the grid to generate
//This must be 2^n+1 (e.g. 257)
const int DATA_SIZE = 1024;

void SaveTerrFile(const double * image);

/// Main function
int main()
{
    /// Define Settings
    int width=1024;
    int height=1024;
    int iterations=6;
    int x=0;
    int y=0;

    // allocate memory
    double * map=new double[width*height];

    map=getFieldDiamondSquaredMap(x,y,width,height,iterations);

    SaveTerrFile(map);

    return 1;
}

double * getFieldDiamondSquaredMap(int x, int y, int width, int height, unsigned int iterations)
{
    /// Allocate memory for final mapdouble
    double * map = new double[width*height];

    map = getFieldSquareTerrain(x, y, x+width, y+height, iterations);

    double maxdeviation = getMaxDeviation(iterations);

    for (unsigned int x = 0; x < width; x++)
    {
        for (unsigned int  y = 0; y < height; y++)
        {
            map[x*y] = map[x*y] / maxdeviation;
        }
    }

    return map;
}

double * getFieldSquareTerrain(int x0, int y0, int x1, int y1, unsigned int iterations)
{
    /// Define final height and width
    int finalwidth  = x1 - x0;
    int finalheight = y1 - y0;

    /// Allocate memory for final map
    double * finalmap = new double[finalwidth*finalheight];

    /// Test iteration
    if (iterations == 0)
    {
        for (unsigned int x = 0; x < finalwidth; x++)
        {
            for (unsigned int y = 0; y < finalheight; y++)
            {
                finalmap[x*y] =  displace(iterations,x0+x,y0+y) ;
            }
            return finalmap;
        }
    }

    /// Define ceil and floor
    int upper_x0=floor(x0/2) - 1;
    int upper_y0=floor(y0/2) - 1;
    int upper_x1=ceil(x1/2)+1;
    int upper_y1=ceil(y1/2)+1;

    /// Define upper height and width for upper maps
    int upper_xwidth= upper_x1-upper_x0;
    int upper_yheight= upper_y1-upper_y0;

    /// Allocate memory for upper map width and height
    double * uppermap = new double[upper_xwidth*upper_yheight];

    /// Pass another iteration
    uppermap = getFieldSquareTerrain(upper_x0, upper_y0, upper_x1, upper_y1, iterations-1);


    /// Define counter height and width
    int counter_x0= upper_x0 * 2;
    int counter_y0= upper_y0 * 2;

    int counter_width = upper_xwidth*2-1;
    int counter_height = upper_yheight*2-1;

    /// Allocate memory for currentmap using counter height and width
    double * currentmap = new double[counter_width*counter_height];

    /// Copy information to double map
    for (unsigned int x = 0; x < upper_xwidth; x++)
    {
        for (unsigned int y = 0; y< upper_yheight; y++)
        {
            currentmap[(x*2)*(y*2)] = uppermap[x*y];
        }
    }

    /// Define offset
    int xoff = x0 - counter_x0;
    int yoff = y0 - counter_y0;


    /// Use a diamond mehod algorithm
    for (unsigned int x = 1; x < counter_width-1; x += 2)
    {
        for (unsigned int y = 1; y < counter_height-1; y += 2)
        {
            currentmap[x*y] = ((currentmap[(x - 1)*(y - 1)] + currentmap[(x - 1)*(y + 1)] + currentmap[(x + 1)*(y - 1)] + currentmap[(x + 1)*(y + 1)]) / 4) + displace(iterations,counter_x0+x,counter_y0+y);
        }
    }
    for (unsigned int x = 1; x < counter_width-1; x += 2)
    {
        for (unsigned int y = 2; y < counter_height-1; y += 2)
        {
            currentmap[x*y] = ((currentmap[(x - 1)*y]     + currentmap[(x + 1)*y]     + currentmap[x*(y - 1)]     + currentmap[x*(y + 1)]) / 4) + displace(iterations,counter_x0+x,counter_y0+y);
        }
    }
    for (unsigned int x = 2; x < counter_width-1; x += 2)
    {
        for (unsigned int y = 1; y < counter_height-1; y += 2)
        {
            currentmap[x*y] = ((currentmap[(x - 1)*y]     + currentmap[(x + 1)*y]     + currentmap[x*(y - 1)]     + currentmap[x*(y + 1)]) / 4) + displace(iterations,counter_x0+x,counter_y0+y);
        }
    }

    /// Copy actual information to returned map
    for (unsigned int x = 0; x < finalwidth; x++)
    {
        for (unsigned int y = 0; y < finalheight; y++)
        {
            finalmap[x*y] = currentmap[(x+xoff)*(y+yoff)];

        }
    }

    return finalmap;
}

/// Random function to offset
double displace(unsigned int  iterations, int x, int y)
{
    return (((PRH(iterations,x,y) - 0.5)*2)) / (iterations+1);
}

/// Get maximum deviations
double getMaxDeviation(unsigned int iterations)
{
    double dev = 0.5 / (iterations+1);
    if (iterations <= 0) return dev;
    return getMaxDeviation(iterations-1) + dev;
}

///This function returns the same result for given values but should be somewhat random.
double PRH(unsigned iterations, int x, int y)
{
    unsigned long long hash;
    x &= 0xFFF;
    y &= 0xFFF;
    iterations &= 0xFF;
    hash = (iterations << 24);
    hash |= (y << 12);
    hash |= x;
    unsigned long long rem = hash & 3;
    unsigned long long h = hash;

    switch (rem)
    {
    case 3:
        hash += h;
        hash ^= hash << 32;
        hash ^= h << 36;
        hash += hash >> 22;
        break;
    case 2:
        hash += h;
        hash ^= hash << 22;
        hash += hash >> 34;
        break;
    case 1:
        hash += h;
        hash ^= hash << 20;
        hash += hash >> 2;
    }
    hash ^= hash << 6;
    hash += hash >> 10;
    hash ^= hash << 8;
    hash += hash >> 34;
    hash ^= hash << 50;
    hash += hash >> 12;

    return (hash & 0xFFFF) / static_cast<double>(0xFFFF);
}


void SaveTerrFile(const double * image)
{
    png::image< png::rgb_pixel > newimage(1024, 1024);


    for (unsigned int y = 0; y < newimage.get_width(); ++y)
    {
        for (unsigned int x = 0; x < newimage.get_height(); ++x)
        {
            int col=(int)(image[x*y]+1)*255;
            newimage[y][x] = png::rgb_pixel(col,col,col);
            // non-checking equivalent of image.set_pixel(x, y, ...);
        }
    }

    newimage.write("rgb.png");
}
Last edited on
vivienneanthony (73)
Hey, All.

I got the code to mostly work. I still have a bug. Here is a photo http://tinypic.com/view.php?pic=oistxi&s=8#.VBj92a1hWio

The results is suppose to be like http://tatarize.nfshost.com/FieldDiamondSquare.htm

I am hoping someone can pick on the problem because I don't see the problem right now. Hmm.


The code is
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
 
///Headers
#include <vector>
#include <cstdio>
#include <cmath>
#include <iostream>

#include <stdio.h>
#include <stdlib.h>

#include <png++/png.hpp>
#include <png++/image.hpp>
#include <png++/rgb_pixel.hpp>

using namespace std;

/// Terraub Functions
double * getFieldSquareTerrain(int x0,int y0, int x1, int y1, double iterations);
double displace(double iterations,int x, int y);
double getMaxDeviation(double iterations);
double PRH(unsigned iterations, int x, int y);
double * getFieldDiamondSquaredMap(int x, int y, int width, int height, double iterations);

//Size of the grid to generate
//This must be 2^n+1 (e.g. 257)
const int DATA_SIZE = 1024;

void SaveTerrFile(const double * image);

/// Main function
int main()
{
    /// Define Settings
    int width=1024;
    int height=1024;
    double iterations=12.0f;
    int x=0;
    int y=0;

    // allocate memory
    double * map=new double[width*height];

    map=getFieldDiamondSquaredMap(x,y,width,height,iterations);

    SaveTerrFile(map);

    return 1;
}

double * getFieldDiamondSquaredMap(int x, int y, int width, int height, double iterations)
{
    /// Allocate memory for final mapdouble
    double * map = new double[width*height];

    map = getFieldSquareTerrain(x, y, x+width, y+height, iterations);

    double maxdeviation = getMaxDeviation(iterations);

    for (unsigned int x = 0; x < width; x++)
    {
        for (unsigned int  y = 0; y < height; y++)
        {
            map[x+(y*width)] = map[x+(y*width)] / maxdeviation;
        }
    }

    return map;
}

double * getFieldSquareTerrain(int x0, int y0, int x1, int y1, double iterations)
{
    /// Define final height and width
    int finalwidth  = x1 - x0;
    int finalheight = y1 - y0;

    /// Allocate memory for final map
    double * finalmap = new double[finalwidth*finalheight];

    /// Test iteration
    if (iterations == 0)
    {
        for (unsigned int x = 0; x < finalwidth; x++)
        {
            for (unsigned int y = 0; y < finalheight; y++)
            {
                finalmap[x+(y*finalwidth)] =  displace(iterations,x0+x,y0+y) ;
            }
            return finalmap;
        }
    }

    /// Define ceil and floor
    int upper_x0=floor(x0/2) - 1;
    int upper_y0=floor(y0/2) - 1;
    int upper_x1=ceil(x1/2)+1;
    int upper_y1=ceil(y1/2)+1;

    /// Define upper height and width for upper maps
    int upper_xwidth= upper_x1-upper_x0;
    int upper_yheight= upper_y1-upper_y0;

    /// Allocate memory for upper map width and height
    double * uppermap = new double[upper_xwidth*upper_yheight];

    /// Pass another iteration
    uppermap = getFieldSquareTerrain(upper_x0, upper_y0, upper_x1, upper_y1, iterations-1);

    /// Define counter height and width
    int counter_x0= upper_x0 * 2;
    int counter_y0= upper_y0 * 2;

    int counter_width = upper_xwidth*2-1;
    int counter_height = upper_yheight*2-1;

    /// Allocate memory for currentmap using counter height and width
    double * currentmap = new double[counter_width*counter_height];

    /// Copy information to double map
    for (unsigned int x = 0; x < upper_xwidth; x++)
    {
        for (unsigned int y = 0; y< upper_yheight; y++)
        {
            currentmap[(x*2)+((y*counter_width)*2)] = uppermap[x+(y*upper_xwidth)];
        }
    }

    /// Define offset
    int xoff = x0 - counter_x0;
    int yoff = y0 - counter_y0;

    /// Use a diamond mehod algorithm
    for (unsigned int x = 1; x < counter_width-1; x += 2)
    {
        for (unsigned int y = 1; y < counter_height-1; y += 2)
        {
            currentmap[x+(y*counter_width)] = ((currentmap[(x - 1)+((y-1)*counter_width)] + currentmap[(x - 1)+((y+1)*counter_width)] + currentmap[(x + 1)+((y-1)*counter_width)] + currentmap[(x + 1)+((y+1)*counter_width)]) / 4) + displace(iterations,counter_x0+x,counter_y0+y);
        }
    }
    for (unsigned int x = 1; x < counter_width-1; x += 2)
    {
        for (unsigned int y = 2; y < counter_height-1; y += 2)
        {
            currentmap[x+(y*counter_width)] = ((currentmap[(x - 1)+(y*counter_width)]     + currentmap[(x + 1)+(y*counter_width)]     + currentmap[x+((y-1)*counter_width)]     + currentmap[x+((y+1)*counter_width)]) / 4) + displace(iterations,counter_x0+x,counter_y0+y);
        }
    }
    for (unsigned int x = 2; x < counter_width-1; x += 2)
    {
        for (unsigned int y = 1; y < counter_height-1; y += 2)
        {
            currentmap[x+(y*counter_width)] = ((currentmap[(x - 1)+(y*counter_width)]     + currentmap[(x + 1)+(y*counter_width)]     + currentmap[x+((y-1)*counter_width)]     + currentmap[x+((y+1)*counter_width) ]) / 4) + displace(iterations,counter_x0+x,counter_y0+y);
        }
    }

    /// Copy actual information to returned map
    for (unsigned int x = 0; x < finalwidth; x++)
    {
        for (unsigned int y = 0; y < finalheight; y++)
        {
            finalmap[x+(y*finalwidth)] = currentmap[(x+xoff)+((y+yoff)*counter_width)];

        }
    }

    return finalmap;
}

/// Random function to offset
double displace(double iterations,int x, int y)
{
    return (((PRH(iterations,x,y) - 0.5)*2)) / (iterations+1);
}

/// Get maximum deviations
double getMaxDeviation(double iterations)
{
    double dev = 0.5 / (iterations+1);
    if (iterations <= 0) return dev;
    return getMaxDeviation(iterations-1) + dev;
}

///This function returns the same result for given values but should be somewhat random.
double PRH(unsigned iterations, int x, int y)
{
    unsigned long long hash;
    x &= 0xFFF;
    y &= 0xFFF;
    iterations &= 0xFF;
    hash = (iterations << 24);
    hash |= (y << 12);
    hash |= x;
    unsigned long long rem = hash & 3;
    unsigned long long h = hash;

    switch (rem)
    {
    case 3:
        hash += h;
        hash ^= hash << 32;
        hash ^= h << 36;
        hash += hash >> 22;
        break;
    case 2:
        hash += h;
        hash ^= hash << 22;
        hash += hash >> 34;
        break;
    case 1:
        hash += h;
        hash ^= hash << 20;
        hash += hash >> 2;
    }
    hash ^= hash << 6;
    hash += hash >> 10;
    hash ^= hash << 8;
    hash += hash >> 34;
    hash ^= hash << 50;
    hash += hash >> 12;

    return (hash & 0xFFFF) / static_cast<double>(0xFFFF);
}


void SaveTerrFile(const double * image)
{
    png::image< png::rgb_pixel > newimage(1024, 1024);



    for (unsigned int y = 0; y < newimage.get_width(); ++y)
    {
        for (unsigned int x = 0; x < newimage.get_height(); ++x)
        {
            int col=(int)(image[x+(y*newimage.get_width())]+1)*255;
            newimage[y][x] = png::rgb_pixel(col,col,col);
            // non-checking equivalent of image.set_pixel(x, y, ...);
        }
    }

    newimage.write("rgb.png");
}
helios (17506)
Wow, that code leaks memory like crazy. There isn't a single deallocation.

Could you post two images generated from the same seed?
vivienneanthony (73)
I'll add the deallocation later actually today before I forget. Yes. I'll post two pics.

Pic 1 - Interation 32
http://tinypic.com/r/aaho3t/8

Pice 2 - Interation 48
http://tinypic.com/r/2pyulxd/8
Last edited on
vivienneanthony (73)
This is a modification. I converted of final image to range to 0 to 1, then muiltiplied that to 255. Which gets better results but.

I rather the final image to be 0 and above only, no negative before saving without extra processing. I'm assuming the floor and ceil has to be changed???

Image produced from this method http://tinypic.com/r/2rr2cqt/8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
 
///Headers
#include <vector>
#include <cstdio>
#include <cmath>
#include <iostream>

#include <stdio.h>
#include <stdlib.h>

#include <png++/png.hpp>
#include <png++/image.hpp>
#include <png++/rgb_pixel.hpp>

using namespace std;

/// Terraub Functions
double * getFieldSquareTerrain(int x0,int y0, int x1, int y1, double iterations);
double displace(double iterations,int x, int y);
double getMaxDeviation(double iterations);
double PRH(unsigned iterations, int x, int y);
double * getFieldDiamondSquaredMap(int x, int y, int width, int height, double iterations);

//Size of the grid to generate
//This must be 2^n+1 (e.g. 257)
const int DATA_SIZE = 1024;

void SaveTerrFile(const double * image);

/// Main function
int main()
{
    /// Define Settings
    int width=1024;
    int height=1024;
    double iterations=52.0f;
    int x=0;
    int y=0;

    // allocate memory
    double * map=new double[width*height];

    map=getFieldDiamondSquaredMap(x,y,width,height,iterations);

    /// Set maxY and minY to 0.0f
    double maxY = map[2];
    double minY = map[2];

    for (int x = 0; x<width; x++)
    {
        for(int y = 0; y<height; y++)
        {
            if ((double)map[x+(y*width)] > maxY)
            {
                maxY = map[x+(y*width)];
            }
            if ((double)map[x+(y*width)] < minY)
            {
                minY = map[x+(y*width)];
            }
        }
    }

    /// Calculate height_ from 0 to 1
    for(int x=0; x < width; x++)
    {
        for(int y=0; y < height; y++)
        {
            //change range to 0..1
            map[x+(y*width)]  = (map[x+(y*width)] - minY) / (maxY - minY);


        }
    }

    SaveTerrFile(map);

    return 1;
}

double * getFieldDiamondSquaredMap(int x, int y, int width, int height, double iterations)
{
    /// Allocate memory for final mapdouble
    double * map = new double[width*height];

    map = getFieldSquareTerrain(x, y, x+width, y+height, iterations);

    double maxdeviation = getMaxDeviation(iterations);

    for (unsigned int x = 0; x < width; x++)
    {
        for (unsigned int  y = 0; y < height; y++)
        {
            map[x+(y*width)] = map[x+(y*width)] / maxdeviation;

        }
    }

    return map;
}

double * getFieldSquareTerrain(int x0, int y0, int x1, int y1, double iterations)
{
    /// Define final height and width
    int finalwidth  = x1 - x0;
    int finalheight = y1 - y0;

    /// Allocate memory for final map
    double * finalmap = new double[finalwidth*finalheight];

    /// Test iteration
    if (iterations == 0)
    {
        for (unsigned int x = 0; x < finalwidth; x++)
        {
            for (unsigned int y = 0; y < finalheight; y++)
            {
                finalmap[x+(y*finalwidth)] =  displace(iterations,x0+x,y0+y) ;
            }
            return finalmap;
        }
    }

    /// Define ceil and floor
    int upper_x0=floor(x0/2) - 1;
    int upper_y0=floor(y0/2) - 1;
    int upper_x1=ceil(x1/2)+1;
    int upper_y1=ceil(y1/2)+1;

    /// Define upper height and width for upper maps
    int upper_xwidth= upper_x1-upper_x0;
    int upper_yheight= upper_y1-upper_y0;

    /// Allocate memory for upper map width and height
    double * uppermap = new double[upper_xwidth*upper_yheight];

    /// Pass another iteration
    uppermap = getFieldSquareTerrain(upper_x0, upper_y0, upper_x1, upper_y1, iterations-1);

    /// Define counter height and width
    int counter_x0= upper_x0 * 2;
    int counter_y0= upper_y0 * 2;

    int counter_width = upper_xwidth*2-1;
    int counter_height = upper_yheight*2-1;

    /// Allocate memory for currentmap using counter height and width
    double * currentmap = new double[counter_width*counter_height];

    /// Copy information to double map
    for (unsigned int x = 0; x < upper_xwidth; x++)
    {
        for (unsigned int y = 0; y< upper_yheight; y++)
        {
            currentmap[(x*2)+((y*counter_width)*2)] = uppermap[x+(y*upper_xwidth)];
        }
    }

    /// Define offset
    int xoff = x0 - counter_x0;
    int yoff = y0 - counter_y0;

    /// Use a diamond mehod algorithm
    for (unsigned int x = 1; x < counter_width-1; x += 2)
    {
        for (unsigned int y = 1; y < counter_height-1; y += 2)
        {
            currentmap[x+(y*counter_width)] = ((currentmap[(x - 1)+((y-1)*counter_width)] + currentmap[(x - 1)+((y+1)*counter_width)] + currentmap[(x + 1)+((y-1)*counter_width)] + currentmap[(x + 1)+((y+1)*counter_width)]) / 4) + displace(iterations,counter_x0+x,counter_y0+y);
        }
    }
    for (unsigned int x = 1; x < counter_width-1; x += 2)
    {
        for (unsigned int y = 2; y < counter_height-1; y += 2)
        {
            currentmap[x+(y*counter_width)] = ((currentmap[(x - 1)+(y*counter_width)]     + currentmap[(x + 1)+(y*counter_width)]     + currentmap[x+((y-1)*counter_width)]     + currentmap[x+((y+1)*counter_width)]) / 4) + displace(iterations,counter_x0+x,counter_y0+y);
        }
    }
    for (unsigned int x = 2; x < counter_width-1; x += 2)
    {
        for (unsigned int y = 1; y < counter_height-1; y += 2)
        {
            currentmap[x+(y*counter_width)] = ((currentmap[(x - 1)+(y*counter_width)]     + currentmap[(x + 1)+(y*counter_width)]     + currentmap[x+((y-1)*counter_width)]     + currentmap[x+((y+1)*counter_width) ]) / 4) + displace(iterations,counter_x0+x,counter_y0+y);
        }
    }

    /// Copy actual information to returned map
    for (unsigned int x = 0; x < finalwidth; x++)
    {
        for (unsigned int y = 0; y < finalheight; y++)
        {
            finalmap[x+(y*finalwidth)] = currentmap[(x+xoff)+((y+yoff)*counter_width)];

        }
    }

    /// Clear Memory
    delete currentmap;
    delete uppermap;

    return finalmap;
}

/// Random function to offset
double displace(double iterations,int x, int y)
{
    return (((PRH(iterations,x,y) - 0.5)*2)) / (iterations+1);
}

/// Get maximum deviations
double getMaxDeviation(double iterations)
{
    double dev = 0.5 / (iterations+1);
    if (iterations <= 0) return dev;
    return getMaxDeviation(iterations-1) + dev;
}

///This function returns the same result for given values but should be somewhat random.
double PRH(unsigned iterations, int x, int y)
{
    unsigned long long hash;
    x &= 0xFFF;
    y &= 0xFFF;
    iterations &= 0xFF;
    hash = (iterations << 24);
    hash |= (y << 12);
    hash |= x;
    unsigned long long rem = hash & 3;
    unsigned long long h = hash;

    switch (rem)
    {
    case 3:
        hash += h;
        hash ^= hash << 32;
        hash ^= h << 36;
        hash += hash >> 22;
        break;
    case 2:
        hash += h;
        hash ^= hash << 22;
        hash += hash >> 34;
        break;
    case 1:
        hash += h;
        hash ^= hash << 20;
        hash += hash >> 2;
    }
    hash ^= hash << 6;
    hash += hash >> 10;
    hash ^= hash << 8;
    hash += hash >> 34;
    hash ^= hash << 50;
    hash += hash >> 12;

    return (hash & 0xFFFF) / static_cast<double>(0xFFFF);
}

void SaveTerrFile(const double * image)
{
    png::image< png::rgb_pixel > newimage(1024, 1024);

    for (unsigned int y = 0; y < newimage.get_width(); ++y)
    {
        for (unsigned int x = 0; x < newimage.get_height(); ++x)
        {
            int col = int(image[x+(y*newimage.get_width())]*255);
            newimage[y][x] = png::rgb_pixel(col,col,col);
            // non-checking equivalent of image.set_pixel(x, y, ...);
        }
    }

    newimage.write("rgb.png");
}


Last edited on
helios (17506)
No, I mean, generate two otherwise identical images that show clearly the difference.
vivienneanthony (73)
Code 1 (Code without the memory deallocation but original problem)
http://tinypic.com/r/v748d5/8

Code 2 (Code that scale the array of doubles to a value from 0 to 1 then multiplied 255 to get a rgb)
http://tinypic.com/r/ftj4f5/8

Javascript demonstration of what it should be close to
http://tatarize.nfshost.com/FieldDiamondSquare.htm
Last edited on
MiiNiPaa (8886)
hash |= (y << 12);!!!
it would change only lower 32 bits, because both y and 12 have a type int and presumably 32 bit long. Change 12 to 12ull and change type of input parameters to unsigned long long too, just to be safe.

Edit: on second thought this is not the case. First lines makes value to not exceed its syze in bytes. However there could be funny things related to a sign bit, so do this anyway.
Last edited on
vivienneanthony (73)
I don't know. I'll look at it later. I feel like ditching that bitwise manipulation code but I want it to get to the original function first.
Topic archived. No new replies allowed.