行動決策模式

Question

我正在寫迷宮發生器，在某些時候我必須選擇一個單元格的隨機未訪問鄰居。第一個想法是枚舉左邊= 0，頂部= 1，右邊= 2，底部= 3的鄰居，並使用rand（）％4生成隨機數並選擇合適的單元格。然而，並非所有的細胞設有4個鄰居，讓我不得不寫下面的代碼：

Cell* getRandomNeighbour(const Maze* const maze, const Cell* const currentCell) { 

int randomNumb = rand() % 4; 

int timer = 1; 

while(timer > 0) { 
    if (randomNumb == 0 && currentCell->x < maze->width-1 && maze->map[currentCell->y][currentCell->x+1].isUnvisited) 
     return &maze->map[currentCell->y][currentCell->x+1]; 
    if (randomNumb == 1 && currentCell->x > 0 && maze->map[currentCell->y][currentCell->x-1].isUnvisited) 
     return &maze->map[currentCell->y][currentCell->x-1]; 
    if (randomNumb == 2 && currentCell->y < maze->height-1 && maze->map[currentCell->y+1][currentCell->x].isUnvisited) 
     return &maze->map[currentCell->y+1][currentCell->x]; 
    if (randomNumb == 3 && currentCell->y > 0 && maze->map[currentCell->y-1][currentCell->x].isUnvisited) 
     return &maze->map[currentCell->y-1][currentCell->x]; 

    timer--; 
    randomNumb = rand() % 4; 
} 


if (currentCell->x < maze->width-1 && maze->map[currentCell->y][currentCell->x+1].isUnvisited) 
    return &maze->map[currentCell->y][currentCell->x+1]; 
if (currentCell->x > 0 && maze->map[currentCell->y][currentCell->x-1].isUnvisited) 
    return &maze->map[currentCell->y][currentCell->x-1]; 
if (currentCell->y < maze->height-1 && maze->map[currentCell->y+1][currentCell->x].isUnvisited) 
    return &maze->map[currentCell->y+1][currentCell->x]; 
if (currentCell->y > 0 && maze->map[currentCell->y-1][currentCell->x].isUnvisited) 
    return &maze->map[currentCell->y-1][currentCell->x]; 

return NULL; 
} 

所以，如果在10次迭代沒有選擇正確的決定，它將被強力回升。這種方法似乎很好，因爲變量變量定時器改變了迷宮的複雜度：更少的定時器是更直接的迷宮。不過，如果我唯一的目的是完全隨機生成迷宮，則需要很長的執行時間，並且看起來有點難看。有沒有任何模式（使用C語言）或重構的方式，可以使我無需長時間切換和大量if-else結構來處理這種情況？

Answer 1

保理重複的代碼，並選擇方向的順序來嘗試這個收益率的更嚴格的方式：

// in_maze returns whether x, y is a valid maze coodinate. 
int in_maze(const Maze* const maze, int x, int y) { 
    return 0 <= x && x < maze->width && 0 <= y && y < maze->height; 
} 

Cell *get_random_neighbour(const Maze* const maze, const Cell* const c) { 
    int dirs[] = {0, 1, 2, 3}; 
    // Randomly shuffle dirs. 
    for (int i = 0; i < 4; i++) { 
     int r = i + rand() % (4 - i); 
     int t = dirs[i]; 
     dirs[i] = dirs[r]; 
     dirs[r] = t; 
    } 
    // Iterate through the shuffled dirs, returning the first one that's valid. 
    for (int trial=0; trial<4; trial++) { 
     int dx = (dirs[trial] == 0) - (dirs[trial] == 2); 
     int dy = (dirs[trial] == 1) - (dirs[trial] == 3); 
     if (in_maze(maze, c->x + dx, c->y + dy)) { 
      const Cell * const ret = &maze->map[c->y + dy][c->x + dx]; 
      if (ret->isUnvisited) return ret; 
     } 
    } 
    return NULL; 
} 

（免責聲明：未經檢驗的 - 它可能有一些小問題，例如const正確性） 。

Answer 2

由於@pat和@Ivan Gritsenko建議，你只能限制你隨意選擇有效的細胞，就像這樣：

Cell* getRandomNeighbour(const Maze* const maze, const Cell* const currentCell) 
{ 
    Cell *neighbours[4] = {NULL}; 
    int count = 0; 

    // first select the valid neighbours 
    if ( currentCell->x < maze->width - 1 
     && maze->map[currentCell->y][currentCell->x + 1].isUnvisited) { 
     neighbours[count++] = &maze->map[currentCell->y][currentCell->x + 1]; 
    } 
    if ( currentCell->x > 0 
     && maze->map[currentCell->y][currentCell->x - 1].isUnvisited) { 
     neighbours[count++] = &maze->map[currentCell->y][currentCell->x - 1]; 
    } 
    if ( currentCell->y < maze->height - 1 
     && maze->map[currentCell->y + 1][currentCell->x].isUnvisited) { 
     neighbours[count++] = &maze->map[currentCell->y + 1][currentCell->x]; 
    } 
    if ( currentCell->y > 0 
     && maze->map[currentCell->y - 1][currentCell->x].isUnvisited) { 
     neighbours[count++] = &maze->map[currentCell->y - 1][currentCell->x]; 
    } 

    // then choose one of them (if any) 
    int chosen = 0; 
    if (count > 1)  
    { 
     int divisor = RAND_MAX/count; 
     do { 
      chosen = rand()/divisor; 
     } while (chosen >= count); 
    } 
    return neighbours[chosen]; 
} 

隨機數生成部分（而不是更常見的rand() % count）背後的基本原理是在this answer中有詳細解釋。