Problem with large arrays.

I am currently making a simple game using different tiles from an image file and placing them with a terrain generator. The terrain generator is based on the diamond square algorithm and I tested it in a smaller scale and it works just fine. However, in my game I want to generate a map made out of 513*513 tiles, which means that I need an int to store the tile values with and array of [513][513], and I also need a double with the same array for the generator.

Declaring the int works just fine, but when I declare the double the program crashes from a stack overflow. Is there any good way to get around this?

PS. Even though this is about a game I thought it would be better to put it in the c++ section since the problem is a generic c++ problem and has nothing to do with the game.

Also, here is the code for my map class (as you can see, I am using SDL):

map.h

Code:

#pragma once
#include "ANewWorld.h"
class Map
{
public:
    SDL_Rect position[513][513];
    int type[513][513];


    void generate();
    void render(SDL_Rect camera);
};

map.cpp

Code:

#include "map.h"
#include "ANewWorld.h"


#include <iostream>


using namespace std;


void Map::generate()
{
            double tM[513][513]; //temporaryMap
                //This is where the problem is.


        int temp;
        srand(time(0));


        int sS = 32; //stepSize
        int hS = sS/2; //halfStep
        int sX = 0; //startX
        int sY = 0; //startY


        for(int x = sX; x < 513; x += sS){
        for(int y = sY; y < 513; y += sS){
            tM[x][y] = rand()%2;
            for(int n = 1; n <= 5; n++){
                temp = rand()%10;
                tM[x][y] += temp/(10^n);
            }
        }
        }


        do{


        hS = sS/2;


        sX = hS;
        sY = hS;


        for(int x = sX; x < 513; x += sS){
        for(int y = sY; y < 513; y += sS){
            tM[x][y] = (tM[x-hS][y-hS] + tM[x-hS][y+hS] + tM[x+hS][y-hS] + tM[x+hS][y+hS])/4;
        }
        }


        sX = hS;
        sY = 0;


        for(int x = sX; x < 513; x += sS){
        for(int y = sY; y < 513; y += sS){
            if(y==0) tM[x][y] = (tM[x-hS][y] + tM[x+hS][y] + tM[x][y+hS]*2)/4;
            else if(y==513) tM[x][y] = (tM[x-hS][y] + tM[x+hS][y] + tM[x][y-hS]*2)/4;
            else tM[x][y] = (tM[x-hS][y] + tM[x+hS][y] + tM[x][y+hS] + tM[x][y-hS])/4;
        }
        }


        sX = 0;
        sY = hS;


        for(int x = sX; x < 513; x += sS){
        for(int y = sY; y < 513; y += sS){
            if(x==0) tM[x][y] = (tM[x][y-hS] + tM[x][y+hS] + tM[x+hS][y]*2)/4;
            else if(x==513) tM[x][y] = (tM[x][y-hS] + tM[x][y+hS] + tM[x-hS][y]*2)/4;
            else tM[x][y] = (tM[x][y-hS] + tM[x][y+hS] + tM[x-hS][y] + tM[x+hS][y])/4;
        }
        }
        
        sS = sS/2;
        }while(sS!=1);


        for(int x = 0; x < 513; x++){
        for(int y = 0; y < 513; y++){
            position[x][y].x = x*64;
            position[x][y].y = y*64;
            
            if(tM[x][y] < 0.45) type[x][y] = 0;
            else if(tM[x][y] > 1.05) type[x][y] = 2;
            else type[x][y] = 1;
        }
        }
}


void Map::render(SDL_Rect camera)
{
    SDL_Rect rPos;


    int rStartx = camera.x/64;
    int rStarty = camera.y/64;
    int rEndx = (camera.x + SCREEN_WIDTH)/64;
    int rEndy = (camera.y + SCREEN_HEIGHT)/64;


    for(int x = rStartx; x <= rEndx; x++){
    for(int y = rStarty; y <= rEndy; y++){
               rPos.x = position[x][y].x - camera.x;
               rPos.y = position[x][y].y - camera.y;
               SDL_BlitSurface(tiles, &clipTiles[type[x][y]], screen, &rPos);
    }
    }
}

Probably needs to be dynamically allocated with new.

Or, better yet, use std::vector's. That eliminates opportunities for memory leaks.

I'm just learning myself, so could you explain a little? I'm familiar with std::vector as a resizable array, but please explain about the possibility for memory leaks.

Generally, you don't allocate a 2MB array on the stack. Instead, you need to dynamically allocate it. Using a vector is easiest:

Code:

// Define it like this:
const size_t SIZE = 513;
vector<double> tM(SIZE * SIZE);

// Access it like this:
tM[x * SIZE + y] = 1;

In your loops, you have a special condition if the loop var is 513, but they will never be 513! You probably mean 512 (SIZE-1).

Also, you seem to be using ^ as an exponential operator. C++ does not have an exponential operator. ^ is the bitwise exclusive-or operator. You probably want int(pow(10, n)) (include cmath).

You probably also shouldn't be calling srand from this funtion. Just call it once from early on in main instead.

Originally Posted by oogabooga

Generally, you don't allocate a 2MB array on the stack. Instead, you need to dynamically allocate it. Using a vector is easiest:

Code:

// Define it like this:
const size_t SIZE = 513;
vector<double> tM(SIZE * SIZE);

// Access it like this:
tM[x * SIZE + y] = 1;

... or use vectors of vectors to enable 2D accesses.

Code:

vector<vector<double> > tM(SIZE, vector<double>(SIZE));
tM[x][y] = 1;    // access an element

Note that, with containers, the SIZE does not need to be fixed at compile time.

Thank you for the help! The vector of vector thing worked amazingly well. And oogabooga, thanks for pointing out those 2 other mistakes, they have now been fixed as well.

EDIT: I also moved the srand to my main. I'm not sure why that's better, but I'm gonna trust you. Thanks.