Skip to main content
Corrected spelling
Source Link
Mast
  • 13.9k
  • 12
  • 57
  • 128
  • true and false: these are actually standard types since C99; #include <stdbool.h> instead.
  • NEWLINE and SPACE: you used the ASCII codes here, but that is actually less portable than just writing the character literals '\n' and ' ' wherever you need to have a space or newline. It's also not consistent, since you did write '_' and '|' directly instead of defining constants for those.
  • TOP_ROW, BOT_ROW etc.: it is a common enough pattern that 0 is the top/left-most index, and rowMAX - 1 and colMAX - 1 spelled out literally are the bottom and right-most indices of a 2D array. The meaning should be clear from those expresisonsexpressions, since arrays are 0-indexed in C.

The only constants I would maybe keep can be converedconverted to static const variables:

In your code, maze[][] is an array which is allocated on the stack of main(). However, the stack has a limited size, depending on the operating system and other constraints. Running out of stack space will cause your program to crash. So it is fine for small arrays, but since you don't know in advance how large a maze a user might want to generate, it's best to allocate it dynamically instead using malloc(). This will allocate it from the heap, which should allow it to be much bigger. Of course if you ask for something that really doesn't fit into your computer's memory, then malloc() will fail and return NULL, which you should gracefullgracefully handle.

Another issue is with the statically allocated cellstack[]. For small mazes, it is too large, wasting memory. For very large mazes, it might be too small, causing a buffer overflow which at best causesscauses your program to crash, but at worst causes silent data corruption. Again, allocate it dynamically. Also note that you can grow memory allocated using malloc() by using realloc().

  • true and false: these are actually standard types since C99; #include <stdbool.h> instead.
  • NEWLINE and SPACE: you used the ASCII codes here, but that is actually less portable than just writing the character literals '\n' and ' ' wherever you need to have a space or newline. It's also not consistent, since you did write '_' and '|' directly instead of defining constants for those.
  • TOP_ROW, BOT_ROW etc.: it is a common enough pattern that 0 is the top/left-most index, and rowMAX - 1 and colMAX - 1 spelled out literally are the bottom and right-most indices of a 2D array. The meaning should be clear from those expresisons, since arrays are 0-indexed in C.

The only constants I would maybe keep can be convered to static const variables:

In your code, maze[][] is an array which is allocated on the stack of main(). However, the stack has a limited size, depending on the operating system and other constraints. Running out of stack space will cause your program to crash. So it is fine for small arrays, but since you don't know in advance how large a maze a user might want to generate, it's best to allocate it dynamically instead using malloc(). This will allocate it from the heap, which should allow it to be much bigger. Of course if you ask for something that really doesn't fit into your computer's memory, then malloc() will fail and return NULL, which you should gracefull handle.

Another issue is with the statically allocated cellstack[]. For small mazes, it is too large, wasting memory. For very large mazes, it might be too small, causing a buffer overflow which at best causess your program to crash, but at worst causes silent data corruption. Again, allocate it dynamically. Also note that you can grow memory allocated using malloc() by using realloc().

  • true and false: these are actually standard types since C99; #include <stdbool.h> instead.
  • NEWLINE and SPACE: you used the ASCII codes here, but that is actually less portable than just writing the character literals '\n' and ' ' wherever you need to have a space or newline. It's also not consistent, since you did write '_' and '|' directly instead of defining constants for those.
  • TOP_ROW, BOT_ROW etc.: it is a common enough pattern that 0 is the top/left-most index, and rowMAX - 1 and colMAX - 1 spelled out literally are the bottom and right-most indices of a 2D array. The meaning should be clear from those expressions, since arrays are 0-indexed in C.

The only constants I would maybe keep can be converted to static const variables:

In your code, maze[][] is an array which is allocated on the stack of main(). However, the stack has a limited size, depending on the operating system and other constraints. Running out of stack space will cause your program to crash. So it is fine for small arrays, but since you don't know in advance how large a maze a user might want to generate, it's best to allocate it dynamically instead using malloc(). This will allocate it from the heap, which should allow it to be much bigger. Of course if you ask for something that really doesn't fit into your computer's memory, then malloc() will fail and return NULL, which you should gracefully handle.

Another issue is with the statically allocated cellstack[]. For small mazes, it is too large, wasting memory. For very large mazes, it might be too small, causing a buffer overflow which at best causes your program to crash, but at worst causes silent data corruption. Again, allocate it dynamically. Also note that you can grow memory allocated using malloc() by using realloc().

Source Link
G. Sliepen
  • 69.5k
  • 3
  • 75
  • 180

There is quite a bit that can be improved here. I see you are trying to do things in a correct way, but you miss the mark here and there. I'll explain below.

Avoid macros

Giving name to constants is a good thing to do. However, macros created with #define have some issues: if they become a bit more complex than a single number, you have to put thing in parentheses (as you did), but they also lack a type. Sometimes they look like constants but they aren't (like BOT_ROW: it depend on the current value of rowMAX). There are a few cases where you really need macros in C, but in many cases they can be avoided.

In some cases, an enum is preferred, like for LEFT, RIGHT and so on. This combines well with switch statements, where the compiler can warn if you forgot to cover one of the enum values. So:

typedef enum {
    LEFT,
    RIGHT,
    TOP,
    BOTTOM,
} direction;

There are also a few cases where you defined things that should not be named at all:

  • true and false: these are actually standard types since C99; #include <stdbool.h> instead.
  • NEWLINE and SPACE: you used the ASCII codes here, but that is actually less portable than just writing the character literals '\n' and ' ' wherever you need to have a space or newline. It's also not consistent, since you did write '_' and '|' directly instead of defining constants for those.
  • TOP_ROW, BOT_ROW etc.: it is a common enough pattern that 0 is the top/left-most index, and rowMAX - 1 and colMAX - 1 spelled out literally are the bottom and right-most indices of a 2D array. The meaning should be clear from those expresisons, since arrays are 0-indexed in C.

The only constants I would maybe keep can be convered to static const variables:

static const int BOTTOM_WALL = 0;
static const int RIGHT_WALL = 1;

Although even that is not necessary, as I'll explain below.

A cell is too big

A cell should only need to track three bits of information: whether it has a top and/or a right wall, and whether it has been visited. It should not have to track which neighbors it has, instead you can tell that from its position in the array maze[][].

For one bit of information, you can use the type bool, but even that actually takes a whole byte of memory. But C also allows you to define bitfields, allowing you to pack three bits in one byte:

typedef struct {
    bool bottom_wall: 1;
    bool right_wall: 1;
    bool visited: 1;
} cell;

Your cell actually uses 48 bytes on a 64-bit computer. You might not think it is important, but it does reduce memory usage and improves performance a lot for large mazes.

Create a struct to represent a maze

You have several functions that get a cellptr as an argument, but to get the size of the maze they actually use the global variables rowMAX and colMAX. That's not great. It's better to create a struct that contains all the information regarding a maze, for example:

typedef struct {
    size_t width;
    size_t height;
    cell *cells;
} maze;

Here cells points to a 1-dimensional array as far as C is concerned, it's support for multi-dimensional arrays is unfortunately a bit limited. To make working with the cells in the maze more easy, write some helper functions:

cell *cell_at(maze *maze, size_t x, size_t y) {
    return maze->cells[x + y * maze->width];
}

bool is_visited(maze *maze, size_t x, size_t y) {
    return (*cell_at(maze, x, y)).visited;
}

void set_visited(maze *maze, size_t x, size_t y) {
    (*cell_at(maze, x, y)).visited = true;
}

Don't hide pointers behind typedefs

It has been found that hiding pointers behind typedefs does more harm than good. So I would avoid creating a cellptr, instead jut write cell *. It should be clear to any programmer that the latter is a pointer, and it's even less typing.

Allocate arrays using malloc()

In your code, maze[][] is an array which is allocated on the stack of main(). However, the stack has a limited size, depending on the operating system and other constraints. Running out of stack space will cause your program to crash. So it is fine for small arrays, but since you don't know in advance how large a maze a user might want to generate, it's best to allocate it dynamically instead using malloc(). This will allocate it from the heap, which should allow it to be much bigger. Of course if you ask for something that really doesn't fit into your computer's memory, then malloc() will fail and return NULL, which you should gracefull handle.

Another issue is with the statically allocated cellstack[]. For small mazes, it is too large, wasting memory. For very large mazes, it might be too small, causing a buffer overflow which at best causess your program to crash, but at worst causes silent data corruption. Again, allocate it dynamically. Also note that you can grow memory allocated using malloc() by using realloc().