在生成随机迷宫时遇到分段错误

Question

我尝试随机生成一个迷宫，但在编译下面的程序时出现了段错误。

以下是代码：

void spread(int v, int x, int y, int *t,int w, int *count){
    //table of directions(Right,Down,Left,Up)
    int d[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; 
    int i;
    t[y * w + x] = v;

    if(v == 0 && (x & 1) && (y & 1))
        (*count)++; /*increments at every box which has value as zero with x odd and y also*/

    //spread the value to all directions
    for(i = 0; i < 4; i++){
        if(v < t[(y+d[i][1]) * w + x +d[i][0]]){
            spread(v,x + d[i][0],y+d[i][0],t,w,count);
        }
    }
}

int *init(int m, int n){
        //Initializing the maze
        int *t = NULL, mp = 2 * m +1, np = 2 * n + 1;
        int x,y,k,d;
        int count = 1;
        t = malloc(mp * np * sizeof *t);
        assert(t);
        for(y = k = 0; y < np ;++y){
            for(x = 0; x < mp; ++x){
                if((x & 1) && (y & 1))
                    t[y * mp + x] = k++;
                else
                    t[y * mp + x] = -1; 
            }

        }
        //Make a labyrinth randomly
        while(count < (m * n)){
            srand(time(NULL));
            if(myRand(2)){ // Up/Down separator 
                do{
                    x = myRand(m) * 2 + 1;
                    y = (myRand(n - 1) + 1) * 2;

                }while(t[(y - 1) * mp + x] == t[(y + 1) * mp + x]); /*Don't select the ones which are equal*/

                d = t[(y - 1) * mp + x] - t[(y + 1) * mp + x];
                //d selects the lowest one
                if(d > 0){
                    t[y * mp +x] = t[(y + 1) * mp + x];
                    spread(t[(y + 1) * mp +x],x,y-1,t,mp,&count);
                }

                else if(d < 0){
                    t[y * mp +x] = t[(y - 1) * mp + x];
                    spread(t[(y - 1) * mp +x],x,y+1,t,mp,&count);
                }   
            }
            else{   //Right/Left separator
                do{         
                    x = (myRand(m - 1) + 1) * 2;
                    y = myRand(n) * 2 + 1;

                }while(t[y * mp + x - 1] == t[y * mp + x + 1]);

                d = t[y * mp + x - 1] - t[y * mp + x + 1];

                if(d > 0){
                    t[y * mp +x] = t[y * mp + x + 1];
                    spread(t[y * mp + x + 1],x-1,y,t,mp,&count);
                }

                else if(d < 0){
                    t[y * mp +x] = t[y * mp +x - 1];
                    spread(t[y * mp + x - 1],x+1,y,t,mp,&count);
                }   
            }
        }   
        return t;
}

迷宫首先被初始化（这里是t），墙的值为-1，节点的值v>0。

然后为了连接节点（以便有一个迷宫），随机选择一个方框，但行或列必须是奇数才能选择代表分隔符（上/下或左/右）的墙。

因此，“d”取围绕墙的盒子中的最小值（意味着在墙上方的盒子和在墙下方的盒子之间取最小值，右/左也是同样的道理）。

函数“spread”：它将一个值向所有方向（右、下、左、上）传播。

以下是一个示例：

+  +  +  +  +  +  +  +  +  
+  0  +  1  +  2  +  3  +  
+  +  +  +  +  +  +  +  +  
+  4  +  5  +  6  +  7  +  
+  +  +  +  +  +  +  +  +  
+  8  +  9  +  10 +  11 +  
+  +  +  +  +  +  +  +  + 

当将某些值传递给其他人时

+  +  +  +  +  +  +  +  +  
+  0  +  1  1  1  +  3  +  
+  +  +  +  +  +  +  +  +  
+  4  +  5  +  6  +  7  +  
+  +  +  +  +  +  +  +  +  
+  8  +  9  9  9  +  11 +  
+  +  +  +  +  +  +  +  + 

我尝试通过调试程序来解决问题，它在一开始能够正常显示上面的内容，但随后出现了以下错误信息：

Program received signal SIGSEGV, Segmentation fault.
0x00000000004008e4 in spread (
   v=<error reading variable: Cannot access memory at address 0x7fffff7fefec>, x=<error reading variable: Cannot access memory at address 0x7fffff7fefe8>, 
    y=<error reading variable: Cannot access memory at address 0x7fffff7fefe4>, t=<error reading variable: Cannot access memory at address 0x7fffff7fefd8>, 
    w=<error reading variable: Cannot access memory at address 0x7fffff7fefe0>, count=<error reading variable: Cannot access memory at address 0x7fffff7fefd0>)
    at Lab.c:34
#1  0x0000000000400a1a in spread (v=8, x=4, y=6, t=0x603010, w=9, 
    count=0x7fffffffddd4) at Lab.c:48
#2  0x0000000000400a1a in spread (v=8, x=4, y=6, t=0x603010, w=9, 
    count=0x7fffffffddd4) at Lab.c:48
#3  0x0000000000400a1a in spread (v=8, x=4, y=6, t=0x603010, w=9, 
    count=0x7fffffffddd4) at Lab.c:48
#4  0x0000000000400a1a in spread (v=8, x=4, y=6, t=0x603010, w=9, 
    count=0x7fffffffddd4) at Lab.c:48

- YYY

---

疑似无限递归。 - vicatcu

x不能超过mp（y也一样，不能超过np），因此我认为y * w + x的值也不能超过mp * np。 - YYY

是的，您没有检查 x 和 y 是否仍在 t 的范围内。我认为这可能会导致内存问题。 - Hollyol

但通常情况下，你可能不会意识到在“for”循环中（递归地）调用函数“spread”时发生了什么。 - YYY

非常感谢大家的帮助，我在显示了x和y的值之后（根据Hollyol的建议），意识到自己犯了一个错误，并发现它们具有相同的值。因此，在循环中的if之后调用函数spread的那一行被替换为：spread(v,x + d[i][0],y+d[i][1],t,w,count)。 - YYY

Answer 1

void spread(int v, int x, int y, int *t,int w, int *count){
    //table of directions(Right,Down,Left,Up)
    int d[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; 
    int i;
    t[y * w + x] = v;

    if(v == 0 && (x & 1) && (y & 1))
        (*count)++; /*increments at every box which has value as zero with x odd and y also*/

    //spread the value to all directions
    for(i = 0; i < 4; i++){
        if(v < t[(y+d[i][1]) * w + x +d[i][0]]){
            spread(v,x + d[i][0],y+d[i][1],t,w,count);
        }
    }
}

int *init(int m, int n){
        //Initializing the maze
        int *t = NULL, mp = 2 * m +1, np = 2 * n + 1;
        int x,y,k,d;
        int count = 1;
        t = malloc(mp * np * sizeof *t);
        assert(t);
        for(y = k = 0; y < np ;++y){
            for(x = 0; x < mp; ++x){
                if((x & 1) && (y & 1))
                    t[y * mp + x] = k++;
                else
                    t[y * mp + x] = -1; 
            }

        }
        //Make a labyrinth randomly
        srand(time(NULL));
        while(count < (m * n)){

            if(myRand(2)){ // Up/Down separator 
                do{
                    x = myRand(m) * 2 + 1;
                    y = (myRand(n - 1) + 1) * 2;

                }while(t[(y - 1) * mp + x] == t[(y + 1) * mp + x]); /*Don't select the ones which are equal*/

                d = t[(y - 1) * mp + x] - t[(y + 1) * mp + x];
                //d selects the lowest one
                if(d > 0){
                    t[y * mp +x] = t[(y + 1) * mp + x];
                    spread(t[(y + 1) * mp +x],x,y-1,t,mp,&count);
                }

                else if(d < 0){
                    t[y * mp +x] = t[(y - 1) * mp + x];
                    spread(t[(y - 1) * mp +x],x,y+1,t,mp,&count);
                }   
            }
            else{   //Right/Left separator
                do{         
                    x = (myRand(m - 1) + 1) * 2;
                    y = myRand(n) * 2 + 1;

                }while(t[y * mp + x - 1] == t[y * mp + x + 1]);

                d = t[y * mp + x - 1] - t[y * mp + x + 1];

                if(d > 0){
                    t[y * mp +x] = t[y * mp + x + 1];
                    spread(t[y * mp + x + 1],x-1,y,t,mp,&count);
                }

                else if(d < 0){
                    t[y * mp +x] = t[y * mp +x - 1];
                    spread(t[y * mp + x - 1],x+1,y,t,mp,&count);
                }   
            }
        }   
        return t;
}

- YYY