How can I improve this code ? It takes an infinite time if i want to create un big maze(arguments 5000 5000 100 50 100)main.c#include <stdio.h>#include <stdlib.h>#include <time.h>#include maze.h/*test: valgrind --show-reachable=yes --leak-check=full -v ./dungeon 50 50 100 50 100*/int main(int argc, char *argv[]){  int maxx;  int maxy;  int randomness;  int sparseness;  int deadendremoval;  if (argc != 6) {    fprintf(stderr, Five arguments needed => X, Y, randomness, sparseness, dead-end-removal\n);    return EXIT_FAILURE;  }  maxx = atoi(argv[1]);  maxy = atoi(argv[2]);  randomness = atoi(argv[3]);  sparseness = atoi(argv[4]);  deadendremoval = atoi(argv[5]);  if (randomness < 0 || randomness > 100) {    fprintf(stderr, Randomness must be between 0 and 100.\n);    return EXIT_FAILURE;  }  if (sparseness < 0 || sparseness > 100) {    fprintf(stderr, Sparseness must be between 0 and 100.\n);    return EXIT_FAILURE;  }  if (deadendremoval < 0 || deadendremoval > 100) {    fprintf(stderr, Dead-end-removal must be between 0 and 100.\n);    return EXIT_FAILURE;  }  createmaze(maxx, maxy, randomness, sparseness, deadendremoval);  return EXIT_SUCCESS;}maze.cThe most important file, algorithm is here:#include <stdio.h>#include <stdlib.h>#include <time.h>#include maze.h#include deadend.h#define visitCell(x, y) map[x][y].visited = 1;/* take a random cell wich is not visited */void visitRand(int *px, int *py, int maxx, int maxy, struct cell **map){  int x, y;  do {    x = rand()%(maxx-1);    y = rand()%(maxy-1);  } while (map[x][y].visited != 0);  visitCell(x, y);  *px = x;  *py = y;}/* take a random cell wich is already visited */void visitRandVisited(int *px, int *py, int maxx, int maxy, struct cell **map){  int x, y;  do {    x = rand()%(maxx-1);    y = rand()%(maxy-1);  } while (map[x][y].visited != 1);  *px = x;  *py = y;}/* test if all the cells are visited */int testEndMaze(int maxx, int maxy, struct cell **map) {  int x, y;  for (y = 0; y < maxy; y++) {    for (x = 0; x < maxx; x++) {      if (map[x][y].visited == 0)         return 1;    }  }  return 0;}/* select a direction, randomness determine the chance of the same direction that the last used (prevdir) */int newDir(int x, int y, int maxx, int maxy, int prevdir, int randomness, struct cell **map){  int N = 0;  int S = 0;  int E = 0;  int W = 0;  int dir = -1;  int tdir;  if ((x == 0) || (map[x-1][y].visited == 1))    W = 1;  if ((y == 0) || (map[x][y-1].visited == 1))    N = 1;  if ((x == (maxx - 1)) || (map[x+1][y].visited == 1))    E = 1;  if ((y == (maxy - 1)) || (map[x][y+1].visited == 1))    S = 1;  if (N == 1 &&  S == 1 && E == 1 && W == 1)     return -1;  tdir = rand()%100;  if (tdir < randomness) {    if ((prevdir == north && N != 1) ||         (prevdir == south && S != 1) ||         (prevdir == east && E != 1) ||         (prevdir == west && W != 1)) {      return prevdir;    }  }  do {    tdir = rand()%4;    if (tdir == north && N == 0)      dir = north;    else if (tdir == south && S == 0)      dir = south;    else if (tdir == east && E == 0)      dir = east;    else if (tdir == west && W == 0)      dir = west;  } while (dir == -1);  return dir;}/* select a direction for diging, with randomness */int newDirdig(int x, int y, int maxx, int maxy, int prevdir, int randomness, struct cell **map){  int N = 0;  int S = 0;  int E = 0;  int W = 0;  int dir = -1;  int tdir;  if ((x == 0) || (map[x][y].wallW == 0)) W = 1;  if ((y == 0) || (map[x][y].wallN == 0)) N = 1;  if ((x == (maxx - 1)) || (map[x][y].wallE == 0)) E = 1;  if ((y == (maxy - 1)) || (map[x][y].wallS == 0)) S = 1;  /* Letters are at 1 if we can't take the  direction associated */   /* do we chose the last dir used ? */   tdir = rand()%100;   if (tdir < randomness) {     if ((prevdir == north && N != 1) ||         (prevdir == south && S != 1) ||         (prevdir == east && E != 1) ||         (prevdir == west && W != 1)) {      return prevdir;    }  }  do {    tdir = rand()%4;    if (tdir == north && N == 0){      dir = north;}    else if (tdir == south && S == 0)      dir = south;    else if (tdir == east && E == 0)      dir = east;    else if (tdir == west && W == 0)      dir = west;  } while (dir == -1);  return dir;}/* count the number of walls in a cell */int countwall(int x, int y, struct cell **map, int dig){  int count = 0;  if (map[x][y].wallN)    count ++;  if (map[x][y].wallS)    count ++;  if (map[x][y].wallE)    count ++;  if (map[x][y].wallW)    count ++;  if(dig)    return (count == 3);  /* if we are diging, we count 3 and 4 walls cells, but only 3 walls cells if we list the dead end */  return (count >= 3);}/* calcul the percentage of the map that must not be a part of the maze */int sparcount(int sparseness, int maxx, int maxy){  return ((sparseness * maxx * maxy) / 100);}/* calcul the number of unvisited cells */int freecasecount(int maxx, int maxy, struct cell **map){  int x, y;  int count = 0;  for (x = 0; x < maxx; x++) {     for (y = 0; y < maxy; y++) {      if (map[x][y].visited == 0)        count++;    }  }  return count;}/* remove the dead end (3 walls cell) */void deldeadend(int maxx, int maxy, struct deadend *liste, struct cell **map){  while (liste) {    map[liste->x][liste->y].visited = 0;    if (map[liste->x][liste->y].wallN == 0) {      map[liste->x][liste->y].wallN = 1;      if (liste->y != 0) {        map[liste->x][liste->y-1].wallS = 1;      }    }    else if (map[liste->x][liste->y].wallE == 0) {      map[liste->x][liste->y].wallE = 1;        if (liste->x != maxx-1) {          map[liste->x+1][liste->y].wallW = 1;      }    }    else if (map[liste->x][liste->y].wallS == 0) {      map[liste->x][liste->y].wallS = 1;      if (liste->y != maxy-1) {        map[liste->x][liste->y+1].wallN = 1;      }    }    else if (map[liste->x][liste->y].wallW == 0) {      map[liste->x][liste->y].wallW = 1;      if (liste->x != 0) {        map[liste->x-1][liste->y].wallE = 1;      }    }    liste = liste->next;  }}/* list all the deadend */void deadendshow(int maxx, int maxy, struct cell **map){  struct deadend *liste = NULL;  int x, y;  for (x = 0; x < maxx; x++) {    for (y = 0; y < maxy; y++) {      if (countwall(x, y, map, 0))        addend(&liste, x, y);    }  }  deldeadend(maxx, maxy, liste, map);  dellist(&liste);}/* choose if a corridor is a dead end or if we have to dig in the map */int dodig(int deadendremoval){  return ((rand()%100) < deadendremoval);}/* dig in the map */void digin(int maxx, int maxy, int randomness, int deadendremoval, struct cell **map){  struct deadend *liste = NULL;  struct deadend *run = NULL;  int x, y;  int prevdir;  int dir;  for (x = 0; x < maxx; x++) {    for (y = 0; y < maxy; y++) {      if (countwall(x, y, map, 1))        addend(&liste, x, y);    }  }  run = liste;  /* while there are items in the list, decide if we let the cells or if we dig for creating a loop */      while (run) {    if (dodig(deadendremoval)) {      prevdir = -1;      x = run->x;      y = run->y;      while (countwall(x, y, map, 1)) {        visitCell(x, y);        dir = newDirdig(x, y, maxx, maxy, prevdir, randomness, map);        switch (dir) {          case north:            prevdir = north;            map[x][y].wallN = 0;            y--;            map[x][y].wallS = 0;            break;          case south:            prevdir = south;            map[x][y].wallS = 0;            y++;            map[x][y].wallN = 0;            break;          case east:            prevdir = east;            map[x][y].wallE = 0;            x++;            map[x][y].wallW = 0;            break;          case west:            prevdir = west;            map[x][y].wallW = 0;            x--;            map[x][y].wallE = 0;            break;        }      }    }    run = run->next;  }  dellist(&liste);}/* initialize the map */void clearmaze(int maxx, int maxy, struct cell **map){  int x, y;  for (y = 0; y < maxy; y++) {    for (x = 0; x < maxx; x++) {      map[x][y].visited = 0;      map[x][y].wallN = 1;      map[x][y].wallS = 1;      map[x][y].wallE = 1;      map[x][y].wallW = 1;    }  }}/* write the maze in a file named donjon */void writedungeon(int maxx, int maxy, struct cell **map){  FILE *donjon = NULL;  int x, y;  donjon = fopen(donjon, w);    if (donjon == NULL) {      fprintf(stderr, Error while writing the map.\n);  }  fputc(' ', donjon);  for (x = 0; x < maxx; x++) {    fputs(_ , donjon);  }  fputc('\n', donjon);  for (y = 0; y < maxy; y++) {    fputc('|', donjon);    for (x = 0; x < maxx; x++) {      if (map[x][y].visited == 0){        fputc('X', donjon);        fputc('|', donjon);      } else {        if (map[x][y].wallS == 1)          fputc('_', donjon);        else          fputc(' ', donjon);        if (map[x][y].wallE == 1)          fputc('|', donjon);        else          fputc(' ', donjon);      }    }    fputc('\n', donjon);  }  fclose(donjon);}/* main algorithm */int createmaze(int maxx, int maxy, int randomness, int sparseness, int deadendremoval){  struct cell **map;  int dir = -1;  int x, y = 0;  int spar, i = 0;  int prevdir;  /* initialisation */  map = malloc(maxx * sizeof(struct cell*));  if(map == NULL) {    fprintf(stderr,Allocation impossible);    exit(EXIT_FAILURE);  }  for (x = 0; x < maxx; x++) {    map[x]=(struct cell *)malloc(maxy * sizeof(struct cell));  }  clearmaze(maxx, maxy, map);  srand(time(NULL));  /* initialisation finished */      /* choose a random unvisited cell */  visitRand(&x, &y, maxx-2, maxy-2, map);  /* for the first time, there is no last direction, choose a random one */  prevdir = rand()%4;  /* while there is an unvisited cell in the map, the maze is not finished */  while (testEndMaze(maxx, maxy, map)) {    /* choose a direction */    dir = newDir(x, y, maxx, maxy, prevdir, randomness, map);    switch (dir) {      case north:        prevdir = north;        map[x][y].wallN = 0;        y--;        map[x][y].wallS = 0;        break;      case south:        prevdir = south;        map[x][y].wallS = 0;        y++;        map[x][y].wallN = 0;        break;      case east:        prevdir = east;        map[x][y].wallE = 0;        x++;        map[x][y].wallW = 0;        break;      case west:        prevdir = west;        map[x][y].wallW = 0;        x--;        map[x][y].wallE = 0;        break;      case -1:        visitRandVisited(&x, &y, maxx, maxy, map);        break;    }    visitCell(x, y);  }  /* detect all the dead end in the map  the spar determine the number of map unvited, in removing dead end */  spar = sparcount(sparseness, maxx, maxy);  while(i < spar) {    deadendshow(maxx, maxy, map);    i = freecasecount(maxx, maxy, map);  }  /* select the dead end and dig for creating loop */  digin(maxx, maxy, randomness, deadendremoval, map);  writedungeon(maxx, maxy, map);  for (x = 0; x < maxx; x++) {    free(map[x]);  }  free(map);  return EXIT_SUCCESS;}maze.h#ifndef MAZE_H#define MAZE_Henum {  north, south, east, west};struct cell {  int visited;  int wallN;  int wallS;  int wallE;  int wallW;};int createmaze(int maxx, int maxy, int randomness, int sparseness, int deadendremoval);#endifdeadend.cThis file is a simple chained list tool.#include <stdio.h>#include <stdlib.h>#include deadend.hvoid addfirst(struct deadend **tete, int x, int y){  struct deadend *element = NULL;  element = malloc(sizeof(struct deadend));  element->x = x;  element->y = y;  element->next = *tete;  *tete = element;}void addend(struct deadend **tete, int x, int y){  struct deadend *element= *tete;  struct deadend *elemprec = NULL;   /* cas liste vide */   if(element == NULL) {    addfirst(tete, x, y);  /* cas general */  } else {    while (element != NULL) {      elemprec = element;      element = element->next;    }    addfirst(&element, x, y);    elemprec->next = element;  }}void delfirst(struct deadend **liste){  struct deadend *tmp = NULL;  if(*liste != NULL) {    tmp = (*liste)->next;    free(*liste);    *liste = tmp;  }}void dellist(struct deadend **liste){  struct deadend *tmp = *liste;  while (tmp != NULL) {    tmp = (*liste)->next;    delfirst(liste);  }}void runlist(struct deadend *liste){  while (liste) {    printf(liste : x: %d y: %d\n, liste->x, liste->y);    liste = liste->next;  }}int countdead(struct deadend *liste){  int itemnb = 0;  while (liste) {    itemnb++;    liste = liste->next;  }  return itemnb;}deadend.h#ifndef DEADEND_H#define DEADEND_Hstruct deadend {  int x;  int y;  struct deadend *next;};void addfirst(struct deadend **tete, int x, int y);void addend(struct deadend **tete, int x, int y);void delfirst(struct deadend **liste);void dellist(struct deadend **liste);void runlist(struct deadend *liste);int countdead(struct deadend *liste);#endifAnd the funny Makefile (I know it is ugly)CC = gccCFLAGS=-O3 -Wall -Wextra -W -Werror -ansi -pedantic -pipe -ffast-math -fforce-addr -march=native -fomit-frame-pointer -finline-functions -funroll-loops -funsafe-loop-optimizations -combineLDFLAGS =ifeq ($(ARG), debug)    CFLAGS += -gendifSRC = $(wildcard *.c)OBJ = $(SRC:.c=.o)EXEC = dungeonall: $(EXEC)$(EXEC): $(OBJ)    $(CC) -o $@ $^ $(LDFLAGS) $(CFLAGS)main.o:%.o: %.c    $(CC) -o $@ -c $< $(CFLAGS)clean :    rm -f *.o $(EXEC)
Maze generation, long random time
optimization;c
I didn't look in great detail because there's no explanation of the algorithm you are using, but I did notice that you have several code blocks similar to the following:do {    x = rand()%(maxx-1);    y = rand()%(maxy-1);} while (map[x][y].visited != 0);That code runs quickly when the map is mostly unvisited, but as the percentage of the map that has been visited increases, thean increasing number of iterations is required to locate an unvisited spot.If your map is 1000 by 1000, there are 1,000,000 cells.  When you get down to the last 10 cells, you have a 1 in 100,000 chance of locating an empty cell with each guess.  You should devise a method of tracking used and unused cells separately so you can make a random pick in a single step.Edit:testEndMaze() may be another source of inefficiency.  Instead of searching every cell to see if it has been visited, can you keep count of cells as you visit them?  If so, then testEndMaze() is just comparing your current count of visited cells with the total number of cells in the maze.