The Mud Connector

Author Topic: Adapting Maze Generator Code  (Read 593 times)

Hades_Kane

  • Community Manager
  • TMC Veteran
  • *****
  • Posts: 1229
  • Owner / Administrator of End of Time
    • View Profile
    • End of Time
Adapting Maze Generator Code
« on: February 21, 2018, 4:01 AM »
I adapted the Smaug/AFK MUD overland map code to my ROM last year and haven't stopped tinkering with it since.

I ran across this maze generator that outputs a text based or GIF based result when you plug in some parameters:

http://www.delorie.com/game-room/mazes/

I have been working on trying to adapt this code to generate a maze in the memory of the game similar to how the PNG (well, actually RAW file) is loaded into memory, and while I learned a lot adapting that code, I can't seem to get this right.

I'm sure I'm overlooking or mixing something up with the Xs and Ys.

The original code is here:

http://www.delorie.com/game-room/mazes/genmaze.cc

I commented out the various dprintf calls in the first half of the code... pretty sure I don't need any of that.

In fact, I believe everything up to where I have commented out the FILE *trans line should be fine as-is... I believe my problems are coming after that point.

In the second chunk I commented out the stuff involving outputting the GIF and have attempted to replace the fputc functions (if I understand this right, this is the function actually writing the color information to the destination GIF) with the function that actually places the proper sector type (and thus visual tile) into the memory for the map/maze.  That is where I feel like I'm going wrong somewhere in it.  It generates the maze... kinda, and the "solution" path is generally similar to what the solution path would be in the actual image the code on the website generates.  I have a variety of sector types in place just so I can try to track where each part of the code is doing, and I've tried all sorts of combinations in the putterr function and just not getting anywhere.

Can anyone see what I'm doing wrong here?

The code as I have it currently adapted is as follows:

Code: [Select]

int print_mime = 1;
int solve = 1;
int html = 0;

#define GIF_GREY 0xcc


#define GO_LEFT 1
#define GO_RIGHT 2
#define GO_UP 4
#define GO_DOWN 8
#define USED 16
#define SOLUTION 32

#define M1(x,y) maze_data[(x)+1+((y)+1)*(c+2)]

#define dprintf if(0)printf

void generate_maze(int c, int r, int w, int h, int s)
{
char *maze_data;
int x, y;
int *xt, *yt;

if (c < 1 || r < 1 || w < 1 || h < 1)
return;

maze_data = (char *)calloc(r+2, c+2);
xt = (int *)malloc(c*r*sizeof(int));
yt = (int *)malloc(c*r*sizeof(int));

for (x=0; x<c; x++)
for (y=0; y<r; y++)
{
xt[x+y*c] = x;
yt[x+y*c] = y;
}

for (x=-1; x<=c; x++)
{
M1(x, -1) = USED;
M1(x, r) = USED;
}
for (y=0; y<=r; y++)
{
M1(-1, y) = USED;
M1(c, y) = USED;
}

if (s == 0)
s = time(0);
srandom(s);

for (x=r*c-1; x>0; x--)
{
y = random() % (x+1);
if (y!=x)
{
int t = xt[x];
xt[x] = xt[y];
xt[y] = t;
t = yt[x];
yt[x] = yt[y];
yt[y] = t;
}
}

M1(-1,0) |= USED | GO_RIGHT;
M1(0,0) |= USED | GO_LEFT;

int num_left = r*c-1;
while (num_left)
for (x=0; x<c; x++)
for (y=0; y<r; y++)
{
//dprintf("%d, %d\n", x, y);
while (1)
{
int px = xt[x+y*c];
int py = yt[x+y*c];
int ways[8], wp;
if (!(M1(px, py) & USED))
break;
//dprintf("\tstarting\n");

while (1)
{
wp = 0;

if (!(M1(px,py-1) & USED))
ways[wp++] = GO_UP;
if (!(M1(px,py-1) & USED))
ways[wp++] = GO_UP;
if (!(M1(px,py+1) & USED))
ways[wp++] = GO_DOWN;
if (!(M1(px-1,py) & USED))
ways[wp++] = GO_LEFT;
if (!(M1(px-1,py) & USED))
ways[wp++] = GO_LEFT;
if (!(M1(px+1,py) & USED))
ways[wp++] = GO_RIGHT;
if (wp == 0)
{
//dprintf("\t\tblocked at %d,%d\n", px, py);
break; // blocked at this point
}
//dprintf("\t\t%d ways found from %d,%d\n", wp, px, py);

wp = random() % wp;

switch (ways[wp])
{
case GO_LEFT:
//dprintf("\t\tleft\n");
M1(px,py) |= GO_LEFT;
px--;
M1(px,py) |= GO_RIGHT | USED;
break;
case GO_RIGHT:
//dprintf("\t\tright\n");
M1(px,py) |= GO_RIGHT;
px++;
M1(px,py) |= GO_LEFT | USED;
break;
case GO_UP:
//dprintf("\t\tup\n");
M1(px,py) |= GO_UP;
py--;
M1(px,py) |= GO_DOWN | USED;
break;
case GO_DOWN:
//dprintf("\t\tdown\n");
M1(px,py) |= GO_DOWN;
py++;
M1(px,py) |= GO_UP | USED;
break;
}
num_left--;
}

//dprintf("\tending at %d,%d\n", px, py);
if (px == xt[x+y*c] && py == yt[x+y*c])
break;
}
}

M1(c,r-1) |= USED | GO_LEFT;
M1(c-1,r-1) |= USED | GO_RIGHT;

if (solve)
{
for (x=0; x<c; x++)
for (y=0; y<r; y++)
M1(x,y) |= SOLUTION;
M1(-1,0) |= SOLUTION;
M1(0,0) |= SOLUTION;
M1(c,r-1) |= SOLUTION;
M1(c-1,r-1) |= SOLUTION;

for (x=0; x<c; x++)
for (y=0; y<r; y++)
{
int px = x;
int py = y;
int ways[4], wp;

while (1)
{
wp = 0;

if (M1(px,py) & GO_UP && M1(px,py-1) & SOLUTION)
ways[wp++] = GO_UP;
if (M1(px,py) & GO_DOWN && M1(px,py+1) & SOLUTION)
ways[wp++] = GO_DOWN;
if (M1(px,py) & GO_LEFT && M1(px-1,py) & SOLUTION)
ways[wp++] = GO_LEFT;
if (M1(px,py) & GO_RIGHT && M1(px+1,py) & SOLUTION)
ways[wp++] = GO_RIGHT;
if (wp != 1)
break; // not a dead end

switch (ways[0])
{
case GO_LEFT:
M1(px,py) &= ~SOLUTION;
px--;
break;
case GO_RIGHT:
M1(px,py) &= ~SOLUTION;
px++;
break;
case GO_UP:
M1(px,py) &= ~SOLUTION;
py--;
break;
case GO_DOWN:
M1(px,py) &= ~SOLUTION;
py++;
break;
}
}
}
}


// 0 = lines  GIF_GREY = blank  255 = solution
int i, dy;
//FILE *trans = popen("/usr/bin/ppmtogif 2>/dev/null", "w");
//fprintf(trans, "P5\n%d %d %d\n", (c+2)*w+1, (r+2)*h+1, 255);

for (i=0; i<((c+2)*w+1) * h; i++)
putterr( MAP_MAZE, 0, 0, SECT_ICE );
// fputc(GIF_GREY, trans);
for (y=0; y<=r; y++)
{
for (i=0; i<w; i++)
putterr( MAP_MAZE, i, y, SECT_ICE );
// fputc(GIF_GREY, trans);
// fputc(0, trans);
putterr( MAP_MAZE, 0, y, SECT_RUINS );
for (x=0; x<c; x++)
{
if (M1(x,y) & GO_UP || x==-1)
for (i=1; i<w; i++)
if(M1(x,y)&SOLUTION && M1(x,y-1)&SOLUTION)
putterr( MAP_MAZE, x, y, SECT_SNOW );
else
putterr( MAP_MAZE, x, y, SECT_DTRAIL );
//fputc((M1(x,y)&SOLUTION && M1(x,y-1)&SOLUTION) ? 255 : GIF_GREY, trans);
else
for (i=1; i<w; i++)
putterr( MAP_MAZE, x, y, SECT_RUINS );
//fputc(0, trans);
putterr( MAP_MAZE, x, y, SECT_RUINS );
// fputc(0, trans);
}

for (i=0; i<w; i++)
putterr( MAP_MAZE, i, y, SECT_DTRAIL );
// fputc(GIF_GREY, trans);

if (y<r)
for (dy=1; dy<h; dy++)
{
for (i=0; i<w; i++)
if(M1(-1,y)&SOLUTION)
putterr( MAP_MAZE, -1, y, SECT_SNOW );
else
putterr( MAP_MAZE, -1, y, SECT_DTRAIL );
// fputc(M1(-1,y)&SOLUTION ? 255 : GIF_GREY, trans);
if (M1(0,y) & GO_LEFT)
if(M1(-1,y)&SOLUTION)
putterr( MAP_MAZE, -1, y, SECT_SNOW );
else
putterr( MAP_MAZE, -1, y, SECT_DTRAIL );
// fputc((M1(-1,y)&SOLUTION) ? 255 : GIF_GREY, trans);
else
putterr( MAP_MAZE, 0, y, SECT_RUINS );
// fputc(0, trans);
for (x=0; x<c; x++)
{
for (i=1; i<w; i++)
if(M1(x,y)&SOLUTION)
putterr( MAP_MAZE, x, y, SECT_SNOW );
else
putterr( MAP_MAZE, x, y, SECT_DTRAIL );
//fputc((M1(x,y)&SOLUTION) ? 255 : GIF_GREY, trans);
if (M1(x,y) & GO_RIGHT)
if(M1(x,y)&SOLUTION && M1(x+1,y)&SOLUTION)
putterr( MAP_MAZE, x+1, y, SECT_SNOW );
else
putterr( MAP_MAZE, x+1, y, SECT_DTRAIL );
//fputc((M1(x,y)&SOLUTION && M1(x+1,y)&SOLUTION) ? 255 : GIF_GREY, trans);
else
putterr( MAP_MAZE, x, y, SECT_RUINS );
// fputc(0, trans);
}
for (i=0; i<w; i++)
if(M1(c,y)&SOLUTION)
putterr( MAP_MAZE, c, y, SECT_SNOW );
else
putterr( MAP_MAZE, c, y, SECT_DTRAIL );
// fputc(M1(c,y)&SOLUTION ? 255 : GIF_GREY, trans);
}
}
for (i=0; i<((c+2)*w+1) * h; i++)
putterr( MAP_MAZE, 0, 0, SECT_ICE );
// fputc(GIF_GREY, trans);
//pclose(trans);
-Diablos
End of Time, a 100% free Final Fantasy & Chrono Trigger based MUD with a large original world, unique combat & magic systems, and more!
eotmud.com : 4000 • http://www.eotmud.comhttp://www.facebook.com/eotmud
http://www.mudconnect.com/mud-bin/adv_search.cgi?Mode=MUD&mud=End+of+Time

Zividave

  • Jr. Member
  • **
  • Posts: 87
    • View Profile
    • AnsalonMUD
Re: Adapting Maze Generator Code
« Reply #1 on: February 21, 2018, 2:19 PM »
Hades, i found the predecessor to this I believe, might be helpful as someone changed it to create Envy area files.
I didn't find it in a google search, but I can past the code here (mazegen.c by Mark Howell, updated in 97 to make Envy files)

Code: [Select]
/*
 * MazeGen.c -- Mark Howell -- 8 May 1991
 * modified 1997/04/16 to generate Envy 1.0 area files.
 *
 * Usage: MazeGen [width [height [seed]]]
 *
 * Outputs the area file to stdout.  Also makes two very useful
 * objects, a map of the maze and a solution to the maze.  This
 * algorithm can be adapted to dynamically generated mazes.  You
 * may wish to prevent the maze from changing if players are actually
 * in the maze at the time or you may wind up trapping them in an
 * unreachable portion.
 *
 * There are different room descriptions based on the number of
 * exits in the room.  Feel free to change them in the source code
 * or edit the resulting output file.  Also, you may want to modify
 * the number of different mobs and mob placement.  Current algorithm
 * it to put one mob in each room.
 */
#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)
{
    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 */

void Maze2Area (maze_t maze, int width, int height)
{
    int w, h;
int vnum=0;
int num_exit;

printf("#ROOMS\n\n");

    maze->up = 0;
    (maze + (width * height) - 1)->down = 0;

    for (h = 0; h < height; h++)
{
        for (w = 0; w < width; w++)
{
num_exit = 0;
if ((maze + w)->up)
++num_exit;
if ((maze + w)->right)
++num_exit;
if ((maze + w)->down)
++num_exit;
if ((maze + w)->left)
++num_exit;
printf("#QQ%3.3d\n", vnum);
switch (num_exit)
{
case 0 :
printf("Lost in the maze~\n");
printf("You are lost in a maze of twisty passages with nowhere to go\n~\n");
break;
case 1 :
printf("Dead end~\n");
printf("Ha ha ha ha ha.  You have to go back now!\n~\n");
break;
case 2 :
printf("Twisty tunnel~\n");
printf("You are in a maze of twisty passages, all alike\n~\n");
break;
case 3:
printf("Twisty passage~\n");
printf("You are in a maze of twisty passages, all alike\n~\n");
break;
case 4 :
printf("Twisty room~\n");
printf("You are in a maze of twisty passages, all alike\n~\n");
break;
}
printf("0 524608 0\n");
if ((maze + w)->up)
printf("D0\n~\n~\n0 0 QQ%3.3d\n", vnum - width );
if ((maze + w)->right)
printf("D1\n~\n~\n0 0 QQ%3.3d\n", vnum + 1 );
if ((maze + w)->down)
printf("D2\n~\n~\n0 0 QQ%3.3d\n", vnum + width );
if ((maze + w)->left)
printf("D3\n~\n~\n0 0 QQ%3.3d\n", vnum - 1 );
printf("S\n");
++vnum;
        }
        maze += width;
    }
printf("#0\n\n");
printf("#RESETS\n\n");

    for (vnum = 0; vnum < width * height; vnum++)
{
printf("M 0 QQ000 %d QQ%3.3d\n", width*height, vnum);
}

printf("S\n\n");
printf("#$\n\n");


}/* PrintMaze */


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

printf("#AREA { 5 50} Envy   Terrible Maze~\n\n");


    CreateMaze (maze, width, height);

printf("#OBJECTS\n\n");

printf("#QQ000\n");
printf("map maze~\n");
printf("a map of the maze.~\n");
printf("A map of the maze.~\n");
printf("~\n");
printf("12 0 1\n");
printf("0~ 0~ 0~ 0~\n");
printf("0 1500 0\n");

printf("E\n");
printf("map~\n");
    PrintMaze (maze, width, height);
printf("~\n");

    SolveMaze (maze, width, height);

printf("E\n");
printf("solution~\n");
    PrintMaze (maze, width, height);
printf("~\n");

printf("#0\n\n");

/* Make the mob */

printf("#MOBILES\n\n");
printf("#QQ000\n");
printf("maze rat~\n");
printf("a maze rat~\n");
printf("A maze rat is hear to gnaw on you.\n~\n");
printf("Yeuch, why would you want to look at that ugly rat?\nJust KILL IT!\n~\n");

printf("1 40 1000 S\n");
printf("50 40 -100 4d175+1400 3d3+33\n");
printf("500 0\n");
printf("18 28 1\n");
printf("#0\n");

/* now generate the rooms */

    Maze2Area (maze, width, height);

/* And the trailer */

printf("#$\n");

    free (maze);
    exit (EXIT_SUCCESS);

    return (0);

}/* main */


Hades_Kane

  • Community Manager
  • TMC Veteran
  • *****
  • Posts: 1229
  • Owner / Administrator of End of Time
    • View Profile
    • End of Time
Re: Adapting Maze Generator Code
« Reply #2 on: February 21, 2018, 3:21 PM »
Thanks for that :)

I'm not sure how well that will translate to what I'm trying to accomplish, but I sure will take a good bit of time to examine it and see if it might help me understand the code behind it all a bit better.

For those unfamiliar with the overland system I'm working with a little more detail on what I'm trying to accomplish...

It was late and I was pretty tired last night, so I didn't really go into much detail, but essentially the Overland code takes a graphic file and reads it, pixel by pixel, in an X axis for loop neslted in a Y axis for loop... it reads the color information from the pixels and assigns a sector based on that into the map array.

The code I'm trying to adapt this from creates an actual graphic, ie:



and so what I'm trying to do is take the code that generates the graphic (which also does it along nestled X/Y axis for loops) and instead of outputting to a file, I'm trying to output to the map array directly.

It is kind of working (its generating into the map array and is visible, and has elements of the maze correctly showing, but parts seem to be being completely skipped leaving weird gaps and mashing up parts), but I'm getting something jumbled because I don't quite understand the code well enough to figure out exactly out to translate bits such as:

Code: [Select]
fputc(GIF_GREY, trans);into:
Code: [Select]
putterr( MAP_MAZE, x, y, SECT_DTRAIL );
And I'm pretty sure the core issue I'm having is figuring out how to take "this specific location (x/y) of the graphic would normally be written as <blah>" and making compatible with the map array.

Specifically, I believe that the way these loops are set up, they are automatically moving trough the points in the graphic, but they are moving oddly, and I'm not quite catching or understanding the additional for loops exactly.
-Diablos
End of Time, a 100% free Final Fantasy & Chrono Trigger based MUD with a large original world, unique combat & magic systems, and more!
eotmud.com : 4000 • http://www.eotmud.comhttp://www.facebook.com/eotmud
http://www.mudconnect.com/mud-bin/adv_search.cgi?Mode=MUD&mud=End+of+Time