Random walk on a grid

Question

// generate a random "walk" of letters from A to Z in a 2D grid, assuming a 
// character set with contiguous values of uppercase letters (e.g. ASCII); 
// stops if the "walker" gets stuck
// example of a successful walk:

//  A  .  .  .  I  J  K  .  .  . 
//  B  C  F  G  H  .  L  .  .  .
//  .  D  E  .  .  .  M  .  .  .
//  .  .  .  .  .  O  N  .  .  .
//  .  .  .  .  .  P  .  .  .  .
//  .  .  .  .  .  Q  .  .  .  .
//  .  .  .  .  .  R  S  .  .  .
//  .  .  .  .  .  .  T  U  .  . 
//  .  .  .  .  .  .  .  V  W  Z
//  .  .  .  .  .  .  .  .  X  Y

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <ctype.h>

#define GRID_SIZE 10

// movement directions
#define DIR_NUM 4

#define UP      0
#define LEFT    1
#define DOWN    2
#define RIGHT   3
#define ANY     (-1)

bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
              char grid[rows][cols]);
void generate_random_walk(size_t rows, size_t cols, char grid[rows][cols]);
void print_array(size_t rows, size_t cols, char grid[rows][cols]);

int main(void)
{
    char grid[GRID_SIZE][GRID_SIZE] = { 0 };

    generate_random_walk(GRID_SIZE, GRID_SIZE, grid);
    print_array(GRID_SIZE, GRID_SIZE, grid);

    return 0;
}

void print_array(size_t rows, size_t cols, char grid[rows][cols])
{
    for (size_t r = 0; r < rows; ++r) {
        for (size_t c = 0; c < cols; ++c) {
            char grid_c = grid[r][c];
            printf(" %c ", isalpha(grid_c) ? grid_c : '.');
        }
        putchar('\n');
    }
}

// checks all the directions by default (ANY)
bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
              char grid[rows][cols])
{
    bool cangoup    = (rpos > 0) && grid[rpos - 1][cpos] == 0;
    bool cangoleft  = (cpos > 0) && grid[rpos][cpos - 1] == 0;
    bool cangodown  = (rpos < rows - 1) && grid[rpos + 1][cpos]  == 0;
    bool cangoright = (cpos < cols - 1) && grid[rpos][cpos + 1]  == 0;

    switch (dir) {
    case UP:    return cangoup;
    case LEFT:  return cangoleft;
    case DOWN:  return cangodown;
    case RIGHT: return cangoright;
    default:    return cangoup || cangoleft || cangodown || cangoright; // ANY
    }
}

void generate_random_walk(size_t rows, size_t cols, char grid[rows][cols])
{
    size_t rpos, cpos;

    srand((unsigned int) time(NULL));

    rpos = cpos = 0;
    grid[0][0] = 'A';
    for (char c = 'B'; c <= 'Z' && can_move(ANY, rpos, cpos, rows, cols, grid); c++) {
        // move in a random direction
        for (int dir;;) {
            dir = rand() % DIR_NUM;
            if (can_move(dir, rpos, cpos, rows, cols, grid)) {
                switch (dir) {
                case UP:    --rpos; break;
                case LEFT:  --cpos; break;
                case DOWN:  ++rpos; break;
                case RIGHT: ++cpos; break;
                default:
                    printf("Impossible movement direction.\n");
                    exit(EXIT_FAILURE);
                }
                break; // break out of the loop
            }
        }

        // leave a trail
        grid[rpos][cpos] = c;
    }
}

To summarize, this program prints a grid with a random walk of uppercase letters in order. If the "walker" cannot move in any direction due to lack of space around it (up, down, left, and right), the walking terminates.

What I'm interested in, aside from general tips regarding my code that you may be able to give me, are two things:

1. I've read that functions shouldn't normally take more than 2–3 parameters; do you think my functions really "suffer" from taking more than 3 parameters, and if so, how would I go about mitigating that?

2. Should I be using a size_t when looping over an array or similar, or should I use an int instead? I've read here on Stack Exchange various opinions concerning this: some people say size_t should always be used since it's essentially undefined behavior if the array's size is greater than MAX_INT, etc., while others say unsigned and signed types ought not to be mixed (and I generally have to use them in expressions that undergo the usual arithmetic conversions), and this is a major source of bugs. Pragmatically, I believe I should therefore use a regular int. There's another thing I've noticed, and that is if I have to actually use these counters to perform some calculation: in those cases I really have no recourse, and what I end up doing is simply casting and praying, hoping that the array is of a reasonable size (i.e. that my size_t counter, or the result of the expression isn't out of the representable range for an int). I think this is even worse than using an int from the beginning, since the interface that the size_t type provides is not conformed to, so my code is "lying" to both itself and the reader.

Note that I would use an enum instead of the #define definitions for the directions, but my book hasn't gotten to them yet, so I think we shouldn't focus on this. Also, I've looked at other questions with this same exercise, but the code/approach presented there is somewhat different.

Answer 1

Answers to your questions

I've read that functions shouldn't normally take more than 2–3 parameters

I wouldn't worry about that too much. If you do have lots of parameters though, you should think about whether they are really necessary, and perhaps if there is a way to group them into a struct, and whether to pass that by value or by pointer. For example, your code might benefit from creating a struct for holding coordinates, like so:

typedef struct {
    size_t row;
    size_t col;
} vec2;

Then you can reduce the number of parameters passed:

bool can_move(int dir, vec2 pos, vec2 size, char grid[size.row][size.col])

This shouldn't change the generated machine code, but it makes the code a bit more readable.

Should I be using a size_t when looping over an array or similar, or should I use an int instead?

I would recommend using size_t. In particular, size_t is guaranteed to be large enough to hold the size of any array, and you should therefore also use it for the array index. It's also unsigned, which simplifies bounds checks. Mixing size_t and int is bad of course, ensure you have compiler warnings turned on, so the compiler can warn you about such issues, and fix all warnings you see.

what I end up doing is simply casting and praying,

Don't do that! Use types consitently and avoid unnecessary casts. It looks like you are still learning C, you will probably learn all the details at some point and then you will be reason about these things instead. If you still need it to do casting somewhere and you are not sure if it is safe, ask on StackOverflow.

Avoid unnecessary forward declarations

If you change the order in which the function appear in your source file, you don't need the forward declarations anymore. That avoids repetition, and also avoids potential mistakes.

Use enum or static const variables

Note that I would use an enum instead of the #define definitions for the directions,

Correct, using an enum here would be much better.

but my book hasn't gotten to them yet, so I think we shouldn't focus on this.

We should, since other people might also read your question here, and they might not be restricted by how far they are in a particular book! It's fine if you want to ignore this at this point though. But apart from enums, another possibility to avoid using #define is to use static const variables:

static const int UP = 0;
static const int LEFT = 1;
...
static const int ANY = -1;

This has the advantage that these constants now have a proper type, and you don't have to worry about how macro substitution works, so less chance of forgetting parenthesis like you correctly had to add to ANY.

You still need to use #define for GRID_SIZE though, as unfortunately a const variable is not good enough for C as the size when declaring an array (unless it is a VLA).

Nicer for-statements

The implementation of the random walk looks reasonably OK. However, the for-loops in generate_random_walk() look a little bit weird to me. The outer for-loop starts at B instead of A. I would rather write it so that it looks like:

for (char c = 'A'; c <= 'Z'; c++) {
    ...
}

Because this way, it clearly states that you want to loop from 'A' to 'Z' in one single line. The inner for-statement is also weird, it doesn't do anything except delcare a variable. Basically, it's an infinite loop, and a more ideomatic way to write that is using while (true). So I would structure it rather like so:

for (char c = 'A'; c <= 'Z'; c++) {
    grid[rpos][cpos] = c;

    if (!can_move(ANY, ...)) {
        break;
    }

    while (true) {
        int dir = rand() % DIR_NUM;
        ...
    }
}

Another option is to change can_move() so it will try to do a random move, and return true if succesful or false if it couldn't move anymore. It should then also be renamed, for example to try_random_move(), and use pointers for rpos and cpos so they can be modified:

bool try_random_move(size_t *rpos, size_t *cpos, ...) {
    bool cangoup    = (*rpos > 0) && grid[*rpos - 1][*cpos] == 0;
    bool cangoleft  = (*cpos > 0) && grid[*rpos][*cpos - 1] == 0;
    bool cangodown  = (*rpos < rows - 1) && grid[*rpos + 1][*cpos] == 0;
    bool cangoright = (*cpos < cols - 1) && grid[*rpos][*cpos + 1] == 0;

    if (!(cangoup || cangoleft || cangodown || cangoright)) {
        return false;
    }

    while (true) {
        int dir = rand() % DIR_NUM;
        ...
    }
}

Then generate_random_walk() simplifies to:

void generate_random_walk(size_t rows, size_t cols, char grid[rows][cols])
{
    size_t rpos = 0;
    size_t cpos = 0;

    for (char c = 'A'; c <= 'Z'; c++) {
        grid[rpos][cpos] = c;

        if (!try_random_move(&rpos, &cpos, rows, cols, grid)) {
            break;
        }
    }
}

Avoiding the "infinite" loop

You select a random direction, and then check whether movement into that direction is possible. If not, you try another random direction. The problem with that is that it can take a lot of attemps to choose a valid direction, as you never know with random numbers. A possible way to avoid repeated random attempts is to just try out all the remaining possibilities. However, you have to be careful to not introduce an accidental bias in your algorithm.