1
\$\begingroup\$

I'm porting a 2-D Terrain Generator from Python to C++ as Python is too slow due to the number of features that have been added.

I'm new to C++ and would like to know of any criticisms that you can make of the code at this time before I continue with the simpler parts of the generation. Right now I'm interested in maintaining my use of arrays rather than std::vector so any improvements besides that would be greatly appreciated.

I'm also aware that this code is currently uncommented, I intend to fix that in the future however right now I'm more interested in the code itself.

#include "stdafx.h"
#include <iostream>
#include <conio.h>

double** white_noise(int w, int h);
double** smooth_noise(double** noise, int w, int h, int octave);
double** perlin_noise(double** noise, int w, int h, int octaves, double persistance);
double interpolate(double a, double b, double alpha);

int main()
{
    const int w = 400;
    const int h = 400;

    double** noise = white_noise(w, h);
    double** perlinnoise = perlin_noise(noise, w, h, 8, 0.7);

    // Code that does things will go here(function calls to add sea-level etc.)

    for (int i = 0; i < w; i++) {
        delete[] noise[i];
        delete[] perlinnoise[i];
    }
    delete[] noise;
    delete[] perlinnoise;
}


double** white_noise(int w, int h) {
    double** noise = new double*[w];
    for (int i = 0; i < w; i++) {
        noise[i] = new double[h];
    }

    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++) {
            noise[i][j] = (float)rand() / RAND_MAX;
        }
    }

    return noise;
}

double** smooth_noise(double** noise, int w, int h, int octave) {
    double** smooth_noise = new double*[w];
    for (int i = 0; i < w; i++) {
        smooth_noise[i] = new double[h];
    }

    int period = 1 << octave;
    double frequency = 1.0 / period;

    for (int i = 0; i < w; i++) {
        int sample_i0 = i / period * period;
        int sample_i1 = (sample_i0 + period) % w;
        double horizontal_blend = (i - sample_i0) * frequency;

        for (int j = 0; j < h; j++) {
            int sample_j0 = j / period * period;
            int sample_j1 = (sample_j0 + period) % h;
            double vertical_blend = (j - sample_j0) * frequency;

            double top = interpolate(noise[sample_i0][sample_j0],
                noise[sample_i1][sample_j0],
                horizontal_blend);
            double bottom = interpolate(noise[sample_i0][sample_j1],
                noise[sample_i1][sample_j1],
                horizontal_blend);
            smooth_noise[i][j] = interpolate(top, bottom, vertical_blend);
        }
    }

    return smooth_noise;
}

double** perlin_noise(double** noise, int w, int h, int octaves, double persistance) {
    double** perlin_noise = new double*[w];
    for (int i = 0; i < w; i++) {
        perlin_noise[i] = new double[h];
    }
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++) {
            perlin_noise[i][j] = 0;
        }
    }

    double*** smooth_noises = new double**[octaves];
    for (int i = 0; i < octaves; i++) {
        smooth_noises[i] = smooth_noise(noise, w, h, i);
    }

    double amplitude = 1;
    double totalamplitude = 0;

    for (int octave = octaves - 1; octave > 0; octave--) {
        amplitude *= persistance;
        totalamplitude += amplitude;

        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++) {
                perlin_noise[i][j] += smooth_noises[octave][i][j] * amplitude;
            }
            delete[] smooth_noises[octave][i];
        }
        delete[] smooth_noises[octave];
    }
    delete[] smooth_noises;

    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++) {
            perlin_noise[i][j] /= totalamplitude;
        }
    }

    return perlin_noise;
}

double interpolate(double a, double b, double alpha) {
    return a * (1 - alpha) + alpha * b;
}
\$\endgroup\$
  • \$\begingroup\$ Why are you choosing arrays over std::vector? Is there a particular need for that in this code? \$\endgroup\$ – Jamal Nov 6 '16 at 19:35
  • \$\begingroup\$ Then at least be aware of some of their evils. \$\endgroup\$ – Jamal Nov 6 '16 at 19:44
  • \$\begingroup\$ @Jamal I am aware of the issues with it, and had a "fair" bit of trouble even developing this but I do feel like it is improving my knowledge of pointers. \$\endgroup\$ – user122352 Nov 6 '16 at 19:46
  • \$\begingroup\$ Arrays are not faster than vector. As for as being too verbose that is just a silly statement as the syntax is identical and you have to write less code. \$\endgroup\$ – Martin York Nov 6 '16 at 20:36
1
\$\begingroup\$

Here are some things that may help you improve your code.

Strive for portable code

Several of the features of this code are either platform-specific or compiler-specific or both. Specifically, #include <conio.h>, and #include "stdafx.h" both non-standard. Further, neither are actually used so I would strongly recommend omitting them.

Prefer to avoid using new and delete directly

In modern C++, it's usually better to avoid explicit calls to new and delete. In particular, it seems that the goal of this program is to create the perlinnoise matrix. It is not clear whether you're intending to also use the noise array or if it's just a byproduct of the production of the perlinnoise array. In any case, use of raw new and delete tends to lead to the problem mentioned in the next suggestion.

Consider using a better random number generator

You are currently using

noise[i][j] = (float)rand() / RAND_MAX;

However, that's the old C way to do things. better solution, if your compiler and library supports it, would be to use the C++11 `std::uniform_real_distribution. It looks complex, but it's actually pretty easy to use, as I'll demonstrate below.

Don't leak memory

If you use new and delete directly, you must take care to make sure they match in every instance. This is quite easy to get wrong, and in fact, this code gets it wrong. In particular, the perlin_noise routine leaks memory. Track how long it takes you to find and fix the problem, and then compare it to the following suggestion.

Use objects

C++ is an object-oriented language and accomodating and encouraging that style of design is one of the key benefits of using C++. For that reason, and because it makes your program cleaner, easier to maintain, easier to re-use and less prone to error, I'd highly recommend using objects for this program.

Use the Standard Template Library

There is a lot of functionality already available to you if you use the Standard Template Library (STL). To illustrate this and a number of the previous points, here is a rewrite of your white_noise routine as an object. First, we need a way to initialize it with random values, and then a way to address individual noise values by index. This is easily done by deriving a WhiteNoise object from a std::valarray.

struct WhiteNoise : public std::valarray<double>
{
    WhiteNoise(int w, int h) :
        std::valarray<double>(w*h), 
        width{w},
        height{h}
    {
        std::mt19937 gen;
        std::uniform_real_distribution<double> dis;
        for (auto &value : *this) {
            value = dis(gen);
        }
    }
    int width;
    int height;
};

Note that there is no explicit call to new or delete and that the width and height are embedded into the object rather than separate quantities. If you create a similar PerlinNoise object, the main function could look like this:

int main()
{
    const int w = 400;
    const int h = 400;

    WhiteNoise wn(w,h);
    PerlinNoise pn(wn, 8, 0.7);

    // Create a bitmap just so that we have something to look at.
    makePGM(pn, "perlin.pgm");
}

The result: no memory leak and a much shorter, cleaner program (also faster in my testing, but you should test it on your machine). The makePGM is just a function I wrote to create a bitmap image to visualize the result.

\$\endgroup\$
0
\$\begingroup\$

Adjustments for Portability

To improve portability I removed #include <conio.h> and #include "stdafx.h". These were here previously so that I could debug my program by the use of _getch() and because MSVS2015 by default makes use of precompiled headers, however as neither of these were needed for the actual program and restricted portability it was better not to have them.

Using a better RNG

Previously I had been using:

noise[i][j] = (float)rand() / RAND_MAX; 

for my random number generation, however the numbers that it provides are less truely representative of random numbers than <random>'s std::uniform_real_distribution. As such I have moved away from the previous method to now use:

std::mt19937 gen(seed);
std::uniform_real_distribution<double> dis;

This allows me to make better use of my software through the changing of seeds while also providing a better feeling of randomness.

Use of objects

My previous method of generation was very much more C than C++ and used arrays of pointers and the dynamically allocated memory rather than making use of what C++ can provide as an OOP language. Previously I had thought that you could only use primitive data types in C++ structs, but being able to have structs be derived from types in the STL allowed the creation of more complex data structures rather than having to manage memory and pointers which is far more error prone.

Memory Leaks

I originally asked this question to help with a memory leak alongside a general review, however as this was off-topic I had to reword the question to focus entirely on the review with the hope that someone would be able to help with the poor memory management as well. Fortunately, the answer provided allowed me to both stop my use of new and delete and resulted in the memory leak being fixed by making use of objects instead of pointer arrays. In the end I couldn't find the source of the memory leak as I thought that I had deleted everything when use of it was done, but that's a lesson for another day.

The Standard Template Library

Having been shown the functionality of std::valarray and how simply it can be used to produce white noise it was clear that by reinventing the wheel I was only causing myself problems, as such I took the advice given and shifted to using valarrays instead. This meant that constructing my data set was much easier, as is passing it between functions and making use of it.

The code after this review is now:

#include <valarray>
#include <fstream>
#include <random>

double interpolate(double a, double b, double alpha);

struct WhiteNoise : public std::valarray<double>
{
    WhiteNoise(int w, int h) :
        std::valarray<double>(w*h),
        width{ w },
        height{ h }
    {
        std::mt19937 gen(5);
        std::uniform_real_distribution<double> dis;
        for (auto &value : *this) {
            value = dis(gen);
        }
    }
    int width;
    int height;
};

struct PerlinNoise : public std::valarray<double>
{
    PerlinNoise(WhiteNoise wn, int octaves, double persistance) :
        std::valarray<double>(wn.size()),
        width{ wn.width },
        height{ wn.height }
    {
        double amplitude = 1;
        double totalamplitude = 0;
        for (int octave = octaves - 1; octave > 0; octave--) {
            amplitude *= persistance;
            totalamplitude += amplitude;

            int period = 1 << octave;
            double frequency = 1.0 / period;

            for (int i = 0; i < width; i++) {
                int sample_i0 = i / period * period;
                int sample_i1 = (sample_i0 + period) % width;
                double horizontal_blend = (i - sample_i0) * frequency;

                for (int j = 0; j < height; j++) {
                    int sample_j0 = j / period * period;
                    int sample_j1 = (sample_j0 + period) % height;
                    double vertical_blend = (j - sample_j0) * frequency;

                    double top = interpolate(wn[sample_j0*width+ sample_i0],
                        wn[sample_j0*width+ sample_i1],
                        horizontal_blend);
                    double bottom = interpolate(wn[sample_j1*width+ sample_i0],
                        wn[sample_j1*width+ sample_i1],
                        horizontal_blend);
                    this[0][j*width+ i] += interpolate(top, bottom, vertical_blend) * amplitude;
                }
            }
        }
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                this[0][j*width+ i] /= totalamplitude;
            }
        }
    }
    int width;
    int height;
};

void convert_to_land(PerlinNoise* pn, double threshold);

int main()
{
    const int w = 1000;
    const int h = 1000;

    WhiteNoise wn(w, h);
    PerlinNoise pn(wn, 8, 0.7);
    PerlinNoise* pnt_pn = &pn;
    convert_to_land(pnt_pn, 0.5);

    saveasbmp(pnt_pn);
}

double interpolate(double a, double b, double alpha) {
    return a * (1 - alpha) + alpha * b;
}

void convert_to_land(PerlinNoise* pn, double threshold) {
    for (int i = 0; i < (*pn).size(); i++) {
        if ((*pn)[i] >= threshold) {
            (*pn)[i] = 1;
        }
        else {
            (*pn)[i] = 0;
        }
    }
}

with the mechanics of saveasbmp(PerlinNoise* pn); left out as it's just for visualisation. There are no doubt more things that I have missed or made a mistake with here and as such I will make a new question if anybody feels they would like to improve this further, just leave a comment so that I know.

Thanks to Edward for his review without which I couldn't have written this.

\$\endgroup\$
  • \$\begingroup\$ The memory leak was subtle; the line for (int octave = octaves - 1; octave > 0; octave--) { condition should have been octave >= 0. At the moment, the last octave isn't processed and the corresponding smooth_noise octave is not deleted. \$\endgroup\$ – Edward Nov 8 '16 at 18:55
  • \$\begingroup\$ You can post a follow up question with the new code. I think you'll likely get more and better reviews now because it's more recognizably C++ code instead of C. Just post a link to this original question so that people can see the improvements already made. Well done so far, but there are still ways to make it still better! :) \$\endgroup\$ – Edward Nov 8 '16 at 18:57
  • \$\begingroup\$ @Edward Of course, I constructed "smooth noise" for octaves 0 -> octaves-1 but because the noise from octave 0 is just the white noise I didn't use it and then never deleted it. And I will, feel free to answer on the upcoming follow-up question. \$\endgroup\$ – user122352 Nov 8 '16 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy