Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is my mt19937 Random generator giving me ridiculous results? C++

Tags:

c++

random

c++11

Working on another project and we're required to use the mt19937 for randomly generating numbers. We're supposed to have it randomly choose an x and y coordinate based on the section of a grid. For example, my function passes minX, maxX, minY, maxY to a function. My x coordinate works fine. I kept getting errors randomly upon test runs. Sometimes it'll run 10 times with no problem, then hits an error. I put in some self debug lines to display what the mt generator is actually generating. Like I said, x works fine and y does sometimes. It'll randomly give me a -3437892 or 9743903.

Here's my code:

void DungeonLevel::generateRoom(int minX,int maxX,int minY, int maxY){
    mt19937 mt;
    mt.seed( time(NULL) );


    // Calculate random width and height; these both range
    // from 4-13
    int iRandomWidth = 4 + (mt() % 10);
    int iRandomHeight = 4 + (mt() % 10);

    // Calculate the start points in both X and Y directions

    int iStartX;
    iStartX = mt() % (maxX - iRandomWidth);
    cout << "xStart: " << iStartX<<endl; //cout flag
    while ((iStartX > maxX) && (iStartX >= 0)){
            cout << "xStart: " << iStartX<<endl;//cout flag
            iStartX = mt() % (maxX - iRandomWidth);
    }
    int iStartY = 0;
    iStartY = mt() % (maxY - iRandomHeight);
    cout<<"yStart: " <<iStartY<<endl; //cout flag
    while ((iStartY > maxY)){
            cout<<"yStart: " <<iStartY<<endl;//cout flag
            iStartY = (mt() % (maxY - iRandomHeight));
    }

    // Iterate through both x and y coordinates, and
    // set the tiles to room tiles
    // SINGLE ROOM
    for( int x = iStartX; x <= iStartX + iRandomWidth; x++ ){
            for( int y = iStartY; y <= iStartY + iRandomHeight; y++ ){
                    if (y == iStartY){
                            dungeonGrid[y][x] = '-';
                    }
                    else if (iStartX == x){
                            dungeonGrid[y][x] = '|';
                    }
                    else if (y == (iStartY+iRandomHeight)){
                            dungeonGrid[y][x] = '-';
                    }
                    else if (x == (iStartX+iRandomWidth)){
                            dungeonGrid[y][x] = '|';
                    }
                    else {
                            dungeonGrid[y][x] = '.';
                    }

            }
    }

}
like image 797
ModdedLife Avatar asked Feb 26 '13 02:02

ModdedLife


2 Answers

I think you should use a random distribution for the mt19937. So use it with

mt19937 mt;
mt.seed( time(nullptr) );
std::uniform_int_distribution<int> dist(4, 13);

int iRandomWidth = dist(mt);
int iRandomHeight = dist(mt);

This way you are guaranteed to get random numbers between 4 and 13.

Update While my answer solves the original problem and is in my opinion an improvement in code readability, it does not actually address the problem in the original code. Please also refer to jogojapan's answer for this.

like image 130
Haatschii Avatar answered Nov 14 '22 23:11

Haatschii


The ultimate cause of the problem is that you mix signed and unsigned integers in the code without taking the necessary precautions (and without need).

Specifically, if minY is sometimes less than 13, it will happen every now and then that iRandomHeight gets negative. What you then get is similar to the effect demonstrated below:

#include <limits>
#include <iostream>

using namespace std;

int main()
{
  /* Unsigned integer larger than would fit into a signed one.
     This is the kind of thing mt199737 returns sometimes. */
  unsigned int i = ((unsigned int)std::numeric_limits<int>::max()) + 1000;
  cout << (i % 3) << endl;
  cout << (i % -3) << endl;
  cout << (signed)(i % -3) << endl;
  return 0;
}

This first generates an unsigned integer slightly larger than would fit into a signed one. mt19937 returns unsigned and will sometimes give you values like i in the code above.

The output of the code above (see on liveworkspace) is as follows:

2
2147484647
-2147482649

The second line shows the result of modulo with a negative number (such as iRandomHeight will sometime be), applied to an unsigned integer larger than fits into a corresponding signed one. The third line shows what happens when you convert that back to signed integer (which you do implicitly when you assign it to your one of your signed integer variables).

Although I agree with Haatschii that you should use std::uniform_int_distribution to make your life easier, it's also important to use signed and unsigned appropriately even then.

like image 29
jogojapan Avatar answered Nov 14 '22 23:11

jogojapan