maze-faq

迷宫

========================================
Maze FAQ
========================================

Sorry this is NOT an organized FAQ it's still useful though
------------------------------------------------------------

Oh, you're really going to love this one.  It's an obfuscated C code
mazegenerator.  Fun fun fun.  Well, if you can figure it out, there's
youralgorithm.  Fun fun fun.

char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C);
--            E;             J[              E]             =T
[E   ]=  E)   printf("._");  for(;(A-=Z=!Z)  ||  (printf("\n|"
)    ,   A    =              39              ,C             --
)    ;   Z    ||    printf   (M   ))M[Z]=Z[A-(E   =A[J-Z])&&!C
&    A   ==             T[                                  A]
|6<<11<rand()||!C&!Z?J[T[E]=T[A]]=E,J[T[A]=A-Z]=A,"_.":" |"];}

Pretty cute, no?

--
Brad Threatt | MISSING! Single white male Jesus look-alike in blue
       | Members Only jacket.  Answers to the name 'Dave Gillespie'.
Safe sex is  | Last seen with roller-skating couple in Pasadena.
for wimps.   | If found, please return to the cs10 lab immediately.
========================================


In <[e-mail]> [e-mail] (Randolph
Carter (nee. Joseph H. Allen)) writes:


>>char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C);
>>--            E;             J[              E]             =T
>>[E   ]=  E)   printf("._");  for(;(A-=Z=!Z)  ||  (printf("\n|"
>>)    ,   A    =              39              ,C             --
>>)    ;   Z    ||    printf   (M   ))M[Z]=Z[A-(E   =A[J-Z])&&!C
>>&    A   ==             T[                                  A]
>>|6<<11<rand()||!C&!Z?J[T[E]=T[A]]=E,J[T[A]=A-Z]=A,"_.":" |"];}
      ^^
This should be 28 if rand() returns a 32-bit quantity.

>>Pretty cute, no?

>No style at all.... :-)

========================================

>--
>/*  [e-mail] */      /* Amazing */             /* Joseph H.
Allen */
>int
a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
>+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*
2
>]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n","
#"[!a[q-1]]);}

Well, it doesn't produce a maze, but try this one...

int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c
-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}
(I disclaim any credit for this!)
--
John Brownie
School of Mathematics and Statistics
University of Sydney
Internet: [e-mail]



========================================

Excerpts from programming: 6-Mar-92 Re: Algorithm to create a m.. Mark
[e-mail]. (5723)


Here's the single level maze algorithm, solver and printer.

/*
 * MazeGen.c -- Mark Howell -- 8 May 1991
 *
 * Usage: MazeGen [width [height [seed]]]
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define WIDTH 39
#define HEIGHT 11

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
#ifdef TRUE
#undef TRUE
#endif /* TRUE */

#define TRUE 1

#define cell_empty(a) (!(a)->up && !(a)->right && !(a)->down && !(a)->left)

typedef struct {
    unsigned int up      : 1;
    unsigned int right   : 1;
    unsigned int down    : 1;
    unsigned int left    : 1;
    unsigned int path    : 1;
    unsigned int visited : 1;
} cell_t;
typedef cell_t *maze_t;

void CreateMaze (maze_t maze, int width, int height);
void SolveMaze (maze_t maze, int width, int height);
void PrintMaze (maze_t maze, int width, int height);

int main (int argc, char *argv [])
{
    int width = WIDTH;
    int height = HEIGHT;
    maze_t maze;

    if (argc >= 2)
        width = atoi (argv [1]);

    if (argc >= 3)
        height = atoi (argv [2]);

    if (argc >= 4)
        srand (atoi (argv [3]));
    else
        srand ((int) time ((time_t *) NULL));

    if (width <= 0 || height <= 0) {
        (void) fprintf (stderr, "Illegal width or height value!\n");
        exit (EXIT_FAILURE);
    }
    maze = (maze_t) calloc (width * height, sizeof (cell_t));
    if (maze == NULL) {
        (void) fprintf (stderr, "Cannot allocate memory!\n");
        exit (EXIT_FAILURE);
    }
    CreateMaze (maze, width, height);

    PrintMaze (maze, width, height);

    (void) putchar ('\n');

    SolveMaze (maze, width, height);

    PrintMaze (maze, width, height);

    free (maze);
    exit (EXIT_SUCCESS);

    return (0);

}/* main */


void CreateMaze (maze_t maze, int width, int height)
{
    maze_t mp, maze_top;
    char paths [4];
    int visits, directions;

    visits = width * height - 1;
    mp = maze;
    maze_top = mp + (width * height) - 1;

    while (visits) {
        directions = 0;

        if ((mp - width) >= maze && cell_empty (mp - width))
            paths [directions++] = UP;
        if (mp < maze_top && ((mp - maze + 1) % width) && cell_empty (mp + 1))
            paths [directions++] = RIGHT;
        if ((mp + width) <= maze_top && cell_empty (mp + width))
            paths [directions++] = DOWN;
        if (mp > maze && ((mp - maze) % width) && cell_empty (mp - 1))
            paths [directions++] = LEFT;

        if (directions) {
            visits--;
            directions = ((unsigned) rand () % directions);

            switch (paths [directions]) {
                case UP:
                    mp->up = TRUE;
                    (mp -= width)->down = TRUE;
                    break;
                case RIGHT:
                    mp->right = TRUE;
                    (++mp)->left = TRUE;
                    break;
                case DOWN:
                    mp->down = TRUE;
                    (mp += width)->up = TRUE;
                    break;
                case LEFT:
                    mp->left = TRUE;
                    (--mp)->right = TRUE;
                    break;
                default:
                    break;
            }
        } else {
            do {
                if (++mp > maze_top)
                    mp = maze;
            } while (cell_empty (mp));
        }
    }
}/* CreateMaze */


void SolveMaze (maze_t maze, int width, int height)
{
    maze_t *stack, mp = maze;
    int sp = 0;

    stack = (maze_t *) calloc (width * height, sizeof (maze_t));
    if (stack == NULL) {
        (void) fprintf (stderr, "Cannot allocate memory!\n");
        exit (EXIT_FAILURE);
    }
    (stack [sp++] = mp)->visited = TRUE;

    while (mp != (maze + (width * height) - 1)) {

        if (mp->up && !(mp - width)->visited)
            stack [sp++] = mp - width;
        if (mp->right && !(mp + 1)->visited)
            stack [sp++] = mp + 1;
        if (mp->down && !(mp + width)->visited)
            stack [sp++] = mp + width;
        if (mp->left && !(mp - 1)->visited)
            stack [sp++] = mp - 1;

        if (stack [sp - 1] == mp)
            --sp;

        (mp = stack [sp - 1])->visited = TRUE;
    }
    while (sp--)
        if (stack [sp]->visited)
            stack [sp]->path = TRUE;

    free (stack);

}/* SolveMaze */


void PrintMaze (maze_t maze, int width, int height)
{
    int w, h;
    char *line, *lp;

    line = (char *) calloc ((width + 1) * 2, sizeof (char));
    if (line == NULL) {
        (void) fprintf (stderr, "Cannot allocate memory!\n");
        exit (EXIT_FAILURE);
    }
    maze->up = TRUE;
    (maze + (width * height) - 1)->down = TRUE;

    for (lp = line, w = 0; w < width; w++) {
        *lp++ = '+';
        if ((maze + w)->up)
            *lp++ = ((maze + w)->path) ? '.' : ' ';
        else
            *lp++ = '-';
    }
    *lp++ = '+';
    (void) puts (line);
    for (h = 0; h < height; h++) {
        for (lp = line, w = 0; w < width; w++) {
            if ((maze + w)->left)
                *lp++ = ((maze + w)->path && (maze + w - 1)->path) ? '.' : ' ';
            else
                *lp++ = '|';
            *lp++ = ((maze + w)->path) ? '.' : ' ';
        }
        *lp++ = '|';
        (void) puts (line);
        for (lp = line, w = 0; w < width; w++) {
            *lp++ = '+';
            if ((maze + w)->down)
                *lp++ = ((maze + w)->path && (h == height - 1 ||
                         (maze + w + width)->path)) ? '.' : ' ';
            else

                *lp++ = '-';
        }
        *lp++ = '+';
        (void) puts (line);
        maze += width;
    }
    free (line);

}/* PrintMaze */



========================================


Excerpts from programming: 6-Mar-92 Re: Algorithm to create a m.. "Jon
C. R. Bennett"@andr (4255)


[e-mail] (Don Gillies) writes:
> grid.  Mark each square in the grid with a unique number.  Make a list

what you want to do is make each grid in the maze into a set.

>
>     rooms = n*n         /* each spot in the grid is a unique room */
>
>     repeat
>         pick a random wall without replacement.
>         if the numbers X and Y in the grid on both sides of the wall
>             are different --
>                 delete the wall and use a recursive depth
>                 first search or brute-force loop to replace
>                 all Y in the grid with X's.
        what you do here is instead
        pick a wall
        if the rooms on either side of the wall belong to differnent sets
               delete the wall
               union the two sets together.

the rest is the same


the brute force solution runs in O(n^2) this runs in O(n) (where n is the
number of grids) so if you had a 100 x 100 maze, this method takes 10,000
time steps, the brute force could take as many as 100,000,000 steps.

jon

p.s. below you will find some code to generate a maze this way


---------------------------------------------------
/* maze.c   a maze generator
   Jon Bennett
        [e-mail]
   */

/* the maze is generated by making a list of all the internal hedges
   and randomizing it, then going lineraly through the list, we take a
   hedge and se if the maze squares adjacent to it are already connected
   (with find) is not the we connect them (with link), this prevents us
   from creating a maze with a cycle because we will not link two maze
   squares that are already connect by some path */
#include <stdio.h>

#define DOWN 1
#define RIGHT 2

struct maze_loc{
    int rank;
    int x,y;
    struct maze_loc *ptr;
};
struct hedge_loc{
    int x,y,pos,on;
};

struct maze_loc *maze;
struct hedge_loc *hedge;
struct hedge_loc **hedge_list;

void link(a,b)
 struct maze_loc *a,*b;
{
    if(a->rank == b->rank){
        a->ptr=b;
        b->rank++;
        return;
    }
    if(a->rank > b->rank){
        b->ptr=a;
        return;
    }
    a->ptr=b;
}
struct maze_loc *find(a)
 struct maze_loc *a;
{
    if(a != a->ptr){
        a->ptr = find(a->ptr);
    }
    return a->ptr;
}

main(argc,argv)
 int argc;
 char **argv;
{
    int x,y,i,j,k,l,tmp;
    struct maze_loc *a,*b;
    struct hedge_loc *htmp;

    if(argc!=3) exit(1);

    srandom(time(0));
    x=atoi(argv[1]);
    y=atoi(argv[2]);

    /*malloc the maze and hedges */
    maze=(struct maze_loc *)malloc(sizeof(struct maze_loc)*x*y);
    hedge=(struct hedge_loc *)malloc(sizeof(struct
hedge_loc)*((x*(y-1))+((x-1)*y)));
    hedge_list=(struct hedge_loc **)malloc(sizeof(struct hedge_loc
*)*((x*(y-1))+((x-1)*y)));

    /*init maze*/

    for(j=0;j<y;j++){
        for(i=0;i<x;i++){
            maze[x*j+i].x = i;
            maze[x*j+i].y = j;
            maze[x*j+i].ptr = &maze[x*j+i];
            maze[x*j+i].rank=0;