 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I'm working on an implementation of the Diamond-Square algorithm, and it seems
to be working... sort of, but for two things.
First, I'm getting seriously large pixel values. I've been trying to clamp them
between 0 and 255 inclusive, but it's not working the way I hoped it would.
Second my random number function. (I've attached the source file, but I'll
reiterate the function here) I'm using the rand() function from cstdlib:
double Random(double r)
{
double rNum;
rNum = r - (2*r)/(rand()%65535);
return rNum;
}
theoretically, this should generate a random number between -r and r, but I'm
only getting positive values within a small range. reducing the range of random
values to 100 or less seems to generate more negative numbers but problems
persist.
At the moment, the largest problem seems to be clamping the values.
the code outputs the result to a pgm file with a depth of 8 bits
changing the range multiplier seems to have some interesting effects, but I'm
not sure I like the results.
Any help would be appreciated.
A.D.B.
Code follows:
/******************************************************
* Name: Main.cpp Date: Aug. 21, 2010 *
* *
* Auth: Anthony D. Baye *
* Desc: basic implementation of the Diamond-Square *
* Algorithm. *
* *
******************************************************/
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <fstream>
#include <cmath>
#include "grids.h"
using namespace std;
double Random(double);
void seedGrid(grid<double> &, int);
void diamond_square(grid<double> &);
void print(grid<double>);
void save(grid<double>);
int main(int argc, char** argv)
{
unsigned long int height, width;
grid<double> canvas;
srand(65535);
height = strtoul(argv[0],NULL,0);
width = strtoul(argv[1],NULL,0);
canvas.create(width, width);
/*
canvas.at(0,0) = 25;
canvas.at(canvas.width()-1, 0) = 25;
canvas.at(0, canvas.height()-1) = 25;
canvas.at(canvas.width()-1, canvas.height()-1) = 255;
*/
// seedGrid(canvas, 30);
diamond_square(canvas);
save(canvas);
return 0;
}
double Random(double r)
{
double rNum;
int n = rand()%100;
if(n == 0)
n++;
rNum = r - ((2*r)/n);
// cout << rNum << " " << n << endl;
return rNum;
}
void seedGrid(grid<double> &canvas, int N)
{
int x, y;
while(N > 0)
{
x = int(Random(1.0)*canvas.width() + 0.5);
y = int(Random(1.0)*canvas.height() + 0.5);
if(x > canvas.width())
x = canvas.width();
if(x < 0)
x = 0;
if(y > canvas.height())
y = canvas.height();
if(y < 0)
y = 0;
canvas.at(y,x) = Random(1.0)*255;
N--;
}
}
void diamond_square(grid<double> &canvas)
{
int sLen = canvas.width();
int hS = sLen / 2;
unsigned long int x, y;
double avg, range;
srand(time(NULL));
range = 1.0;
while(sLen >= 2)
{
int hS = sLen / 2;
for(y = 0; y < canvas.height()-1; y+=sLen)
{
for(x = 0; x < canvas.width()-1; x+=sLen)
{
avg =
canvas.at(y,x) +
canvas.at(y,x+sLen) +
canvas.at(y+sLen,x+sLen) +
canvas.at(y+sLen,x);
avg /= 4;
canvas.at(y+hS, x+hS) = avg + Random(range)*255;
}
}
for(y = 0; y < canvas.height()-1; y+=hS)
{
for(x = (y+hS)%sLen; x < canvas.width()-1; x+=sLen)
{
avg =
canvas.at(y,(x+hS)%canvas.width()) +
canvas.at(y,(x-hS+canvas.width())%canvas.width()) +
canvas.at((y+hS)%canvas.height(),x) +
canvas.at((y-hS+canvas.height())%canvas.height(),x);
avg /= 4;
canvas.at(y,x) = avg + Random(range)*255;
}
}
sLen /= 2;
range /= 2;
}
}
void print(grid<double> canvas)
{
int x, y;
for(y=0; y<canvas.height(); y++)
{
for(x=0; x<canvas.width(); x++)
{
cout << setw(3) << right << canvas.at(y,x) <<
setw(2) << ", ";
}
cout << endl;
}
}
void save(grid<double> canvas)
{
int x, y;
fstream fout;
fout.open("lscape.pgm", ios::out);
fout << "P2" << endl;
fout << canvas.width() << endl;
fout << canvas.height() << endl;
fout << "255" << endl;
for(y=0; y<canvas.height(); y++)
{
for(x=0; x<canvas.width(); x++)
{
fout << setw(10) << right << canvas.at(y,x) <<
setw(1) << " ";
}
fout << endl;
}
fout.close();
}
grids.h:
// Name: grids.h
// Vers: 1.0b
// Auth: Anthony D. Baye
/* Desc: Creates a linearly-addressed 2D array of a given datatype.
Handles insertion and retrieval of values into and from the array,
making sure that the index values do not overstep the array bounds.
*/
#ifndef _GRID_TEMP_H_
#define _GRID_TEMP_H_
#include <iostream>
using namespace std;
template<class _TY>
class grid
{
public:
grid();
grid(grid<_TY> &c);
~grid();
int create(unsigned long int hgt, unsigned long int wid);
_TY &at(unsigned long int row, unsigned long int col);
_TY &at(unsigned long int pos);
unsigned long int height() const;
unsigned long int width() const;
unsigned long int size() const;
bool destroy();
bool isEmpty() const;
private:
_TY **cptr;
unsigned long int H, W, S;
_TY Error;
};
/***************************************************
***
* Name: grid() Date: Thu. 06-12-08 *
* *
* Auth: Anthony D. Baye *
* Desc: Constructor function for template class. *
* Sets pointers to NULL and size values to zero. *
******************************************************/
template<class _TY>
grid<_TY>::grid()
{
cptr = NULL;
//Error = NULL;
H = 0;
W = 0;
S = 0;
};
/***************************************************
* Name: grid() Date: Thu. 06-12-08 *
* *
* Auth: Anthony D. Baye *
* Desc: Copy constructor function for template grid *
* class. *
***************************************************/
template<class _TY>
grid<_TY>::grid(grid<_TY> &c)
{
unsigned long int i, j;
cptr = NULL;
//Error = NULL;
H = 0;
W = 0;
S = 0;
create(c.height(), c.width());
for(i=0; i<H; i++)
for(j=0; j<W; j++)
cptr[i][j] = c.at(i, j);
};
template<class _TY>
grid<_TY>::~grid()
{
if(cptr != NULL)
destroy();
};
template<class _TY>
bool grid<_TY>::isEmpty() const
{
return (cptr == NULL);
};
template<class _TY>
bool grid<_TY>::destroy()
{
if(cptr == NULL)
return false;
delete cptr[0];
delete [] cptr;
cptr = NULL;
return true;
};
/***************************************************
* Name: create() Date: Thu. 6-12-08 *
* *
* Auth: Anthony D. Baye *
* Desc: Creates a grid object with the dimesions *
* (hgt)x(wid) returns an integer flag. *
* *
* Flag: *
* 0 -> Execution complete, no errors. *
* 1 -> Execution terminated, grid exists. *
* -1 -> Execution terminated, out of memory. *
***************************************************/
template<class _TY>
int grid<_TY>::create(unsigned long int hgt, unsigned long int wid)
{
unsigned long int i, j;
if(cptr != NULL)
return 1;
// Initialize the pointer to the number of rows.
cptr = new(nothrow) _TY *[hgt];
if(cptr == NULL)
return -1;
S = hgt * wid; // Calculate the number of entries in the array, and store the
number in private variable
cptr[0] = new(nothrow) _TY [S]; // Initialize ptr[0] to the full size of the
array. Clean up if fail.
if(cptr[0] == NULL)
{
S = 0;
delete [] cptr;
return -1;
}
// Store the dimensions in private variables.
H = hgt;
W = wid;
// Step through the rows.
for(i=1; i<H; i++)
{
// Step through row 0.
for(j=0; j<S; j++)
{
// If j is a multiple of columns and rows, set the contents of ptr[i] to the
address of ptr[0][j].
if(j == (W*i))
cptr[i] = &cptr[0][j];
}
}
return 0; // Home again, home again...
};
/***************************************************
* Name: at() Date: Thu. 6-12-08 *
* *
* Auth: Anthony D. Baye *
* Args: unsigned long int row, col *
* Desc: If row and col are within the bounds of the *
* array, returns a pointer to cptr[row][col]. *
* Otherwise, returns address to Error space. *
***************************************************/
template<class _TY>
_TY &grid<_TY>::at(unsigned long int row, unsigned long int col)
{
if(cptr == NULL || col >= W || row >= H)
return Error;
return cptr[row][col];
};
/*******************************************************
* Name: at() Date: Thu. 6-12-08 *
* *
* Auth: Anthony D. Baye *
* Args: int x, int y *
* Desc: Performs same function as above, but returns *
* Nth index from the beginning of the array. This *
* is possible, because of the way that the array *
* is addressed. Returns Error space if pos is out *
* of bounds *
*******************************************************/
template<class _TY>
_TY &grid<_TY>::at(unsigned long int pos)
{
if(cptr == NULL || pos >= S)
return Error;
return cptr[0][pos];
};
template<class _TY>
unsigned long int grid<_TY>::height() const
{
return H;
};
template<class _TY>
unsigned long int grid<_TY>::width() const
{
return W;
};
template<class _TY>
unsigned long int grid<_TY>::size() const
{
return S;
};
#endif
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le 25/08/2010 06:13, Anthony D. Baye a écrit :
> I'm working on an implementation of the Diamond-Square algorithm, and it seems
> to be working... sort of, but for two things.
>
> First, I'm getting seriously large pixel values. I've been trying to clamp them
> between 0 and 255 inclusive, but it's not working the way I hoped it would.
>
> Second my random number function. (I've attached the source file, but I'll
> reiterate the function here) I'm using the rand() function from cstdlib:
>
> double Random(double r)
> {
> double rNum;
>
> rNum = r - (2*r)/(rand()%65535);
>
> return rNum;
> }
>
> theoretically, this should generate a random number between -r and r, but I'm
> only getting positive values within a small range. reducing the range of random
> values to 100 or less seems to generate more negative numbers but problems
> persist.
The problem is in your formula: R - 2R/X with X between 0 & 65534 leads to:
* a problem with when X== 0
* -r when X== 1
* 0 when X== 2
* a positive value near r when X > 10 (with near ~ within 10%)
I guess you want to fix it.
Also, rand() is weak, why not using drand48() instead ?
rnum = r*(1.0-2.0*drand48());
/* notice the usage of .0 to force double computation not integer one */
or even better if non portable is not a problem and you are in the gnu
world: the drand48_r version (or at least the rand_r version), so as to
avoid reentrancy issue ? (as long as YOU protect the state)
>
> At the moment, the largest problem seems to be clamping the values.
>
> the code outputs the result to a pgm file with a depth of 8 bits
>
> changing the range multiplier seems to have some interesting effects, but I'm
> not sure I like the results.
>
> Any help would be appreciated.
>
> A.D.B.
>
--
Real software engineers work from 9 to 5, because that is<br/>
the way the job is described in the formal spec. Working<br/>
late would feel like using an undocumented external procedure.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 25.08.2010 06:13, schrieb Anthony D. Baye:
> Second my random number function. (I've attached the source file, but I'll
> reiterate the function here) I'm using the rand() function from cstdlib:
>
> double Random(double r)
> {
> double rNum;
>
> rNum = r - (2*r)/(rand()%65535);
>
> return rNum;
> }
What type of random distribution do you want to achieve? If you're
attempting to get a uniform distribution in the interval -r to +r (i.e.
each value in this interval is equally likely), then you're pretty much
off the track.
First, note that rand() /is/ uniformly distributed, in the interval 0 to
RAND_MAX (which, BTW, is typically 32767, but you shouldn't rely on that).
Now, taking this number modulo 65535 doesn't change a thing, provided
that RAND_MAX < 65535. Otherwise, it will give you a uniformly
distributed value in the range 0 to 65534 (sic!).
You take the inverse of this value, which gives you a /non-uniformly/
distributed number. Not sure from the top of my hat /what/ distribution
this gives you, but I think it's an exponential one, with the value x
having a probability of c*e^-x. At any rate, the range is also modified.
In a nutshell, at this point you get random values in the range
1/RAND_MAX (about 0.00003) to 1/0 (1.#INF, positive infinity), and while
each individual value in practice still has roughly the same
probability, the values clump together near 0.0 (for instance, the
highest values are ..., 0.20, 0.25, 0.333, 0.50, 1.00, 1.#INF).
The final operations - multiplying by 2*r and subtracting the result
from r - just scale and shift this non-uniform distribution.
What you probably really want is
rNum = r - (2*r) * ((double)rand() / (double)RAND_MAX);
This will give you a uniformly distributed value in the range -r to +r
(excluding +r). Or, to get rid of the small bias towards -r:
rNum = r - (2*r) * ((rand() + 0.5) / (double)RAND_MAX);
OTOH, if the exponential distribution is intentional, then what you want is:
rNum = r / (1 - 2 * ((rand() + 0.5) / (double)RAND_MAX));
This will give you a uniformly distributed value in the range -1.#INF to
+1.#INF (actually -r*RAND_MAX to +r*RAND_MAX if I'm not mistaken),
clustering around 0.0.
> srand(65535);
Are you sure you know what seed() does? The parameter, though not being
illegal, looks suspicious for a random seed.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka <ano### [at] anonymous org> wrote:
> Am 25.08.2010 06:13, schrieb Anthony D. Baye:
>
> > Second my random number function. (I've attached the source file, but I'll
> > reiterate the function here) I'm using the rand() function from cstdlib:
> >
> > double Random(double r)
> > {
> > double rNum;
> >
> > rNum = r - (2*r)/(rand()%65535);
> >
> > return rNum;
> > }
>
> What type of random distribution do you want to achieve? If you're
> attempting to get a uniform distribution in the interval -r to +r (i.e.
> each value in this interval is equally likely), then you're pretty much
> off the track.
>
> First, note that rand() /is/ uniformly distributed, in the interval 0 to
> RAND_MAX (which, BTW, is typically 32767, but you shouldn't rely on that).
this has not been my experience. printing the result of one million calls to
rand() gives numbers up to ten digits long, but I've never seen a result less
than six digits in length. If every result were equally likely, there should be
SOME lower numbers in the batch, shouldn't there?
A.D.B.
>
> Now, taking this number modulo 65535 doesn't change a thing, provided
> that RAND_MAX < 65535. Otherwise, it will give you a uniformly
> distributed value in the range 0 to 65534 (sic!).
>
> You take the inverse of this value, which gives you a /non-uniformly/
> distributed number. Not sure from the top of my hat /what/ distribution
> this gives you, but I think it's an exponential one, with the value x
> having a probability of c*e^-x. At any rate, the range is also modified.
> In a nutshell, at this point you get random values in the range
> 1/RAND_MAX (about 0.00003) to 1/0 (1.#INF, positive infinity), and while
> each individual value in practice still has roughly the same
> probability, the values clump together near 0.0 (for instance, the
> highest values are ..., 0.20, 0.25, 0.333, 0.50, 1.00, 1.#INF).
>
> The final operations - multiplying by 2*r and subtracting the result
> from r - just scale and shift this non-uniform distribution.
>
>
> What you probably really want is
>
> rNum = r - (2*r) * ((double)rand() / (double)RAND_MAX);
>
> This will give you a uniformly distributed value in the range -r to +r
> (excluding +r). Or, to get rid of the small bias towards -r:
>
> rNum = r - (2*r) * ((rand() + 0.5) / (double)RAND_MAX);
>
>
> OTOH, if the exponential distribution is intentional, then what you want is:
>
> rNum = r / (1 - 2 * ((rand() + 0.5) / (double)RAND_MAX));
>
> This will give you a uniformly distributed value in the range -1.#INF to
> +1.#INF (actually -r*RAND_MAX to +r*RAND_MAX if I'm not mistaken),
> clustering around 0.0.
>
>
> > srand(65535);
>
> Are you sure you know what seed() does? The parameter, though not being
> illegal, looks suspicious for a random seed.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 25.08.2010 18:38, schrieb Anthony D. Baye:
>> First, note that rand() /is/ uniformly distributed, in the interval 0 to
>> RAND_MAX (which, BTW, is typically 32767, but you shouldn't rely on that).
>
> this has not been my experience. printing the result of one million calls to
> rand() gives numbers up to ten digits long, but I've never seen a result less
> than six digits in length. If every result were equally likely, there should be
> SOME lower numbers in the batch, shouldn't there?
Okay, let me rephrase that:
"... rand() /is/ _supposed_ to be uniformly distributed..."
According to ANSI-C standard, the actual implementation of rand() is
implementation-specific, and is known to be poor in typical
implementations. The maximum number returned - RAND_MAX - is
implementation-specific as well, and is specified to be at least 32767.
According to Microsoft documentation, their C runtime library has
RAND_MAX=32767, though I haven't actually bothered to test it.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka <ano### [at] anonymousorg> wrote:
> Am 25.08.2010 18:38, schrieb Anthony D. Baye:
>
> >> First, note that rand() /is/ uniformly distributed, in the interval 0 to
> >> RAND_MAX (which, BTW, is typically 32767, but you shouldn't rely on that).
> >
> > this has not been my experience. printing the result of one million calls to
> > rand() gives numbers up to ten digits long, but I've never seen a result less
> > than six digits in length. If every result were equally likely, there should be
> > SOME lower numbers in the batch, shouldn't there?
>
> Okay, let me rephrase that:
>
> "... rand() /is/ _supposed_ to be uniformly distributed..."
>
> According to ANSI-C standard, the actual implementation of rand() is
> implementation-specific, and is known to be poor in typical
> implementations. The maximum number returned - RAND_MAX - is
> implementation-specific as well, and is specified to be at least 32767.
> According to Microsoft documentation, their C runtime library has
> RAND_MAX=32767, though I haven't actually bothered to test it.
At any rate, the solution suggested by Le Forgeron, using drand48(), seems to
work.
There are still a few issues, however.
The chief problem is thatsuccessive calls to the program return the same result
every time.
The only way I've found to change the result is to modify the initial conditions
(i.e. changing the number of seed values in the grid before calling the
Diamond_Square() function.)
Thanks for the input, so far.
A.D.B.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Anthony D. Baye wrote:
> The chief problem is thatsuccessive calls to the program return the same result
> every time.
There's undoubtedly a way to seed any such random number generator. Most
people seed it off the wall clock.
--
Darren New, San Diego CA, USA (PST)
Quoth the raven:
Need S'Mores!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 26.08.2010 00:52, schrieb Anthony D. Baye:
> The chief problem is thatsuccessive calls to the program return the same result
> every time.
>
> The only way I've found to change the result is to modify the initial conditions
> (i.e. changing the number of seed values in the grid before calling the
> Diamond_Square() function.)
Why, yes - of course; that's how pseudo-random number generators work
;-). they're deterministic, after all (and as often as not this is even
desired). To get a different result each time, a typical solution
(outside of cryptographic applications that is) would be to seed with
the current system time instead of a constant.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka <ano### [at] anonymousorg> wrote:
> Am 26.08.2010 00:52, schrieb Anthony D. Baye:
>
> > The chief problem is thatsuccessive calls to the program return the same result
> > every time.
> >
> > The only way I've found to change the result is to modify the initial conditions
> > (i.e. changing the number of seed values in the grid before calling the
> > Diamond_Square() function.)
>
> Why, yes - of course; that's how pseudo-random number generators work
> ;-). they're deterministic, after all (and as often as not this is even
> desired). To get a different result each time, a typical solution
> (outside of cryptographic applications that is) would be to seed with
> the current system time instead of a constant.
I was getting hinky results when calling srand48(time(NULL)), but it turns out
that the solution was to call it once at the beginning of the program, rather
than every time I called my Random() function...
makes sense, I guess...
Thanks for all the help...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> this has not been my experience. printing the result of one million
calls to
> rand() gives numbers up to ten digits long, but I've never seen a
result less
> than six digits in length. If every result were equally likely,
there should be
> SOME lower numbers in the batch, shouldn't there?
If your rand() gives you numbers between 0 and, say, 9999999999 (the
largest number that is ten digits long), then 99.99% of those numbers
will be over six digits in length. That's assuming that all numbers in
the range are possible, which would not be the case if, say, it were
taking a random integer from 0 to 32767 and then multiplying it to be
much higher.
- Slime
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
