Maze generation, long random time

Question

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.c The 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_H

enum {
  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);

#endif

deadend.c This file is a simple chained list tool.

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

#include "deadend.h"

void 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_H

struct 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);
#endif

And the funny Makefile (I know it is ugly)

CC = gcc
CFLAGS=-O3 -Wall -Wextra -W -Werror -ansi -pedantic -pipe -ffast-math -fforce-addr -march=native -fomit-frame-pointer -finline-functions -funroll-loops -funsafe-loop-optimizations -combine
LDFLAGS =

ifeq ($(ARG), debug)
    CFLAGS += -g
endif

SRC = $(wildcard *.c)
OBJ = $(SRC:.c=.o)

EXEC = dungeon



all: $(EXEC)

$(EXEC): $(OBJ)
    $(CC) -o $@ $^ $(LDFLAGS) $(CFLAGS)

main.o:

%.o: %.c
    $(CC) -o $@ -c $< $(CFLAGS)

clean :
    rm -f *.o $(EXEC)

That is a lot of uncommented code for someone to look at and figure out to answer your question. Can you provide an explanation (ideally in comments) or a link to the algorithm you are using? — jimreed, Commented Jul 13, 2011 at 16:25
The algorithm is here: web.archive.org/web/20080203123815/www.aarg.net/~minam/…. I'll edit my question for comment. — Lutin, Commented Jul 13, 2011 at 17:41

jimreed · Accepted Answer · 2011-07-13 18:49:54Z

6

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.

edited Jul 13, 2011 at 18:49

answered Jul 13, 2011 at 16:43

jimreed

5013 silver badges8 bronze badges

\$\begingroup\$ Sorry for the explanations, I renamed all functions and variables so I thought it was easily readable. The algorithme that I use is like described in this page web.archive.org/web/20080203123815/www.aarg.net/~minam/… but without rooms. You had a great point, do you have an idea about what kind of structure I have to use for tracking visited and univisited cells separately ? That was one of my ideas at the first but I didn't succeed in creating a tool for that. Of course, thank you very much for your answer. \$\endgroup\$
– Lutin
Commented Jul 13, 2011 at 17:39
\$\begingroup\$ @Lutin Your function and variable names are not bad, but they are not necessarily enough. Your question contains hundreds of lines of code. That's a lot to sort through without knowing what you are looking at. Even a high-level description of your algorithm would have been helpful. \$\endgroup\$
– jimreed
Commented Jul 13, 2011 at 17:40
\$\begingroup\$ @Lutin This may not be not very elegant, but the first thing that comes to mind is to build an array listing all of the unvisited cells, use rand()%(unvisitedCellCount-1) to pick one. After you pick one, copy the last unvisited cell to the array location you just picked and decrement your unvisitedCellCount. \$\endgroup\$
– jimreed
Commented Jul 13, 2011 at 17:50
\$\begingroup\$ @jimred That's a good idea, I will work in this direction. I've commented enough ? I never work in team and I don't realize if what I did is fairly described. \$\endgroup\$
– Lutin
Commented Jul 13, 2011 at 18:10
\$\begingroup\$ @Jerry Coffin I can't, because the random cells that I choose must be already visited, and I choose a random cell only when I there is no possible direction. \$\endgroup\$
– Lutin
Commented Jul 13, 2011 at 18:33

Add a comment |

Stack Exchange Network

Maze generation, long random time

1 Answer 1

Your Answer

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

Hot Network Questions

Maze generation, long random time

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

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