алгоритм генерации лабиринта в c с DFS - PullRequest
0 голосов
/ 30 декабря 2018

недавно я прочитал эту тему о создании лабиринтов в с.см. здесь https://www.algosome.com/articles/maze-generation-depth-first.html, и я хочу написать это в с.Вот мой код, и он не работает правильно.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int check[5][5];
int v[5][5];
int border(int x , int y ){
    if(x> -1 && x< 6 && y > -1 && y<6)
        return 1;
    else
        return 0 ;
}
int wall[6][6][6][6];
void dfs ( int x , int y){
    srand(time(NULL));
    int s = 1/*rand() % 4 ;*/ ;
    if(s=1 ){
        if(border(x ,y-1)&& check[x][y-1]==0){
            check[x][y]=1;
            wall[x][y][x+1][y]=1;
            dfs(x , y-1);
        }
        else
            return ;
    }
    else if(s=2){
        if(border(x+1 ,y)&&check[x+1][y]==0){
            check[x][y]=1;
            wall[x+1][y][x+1][y+1]=1;
            dfs(x+1 , y);
        }
        else return ;
    }
    else if(s=3){
        if(border(x ,y+1)&&check[x][y+1]==0){
            check[x][y]=1;
            wall[x][y+1][x+1][y+1]=1;
            dfs(x , y+1);
        }
        else return ;
    }
    else if(s=0){
        if(border(x-1 ,y)&&check[x-1][y]==0){
            check[x][y]=1;
            wall[x][y][x][y+1]=1;
            dfs(x-1 , y);
        }
        else return ;
    }
return ;
}

int main(){
dfs( 4, 4);
for(int i =0 ; i < 6 ; i++)
    for (int j =0 ; j < 6 ; j++)
        for ( int h =0 ; h <6 ; h++)
            for (int k =0 ; k < 6 ; k ++)
                printf("%d \n" , wall[i][j][h][k]);

return 0 ;
}

Я инвертирую свою таблицу в график и хочу показать мне координаты моих стен.в чем проблема?

1 Ответ

0 голосов
/ 31 декабря 2018

В вашем коде есть несколько ошибок - ошибок программирования и логических ошибок:

  • Когда вы различаете направления, s=1 и т. Д. Должно быть s == 1.Вы хотите сравнение, а не назначение.(Ваш код является допустимым C, поэтому ошибки нет.)
  • Вы звоните srand в начале dfs, который вы вызываете рекурсивно.Это заставит ваш единственный (прокомментированный) вызов rand всегда создавать одно и то же случайное число.Вы должны заполнить генератор псевдослучайных чисел только один раз в начале main.
  • Вы можете сохранить пути так, как вы это делаете, но это расточительно.В каждой ячейке есть только четыре возможных пути, поэтому вам не нужен массив, который позволяет, например, создать путь между (0,0) и (3,4).
  • Ваш код выиграетот использования констант или перечисляемых значений вместо жестко закодированных 5 и 6.Это позволит вам позже легко изменить размеры.

Но ваша главная ошибка в том, как вы реализуете алгоритм.Вы выбираете одно из произвольных направлений, а затем проверяете, приводит ли это направление к действительной непосещаемой ячейке.Если это так, вы вернетесь.Если нет, вы остановитесь.Это создаст единый неразветвленный путь через ячейки.Обратите внимание, что если вы начинаете с угловой ячейки, у вас уже есть 50% шанс остановить короткую рекурсию.

Но вам нужно что-то еще: вам нужен лабиринт с множеством ветвей, который ведет к каждой ячейке в лабиринте,Поэтому, когда возвращается первая рекурсия, вы должны попытаться перейти к другим ячейкам.Алгоритм выглядит следующим образом:

  • Составьте список всех возможных выходов.
  • Если есть возможные выходы:
    • Выберите один выход, создайте путь к немуexit и recurse.
    • Обновите список возможных выходов.

Обратите внимание, что вы не можете повторно использовать старый список выходов, поскольку рекурсия может иметьсделал некоторые возможные выходы недействительными, посетив ячейки назначения.

Ниже приведен код, который создает лабиринт с описанным алгоритмом.Я использовал два разных массива для описания горизонтальных и вертикальных путей:

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

enum {
    W = 36,         // width of maze
    H = 25          // height of maze
};

enum {
    North,
    East,
    South,
    West,
    NDir
};

char visited[H][W];
char horz[H][W - 1];        // horizontal E-W paths in the maze
char vert[H - 1][W];        // veritcal N-S paths in the maze

/*
 *      Fill dir with directions to unvisited cells, return count
 */
int adjacent(int dir[], int x, int y)
{
    int ndir = 0;

    if (y > 0     && visited[y - 1][x] == 0) dir[ndir++] = North;
    if (x < W - 1 && visited[y][x + 1] == 0) dir[ndir++] = East;
    if (y < H - 1 && visited[y + 1][x] == 0) dir[ndir++] = South;
    if (x > 0     && visited[y][x - 1] == 0) dir[ndir++] = West;

    return ndir;
}

/*
 *      Traverse cells depth first and create paths as you go
 */
void dfs(int x, int y)
{
    int dir[NDir];
    int ndir;

    visited[y][x] = 1;

    ndir = adjacent(dir, x, y);

    while (ndir) {
        int pick = rand() % ndir;

        switch (dir[pick]) {
        case North: vert[y - 1][x] = 1; dfs(x, y - 1); break;
        case East:  horz[y][x] = 1;     dfs(x + 1, y); break;
        case South: vert[y][x] = 1;     dfs(x, y + 1); break;
        case West:  horz[y][x - 1] = 1; dfs(x - 1, y); break;
        }

        ndir = adjacent(dir, x, y);
    }
}

/*
 *      Print a map of the maze
 */
void map(void)
{
    int i, j;

    for (i = 0; i < W; i++) {
        putchar('_');
        putchar('_');
    }

    putchar('\n');

    for (j = 0; j < H; j++) {
        putchar('|');

        for (i = 0; i < W; i++) {
            putchar(j < H - 1 && vert[j][i] ? ' ' : '_');
            putchar(i < W - 1 && horz[j][i] ? '_' : '|');
        }

        putchar('\n');
    }
}

int main()
{
    srand(time(NULL));

    dfs(0, 0);
    map();

    return 0;
}

Вы можете проверить это здесь .Если вы замените while в dsf на простой if, вы получите более или менее то, что реализовали.Обратите внимание, что это создает только один, обычно короткий путь.

...