Diamond Square/ Midpoint Displacement Algorithm

[C!rcle]

Hi,
ich probiere seit einiger Zeit mit dem Diamond Square Algorithmus zu arbeiten.
Als Hilfe hab ich verwendet.

Jedoch sieht mein Resultat nicht so aus, wie ich es gerne hätte.

(Mein Resultat)


(Was ich erreichen möchte)


Ich wüsste nicht woran es in meinem Code liegen könnte, deshalb poste ich ihn einfach mal.

DiamondSquare.h

 Spoiler

#include <Windows.h>
#include <math.h>
#include <assert.h>

/*
	Big Thanks for the explenation of the Diamond Square Algorithm 
	to the Team from lighthouse3d.com.
	Source: http://www.lighthouse3d.com/opengl/terrain/index.php?mpd2
*/
class DiamondSquare
{
private:
	int oWidth; // Original Width
	int oHeight; // Original Height
	double roughness; // Roughness
public:
	DiamondSquare();
	double** CreateDiamondSquare(int width,int height,double d,double seed,double roughness);
	void MidPointDisplacement(double** map,int width,int height,double d);
	void SquareStep(double** map,int x,int y,int width,int height,double d);
	void DiamondStep(double** map,int x,int y,int width,int height,double d);
	void Smooth(double ** map,double level,int rounds);
	double RandomDouble(double min, double max);
};

DiamondSquare.cpp

 Spoiler

#include "DiamondSquare.h"

DiamondSquare::DiamondSquare()
{
}

double** DiamondSquare::CreateDiamondSquare(int width,int height,double d,double seed,double roughness)
{
	double** result = new double*[width];
	for(int i=0;i<width;i++)
	{
		result[i] = new double[height];
	}
	
	this->oWidth = width+1;
	this->oHeight = height+1;
	this->roughness = roughness;

	srand(seed); // Set the Seed

	for(int x=0;x<width;x++)
	{
		for(int y=0;y<height;y++)
		{
			result[x][y] = this->RandomDouble(0,1);
		}
	}

	this->MidPointDisplacement(result,this->oWidth,this->oHeight,d);
	this->Smooth(result,0.90,5);
	return result;
}

void DiamondSquare::MidPointDisplacement(double** map,int width,int height,double d)
{
	if(width <= 1 || height <= 1)
	{
		return;
	}
	int hWidth = width;
	int hHeight = height;

	while(true)
	{
		d *= pow(2,-(this->roughness));
		hWidth /= 2;
		hHeight /= 2;
		if(hWidth < 2 || hHeight < 2)
			break;
		for(int x=0;x<width-1;x+=hWidth)
		{
			for(int y=0;y<height-1;y+=hHeight)
			{
				this->SquareStep(map,x,y,hWidth,hHeight,d);
			}
		}

		for(int x=0;x<width-1;x+=hWidth)
		{
			for(int y=0;y<height-1;y+=hHeight)
			{
				this->DiamondStep(map,x,y,hWidth,hHeight,d);
			}
		}
	}
}

void DiamondSquare::SquareStep(double** map,int x,int y,int width,int height,double d)
{
	//Check if the Width and Height is large enough, and if the X and Y position is not out of bounds.
	if(width <= 1 || height <= 1 || (x+width) > width || (x-width) < 0 || (y+height) > height || (y-height) < 0)
	{
		return;
	}

	double A = map[x][y];
	double B = map[x+width][y];
	double C = map[x][y+height];
	double D = map[x+width][y+height];

	//E
	double EVal = (A+B+C+D) / 4 + this->RandomDouble(-d,d);
	if(EVal > 1.0)
	{
		map[x+(width/2)][y+(height/2)] = 1.0;
	}
	else
	{
		map[x+(width/2)][y+(height/2)] = EVal;
	}
	
}

void DiamondSquare::DiamondStep(double** map,int x,int y,int width,int height,double d)
{
	//Check if the Width and Height is large enough, and if the X and Y position is not out of bounds.
	if(width <= 1 || height <= 1 || (x+width) > width || (x-width) < 0 || (y+height) > height || (y-height) < 0)
	{
		return;
	}

	double A = map[x][y];
	double B = map[x+width][y];
	double C = map[x][y+height];
	double D = map[x+width][y+height];
	double E = map[x+(width/2)][y+(height/2)];

	int E_Left = -1;
	int E_Right = -1;
	int E_Top = -1;
	int E_Bot = -1;

	if((x-width > 0) && (y+(height/2) < height))
		E_Left = map[x-width][y+(height/2)];
	
	if((x+width+(width/2) < width) && (y+(height/2) < height))
		E_Right = map[x+width+(width/2)][y+(height/2)];
	
	if((x+(width/2) < width) && (y-(height/2) > 0))
		E_Top = map[x+(width/2)][y-(height/2)];

	if((x+(width/2) < width) && (y+height+(height/2) < height))
		E_Bot = map[x+(width/2)][y+height+(height/2)];

	//F
	if(E_Left != -1)
		map[x][y+(height/2)] = (A+C+E+E_Left)/4+this->RandomDouble(-d,d);
	else
		map[x][y+(height/2)] = (A+C+E)/3+this->RandomDouble(-d,d);

	//G 
	if(E_Top != -1)
		map[x+(width/2)][y-(height/2)] = (A+B+E+E_Top)/4+this->RandomDouble(-d,d);
	else
		map[x+(width/2)][y-(height/2)] = (A+B+E)/3+this->RandomDouble(-d,d);

	//H
	if(E_Right != -1)
		map[x+width+(width/2)][y+(height/2)] = (B+D+E+E_Right)/4+this->RandomDouble(-d,d);
	else
		map[x+width+(width/2)][y+(height/2)] = (B+D+E)/3+this->RandomDouble(-d,d);

	//I
	if(E_Bot != -1)
		map[x+(width/2)][y+height+(height/2)] = (C+D+E+E_Bot)/4+this->RandomDouble(-d,d);
	else
		map[x+(width/2)][y+height+(height/2)] = (C+D+E)/3+this->RandomDouble(-d,d);
}

void DiamondSquare::Smooth(double ** map,double level,int rounds)
{
	for(int i=0;i<rounds;i++)
	{
		//Left to right
		for(int x=1;x<this->oWidth-1;x++)
		{
			for(int y=0;y<this->oHeight-1;y++)
			{
				map[x][y] = map[x-1][y]*(1-level)+map[x][y]*level;
			}
		}

		//Right to Left
		for(int x=this->oWidth-3;x<-1;x--)
		{
			for(int y=0;y<this->oHeight-1;y++)
			{
				map[x][y] = map[x+1][y]*(1-level)+map[x][y]*level;
			}
		}

		//Bottom to Top
		for(int x=0;x<this->oWidth-1;x++)
		{
			for(int y=1;y<this->oHeight-1;y++)
			{
				map[x][y] = map[x][y-1]*(1-level)+map[x][y]*level;
			}
		}

		//Top to Bottom
		for(int x=0;x<this->oWidth-1;x++)
		{
			for(int y=this->oHeight-1;y<-1;y--)
			{
				map[x][y] = map[x][y+1]*(1-level)+map[x][y]*level;
			}
		}
	}
}

double DiamondSquare::RandomDouble(double min, double max)
{
    assert(max > min); 
    double random = ((double) rand()) / (double) RAND_MAX;
    double range = max - min;  
    return (random*range) + min;
}

Main.cpp

 Spoiler

#include <Windows.h>
#include <SDL.h>
#include <math.h>
#include "DiamondSquare.h"

void DrawPixel(SDL_Surface *screen, int x, int y, int R, int G, int B);

int main(int argc, char **argv)
{
    SDL_Init(SDL_INIT_EVERYTHING);
	SDL_Surface *screen = ::SDL_SetVideoMode(300,300,32,SDL_SWSURFACE);
	DiamondSquare* s = new DiamondSquare();
	double** map = s->CreateDiamondSquare(250,250,0.5,182192,1);
	for(int x=0;x<250;x++)
	{
		for(int y=0;y<250;y++)
		{
			int col = (int)((map[x][y]*128.0)+128.0);
			if(col > 255)
				col = 255;
			if(col < 0)
				col = 0;
			DrawPixel(screen,x,y,(int)((0xFF/255.0)*(double)col),(int)((0xFF/255.0)*(double)col),(int)((0xFF/255.0)*(double)col));
		}
	}

	bool quit = false;
    while(!quit)
    {
        SDL_Event e;

        SDL_WaitEvent(&e);

        switch(e.type)
        {
        case SDL_QUIT:
            quit = true;
			break;
		case SDL_KEYDOWN:
			switch(e.key.keysym.sym)
			{
			case SDLK_SPACE:

			break;
			}
		break;
        }
    };
    SDL_Quit();

    return 0;
}


void DrawPixel(SDL_Surface *screen, int x, int y, int R, int G, int B)
{
    int color = SDL_MapRGB(screen->format, R, G, B);
	
    if(SDL_MUSTLOCK(screen))
    {
        if(SDL_LockSurface(screen) < 0)
        {
            return;
        }
    }

    switch(screen->format->BytesPerPixel)
    {
    case 1:
        {
        Uint8 *bufp;

        bufp = (Uint8 *)screen->pixels + y*screen->pitch + x;
        *bufp = color;
        }
        break;

    case 2:
        {
        Uint16 *bufp;
        bufp = (Uint16 *)screen->pixels + y*screen->pitch/2 + x;
        *bufp = color;
        }
        break;

    case 3:
        {
        Uint8 *bufp;

        bufp = (Uint8 *)screen->pixels + y*screen->pitch + x;
        *(bufp+screen->format->Rshift/8) = R;
        *(bufp+screen->format->Bshift/8) = B;
        *(bufp+screen->format->Gshift/8) = G;
        }
        break;

    case 4:
        {
        Uint32 *bufp;

        bufp = (Uint32 *)screen->pixels + y*screen->pitch/4 + x;
        *bufp = color;
        }
        break;
    }

    if(SDL_MUSTLOCK(screen))
    {
        SDL_UnlockSurface(screen);
    }
    SDL_UpdateRect(screen, x, y, 1, 1);
}

Ich suche wirklich nur Hilfe, wer hier etwas anderes schreibt wird gemeldet.

MfG,
C!rcle