Uni IT mini-project: "Maze & Graph random generation"

Question

Task details:

1. Generate a random 2x2 - 10x10 (size = number of maze's cells, defined by user) maze using any known algorithm (the cells '.' are surrounded by walls '#')
2. The maze consists of cells (2x2 - 10x10).
3. The maze must have an entrance at the top and an exit on the bottom of it.
4. The maze can't contain any 'closed cells' (meaning there need to be a path between each cell in the maze, open path = no wall ' ').
5. Each cell has to hold a random value assigned to it (0.1 - 10.0).
6. Represent the maze by any known representation of a directed graph (adjacency list, neighborhood list, etc.) so that: the vertex = cells & the edges = connections between cells

I had two attempts to solve it.

1. Very very stupid and illogical one, but it worked somehow.

2. More complex and mature way, but I can't make it work. Although, it seems to be a better idea. Using Depth-First Search Algorithm (at least trying to).

The code is commented in Polish but variables and functions are pretty straightforward with their names in English.

Currently "segmentation fault" within the openMaze() function. I can't figure out how to use Depth-First Search algorithm in my case.

#include <stdbool.h> // TYP BOOL
#include <stdio.h> // INPUT & OUTPUT
#include <stdlib.h> // MALLOC
#include <time.h> // RANDOM

// KOLORY WYJSCIA I WEJSCIA Z LABIRYNTU
#define COLOR_RED "\x1b[31m"
#define COLOR_GREEN "\x1b[32m"
#define COLOR_RESET "\x1b[0m"

// MAKSYMALNA WIELKOSC TABLICY LABIRYNTU
#define MAX_SIZE 100

typedef struct cell cell; // PRE-DEKLARACJA STRUKTURY

// STRUKTURA KOMORKI LABIRYNTU
struct cell {
    int nr;
    double value;
    char content;
    int x;
    int y;
    bool isVisited;
    bool isStart;
    bool isEnd;
    cell *neighbours[4];
};

// NUMEROWANIE KOMOREK LABIRYNTU OD 1
void numberCells(cell *cells, int cellCount) {
    for (int i = 0; i < cellCount; i++) {
        cells[i].nr = i + 1;
    }
}

// USTAWIENIE WSZYSTKICH KOMOREK NA "NIEODWIEDZONE"
void unvisitAllCells(cell *cells, int cellCount) {
    for (int i = 0; i < cellCount; i++) {
        cells[i].isVisited = 0;
    }
}

// LOSOWE PRZYPISANIE WAG KOMORKOM LABIRYNTU
void assignValuesToCells(cell *cells, int cellCount) {
    srand(time(NULL));

    for (int i = 0; i < cellCount; i++) {
        cells[i].value = (rand() / RAND_MAX) * 10.0;
    }
}

// WYPEŁNIENIE KOMOREK ZNAKIEM
void fillCells(cell *cells, int cellCount) {
    for (int i = 0; i < cellCount; i++) {
        cells[i].content = '.';
    }
}

// LOSOWE WYBRANIE WEJSCIA I WYJSCIA LABIRYNTU
void chooseGates(cell *cells, int cellWidth, int cellCount) {
    srand(time(NULL));

    for (int i = 0; i < cellCount; i++) {
        cells[i].isStart = 0;
        cells[i].isEnd = 0;
    }

    int s = rand() % cellWidth;
    cells[s].isStart = 1;
    cells[s].content = '@';

    int e = rand() % cellWidth;
    cells[cellCount - 1 - e].isEnd = 1;
    cells[cellCount - 1 - e].content = '@';
}

// GENERACJA SUROWEGO LABIRYNTU (SCIANY I KOMORKI)
void mazeGen(cell *cells, int mazeSize, char maze[MAX_SIZE][MAX_SIZE]) {
    int cellsIteration = 0;
    for (int i = 0; i < mazeSize; i++) {
        for (int j = 0; j < mazeSize; j++) {
            if (i % 2 == 0 || j % 2 == 0) {
                maze[i][j] = '#';
            } else {
                maze[i][j] = cells[cellsIteration].content;
                cells[cellsIteration].x = i;
                cells[cellsIteration].y = j;
                cellsIteration++;
            }
        }
    }
}

// WYSWIETLENIE GRAFICZNE LABIRYNTU
void mazePrint(char maze[MAX_SIZE][MAX_SIZE], int mazeSize) {
    for (int i = 0; i < mazeSize; i++) {
        for (int j = 0; j < mazeSize; j++) {
            if (i == 1 && maze[i - 1][j] == ' ') {
                printf(COLOR_GREEN " %c " COLOR_RESET, maze[i][j]);
            } else if (i == mazeSize - 2 && maze[i + 1][j] == ' ') {
                printf(COLOR_RED " %c " COLOR_RESET, maze[i][j]);
            } else {
                printf(" %c ", maze[i][j]);
            }
        }
        printf("\n\n");
    }
    printf("\n");
}

// OTWORZENIE WEJSCIA I WYJSCIA LABIRYNTU
void openGates(cell *cells, char maze[MAX_SIZE][MAX_SIZE], int cellCount) {
    for (int i = 0; i < cellCount; i++) {
        if (cells[i].isStart == 1) {
            maze[cells[i].x - 1][cells[i].y] = ' ';
        }
        if (cells[i].isEnd == 1) {
            maze[cells[i].x + 1][cells[i].y] = ' ';
        }
    }
}
// SPRAWDZENIE CZY WSZYSTKIE KOMORKI LABIRYNTU SA "ODWIEDZONE"
bool allCellsVisited(cell *cells, int cellCount) {
    for (int i = 0; i < cellCount; i++) {
        if (cells[i].isVisited == 0) {
            return 0;
        }
    }
    return 1;
}
// SPRAWDZENIE CZY KOMORKA JEST WŁAŚCIWA
bool isCellValid(cell cell, int cellCount) {
    if (cell.nr > 0 && cell.nr <= cellCount) {
        return 1;
    }
    return 0;
}

// PRZYPISANIE SĄSIADOW KOMORKOM
void setNeighbours(cell *cells, int cellCount, int cellWidth) {
    for (int i = 0; i < cellCount; i++) {
        for (int j = 0; j < 4; j++) {
            cells[i].neighbours[j] = NULL;
        }
    }

    for (int i = 0; i < cellCount; i++) {
        int j = 0;
        // printf("%d: ", cells[i].nr);
        int up = i - cellWidth;
        if (isCellValid(cells[up], cellCount)) {
            cells[i].neighbours[j] = &cells[up];
            // printf("u - %d, ",cells[i].neighbours[j]->nr);
            j++;
        }

        int right = i + 1;
        if (isCellValid(cells[right], cellCount)) {
            cells[i].neighbours[j] = &cells[right];
            // printf("r - %d, ",cells[i].neighbours[j]->nr);
            j++;
        }

        int down = i + cellWidth;
        if (isCellValid(cells[down], cellCount)) {
            cells[i].neighbours[j] = &cells[down];
            // printf("d - %d, ",cells[i].neighbours[j]->nr);
            j++;
        }

        int left = i - 1;
        if (isCellValid(cells[left], cellCount)) {
            cells[i].neighbours[j] = &cells[left];
            // printf("l - %d, ",cells[i].neighbours[j]->nr);
            j++;
        }

        // printf("\n");
    }
}

// SPRAWDZENIE CZY KOMORKA MA "NIEODWIEDZONYCH" SASIADOW
bool hasUnvisitedNeighbour(cell cell, int cellCount) {
    for (int i = 0; i < 4; i++) {
        if (cell.neighbours[i] != NULL) {
            if (cell.neighbours[i]->isVisited == 0) {
                //printf("tak");
                return 1;
            }
        }
    }
    return 0;
}

// ZNISZCZENIE SCIANY MIEDZY DWOMA KOMORKAMI
void breakWall(cell current, cell adjacent, char maze[MAX_SIZE][MAX_SIZE]){
    if(adjacent.x < current.x){
        maze[current.x-1][current.y] = ' ';
    }
    if(adjacent.x > current.x){
        maze[current.x+1][current.y] = ' ';
    }
    if(adjacent.y < current.y){
        maze[current.x][current.y-1] = ' ';
    }
    if(adjacent.y > current.y){
        maze[current.x][current.y+1] = ' ';
    }
}

// LOSOWE TWORZENIE PRZEJSC LABIRYNTU
void openMaze(cell *cells, char maze[MAX_SIZE][MAX_SIZE], int mazeSize, int cellCount, int cellWidth) {
    // PRZYPISANIE KOMORKOM SASIADOW
    setNeighbours(cells, cellCount, cellWidth);

    // INICJALIZACJA STOSU
    cell *stack = malloc(MAX_SIZE * sizeof(cell)); 
    int top = -1;

    // DODANIE NA STOS KOMORKI STARTOWEJ
    for(int i=0; i<cellCount; i++){
        if(cells[i].isStart == 1){
            stack[++top] = cells[i];
            break;
        }
    }

    cell previous;

    // DFS
    while(top>=0){
        cell current = stack[top];
        stack[top].isVisited = 1;
        
        for(int i=0; i<4; i++){
            if(current.neighbours[i] != NULL && current.neighbours[i]->isVisited == 0){
                stack[++top] = *(current.neighbours[i]);
            }
        }
        
        breakWall(current, previous, maze);
        
        if(!hasUnvisitedNeighbour(current, cellCount)){
            top--;
        }
        previous = current;
    }
    free(stack);
}

int main() {
    int cellWidth = 0; // ROZMIAR LABIRYNTU (LICZBA KOMOREK W WIERSZU)
    printf("Podaj wymiar labiryntu: ");
    scanf("%d", &cellWidth);
    printf("\n");

    while (cellWidth < 2 || cellWidth > 10) {
        printf("Wymiar od 2 do 10! Jeszcze raz: ");
        scanf("%d", &cellWidth);
    }
    printf("\n");

    int cellCount = cellWidth * cellWidth; // LICZBA KOMOREK LABIRYNTU
    int mazeSize = cellWidth * 2 + 1;      // ROZMIAR TABLICY ZNAKOW LABIRYNTU

    cell *cells = malloc(cellCount * sizeof(cell)); // WEKTOR KOMOREK

    numberCells(cells, cellCount); // PONUMERUJ KOMORKI
    unvisitAllCells(cells, cellCount); // USTAW KOMORKI NA "NIEODWIEDZONE"
    assignValuesToCells(cells, cellCount); // PRZYPISZ LOSOWE WAGI KOMORKOM
    fillCells(cells, cellCount);

    chooseGates(cells, cellWidth, cellCount); // LOSOWO WYBIERZ WEJSCIE I WYJSCIE Z LABIRYNTU

    char maze[MAX_SIZE][MAX_SIZE]; // TABLICA ZNAKOW LABIRYNTU
    mazeGen(cells, mazeSize, maze); // GENEROWANIE "SUROWEGO" LABIRYNTU

    openGates(cells, maze, cellCount); // OTWORZ KOMORKI WEJSCIA I WYJSCIA

    openMaze(cells, maze, mazeSize, cellCount, cellWidth); // LOSOWO ODBLOKUJ SCIEZKI W LABIRYNCIE

    mazePrint(maze, mazeSize); // WYSWIETL LABIRYNT

    free(cells);

    return 0;
}

This one is in Polish. I tried to comment it in English, but this code is really messed up. Very primitive approach.

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

#define MAX_SIZE 100

// MAZE GENERATION
void generujLabirynt(char labirynt[][MAX_SIZE], int size) {
  srand(time(NULL));

  // ENTRANCE & EXIT
  int wyjscie = rand() % (size - 2) + 1;
  int wejscie = rand() % (size - 2) + 1;

  while (wyjscie % 2 == 0) {
    wyjscie = rand() % (size - 2) + 1;
  }
  while (wejscie % 2 == 0) {
    wejscie = rand() % (size - 2) + 1;
  }

  // WALLS AND CELLS
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
      // krawedzie labiryntu
      if (i == 0 || i == size - 1 || j == 0 || j == size - 1) {
        labirynt[i][j] = '#';
      } else {
        labirynt[i][j] = '0'; // reszta
      }

      labirynt[0][wejscie] = ' ';
      labirynt[size - 1][wyjscie] = ' ';

      if (labirynt[i][j] == '0') {
        if (i % 2 == 1 && j % 2 == 1) {
          labirynt[i][j] = '.';
        } else if (i % 2 == 0 && j % 2 == 0) {
          labirynt[i][j] = '#';
        } else {
          // NOT ALL WALLS ARE SOLID
          if (rand() % 3 > 1) {
            labirynt[i][j] = '#';
          } else {
            labirynt[i][j] = ' ';
          }
        }
      }
    }
  }
}

// UNLOCK CELLS THAT ARE CLOSED
void odblokujKomorki(char labirynt[][MAX_SIZE], int size) {
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {

      // TOP EDGE
      if (labirynt[i][j] == '.' && i == 1 && j > 1 && j < size - 2) {
        if (labirynt[i][j + 1] == '#' && labirynt[i][j - 1] == '#' &&
            labirynt[i + 1][j] == '#') {
          labirynt[i + 1][j] = ' ';
        }
      }
      // LEFT EDGE
      if (labirynt[i][j] == '.' && j == 1 && i > 1 && i < size - 2) {
        if (labirynt[i + 1][j] == '#' && labirynt[i - 1][j] == '#' &&
            labirynt[i][j + 1] == '#') {
          labirynt[i][j + 1] = ' ';
        }
      }
      // BOTTOM
      if (labirynt[i][j] == '.' && i == size - 2 && j > 1 && j < size - 2) {
        if (labirynt[i][j + 1] == '#' && labirynt[i][j - 1] == '#' &&
            labirynt[i - 1][j] == '#') {
          labirynt[i - 1][j] = ' ';
        }
      }
      // RIGHT
      if (labirynt[i][j] == '.' && j == size - 2 && i > 1 && i < size - 2) {
        if (labirynt[i + 1][j] == '#' && labirynt[i - 1][j] == '#' &&
            labirynt[i][j - 1] == '#') {
          labirynt[i][j - 1] = ' ';
        }
      }
      // TOP-LEFT CORNER CELL
      if (labirynt[i][j] == '.' && i == 1 && j == 1) {
        if (labirynt[i + 1][j] == '#' && labirynt[i][j + 1] == '#') {
          labirynt[i][j + 1] = ' ';
        }
      }
      // TOP-RIGHT CORNER CELL
      if (labirynt[i][j] == '.' && i == 1 && j == size - 2) {
        if (labirynt[i + 1][j] == '#' && labirynt[i][j - 1] == '#') {
          labirynt[i][j - 1] = ' ';
        }
      }
      // BOTTOM-LEFT CORNER CELL
      if (labirynt[i][j] == '.' && i == size - 2 && j == 1) {
        if (labirynt[i - 1][j] == '#' && labirynt[i][j + 1] == '#') {
          labirynt[i][j + 1] = ' ';
        }
      }
      // BOTTOM-RIGHT CORNER CELL
      if (labirynt[i][j] == '.' && i == size - 2 && j == size - 2) {
        if (labirynt[i - 1][j] == '#' && labirynt[i][j - 1] == '#') {
          labirynt[i - 1][j] = ' ';
        }
      }

      // MIDDLE CELLS
      if (labirynt[i][j] == '.' && i > 1 && i < size - 2 && j > 1 &&
          j < size - 2) {
        if (labirynt[i - 1][j] == '#' && labirynt[i + 1][j] == '#' &&
            labirynt[i][j - 1] == '#' && labirynt[i][j + 1] == '#') {
          labirynt[i - 1][j] = ' ';
          labirynt[i + 1][j] = ' ';
        }
      }
    }
  }
}
// UNLOCK WHOLE BLOCKED ROWS
void odblokujWiersze(char labirynt[][MAX_SIZE], int size) {
  int dlugosc = size - 2;
  int licz = 0;
  for (int i = 1; i < size - 1; i++) {
    for (int j = 1; j < size - 1; j++) {
      if (labirynt[i][1] == '#')
        licz++;
    }
    if (licz == dlugosc) {
      int doUsuniecia = rand() % dlugosc + 1;
      while (doUsuniecia % 2 != 1) {
        doUsuniecia = rand() % dlugosc + 1;
      }
      labirynt[i][doUsuniecia] = ' ';
    }
    licz = 0;
  }
}

// UNLOCK WHOLE BLOCKED COLUMNS
void odblokujKolumny(char labirynt[][MAX_SIZE], int size) {
  int dlugosc = size - 2;
  int licz = 0;
  for (int j = 1; j < size - 1; j++) {
    for (int i = 1; i < size - 1; i++) {
      if (labirynt[i][j] == '#')
        licz++;
    }
    if (licz == dlugosc) {
      int doUsuniecia = rand() % dlugosc + 1;
      while (doUsuniecia % 2 != 1) {
        doUsuniecia = rand() % dlugosc + 1;
      }
      labirynt[doUsuniecia][j] = ' ';
    }
    licz = 0;
  }
}
// NEIGHBORHOOD LIST GEN (ACTUALLY ONLY PRINTING IT)
void generujListe(char labirynt[][MAX_SIZE], int sizeCell, int size) {

  int nr = 0;
  for (int i = 1; i < size - 1; i += 2) {
    for (int j = 1; j < size - 1; j += 2) {
      printf("%d: ", nr);
      if (labirynt[i - 1][j] == ' ' && i > 1) {
        printf("%d ", nr - sizeCell);
      }
      if (labirynt[i + 1][j] == ' ' && i < size - 2) {
        printf("%d ", nr + sizeCell);
      }
      if (labirynt[i][j - 1] == ' ' && j > 1) {
        printf("%d ", nr - 1);
      }
      if (labirynt[i][j + 1] == ' ' && j < size - 2) {
        printf("%d ", nr + 1);
      }
      nr++;
      printf("\n");
    }
  }
}

int main() {

  int sizeCell = 0;
  printf("Podaj wymiar labiryntu: ");
  scanf("%d", &sizeCell);
  printf("\n");

  while (sizeCell < 2 || sizeCell > 10) {
    printf("Wymiar od 2 do 10! Jeszcze raz: ");
    scanf("%d", &sizeCell);
  }
  printf("\n");

  int size = sizeCell * 2 + 1;
  char labirynt[size][MAX_SIZE];

  generujLabirynt(labirynt, size);

  odblokujWiersze(labirynt, size);
  odblokujKolumny(labirynt, size);

  int naprawa = 0;
  while (naprawa != 2) {
    odblokujKomorki(labirynt, size);
    naprawa++;
  }

  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
      printf(" %c ", labirynt[i][j]);
    }
    printf("\n\n");
  }

  generujListe(labirynt, sizeCell, size);

  return 0;
}