5
\$\begingroup\$

Beware: if you run this program with default configuration, it will produce from ~250 to ~1000 plain PPM images in the directory it's being run in, which all summed up will weigh ~4MB.

These PPMs can be turned into a gif or other format of your choice that supports animation using a media converter command. For example, ImageMagick program convert does the job:

convert -delay 5 *.ppm maze.gif

This will take awhile (less than a minute on my machine) and produce a tiny 25x25 gif. You can change IMG_SCALE from 1 to 10 to make a 250x250 gif, however the PPM chain will take up ~500MB. Scaling with my program is hella faster than using a general convert scaler, and the end result weighs much less.

Maze

I would like feedback on how I could improve the code of the program. I would be particularly interested on opinions on my very heavy use of preprocessor macros in this program, which I think help the program be shorter and thus more readable, however they were a huge pain to debug while I developed this program.

In the end you will probably want to cleanup everything, so just run rm maze*.

All the commands assume you're using a POSIX-compliant OS, by the way, but I'm sure you will find a way to achieve the equivalent result on other OS.

Here's the program (136 code, 17 blank and 7 comment lines, all < 80 characters):

// Make chains of PPMs showing a maze generated and solved using backtracking

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

// Configurables
#define GEN_PATH ("maze%05d.ppm") // PPM generation chain format string
#define SOLVE_PATH ("maze%05d.ppm") // PPM solution chain format string
#define MAZE_W (25) // maze width: must be odd, >= 3, < 32768
#define MAZE_H (25) // maze height: must be odd, >= 3, < 32768
#define START_X (0) // start x coordinate: must be even, >= 0, < MAZE_W
#define START_Y (0) // start y coordinate: must be even, >= 0, < MAZE_H
#define FINISH_X (24) // finish x coordinate: must be odd, >= 1, < MAZE_W
#define FINISH_Y (24) // finish y coordinate: must be idd, >= 1, < MAZE_H
#define IMG_SCALE (1) // image scale: size of square in pixels

// Colors (also configurable)
enum {
    COLOR_WALL, // Color for walls (solid blocks)
    COLOR_HOLE, // Color for holes (empty blocks)
    COLOR_PATH, // Color for current algorithm path
    COLOR_ENDS, // Color of ends (start and finish)
    COLOR_COUNT
};
const char *COLORS[COLOR_COUNT] = {
    "  0   0   0\n",
    "255   0   0\n",
    "  0 255   0\n",
    "255   0 255\n",
};

// Helper macros
#define MAZE_A (MAZE_W * MAZE_H) // maze area
#define MAZE_I(x, y) ((y) * MAZE_W + (x)) // convert coordinates into index
#define MAZE_X(i) ((i) % MAZE_W) // extract X coordinate from index
#define MAZE_Y(i) ((i) / MAZE_W) // extract Y coordinate from index
#define IMG_W (MAZE_W * IMG_SCALE) // image width
#define IMG_H (MAZE_H * IMG_SCALE) // image height
#define START_I (MAZE_I(START_X, START_Y)) // start index
#define FINISH_I (MAZE_I(FINISH_X, FINISH_Y)) // finish index
#define INVALID_INDEX (-1) // an invalid index
#define VALID_I(i) ((i) >= 0 && (i) < MAZE_A) // is index valid
#define INVALID_I(i) (!VALID_I(i)) // is index invalid
#define NORTH_EDGE(i) (VALID_I(i) && MAZE_Y(i) == MAZE_H - 1) // on North edge?
#define SOUTH_EDGE(i) (VALID_I(i) && MAZE_Y(i) == 0) // on South edge?
#define EAST_EDGE(i) (VALID_I(i) && MAZE_X(i) == MAZE_W - 1) // on East edge?
#define WEST_EDGE(i) (VALID_I(i) && MAZE_X(i) == 0) // on West edge?
#define GO_NORTH(i) (MAZE_I(MAZE_X(i), MAZE_Y(i) + 1)) // NORTH w/o err checks
#define GO_SOUTH(i) (MAZE_I(MAZE_X(i), MAZE_Y(i) - 1)) // SOUTH w/o err checks
#define GO_EAST(i) (MAZE_I(MAZE_X(i) + 1, MAZE_Y(i))) // EAST w/o err checks
#define GO_WEST(i) (MAZE_I(MAZE_X(i) - 1, MAZE_Y(i))) // WEST w/o err checks
#define NORTH(i) (VALID_I(i) && !NORTH_EDGE(i) ? GO_NORTH(i) : INVALID_INDEX)
#define SOUTH(i) (VALID_I(i) && !SOUTH_EDGE(i) ? GO_SOUTH(i) : INVALID_INDEX)
#define EAST(i) (VALID_I(i) && !EAST_EDGE(i) ? GO_EAST(i) : INVALID_INDEX)
#define WEST(i) (VALID_I(i) && !WEST_EDGE(i) ? GO_WEST(i) : INVALID_INDEX)

// Global variables
static int maze[MAZE_A];

// Function signatures
static void recordFrame(const char *fstr);
static void generate(int i);
static bool chooseRandomPath(int i, int *bridge, int *path);
static bool isValidNewIndex(int i, bool validateFinish);
static bool solve(int i);

//////////////////////////////////////////////////////////////////////////////

int main(void) {
    srand(time(NULL));
    for (int i = 0; i < MAZE_A; ++i) maze[i] = COLOR_WALL;
    maze[START_I] = maze[FINISH_I] = COLOR_ENDS;
    generate(START_I);
    solve(START_I);
}

static void recordFrame(const char *fstr) {
    static int n = 0;
    char filename[FILENAME_MAX];
    snprintf(filename, FILENAME_MAX, fstr, n++);
    FILE *f = fopen(filename, "w");
    fprintf(f, "P3 %d %d 255\n", IMG_W, IMG_H);
    for (int y = MAZE_H - 1; y >=0; --y) {
        for (int i = 0; i < IMG_SCALE; ++i) {
            for (int x = 0; x < MAZE_W; ++x) {
                for (int j = 0; j < IMG_SCALE; ++j) {
                    fputs(COLORS[maze[MAZE_I(x, y)]], f);
                }
            }
        }
    }
    fclose(f);
}

static void generate(int i) {
    int bridge, path;
    if (maze[i] != COLOR_ENDS) maze[i] = COLOR_PATH;
    recordFrame(GEN_PATH);
    while (chooseRandomPath(i, &bridge, &path)) {
        maze[bridge] = COLOR_PATH;
        generate(path);
        maze[bridge] = COLOR_HOLE;
        recordFrame(GEN_PATH);
    }
    if (maze[i] == COLOR_PATH) maze[i] = COLOR_HOLE;
}

static bool chooseRandomPath(int i, int *bridge, int *path) {
    static bool finish = false; // finish must be reached only once
    if (i == FINISH_I) return false; // don't generate new paths from finish
    int n = 0, paths[4], bridges[4];
    if (isValidNewIndex(NORTH(NORTH(i)), !finish)) {
        bridges[n] = NORTH(i);
        paths[n++] = NORTH(NORTH(i));
    }
    if (isValidNewIndex(SOUTH(SOUTH(i)), !finish)) {
        bridges[n] = SOUTH(i);
        paths[n++] = SOUTH(SOUTH(i));
    }
    if (isValidNewIndex(EAST(EAST(i)), !finish)) {
        bridges[n] = EAST(i);
        paths[n++] = EAST(EAST(i));
    }
    if (isValidNewIndex(WEST(WEST(i)),  !finish)) {
        bridges[n] = WEST(i);
        paths[n++] = WEST(WEST(i));
    }
    if (n <= 0) return false; // no free paths left
    int rnd = rand() % n;
    *bridge = bridges[rnd];
    *path = paths[rnd];
    if (*path == FINISH_I) finish = true;
    return true;
}

static bool isValidNewIndex(int i, bool validateFinish) {
    if (i == FINISH_I) return validateFinish;
    else return VALID_I(i) && maze[i] == COLOR_WALL;
}

static bool solve(int i) {
    if (i == FINISH_I) return true;
    if (INVALID_I(i) || (i != START_I && maze[i] != COLOR_HOLE)) return false;

    if (maze[i] != COLOR_ENDS) maze[i] = COLOR_PATH;
    recordFrame(SOLVE_PATH);

    if (VALID_I(NORTH(i))) if (solve(NORTH(i))) return true;
    if (VALID_I(SOUTH(i))) if (solve(SOUTH(i))) return true;
    if (VALID_I(EAST(i))) if (solve(EAST(i))) return true;
    if (VALID_I(WEST(i))) if (solve(WEST(i))) return true;

    if (maze[i] == COLOR_PATH) maze[i] = COLOR_HOLE;
    recordFrame(SOLVE_PATH);

    return false;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Was there a specific reason to bascially program this in the preprocessor ?? \$\endgroup\$ – Harald Scheirich Sep 29 '17 at 17:27
  • \$\begingroup\$ @HaraldScheirich I thought it made code cleaner and shorter. \$\endgroup\$ – MarkWeston Sep 29 '17 at 17:39
  • 1
    \$\begingroup\$ You have more macros in this than we've put into a 150k line simulation package. I don't know what the C-crowd thinks about this, but it might be shorter in text but possibly longer in code. and much harder to reason over. WEST(WEST(i)) for example instantiates VALID_I at least 4 times. I'd consider that "not a good thing" \$\endgroup\$ – Harald Scheirich Sep 29 '17 at 19:39
3
\$\begingroup\$

I really like the results this produces. It's mesmerizing! Here are some things I would do differently:

Avoid Macros

You say:

I would be particularly interested on opinions on my very heavy use of preprocessor macros in this program, which I think help the program be shorter and thus more readable, however they were a huge pain to debug while I developed this program.

I'll be honest – I hate macros. They cause a lot of problems, and as you noted, are hard to debug. But the good news is that you don't need them for anything you've written here. Many of them can be replaced with proper named constants. For example:

const char* GEN_PATH = "maze%05d.ppm";
const char* SOLVE_PATH = "maze%06d.ppm";
const int MAZE_W = 25;
const int MAZE_H = 25;
// ... etc.

The others could easily be replaced with inline functions which are much easier to debug. Like this:

inline int MAZE_I (const int x, const int y)
{
    return y * MAZE_W + x;
}

Now you can actually step into the function to debug it! And you don't end up with any of the weird side effects of using macros.

Use Whitespace

You also say:

Here's the program (136 code, 17 blank and 7 comment lines, all < 80 characters)

Is there a reason why those numbers are important to you? I find the code to be rather cramped and hard to read. For example, I would never put the body of a for loop on the same line as the conditions as you do in main(). Same with an if statement. (Further, I would always put brackets around the body of an if, for, or while, even if it's only a single line.)

Of all your functions, only the last one, solve() has any blank lines in it. The blank lines really make it easier to read. You should add them between logical parts of your other functions.

Use The Right Type

I don't see much point in making a 1-dimensional array to represent a 2-dimensional array. First, it means you have to use the funky macro to get a value into or out of it. Second, it doesn't really save you anything. A 2D array of ints is going to be the same size.

Furthermore, rather than making it an array of ints then assigning enums to each member of the array, why not just make it an array of enums? That makes the code easier to understand and makes your intent more clear. Doing that requires making a typedef of the enum rather than leaving it anonymous. Something like this:

typedef enum {
    COLOR_WALL,
    COLOR_HOLE,
    COLOR_PATH,
    COLOR_ENDS,
    COLOR_COUNT
} Color;

Don't Repeat Yourself

When writing out the files in recordFrame(), you could improve things a little bit. You could pull the lookup of the next pixel out of the innermost loop, since neither x nor y change inside of it. So it would be like this:

for (int x = 0; x < MAZE_W; ++x) {
    int nextColor = COLORS [ maze [ MAZE_I(x, y) ] ];
    for (int j = 0; j < IMG_SCALE; ++j) {
        fputs(nextColor, f);
    }
}

There are other ways to speed this up, too. You could probably make an array that represents a single row of pixels, fill it, then write the entire thing out at once. Then simply write it out IMG_SCALE times.

Avoid Global and Static Variables

You have what are essentially 3 global variables: maze, n in recordFrame(), and finish in choosRandomPath(). Keeping track of what's changing maze is essentially impossible because it's updated in every function. Obviously n and finish are only updated in the functions they're in, but they still maintain state in a way that is error prone. If you later decide you want to generate 2 mazes at once, they will be difficult to work with. I recommend making a structure to hold these things and passing it into any function that needs access to them:

struct Maze {
    Color cells[MAZE_H][MAZE_W];
    int frameNumber;
    bool finish;
};
\$\endgroup\$
  • \$\begingroup\$ Not using global variables is common sense and a good rule. Static functions are the only way of keeping functions private to a module. C has a different standard than C++. In strict C not using a C++ compiler const is not allowed. \$\endgroup\$ – pacmaninbw Oct 1 '17 at 13:44
  • \$\begingroup\$ I wasn't referring to static functions, just static variables. You are correct. const is part of the C89 spec according to Dennis Ritchie's "The development of the C language". (Unfortunately the link from wikipedia appears dead.) I don't know of any modern C compiler that doesn't accept const by default. 1989 was 28 years ago, so it seems reasonable to assume we're discussing a modern variant of C unless otherwise specified. \$\endgroup\$ – user1118321 Oct 1 '17 at 16:56
  • \$\begingroup\$ You can't replace MAZE_W and MAZE_H #defines with const int, because they're not true constants and are used in global array declaration, which size needs to be a proper constant. I would have to malloc it. Your struct Maze wouldn't compile then, too, it would have to have Color **cells; instead of Color cells[MAZE_H][MAZE_W]. Otherwise, very nice review. \$\endgroup\$ – MarkWeston Oct 2 '17 at 9:11
  • \$\begingroup\$ @MarkWeston I get no complaints from my compiler (llvm 9.0) when set to C89, C99, or C11 whether using the gnu dialect or not for that. Perhaps there's a setting that's on by default in Xcode that isn't in other compilers? \$\endgroup\$ – user1118321 Oct 3 '17 at 2:30
  • \$\begingroup\$ It should have not compiled when set to C89, because of bool and VLAs. Are you using the -pedantic-errors compiler flag? const int SIZE = 42; int main(void) { int array[SIZE][SIZE]; } constructs a VLA at runtime, which is only valid in C99 and made optional in C11, while const int SIZE = 42; struct Type { int array[SIZE]; }; int main(void) {} doesn't compile in all dialects of the language, because you can't have a VLA in a struct. So you would have to definestruct Maze like this: struct Maze { Color **colors; int framenumber; bool finish; } and malloc it at runtime \$\endgroup\$ – MarkWeston Oct 3 '17 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.