c++ - 递归回溯迷宫生成器 C++ 中的段错误

Question

我正在尝试使用递归回溯创建迷宫生成器，但遇到了一个我无法理解的问题。出于某种原因，我的移动函数返回值“18446744073709551615”。这(当然)会导致段错误。为什么我的移动函数只能将值增加或减少 2，而我的移动函数会返回这么大的值？

bool maze::generate(size_t x, size_t y) {

//mark the position as visited
labyrinth.s[y][x] = true;

//print to see progress
//this->print();

//if the position is not out of bounds
if (x < 0 || x > labyrinth.MAXWIDTH - 1 || y < 0 || y > labyrinth.MAXHIGHT - 1) {
//if the position is the endpoint return true
if (labyrinth.v[y][x - 1] == 'W' || labyrinth.v[y][x + 1] == 'W' || labyrinth.v[y - 1][x] == 'W' || labyrinth.v[y + 1][x] == 'W') {
  return true;
 }
}

//pick a random direction
do {
  d = size_t(rand() % 4);
} while(!this->pos_test(x, y, d));
std::cout << x << ' ' << y << std::endl;

if (d == UP) {
y = move(x, y, UP);
}
else if (d == DOWN) {
y = move(x, y, DOWN);
}
else if (d == RIGHT) {
x = move(x, y, RIGHT);
}
else if (d == LEFT) {
x = move(x, y, LEFT);
}
else{
}
std::cout << x << ' ' << y << std::endl;
//recursively generate the maze
if (this->generate(x, y)) {
  return true;
}
}

void maze::initialize(size_t x, size_t y) {
   //set the maxhight and the maxwidth to y and x
   labyrinth.MAXHIGHT = y;
   labyrinth.MAXWIDTH = x;
   //set all elements in the vector to #
   for (size_t i = 0; i < labyrinth.MAXHIGHT; i++) {
     std::vector<char> temp;
     for (size_t j = 0; j < labyrinth.MAXWIDTH; j++) {
       temp.push_back(labyrinth.wall);
     }
     labyrinth.v.push_back(temp);
   }
   for (size_t i = 0; i < labyrinth.MAXHIGHT; i++) {
     for (size_t j = 0; j < labyrinth.MAXWIDTH; j++) {
       if (j % 2 == 1 && i % 2 == 1 && j != labyrinth.MAXWIDTH - 1 && j != 0 && i != labyrinth.MAXHIGHT - 1 && i != 0) {
         labyrinth.v[j][i] = labyrinth.path;
       }
     }
   }
     //set all posistions to unvisited
     for (size_t i = 0; i < labyrinth.MAXHIGHT; i++) {
       std::vector<bool> temp2;
       for (size_t j = 0; j < labyrinth.MAXWIDTH; j++) {
         temp2.push_back(false);
       }
       labyrinth.s.push_back(temp2);
    }
     //setup the start point
     labyrinth.v[0][1] = 'S';
     //setup the endpoint
     labyrinth.v[labyrinth.MAXHIGHT - 2][labyrinth.MAXWIDTH - 1] = 'W';

  }

  //if a position has been visited or if not possible to go to return true
 bool maze::pos_test(size_t x, size_t y, size_t d) const {
    //if the position is out of bounds return false
    if (x < 0 || y < 0 || x > labyrinth.MAXWIDTH - 1 || y > labyrinth.MAXHIGHT - 1) {
       return true;
   }
    else if (x == 1 && d == LEFT) {
      return true;
   }
    else if (y == 1 && d == UP) {
      return true;
   }
   else if (x == labyrinth.MAXWIDTH - 1 && d == RIGHT) {
     return true;
   }
   else if (y == labyrinth.MAXHIGHT - 1 && d == DOWN) {
     return true;
   }
   else if (d == UP) {
     return labyrinth.s[y - 2][x];
   }
   else if (d == DOWN) {
     return labyrinth.s[y + 2][x];
   }
   else if (d == RIGHT) {
     return labyrinth.s[y][x + 2];
   }
   else if (d == LEFT) {
     return labyrinth.s[y][x - 2];
   }
   else  {
     return true;
   }
 }


size_t maze::move(size_t x, size_t y, size_t d) {
//if the position is out of bounds return without modifying
if (x < 0 || x > labyrinth.MAXWIDTH - 1) {
  return x;
}
else if (y < 0 || y > labyrinth.MAXHIGHT - 1) {
  return y;
}
else if (d == UP) {
  labyrinth.v[y - 1][x] = labyrinth.path;
  return y =  y - 2;
}
else  if (d == DOWN) {
  labyrinth.v[y + 1][x] = labyrinth.path;
  return y = y + 2;
}
else if (d == RIGHT) {
  labyrinth.v[y][x + 1] = labyrinth.path;
  return x = x + 2;
}
else if (d == LEFT) {
  labyrinth.v[y][x - 1] = labyrinth.path;
  return x = x - 2;
}
else  {
}
}

Answer 1

您的无符号 64 位返回类型 size_t 正在下溢。

您正在检查 x 和 y 是否小于零，但这还不够，因为 0 和 1 仍然太低，因为您要减去 2!

你得到的数字是十六进制的 0xFFFFFFFFFFFFFFFF。这是无符号 64 位整数的最大可能值。

它来自计算1 - 2。是的，这应该是 -1，但是因为您的移动函数不返回一个有符号数字而是一个无符号数字(检查size_t 上的文档)，它不能是负数! Instead, it wraps around to the highest possible number.

您可以想象这与您在尝试计算纸上的 1 - 2 时忽略“您不能从纸上较小的数字中减去较大的数字”规则时得到 ...99999999999 的方式相同。

作为旁注:我想无论如何都不需要负结果，因为实际上你的巨大数字一旦添加到指针，就会溢出回正，所以基本上它会起作用在你的情况下，同样是一个真实的 -1 并且段错误来自于访问缓冲区开始之前之前的东西，不超过它，但它归结为同样的事情。

除此之外，无需执行 return y = y - 2 等操作。只需返回 y - 2。