Генерация лабиринта, долгое время


Как я могу улучшить этот код ? Это займет бесконечное время, если я хочу создать большой лабиринт ООН (аргументы 5000 5000 100 50 100)

главная.с

#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;
}

лабиринт.с Самый важный файл, алгоритм-это здесь:

#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;
}

лабиринт.ч

#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

ул.с Этот файл представляет собой простой инструмент, список посетителей.

#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;
}

ул.ч

#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

И самое забавное файл Makefile (я знаю, что это некрасиво)

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)


333
3
задан 13 июля 2011 в 03:07 Источник Поделиться
Комментарии
1 ответ

Я не смотрел в мельчайших подробностях, потому что объяснения не существует алгоритма, который вы используете, но я заметил, что у вас есть несколько блоков кода, аналогичного следующему:

do {
x = rand()%(maxx-1);
y = rand()%(maxy-1);
} while (map[x][y].visited != 0);

Этот код работает быстро, когда карта в основном непосещенных, но как процент от карта, что посетили увеличивается, Теан увеличивая число итераций, необходимых для поиска непосещенных месте.

Если вашей карты составляет 1000 на 1000, есть 1 000 000 ячеек. Когда Вы дойдете до последней 10 клеток, у вас есть 1 из 100000 шансов найти пустую ячейку с каждым предположением. Вы должны разработать метод отслеживания использованные и неиспользованные ячейки отдельно, так что вы можете сделать случайный выбор в один шаг.

Редактировать:
testEndMaze() может быть еще один источник неэффективности. Вместо того, чтобы искать каждую клетку, чтобы увидеть, если он был посещен, вы можете вести подсчет клеток при их посещении? Если это так, то testEndMaze() просто сравнивая текущее количество посещенных клеток общее количество клеток в лабиринте.

5
ответ дан 13 июля 2011 в 04:07 Источник Поделиться