Pattern for action decision

Question

I am writing maze generator and at the some point I have to choose random unvisited neighbour of a cell. The first idea was just to enumerate neighbours such as left = 0, top = 1, right = 2, bottom = 3 and use rand() % 4 to generate random number and choose appropriate cell. However, not all cells features 4 neighbours, so that I had to write following code:

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;
}

So, if after 10 iterations the right decision isn't chosen, it will be picked by brute force. This approach seems to be good for the reason that varying of variable timer changes the complexity of maze: the less timer is, the more straightforward maze is. Nevertheless, if my only purpose is to generate completely random maze, it takes a lot of execution time and look a little bit ugly. Is there any pattern(in C language) or way of refactoring that could enable me to deal with this situation without long switches and a lot of if-else constructions?

You ask for an algorithm. A design-pattern is something completely different. — too honest for this site, Feb 25 '17 at 14:05
Why not push the legal neighbors onto a stack (an array with a depth counter) and pick one of those elements at random, using the depth as the modulus. — pat, Feb 25 '17 at 14:10
@pat, @ NikitaRock there might be a corner case when you end up in a dead-end. Then the stack of legal neighbours will be empty. Make sure to add a correct handling of such situation. — Ivan Gritsenko, Feb 25 '17 at 15:12

score 1 · Answer 1 · edited May 23 '17 at 10:29

As @pat and @Ivan Gritsenko suggested, you can limit your random choice to the valid cells only, like this:

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];
}

The rationale behind the random number generation part (as opposed to the more common rand() % count) is well explained in this answer.

score 0 · Answer 2 · answered Feb 25 '17 at 15:22

Factoring repeated code, and a more disciplined way of picking the order of directions to try yields this:

// 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;
}

(Disclaimer: untested -- it probably has a few minor issues, for example const correctness).

Pattern for action decision

2 Answers2