具有确定性程序的未定义行为

Question

我目前正在尝试按照 "Game of Life" 的想法将 "cave generation" 实现为二维数组。思路如下：

我有一个由 uniform_real_distribution 和 density 随机生成的 0s 和 1s 的二维向量（分别代表空气和方块）（这里是 0.45，所以数组的 45% 将是 1 ).

之后我们在数组上迭代 x 次。迭代如下所示：

首先，我们将数组复制到一个新数组上。
其次，我们按如下方式迭代 old 数组：我们查看我们所在街区附近的街区数量，并且根据两件事我们做这个：如果当前方块是空气并且在它的邻域 (-1,-1) 到 (1,1) 不包括他自己有超过 4 个块，将它更改为 NEW ARRAY 中的块如果当前图块是一个方块并且其附近的方块少于 3 个，则将其更改为 NEW ARRAY
复制旧数组中的新数组

问题是，即使我用确定性种子为统一法则播种，有时（1 次超过 3 次），经过两到三次迭代后，地图也会完全被块填满。在看了我的代码好几个小时之后，我几乎没有什么想法，这就是我来这里的原因。有代码：

cavefactory.h

#ifndef CAVEFACTORY_H_
#define CAVEFACTORY_H_

#include <vector>

namespace cavegenerator {

// define cave_t as a 2d vector of integers
using cave_t = std::vector<std::vector<int>>;

// constants
namespace DEFAULT {

constexpr unsigned short int WIDTH = 64;
constexpr unsigned short int HEIGHT = 64;
constexpr float DENSITY = 0.45;
constexpr unsigned short int BIRTH_LIMIT = 4;
constexpr unsigned short int DEATH_LIMIT = 3;

} // namespace DEFAULT


class CaveFactory {
    public:
        CaveFactory(unsigned short int width = DEFAULT::WIDTH,
                                unsigned short int height = DEFAULT::HEIGHT,
                                float density = DEFAULT::DENSITY);

        // makes a cave with the desired number of iterations and parameters
    static cave_t MakeCave(unsigned short int width = DEFAULT::WIDTH,
                                                    unsigned short int height = DEFAULT::HEIGHT,
                                                    float density = DEFAULT::DENSITY,
                                                    int iterations = 3,
                                                    unsigned short int bl = DEFAULT::BIRTH_LIMIT,
                                                    unsigned short int dl = DEFAULT::DEATH_LIMIT);

        // implemented in case of generalization of cave(more than two blocks)
        bool isSolid(int i, int j);

        cave_t getCave();

        void Print();
        void Iterate( unsigned short int bl = DEFAULT::BIRTH_LIMIT,
                                    unsigned short int dl = DEFAULT::DEATH_LIMIT );

    private:
    cave_t cave_;

    int NumberOfNeighbours(int i, int j);

    void Initialize(float density = DEFAULT::DENSITY);


};

} // namespace cavegenerator

#endif // CAVEFACTORY_H_

cavefactory.cc

#include "cavefactory.h"
#include <random>
#include <iostream>
#include <ctime>
#include <algorithm>


namespace cavegenerator {


CaveFactory::CaveFactory(unsigned short int width, unsigned short int height, float density) {
    cave_.resize(width);
  for (auto &i : cave_) {
    i.resize(height);
  }
  Initialize(density);
}

bool CaveFactory::isSolid(int i, int j) {
    return (cave_[i][j] == 1);
}

int CaveFactory::NumberOfNeighbours(int x, int y) {
    int num = 0;

  for (int i = -1; i < 2; i++) {
        for (int j = -1; j < 2; j++) {
      if ( i == 0 && j == 0 ) continue; // we don't want to count ourselve

      // if out of bounds, add a solid neighbour
      if ( x + i >= (int)cave_.size() || x + i < 0 || y + j >= (int)cave_[i].size() || y + j < 0) {
                ++num;
            } else if (isSolid(x+i, y+j)) {
                ++num;
            }
        }
    }

    return num;
}

cave_t CaveFactory::getCave() {
    return cave_;
}

void CaveFactory::Print() {
    for (auto &i : cave_) {
        for (auto &j : i) {
            std::cout << ((j==1) ? "x" : " ");
        }
        std::cout << "\n";
  }
  return;
}

cave_t CaveFactory::MakeCave(unsigned short int width,
                                unsigned short int height,
                                float density,
                                int iterations,
                                unsigned short int bl,
                                unsigned short int dl)
{

    CaveFactory cave(width, height, density);
  for (int i = 0; i < iterations; i++) {
        cave.Iterate(bl, dl);
  }

  return cave.getCave();
}


// Initlialize the cave with the specified density
void CaveFactory::Initialize(float density) {
  std::mt19937 rd(4);
  std::uniform_real_distribution<float> roll(0, 1);

  for (auto &i : cave_) {
        for (auto &j : i) {
            if (roll(rd) < density) {
                j = 1;
            } else {
                j = 0;
            }
        }
  }
}

// for each cell in the original cave, if the cell is solid:
// if the number of solid neighbours is under the death limit, we kill the block
// if the cell is air, if the number of solid blocks is above the birth limit we place a block
void CaveFactory::Iterate(unsigned short int bl, unsigned short int dl) {
  cave_t new_cave = cave_;

  for (int i = 0; i < (int)cave_.size(); i++) {
        for (int j = 0; j < (int)cave_[0].size(); j++) {

      int number_of_neighbours = NumberOfNeighbours(i, j);
      if (isSolid(i, j) && number_of_neighbours < dl) {
                new_cave[i][j] = 0;
      } else if (!isSolid(i,j) && number_of_neighbours > bl) {
                new_cave[i][j] = 1;
      }
      }
  }

  std::copy(new_cave.begin(), new_cave.end(), cave_.begin());
}



} // namespace cavegenerator

main.cc

#include <iostream>
#include <vector>
#include <random>
#include <ctime>
#include <windows.h>

#include "cavefactory.h"



int main() {

  cavegenerator::CaveFactory caveEE;
  caveEE.Print();


for(int i = 0; i < 15; i++) {
        caveEE.Iterate();
        Sleep(600);
        system("cls");
        caveEE.Print();
  }
  return 0;
}

我知道windows.h是个坏习惯，我只是用它来调试。

我希望有人能让我明白，也许这只是我不知道的正常行为？

非常感谢。

Answer 1

NumberOfNeighbours 中的

(int)cave_[i].size() 不正确，应该是 (int)cave_[x+i].size()（或 (int)cave_[0].size()，因为所有行和列的大小都相等）。当 i 等于 -1 时，您有越界向量访问和未定义的行为。

具有确定性程序的未定义行为

Undefined behavior with determinist procedure

c++

arrays

vector

2d

procedural-generation