Maze generation algorithm

Posted By: 3run

Maze generation algorithm - 09/28/13 19:05

As my math really does suck, I want to ask someone to lend me a hand of help, to create a maze generator.
There are those several algorithms on the Wiki, and I would like to see, how one of them will work with lite-c.
Here is the link to the Wiki page:
Maze generation algorithm

There is even an example, in Python, but I don't get a damn thing:
Code:
import numpy
from numpy.random import random_integers as rand
import matplotlib.pyplot as pyplot
 
def maze(width=81, height=51, complexity=.75, density=.75):
    # Only odd shapes
    shape = ((height // 2) * 2 + 1, (width // 2) * 2 + 1)
    # Adjust complexity and density relative to maze size
    complexity = int(complexity * (5 * (shape[0] + shape[1])))
    density    = int(density * (shape[0] // 2 * shape[1] // 2))
    # Build actual maze
    Z = numpy.zeros(shape, dtype=bool)
    # Fill borders
    Z[0, :] = Z[-1, :] = 1
    Z[:, 0] = Z[:, -1] = 1
    # Make isles
    for i in range(density):
        x, y = rand(0, shape[1] // 2) * 2, rand(0, shape[0] // 2) * 2
        Z[y, x] = 1
        for j in range(complexity):
            neighbours = []
            if x > 1:             neighbours.append((y, x - 2))
            if x < shape[1] - 2:  neighbours.append((y, x + 2))
            if y > 1:             neighbours.append((y - 2, x))
            if y < shape[0] - 2:  neighbours.append((y + 2, x))
            if len(neighbours):
                y_,x_ = neighbours[rand(0, len(neighbours) - 1)]
                if Z[y_, x_] == 0:
                    Z[y_, x_] = 1
                    Z[y_ + (y - y_) // 2, x_ + (x - x_) // 2] = 1
                    x, y = x_, y_
    return Z
 
pyplot.figure(figsize=(10, 5))
pyplot.imshow(maze(80, 40), cmap=pyplot.cm.binary, interpolation='nearest')
pyplot.xticks([]), pyplot.yticks([])
pyplot.show()
This could really help me (and not only ME) out! And could be an awesome contribution.


Best greets
Posted By: txesmi

Re: Maze generation algorithm - 09/29/13 01:11

Hi,
since i like this kind of things, I wrote the first maze generation algorithm of the wiki: Depth first

Code:
#include <acknex.h>

#define PRAGMA_POINTER

PANEL *panMaze;

int make_odd ( int i )
{
	return i - ( i % 2 ) + 1;
}

#define array_cell(array,x,y) *(*(array+x)+y)

var **array_create ( int size_x, int size_y )
{
	var **array = (var**)sys_malloc ( sizeof(var*) * size_x );
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c++ )
		*c = (var*)sys_malloc ( sizeof(var) * size_y );
	
	return array;
}

void array_remove ( var **array, int size_x )
{
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c++ )
	{
		var *r = *c;
		sys_free ( r );
	}
	sys_free ( array );
}

#define MAZEX      81 // odd!
#define MAZEY      61 // odd!
#define ENDX       41  // odd!
#define ENDY       31  // odd!

#define UNVISITED   0
#define END         1
#define WALL        2
#define OPEN        3

void array_draw ( var **maze, int size_x, int size_y, BMAP *bmp )
{
	var cell_x = bmap_width ( bmp ) / size_x;
	var cell_y = bmap_height ( bmp ) / size_y;
	
	bmap_rendertarget ( bmp, 0, 0 );
	int c = 0;
	for ( ; c<size_x; c+=1 )
	{
		int r = 0;
		for ( ; r<size_y; r+=1 )
		{
			switch ( array_cell(maze,c,r) )
			{
				case UNVISITED:
				case WALL:      
					break;
				case END:    draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_RED, 100, 0 );    break;
				case OPEN:   draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );   break;
				default:     draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 );  break;
			}
		}
	}
	bmap_rendertarget ( NULL, 0, 0 );
}

var no[4][2] =
{
	-1, 0,
	0, -1,
	1, 0,
	0, 1
};

void maze_depth_first ( var **array, int size_x, int size_y, int end_x, int end_y )
{
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c+=2 )
	{
		var *r = *c;
		var *rl = r + size_y;
		for ( ; r<rl; r++ )
		{
			*r = WALL;
		}
	}
	
	var **c = array + 1;
	var **cl = c + size_x - 1;
	for ( ; c<cl; c+=2 )
	{
		var *r = *c;
		var *rl = r + size_y;
		for ( ; r<rl; r+=2 )
		{
			*r = WALL;
		}
	}
	
	int x = end_x;
	int y = end_y;
	array_cell(array,x,y) = END;
	int cells_to_end = OPEN;
	
	while (1)
	{
		int noi = integer ( random(4) );
		int i = 0;
		for ( ; i<4; i+=1 )
		{
			int nx = x + no[noi][0] * 2;
			int ny = y + no[noi][1] * 2;
			if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
			{
				noi = cycle ( noi + 1, 0, 4 );
				continue;
			}
			if ( array_cell(array,nx,ny) > UNVISITED )
			{
				noi = cycle ( noi + 1, 0, 4 );
				continue;
			}
			int nx2 = x + no[noi][0];
			int ny2 = y + no[noi][1];
			array_cell(array,nx2,ny2) = OPEN;
			array_cell(array,nx,ny) = OPEN;
			x = nx;
			y = ny;
			cells_to_end += 2;
			break;
		}
		
		if ( i == 4 )
		{
			if ( array_cell(array,x,y) == END )
				break;
			array_cell(array,x,y) = cells_to_end;
			cells_to_end -= 1;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = x + no[i][0];
				int ny = y + no[i][1];
				if ( array_cell(array,nx,ny) != OPEN )
					continue;
				array_cell(array,nx,ny) = cells_to_end;
				cells_to_end -= 1;
				x += no[i][0] * 2;
				y += no[i][1] * 2;
				break;
			}
		}
		
		// delete his two code lines to get a straight maze generation
		array_draw ( array, size_x, size_y, panMaze->bmap );
		wait(1);
	}
	array_draw ( array, size_x, size_y, panMaze->bmap );
}


void main ()
{
	video_mode = 12;
	fps_max = 20;
	random_seed ( 0 );
	wait(3);
	panMaze = pan_create ( "flags=SHOW;", 1 );
	panMaze->bmap = bmap_createblack ( screen_size.x, screen_size.y, 24 );
	
	var **maze = array_create ( MAZEX, MAZEY );
	maze_depth_first ( maze, MAZEX, MAZEY, ENDX, ENDY );
	
	while ( !key_esc )
		wait(1);
	
	bmap_remove ( panMaze->bmap );
	pan_remove ( panMaze );
	array_remove ( maze, MAZEX );
	
	sys_exit ( NULL );
}


Enjoy it!
Posted By: Superku

Re: Maze generation algorithm - 09/29/13 01:19

The maze generation looks pretty cute, I like it! Could be made into a simple screen saver.
Posted By: xbox

Re: Maze generation algorithm - 09/29/13 05:13

This works amazingly! The only thing I have a problem with, is where is the size of the maze defined? I would like to make a maze like 10 by 10 cells or 20 by 20 cells instead of the full screen.

Also, I get an error after every iteration because I have A8 Free and render target is not a valid feature. frown
Posted By: Kartoffel

Re: Maze generation algorithm - 09/29/13 07:36

@^:

#define MAZEX 81 // odd!
#define MAZEY 61 // odd!
Posted By: 3run

Re: Maze generation algorithm - 09/29/13 07:45

txesmi@ it works flawlessly man, thank you very much! I'll try to create a 3D level with it.


Greets
Posted By: txesmi

Re: Maze generation algorithm - 09/29/13 08:50



I'll write more algorithms today. Sunday entertainment wink

Salud!
Posted By: 3run

Re: Maze generation algorithm - 09/29/13 09:07

I've got it to work already grin Thank you man, you've made my weekend!

Download link

But I yet can't find a way, to define the end of the maze :<
Plus, I'm thinking about placing some models, randomly on the maze to scare player grin


Greets
Posted By: txesmi

Re: Maze generation algorithm - 09/29/13 09:12

@3run
Check for the highest value into the array and make it the starting point. That is the reason of 'cells_to_end' variable. Note that only odd cells can be a deadend cell wink

Posted By: 3run

Re: Maze generation algorithm - 09/29/13 09:29

Well, that sounds a little bit more difficult for me, I'll try to get more into details of the algorithm, if I can grin
Posted By: txesmi

Re: Maze generation algorithm - 09/29/13 09:59

I mean after maze generation.

Code:
wait_for ( maze_depth_first );
int start_x = 0;
int start_y = 0;
int x = 1;
for ( ; x<MAZEX; x+=2 )
{
	int y = 1;
	for ( ; y<MAZEY; y+=2 )
	{
		if ( array_cell(maze,x,y) > array_cell(maze,start_x,start_y) )
		{
			start_x = x;
			start_y = y;
		}
	}
}
array_cell(maze,start_x,start_y) = START;
array_draw ( maze, MAZEX, MAZEY, panMaze->bmap );
Posted By: Kartoffel

Re: Maze generation algorithm - 09/29/13 10:01

@3run: if I have to guess: on every maze-step the depth value gets increased by 1. which means that the position with the maximum depth has the highest distance to the generation start-point.
Posted By: 3run

Re: Maze generation algorithm - 09/29/13 10:25

txesmi@ thank you very much man, I've got a fully functional simple maze-game grin
Kartoffel@ I've got the theory, but I'm always messed up on practice.. :<

Link:
Download
Screen:


Thank you man! laugh
Posted By: Kartoffel

Re: Maze generation algorithm - 09/29/13 10:51

the same as above, just in 1st person tongue

edit: just noticed that the player's start position isn't calculated right...
Posted By: 3run

Re: Maze generation algorithm - 09/29/13 11:06

I've got trapped :<



Edit: just noticed, that you've edited your post grin btw, nice graphics man!
Posted By: xbox

Re: Maze generation algorithm - 09/29/13 18:52

I've changed to start position so it's always cell 1,1 but how can I change the finish position so its always 9,10 (a 10x10 maze)?
Posted By: 3run

Re: Maze generation algorithm - 09/29/13 18:53

xbox@ it's always the last cell in the maze (finish).
Posted By: xbox

Re: Maze generation algorithm - 09/29/13 19:47

got it, thanks!
Posted By: txesmi

Re: Maze generation algorithm - 09/29/13 20:59

Hi,
I modified the algorithm to get halls in the path.


It does not fill all the square and the code is pretty messy but here it goes

Code:
#include <acknex.h>
#include <default.c>

#define PRAGMA_POINTER

//#define WATCH_GENERATION

PANEL *panMaze;

int make_odd ( int i )
{
	return i - ( i % 2 ) + 1;
}

#define array_cell(array,x,y) *(*(array+x)+y)

var **array_create ( int size_x, int size_y )
{
	var **array = (var**)sys_malloc ( sizeof(var*) * size_x );
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c++ )
		*c = (var*)sys_malloc ( sizeof(var) * size_y );
	
	return array;
}

void array_remove ( var **array, int size_x )
{
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c++ )
	{
		var *r = *c;
		sys_free ( r );
	}
	sys_free ( array );
}

#define START      -1
#define UNVISITED   0
#define WALL        1
#define END         2
#define OPEN        3

void array_draw ( var **maze, int size_x, int size_y, BMAP *bmp )
{
	var cell_x = bmap_width ( bmp ) / size_x;
	var cell_y = bmap_height ( bmp ) / size_y;
	
	bmap_rendertarget ( bmp, 0, 0 );
	draw_quad ( NULL, vector(0,0,0), NULL, vector(bmap_width(bmp),bmap_height(bmp),0), NULL, vector(1,1,1), 100, 0 );
	int c = 0;
	for ( ; c<size_x; c+=1 )
	{
		int r = 0;
		for ( ; r<size_y; r+=1 )
		{
			switch ( array_cell(maze,c,r) )
			{
				case UNVISITED:
				case WALL:      
					break;
				case END:    draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_RED, 100, 0 );    break;
				case OPEN:   draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );   break;
				case START:  draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREEN, 100, 0 );  break;
				default:     draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 );  break;
			}
		}
	}
	bmap_rendertarget ( NULL, 0, 0 );
}

void array_draw_update ( var **maze, int size_x, int size_y, int pos_x, int pos_y, BMAP *bmp )
{
	var cell_x = bmap_width ( bmp ) / size_x;
	var cell_y = bmap_height ( bmp ) / size_y;
	
	bmap_rendertarget ( bmp, 0, 1 );
	int c = pos_x - 1;
	for ( ; c<pos_x+2; c+=1 )
	{
		int r = pos_y - 1;
		for ( ; r<pos_y+2; r+=1 )
		{
			switch ( array_cell(maze,c,r) )
			{
				case UNVISITED:
				case WALL:      
					break;
				case END:    draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_RED, 100, 0 );    break;
				case OPEN:   draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );   break;
				case START:  draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREEN, 100, 0 );  break;
				default:     draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 );  break;
			}
		}
	}
	bmap_rendertarget ( NULL, 0, 0 );
}

var no[4][2] =
{
	-1, 0,
	0, -1,
	1, 0,
	0, 1
};

var ns[8][2] =
{
	-1, 0,
	-1, -1,
	0, -1,
	1, -1,
	1, 0,
	1, 1,
	0, 1,
	-1, 1
};

int maze_step_calls = 0;

void maze_hall ( var **array, int size_x, int size_y, int x, int y, int cells_to_end )
{
	if ( array_cell(array,x,y) == END )
		return;
	int noi = integer ( random(4) );
	int roll_side = sign ( random(1)-0.5 );
	int i = 0;
	for ( ; i<4; i+=1 )
	{
		int nx = x + no[noi][0] * 2;
		int ny = y + no[noi][1] * 2;
		int noi2 = cycle ( noi + roll_side, 0, 4 );
		int nx2 = x + no[noi2][0] * 2;
		int ny2 = y + no[noi2][1] * 2;
		int nx3 = x + ( no[noi][0] * 2 ) + ( no[noi2][0] * 2 );
		int ny3 = y + ( no[noi][1] * 2 ) + ( no[noi2][1] * 2 );
		if ( ( nx3 < 0 ) || ( nx3 >= size_x ) || ( ny3 < 0 ) || ( ny3 >= size_y ) )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		if ( ( array_cell(array,nx,ny) > UNVISITED ) || ( array_cell(array,nx2,ny2) > UNVISITED ) || ( array_cell(array,nx3,ny3) > UNVISITED ) )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		int nx4 = x + ( no[noi][0] * 3 ) + ( no[noi2][0] * 3 );
		int ny4 = y + ( no[noi][1] * 3 ) + ( no[noi2][1] * 3 );
		int step_x = sign ( nx3 - x );
		int step_y = sign ( ny3 - y );
		int pos_x = x;
		for ( ; pos_x!=nx4; pos_x+=step_x )
		{
			int pos_y = y;
			for ( ; pos_y!=ny4; pos_y+=step_y )
			{
				if ( array_cell(array,pos_x,pos_y) < END )
				{
					array_cell(array,pos_x,pos_y) = cells_to_end;
					int i = 0;
					for ( ; i<4; i+=1 )
					{
						int nx5 = pos_x+no[i][0]*2;
						int ny5 = pos_y+no[i][1]*2;
						if ( ( nx5 < 0 ) || ( nx5 >= size_x ) || ( ny5 < 0 ) || ( ny5 >= size_y ) )
							continue;
						if ( abs ( array_cell(array,nx5,ny5) - cells_to_end ) < 3 )
						{
							nx5 = pos_x+no[i][0];
							ny5 = pos_y+no[i][1];
							array_cell(array,nx5,ny5) = cells_to_end;
						}
					}
				}
				#ifdef WATCH_GENERATION
					array_draw_update ( array, size_x, size_y, pos_x, pos_y, panMaze->bmap );
				#endif
			}
		}
		#ifdef WATCH_GENERATION
			wait(1);
		#endif
		
		int hall = integer ( random(6) );
		switch ( hall )
		{
			case 0:  maze_hall ( array, size_x, size_y, nx, ny, cells_to_end );    break;
			case 1:  maze_hall ( array, size_x, size_y, nx2, ny2, cells_to_end );  break;
			case 2:  maze_hall ( array, size_x, size_y, nx3, ny3, cells_to_end );  break;
		}
		
		break;
	}

}

void maze_step ( var **array, int size_x, int size_y, int *x, int *y, int *cells_to_end )
{
	int noi = integer ( random(4) );
	int roll_side = sign ( random(1)-0.5 );
	int i = 0;
	for ( ; i<4; i+=1 )
	{
		int nx = *x + no[noi][0] * 2;
		int ny = *y + no[noi][1] * 2;
		if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		if ( array_cell(array,nx,ny) > UNVISITED )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		int nx2 = *x + no[noi][0];
		int ny2 = *y + no[noi][1];
		array_cell(array,nx2,ny2) = OPEN;
		array_cell(array,nx,ny) = OPEN;
		*x = nx;
		*y = ny;
		*cells_to_end += 2;

		int ii = 0;
		for ( ; ii<4; ii+=1 )
		{
			int nx5 = nx+no[ii][0]*2;
			int ny5 = ny+no[ii][1]*2;
			if ( ( nx5 < 0 ) || ( nx5 >= size_x ) || ( ny5 < 0 ) || ( ny5 >= size_y ) )
				continue;
			if ( abs ( array_cell(array,nx5,ny5) - *cells_to_end ) < 3 )
			{
				int nx6 = nx+no[ii][0];
				int ny6 = ny+no[ii][1];
				array_cell(array,nx6,ny6) = *cells_to_end;
			}
		}
		
		#ifdef WATCH_GENERATION
			array_draw_update ( array, size_x, size_y, *x-no[noi][0] * 2, *y-no[noi][1] * 2, panMaze->bmap );
			wait(1);
		#endif
		int hall = integer ( random(1.2) );
		if ( hall == 0 )
		{
			maze_step_calls += 1;
			maze_hall ( array, size_x, size_y, *x-no[noi][0] * 2, *y-no[noi][1] * 2, *cells_to_end );
		}
		maze_step_calls += 1;
		maze_step ( array, size_x, size_y, x, y, cells_to_end );
		break;
	}

	if ( i == 4 )
	{
		if ( array_cell(array,*x,*y) != END )
		{
			array_cell(array,*x,*y) = *cells_to_end;
			*cells_to_end -= 1;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = *x + no[i][0];
				int ny = *y + no[i][1];
				if ( array_cell(array,nx,ny) != OPEN )
					continue;
				array_cell(array,nx,ny) = *cells_to_end;
				*cells_to_end -= 1;
				*x += no[i][0] * 2;
				*y += no[i][1] * 2;
				#ifdef WATCH_GENERATION
					array_draw_update ( array, size_x, size_y, *x-no[i][0] * 2, *y-no[i][1] * 2, panMaze->bmap );
					wait(1);
				#endif
				maze_step_calls += 1;
				maze_step ( array, size_x, size_y, x, y, cells_to_end );
				break;
			}
		}
	}
}

void maze_depth_first ( var **array, int size_x, int size_y, int end_x, int end_y )
{
	array_draw ( array, size_x, size_y, panMaze->bmap );
	
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c+=2 )
	{
		var *r = *c;
		var *rl = r + size_y;
		for ( ; r<rl; r++ )
		{
			*r = WALL;
		}
	}
	
	var **c = array + 1;
	var **cl = c + size_x - 1;
	for ( ; c<cl; c+=2 )
	{
		var *r = *c;
		var *rl = r + size_y;
		for ( ; r<rl; r+=2 )
		{
			*r = WALL;
		}
	}
	
	int *x = sys_malloc ( sizeof(int) );
	int *y = sys_malloc ( sizeof(int) );
	int *cells_to_end = sys_malloc ( sizeof(int) );
	*x = end_x;
	*y = end_y;
	*cells_to_end = OPEN;
	array_cell(array,*x,*y) = END;
	
	maze_step_calls += 1;
	maze_step ( array, size_x, size_y, x, y, cells_to_end );
	
	#ifdef WATCH_GENERATION
		while ( proc_status ( maze_step ) > 0 )
			wait(1);
	#endif
	
	sys_free ( x );
	sys_free ( y );
	sys_free ( cells_to_end );
	
	// Clean up
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			int n = 0;
			int cell_depth = 0;
			int i = 0;
			for ( ; i<8; i+=1 )
			{
				int nx = pos_x + ns[i][0];
				int ny = pos_y + ns[i][1];
				if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
					continue;
				if ( array_cell(array,nx,ny) > WALL )
				{
					n += 1;
					cell_depth += array_cell(array,nx,ny);
				}
			}
			if ( n == 8 )
				array_cell(array,pos_x,pos_y) = cell_depth / 8;
		}
	}
	
	// Look for start point
	int start_x = 0;
	int start_y = 0;
	int pos_x = 1;
	for ( ; pos_x<size_x; pos_x+=2 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y; pos_y+=2 )
		{
			if ( array_cell(array,pos_x,pos_y) > array_cell(array,start_x,start_y) )
			{
				start_x = pos_x;
				start_y = pos_y;
			}
		}
	}
	array_cell(array,start_x,start_y) = START;
}


void main ()
{
//	video_mode = 8;
	video_set ( 512, 512, 32, 2 );
	random_seed ( 0 );
	fps_max = 30;
	wait(3);
	panMaze = pan_create ( "flags=SHOW;", 1 );
	panMaze->bmap = bmap_createblack ( 512, 512, 24 );
	
	int maze_x = integer ( make_odd ( bmap_width(panMaze->bmap) / 15 ) );
	int maze_y = integer ( make_odd ( bmap_height(panMaze->bmap) / 15 ) );
	
	var **maze = array_create ( maze_x, maze_y );
	maze_depth_first ( maze, maze_x, maze_y, make_odd ( maze_x / 2 ), make_odd ( maze_y / 2 ) );
	#ifdef WATCH_GENERATION
		wait_for ( maze_depth_first );
	#endif
	
	array_draw ( maze, maze_x, maze_y, panMaze->bmap );
	
	var keySpace = 0;
	var clock = total_ticks + 1;
	while ( !key_esc )
	{
		if ( key_space )
			keySpace = 1;
		else if ( keySpace ) //|| ( total_ticks > clock ) )
		{
			clock = total_ticks + 1;
			keySpace = 0;
			array_remove ( maze, maze_x );
			maze = array_create ( maze_x, maze_y );
			maze_depth_first ( maze, maze_x, maze_y, make_odd ( maze_x / 2 ), make_odd ( maze_y / 2 ) );
			#ifdef WATCH_GENERATION
				wait_for ( maze_depth_first );
			#endif
			
			array_draw ( maze, maze_x, maze_y, panMaze->bmap );
		}
		wait(1);
	}
	
	bmap_remove ( panMaze->bmap );
	pan_remove ( panMaze );
	array_remove ( maze, maze_x );
	
	sys_exit ( NULL );
}


Posted By: 3run

Re: Maze generation algorithm - 09/29/13 23:01

txesmi@ man, this could be used to create some kind of a Wolfenstein3D game, but with random levels laugh
I'll give it a try tomorrow, the screen looks promising, I wish I could write such stuff myself grin
Thank you very much!


Best greets
Posted By: txesmi

Re: Maze generation algorithm - 09/30/13 12:50

glad to help grin

I went a bit deeper with this: Halls, doors and treasures are indentified.



Code:
#include <acknex.h>
#include <default.c>

#define PRAGMA_POINTER

//#define WATCH_GENERATION

PANEL *panMaze;

int make_odd ( int i )
{
	return i - ( i % 2 ) + 1;
}

#define array_cell(array,x,y) *(*(array+x)+y)

var **array_create ( int size_x, int size_y )
{
	var **array = (var**)sys_malloc ( sizeof(var*) * size_x );
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c++ )
		*c = (var*)sys_malloc ( sizeof(var) * size_y );
	
	return array;
}

void array_remove ( var **array, int size_x )
{
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c++ )
	{
		var *r = *c;
		sys_free ( r );
	}
	sys_free ( array );
}

#define UNVISITED   0
#define WALL        1
#define START       2
#define END         3
#define HALL        4
#define HALL2       5
#define DOOR        6
#define BONUS       7

#define OPEN        100

void array_draw ( var **maze, int size_x, int size_y, BMAP *bmp )
{
	var cell_x = bmap_width ( bmp ) / size_x;
	var cell_y = bmap_height ( bmp ) / size_y;
	draw_textmode ( "Arial", 0, cell_y, 100 );
	
	bmap_rendertarget ( bmp, 0, 0 );
	draw_quad ( NULL, vector(0,0,0), NULL, vector(bmap_width(bmp),bmap_height(bmp),0), NULL, vector(1,1,1), 100, 0 );
	int c = 0;
	for ( ; c<size_x; c+=1 )
	{
		int r = 0;
		for ( ; r<size_y; r+=1 )
		{
			switch ( array_cell(maze,c,r) )
			{
				case UNVISITED:
				case WALL:      
					break;
				case END:    draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_RED, 100, 0 );             break;
				case HALL:   draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, vector(240,240,240), 100, 0 );   break;   
				case HALL2:  draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 );           break;    
				case OPEN:   draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 );           break;
				case START:  draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREEN, 100, 0 );           break;
				case DOOR:   draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );
				             draw_text ( "d", (size_x/8)+c*cell_x, r*cell_y, nullvector );                                                                break;
				case BONUS:  draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );
				             draw_text ( "t", (size_x/8)+c*cell_x, r*cell_y, nullvector );                                                                break;
				default:     draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );            break;
			}
		}
	}
	bmap_rendertarget ( NULL, 0, 0 );
}

void array_draw_update ( var **maze, int size_x, int size_y, int pos_x, int pos_y, BMAP *bmp )
{
	var cell_x = bmap_width ( bmp ) / size_x;
	var cell_y = bmap_height ( bmp ) / size_y;
	
	bmap_rendertarget ( bmp, 0, 1 );
	int c = pos_x - 1;
	for ( ; c<pos_x+2; c+=1 )
	{
		int r = pos_y - 1;
		for ( ; r<pos_y+2; r+=1 )
		{
			switch ( array_cell(maze,c,r) )
			{
				case UNVISITED:
				case WALL:      
					break;
				case END:    draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_RED, 100, 0 );    break;
				case HALL:      
				case OPEN:   draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );   break;
				case START:  draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREEN, 100, 0 );  break;
				default:     draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 );  break;
			}
		}
	}
	bmap_rendertarget ( NULL, 0, 0 );
}

var no[4][2] =
{
	-1, 0,
	0, -1,
	1, 0,
	0, 1
};

var ns[8][2] =
{
	-1, 0,
	-1, -1,
	0, -1,
	1, -1,
	1, 0,
	1, 1,
	0, 1,
	-1, 1
};

int maze_step_calls = 0;

void maze_hall ( var **array, int size_x, int size_y, int x, int y, int cells_to_end )
{
	if ( array_cell(array,x,y) == END )
		return;
	int noi = integer ( random(4) );
	int roll_side = sign ( random(1)-0.5 );
	int i = 0;
	for ( ; i<4; i+=1 )
	{
		int nx = x + no[noi][0] * 2;
		int ny = y + no[noi][1] * 2;
		int noi2 = cycle ( noi + roll_side, 0, 4 );
		int nx2 = x + no[noi2][0] * 2;
		int ny2 = y + no[noi2][1] * 2;
		int nx3 = x + ( no[noi][0] * 2 ) + ( no[noi2][0] * 2 );
		int ny3 = y + ( no[noi][1] * 2 ) + ( no[noi2][1] * 2 );
		if ( ( nx3 < 0 ) || ( nx3 >= size_x ) || ( ny3 < 0 ) || ( ny3 >= size_y ) )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		if ( ( array_cell(array,nx,ny) > UNVISITED ) || ( array_cell(array,nx2,ny2) > UNVISITED ) || ( array_cell(array,nx3,ny3) > UNVISITED ) )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		int nx4 = x + ( no[noi][0] * 3 ) + ( no[noi2][0] * 3 );
		int ny4 = y + ( no[noi][1] * 3 ) + ( no[noi2][1] * 3 );
		int step_x = sign ( nx3 - x );
		int step_y = sign ( ny3 - y );
		int pos_x = x;
		for ( ; pos_x!=nx4; pos_x+=step_x )
		{
			int pos_y = y;
			for ( ; pos_y!=ny4; pos_y+=step_y )
			{
				if ( array_cell(array,pos_x,pos_y) < END )
				{
					array_cell(array,pos_x,pos_y) = cells_to_end;
					int i = 0;
					for ( ; i<4; i+=1 )
					{
						int nx5 = pos_x+no[i][0]*2;
						int ny5 = pos_y+no[i][1]*2;
						if ( ( nx5 < 0 ) || ( nx5 >= size_x ) || ( ny5 < 0 ) || ( ny5 >= size_y ) )
							continue;
						if ( abs ( array_cell(array,nx5,ny5) - cells_to_end ) < 3 )
						{
							nx5 = pos_x+no[i][0];
							ny5 = pos_y+no[i][1];
							array_cell(array,nx5,ny5) = cells_to_end;
						}
					}
				}
				#ifdef WATCH_GENERATION
					array_draw_update ( array, size_x, size_y, pos_x, pos_y, panMaze->bmap );
				#endif
			}
		}
		#ifdef WATCH_GENERATION
			wait(1);
		#endif
		
		int hall = integer ( random(6) );
		switch ( hall )
		{
			case 0:  maze_hall ( array, size_x, size_y, nx, ny, cells_to_end );    break;
			case 1:  maze_hall ( array, size_x, size_y, nx2, ny2, cells_to_end );  break;
			case 2:  maze_hall ( array, size_x, size_y, nx3, ny3, cells_to_end );  break;
		}
		
		break;
	}

}

void maze_step ( var **array, int size_x, int size_y, int *x, int *y, int *cells_to_end )
{
	int noi = integer ( random(4) );
	int roll_side = sign ( random(1)-0.5 );
	int i = 0;
	for ( ; i<4; i+=1 )
	{
		int nx = *x + no[noi][0] * 2;
		int ny = *y + no[noi][1] * 2;
		if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		if ( array_cell(array,nx,ny) > UNVISITED )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		int nx2 = *x + no[noi][0];
		int ny2 = *y + no[noi][1];
		array_cell(array,nx2,ny2) = OPEN;
		array_cell(array,nx,ny) = OPEN;
		*x = nx;
		*y = ny;
		*cells_to_end += 2;

		int ii = 0;
		for ( ; ii<4; ii+=1 )
		{
			int nx5 = nx+no[ii][0]*2;
			int ny5 = ny+no[ii][1]*2;
			if ( ( nx5 < 0 ) || ( nx5 >= size_x ) || ( ny5 < 0 ) || ( ny5 >= size_y ) )
				continue;
			if ( abs ( array_cell(array,nx5,ny5) - *cells_to_end ) < 3 )
			{
				int nx6 = nx+no[ii][0];
				int ny6 = ny+no[ii][1];
				array_cell(array,nx6,ny6) = *cells_to_end;
			}
		}
		
		#ifdef WATCH_GENERATION
			array_draw_update ( array, size_x, size_y, *x-no[noi][0] * 2, *y-no[noi][1] * 2, panMaze->bmap );
			wait(1);
		#endif
		int hall = integer ( random(1.2) );
		if ( hall == 0 )
		{
			maze_step_calls += 1;
			maze_hall ( array, size_x, size_y, *x-no[noi][0] * 2, *y-no[noi][1] * 2, *cells_to_end );
		}
		maze_step_calls += 1;
		maze_step ( array, size_x, size_y, x, y, cells_to_end );
		break;
	}

	if ( i == 4 )
	{
		if ( array_cell(array,*x,*y) != END )
		{
			array_cell(array,*x,*y) = *cells_to_end;
			*cells_to_end -= 1;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = *x + no[i][0];
				int ny = *y + no[i][1];
				if ( array_cell(array,nx,ny) != OPEN )
					continue;
				array_cell(array,nx,ny) = *cells_to_end;
				*cells_to_end -= 1;
				*x += no[i][0] * 2;
				*y += no[i][1] * 2;
				#ifdef WATCH_GENERATION
					array_draw_update ( array, size_x, size_y, *x-no[i][0] * 2, *y-no[i][1] * 2, panMaze->bmap );
					wait(1);
				#endif
				maze_step_calls += 1;
				maze_step ( array, size_x, size_y, x, y, cells_to_end );
				break;
			}
		}
	}
}

void maze_depth_first ( var **array, int size_x, int size_y, int end_x, int end_y )
{
	array_draw ( array, size_x, size_y, panMaze->bmap );
	
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c+=2 )
	{
		var *r = *c;
		var *rl = r + size_y;
		for ( ; r<rl; r++ )
		{
			*r = WALL;
		}
	}
	
	var **c = array + 1;
	var **cl = c + size_x - 1;
	for ( ; c<cl; c+=2 )
	{
		var *r = *c;
		var *rl = r + size_y;
		for ( ; r<rl; r+=2 )
		{
			*r = WALL;
		}
	}
	
	int *x = sys_malloc ( sizeof(int) );
	int *y = sys_malloc ( sizeof(int) );
	int *cells_to_end = sys_malloc ( sizeof(int) );
	*x = end_x;
	*y = end_y;
	*cells_to_end = OPEN;
	array_cell(array,*x,*y) = END;
	
	maze_step_calls += 1;
	maze_step ( array, size_x, size_y, x, y, cells_to_end );
	
	#ifdef WATCH_GENERATION
		while ( proc_status ( maze_step ) > 0 )
			wait(1);
	#endif
	
	sys_free ( x );
	sys_free ( y );
	sys_free ( cells_to_end );
	
	// Clean up
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			int n = 0;
			int cell_depth = 0;
			int i = 0;
			for ( ; i<8; i+=1 )
			{
				int nx = pos_x + ns[i][0];
				int ny = pos_y + ns[i][1];
				if ( array_cell(array,nx,ny) > WALL )
				{
					n += 1;
					cell_depth += array_cell(array,nx,ny);
				}
			}
			if ( n == 8 )
				array_cell(array,pos_x,pos_y) = cell_depth / 8;
		}
	}
	
	// Look for start point
	int start_x = 0;
	int start_y = 0;
	int pos_x = 1;
	for ( ; pos_x<size_x; pos_x+=2 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y; pos_y+=2 )
		{
			if ( array_cell(array,pos_x,pos_y) > array_cell(array,start_x,start_y) )
			{
				start_x = pos_x;
				start_y = pos_y;
			}
		}
	}
	array_cell(array,start_x,start_y) = START;
	
	// Isolate halls
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int n = 0;
			int i = 0;
			for ( ; i<8; i+=1 )
			{
				int nx = pos_x + ns[i][0];
				int ny = pos_y + ns[i][1];
				if ( ( array_cell(array,nx,ny) > WALL ) || ( array_cell(array,pos_x,pos_y) == START ) || ( array_cell(array,pos_x,pos_y) == END ) )
					n += 1;
			}
			if ( n == 8 )
				array_cell(array,pos_x,pos_y) = HALL;
		}
	}
	
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int i = 0;
			for ( ; i<8; i+=1 )
			{
				int nx = pos_x + ns[i][0];
				int ny = pos_y + ns[i][1];
				if ( array_cell(array,nx,ny) != HALL )
					continue;
				array_cell(array,pos_x,pos_y) = HALL2;
				break;
			}
		}
	}
	
	// Look for doors
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = pos_x + no[i][0];
				int ny = pos_y + no[i][1];
				if ( array_cell(array,nx,ny) != HALL2 )
					continue;
				array_cell(array,pos_x,pos_y) = DOOR;
				break;
			}
		}
	}
	
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int n = 0;
			int cheapest_x = 0;
			int cheapest_y = 0;
			var weight = 100000;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = pos_x + no[i][0];
				int ny = pos_y + no[i][1];
				if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
					continue;
				if ( ( array_cell(array,nx,ny) >= OPEN ) || ( array_cell(array,nx,ny) == BONUS ) )
				{
					n += 1;
					if ( array_cell(array,nx,ny) < weight )
					{
						cheapest_x = nx;
						cheapest_y = ny;
						weight = array_cell(array,nx,ny);
					}
				}
			}
			if ( n >= 3 )
				array_cell(array,cheapest_x,cheapest_y) = DOOR;
		}
	}
	
	// Look for bonus
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int n = 0;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = pos_x + no[i][0];
				int ny = pos_y + no[i][1];
				if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
					continue;
				if ( ( array_cell(array,nx,ny) >= OPEN ) || ( array_cell(array,nx,ny) == DOOR ) || ( array_cell(array,nx,ny) == BONUS ) || ( array_cell(array,nx,ny) == END ) || ( array_cell(array,nx,ny) == START ) )
					n += 1;
			}
			if ( n == 1 )
				array_cell(array,pos_x,pos_y) = BONUS;
		}
	}
	
	
		
}

void main ()
{
//	video_mode = 8;
	video_set ( 700, 700, 32, 2 );
	random_seed ( 0 );
	fps_max = 30;
	wait(3);
	panMaze = pan_create ( "flags=SHOW;", 1 );
	panMaze->bmap = bmap_createblack ( 700, 700, 24 );
	
	int maze_x = integer ( make_odd ( bmap_width(panMaze->bmap) / 15 ) );
	int maze_y = integer ( make_odd ( bmap_height(panMaze->bmap) / 15 ) );
	
	var **maze = array_create ( maze_x, maze_y );
	maze_depth_first ( maze, maze_x, maze_y, make_odd ( maze_x / 2 ), make_odd ( maze_y / 2 ) );
	#ifdef WATCH_GENERATION
		wait_for ( maze_depth_first );
	#endif
	
	array_draw ( maze, maze_x, maze_y, panMaze->bmap );
	
	var keySpace = 0;
	var clock = total_ticks + 8;
	while ( !key_esc )
	{
		if ( key_space )
			keySpace = 1;
		else if ( keySpace ) //|| ( total_ticks > clock ) )
		{
			clock = total_ticks + 8;
			keySpace = 0;
			array_remove ( maze, maze_x );
			maze = array_create ( maze_x, maze_y );
			maze_depth_first ( maze, maze_x, maze_y, make_odd ( maze_x / 2 ), make_odd ( maze_y / 2 ) );
			#ifdef WATCH_GENERATION
				wait_for ( maze_depth_first );
			#endif
			
			array_draw ( maze, maze_x, maze_y, panMaze->bmap );
		}
		wait(1);
	}
	
	bmap_remove ( panMaze->bmap );
	pan_remove ( panMaze );
	array_remove ( maze, maze_x );
	
	sys_exit ( NULL );
}


Salud!
Posted By: Kartoffel

Re: Maze generation algorithm - 09/30/13 14:08

wow, great
( I'll implement it into my 1st person maze for practise laugh )
Posted By: 3run

Re: Maze generation algorithm - 09/30/13 15:08

txesmi@ damn! it's so freaking awesome dude! I'll create fps shooter with it (or horror), as I've said before! laugh
Is there a way to identify a closed door with a key, which is available for it? So the key will be placed out of the closed room.



Greets
Posted By: Kartoffel

Re: Maze generation algorithm - 09/30/13 15:23

@3run some kind of flood fill algorithm should be enough to place keys wink
Posted By: txesmi

Re: Maze generation algorithm - 09/30/13 16:05

@3run
I can imagine how to order the doors and treasures from start to end, so there is a chance for that gameplay.

For now I placed light points



Code:
#include <acknex.h>
#include <default.c>

#define PRAGMA_POINTER

//#define WATCH_GENERATION

PANEL *panMaze;

int make_odd ( int i )
{
	return i - ( i % 2 ) + 1;
}

#define array_cell(array,x,y) *(*(array+x)+y)

var **array_create ( int size_x, int size_y )
{
	var **array = (var**)sys_malloc ( sizeof(var*) * size_x );
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c++ )
		*c = (var*)sys_malloc ( sizeof(var) * size_y );
	
	return array;
}

void array_remove ( var **array, int size_x )
{
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c++ )
	{
		var *r = *c;
		sys_free ( r );
	}
	sys_free ( array );
}

#define UNVISITED       0
#define WALL            1
#define START           2
#define END             3
#define HALLCENTER      4
#define HALLBORDER      5
#define DOOR            6
#define BONUS           7
#define LIGHTWALL       8
#define LIGHTHALL       9
#define LIGHTCORRIDOR   10

#define OPEN        100

void array_draw ( var **maze, int size_x, int size_y, BMAP *bmp )
{
	var cell_x = bmap_width ( bmp ) / size_x;
	var cell_y = bmap_height ( bmp ) / size_y;
	draw_textmode ( "Arial", 0, cell_y, 100 );
	
	bmap_rendertarget ( bmp, 0, 0 );
	draw_quad ( NULL, vector(0,0,0), NULL, vector(bmap_width(bmp),bmap_height(bmp),0), NULL, vector(1,1,1), 100, 0 );
	int c = 0;
	for ( ; c<size_x; c+=1 )
	{
		int r = 0;
		for ( ; r<size_y; r+=1 )
		{
			switch ( array_cell(maze,c,r) )
			{
				case UNVISITED:
				case WALL:      
					break;
				case END:            draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_RED, 100, 0 );             break;
				case HALLCENTER:     draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, vector(240,240,240), 100, 0 );   break;   
				case HALLBORDER:     draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 );           break;    
				case OPEN:           draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_BLUE, 100, 0 );            break;
				case START:          draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREEN, 100, 0 );           break;
				case DOOR:           draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );
				                     draw_text ( "D", (size_x/8)+c*cell_x, r*cell_y, nullvector );                                                                break;
				case BONUS:          draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );
				                     draw_text ( "T", (size_x/8)+c*cell_x, r*cell_y, nullvector );                                                                break;
				case LIGHTWALL:      draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 );   
				                     draw_text ( "L", (size_x/8)+c*cell_x, r*cell_y, nullvector );                                                                break;
				case LIGHTHALL:      draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, vector(240,240,240), 100, 0 );   
				                     draw_text ( "L", (size_x/8)+c*cell_x, r*cell_y, nullvector );                                                                break;
				case LIGHTCORRIDOR:  draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );   
				                     draw_text ( "L", (size_x/8)+c*cell_x, r*cell_y, nullvector );                                                                break;
				default:             draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );   break;
			}
		}
	}
	bmap_rendertarget ( NULL, 0, 0 );
}

void array_draw_update ( var **maze, int size_x, int size_y, int pos_x, int pos_y, BMAP *bmp )
{
	var cell_x = bmap_width ( bmp ) / size_x;
	var cell_y = bmap_height ( bmp ) / size_y;
	
	bmap_rendertarget ( bmp, 0, 1 );
	int c = pos_x - 1;
	for ( ; c<pos_x+2; c+=1 )
	{
		int r = pos_y - 1;
		for ( ; r<pos_y+2; r+=1 )
		{
			switch ( array_cell(maze,c,r) )
			{
				case UNVISITED:
				case WALL:      
					break;
				case END:    draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_RED, 100, 0 );    break;
				case HALLCENTER:      
				case OPEN:   draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREY, 100, 0 );   break;
				case START:  draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_GREEN, 100, 0 );  break;
				default:     draw_quad ( NULL, vector(c*cell_x, r*cell_y, 0), NULL, vector(cell_x+1, cell_y+1, 0), NULL, COLOR_WHITE, 100, 0 );  break;
			}
		}
	}
	bmap_rendertarget ( NULL, 0, 0 );
}

var no[4][2] =
{
	-1, 0,
	0, -1,
	1, 0,
	0, 1
};

var ns[8][2] =
{
	-1, 0,
	-1, -1,
	0, -1,
	1, -1,
	1, 0,
	1, 1,
	0, 1,
	-1, 1
};

int maze_step_calls = 0;

void maze_hall ( var **array, int size_x, int size_y, int x, int y, int cells_to_end )
{
	if ( array_cell(array,x,y) == END )
		return;
	int noi = integer ( random(4) );
	int roll_side = sign ( random(1)-0.5 );
	int i = 0;
	for ( ; i<4; i+=1 )
	{
		int nx = x + no[noi][0] * 2;
		int ny = y + no[noi][1] * 2;
		int noi2 = cycle ( noi + roll_side, 0, 4 );
		int nx2 = x + no[noi2][0] * 2;
		int ny2 = y + no[noi2][1] * 2;
		int nx3 = x + ( no[noi][0] * 2 ) + ( no[noi2][0] * 2 );
		int ny3 = y + ( no[noi][1] * 2 ) + ( no[noi2][1] * 2 );
		if ( ( nx3 < 0 ) || ( nx3 >= size_x ) || ( ny3 < 0 ) || ( ny3 >= size_y ) )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		if ( ( array_cell(array,nx,ny) > UNVISITED ) || ( array_cell(array,nx2,ny2) > UNVISITED ) || ( array_cell(array,nx3,ny3) > UNVISITED ) )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		int nx4 = x + ( no[noi][0] * 3 ) + ( no[noi2][0] * 3 );
		int ny4 = y + ( no[noi][1] * 3 ) + ( no[noi2][1] * 3 );
		int step_x = sign ( nx3 - x );
		int step_y = sign ( ny3 - y );
		int pos_x = x;
		for ( ; pos_x!=nx4; pos_x+=step_x )
		{
			int pos_y = y;
			for ( ; pos_y!=ny4; pos_y+=step_y )
			{
				if ( array_cell(array,pos_x,pos_y) < END )
				{
					array_cell(array,pos_x,pos_y) = cells_to_end;
					int i = 0;
					for ( ; i<4; i+=1 )
					{
						int nx5 = pos_x+no[i][0]*2;
						int ny5 = pos_y+no[i][1]*2;
						if ( ( nx5 < 0 ) || ( nx5 >= size_x ) || ( ny5 < 0 ) || ( ny5 >= size_y ) )
							continue;
						if ( abs ( array_cell(array,nx5,ny5) - cells_to_end ) < 3 )
						{
							nx5 = pos_x+no[i][0];
							ny5 = pos_y+no[i][1];
							array_cell(array,nx5,ny5) = cells_to_end;
						}
					}
				}
				#ifdef WATCH_GENERATION
					array_draw_update ( array, size_x, size_y, pos_x, pos_y, panMaze->bmap );
				#endif
			}
		}
		#ifdef WATCH_GENERATION
			wait(1);
		#endif
		
		int hall = integer ( random(6) );
		switch ( hall )
		{
			case 0:  maze_hall ( array, size_x, size_y, nx, ny, cells_to_end );    break;
			case 1:  maze_hall ( array, size_x, size_y, nx2, ny2, cells_to_end );  break;
			case 2:  maze_hall ( array, size_x, size_y, nx3, ny3, cells_to_end );  break;
		}
		
		break;
	}

}

void maze_step ( var **array, int size_x, int size_y, int *x, int *y, int *cells_to_end )
{
	int noi = integer ( random(4) );
	int roll_side = sign ( random(1)-0.5 );
	int i = 0;
	for ( ; i<4; i+=1 )
	{
		int nx = *x + no[noi][0] * 2;
		int ny = *y + no[noi][1] * 2;
		if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		if ( array_cell(array,nx,ny) > UNVISITED )
		{
			noi = cycle ( noi + roll_side, 0, 4 );
			continue;
		}
		int nx2 = *x + no[noi][0];
		int ny2 = *y + no[noi][1];
		array_cell(array,nx2,ny2) = OPEN;
		array_cell(array,nx,ny) = OPEN;
		*x = nx;
		*y = ny;
		*cells_to_end += 2;

		int ii = 0;
		for ( ; ii<4; ii+=1 )
		{
			int nx5 = nx+no[ii][0]*2;
			int ny5 = ny+no[ii][1]*2;
			if ( ( nx5 < 0 ) || ( nx5 >= size_x ) || ( ny5 < 0 ) || ( ny5 >= size_y ) )
				continue;
			if ( abs ( array_cell(array,nx5,ny5) - *cells_to_end ) < 3 )
			{
				int nx6 = nx+no[ii][0];
				int ny6 = ny+no[ii][1];
				array_cell(array,nx6,ny6) = *cells_to_end;
			}
		}
		
		#ifdef WATCH_GENERATION
			array_draw_update ( array, size_x, size_y, *x-no[noi][0] * 2, *y-no[noi][1] * 2, panMaze->bmap );
			wait(1);
		#endif
		int hall = integer ( random(1.2) );
		if ( hall == 0 )
		{
			maze_step_calls += 1;
			maze_hall ( array, size_x, size_y, *x-no[noi][0] * 2, *y-no[noi][1] * 2, *cells_to_end );
		}
		maze_step_calls += 1;
		maze_step ( array, size_x, size_y, x, y, cells_to_end );
		break;
	}

	if ( i == 4 )
	{
		if ( array_cell(array,*x,*y) != END )
		{
			array_cell(array,*x,*y) = *cells_to_end;
			*cells_to_end -= 1;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = *x + no[i][0];
				int ny = *y + no[i][1];
				if ( array_cell(array,nx,ny) != OPEN )
					continue;
				array_cell(array,nx,ny) = *cells_to_end;
				*cells_to_end -= 1;
				*x += no[i][0] * 2;
				*y += no[i][1] * 2;
				#ifdef WATCH_GENERATION
					array_draw_update ( array, size_x, size_y, *x-no[i][0] * 2, *y-no[i][1] * 2, panMaze->bmap );
					wait(1);
				#endif
				maze_step_calls += 1;
				maze_step ( array, size_x, size_y, x, y, cells_to_end );
				break;
			}
		}
	}
}

void maze_depth_first ( var **array, int size_x, int size_y, int end_x, int end_y )
{
	array_draw ( array, size_x, size_y, panMaze->bmap );
	
	var **c = array;
	var **cl = c + size_x;
	for ( ; c<cl; c+=2 )
	{
		var *r = *c;
		var *rl = r + size_y;
		for ( ; r<rl; r++ )
		{
			*r = WALL;
		}
	}
	
	var **c = array + 1;
	var **cl = c + size_x - 1;
	for ( ; c<cl; c+=2 )
	{
		var *r = *c;
		var *rl = r + size_y;
		for ( ; r<rl; r+=2 )
		{
			*r = WALL;
		}
	}
	
	int *x = sys_malloc ( sizeof(int) );
	int *y = sys_malloc ( sizeof(int) );
	int *cells_to_end = sys_malloc ( sizeof(int) );
	*x = end_x;
	*y = end_y;
	*cells_to_end = OPEN;
	array_cell(array,*x,*y) = END;
	
	maze_step_calls += 1;
	maze_step ( array, size_x, size_y, x, y, cells_to_end );
	
	#ifdef WATCH_GENERATION
		while ( proc_status ( maze_step ) > 0 )
			wait(1);
	#endif
	
	sys_free ( x );
	sys_free ( y );
	sys_free ( cells_to_end );
	
	// Clean up
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			int n = 0;
			int cell_depth = 0;
			int i = 0;
			for ( ; i<8; i+=1 )
			{
				int nx = pos_x + ns[i][0];
				int ny = pos_y + ns[i][1];
				if ( array_cell(array,nx,ny) > WALL )
				{
					n += 1;
					cell_depth += array_cell(array,nx,ny);
				}
			}
			if ( n == 8 )
				array_cell(array,pos_x,pos_y) = cell_depth / 8;
		}
	}
	
	// Look for start point
	int start_x = 0;
	int start_y = 0;
	int pos_x = 1;
	for ( ; pos_x<size_x; pos_x+=2 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y; pos_y+=2 )
		{
			if ( array_cell(array,pos_x,pos_y) > array_cell(array,start_x,start_y) )
			{
				start_x = pos_x;
				start_y = pos_y;
			}
		}
	}
	array_cell(array,start_x,start_y) = START;
	
	// Isolate halls
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int n = 0;
			int i = 0;
			for ( ; i<8; i+=1 )
			{
				int nx = pos_x + ns[i][0];
				int ny = pos_y + ns[i][1];
				if ( array_cell(array,nx,ny) > WALL )
					n += 1;
			}
			if ( n == 8 )
				array_cell(array,pos_x,pos_y) = HALLCENTER;
		}
	}
	
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int i = 0;
			for ( ; i<8; i+=1 )
			{
				int nx = pos_x + ns[i][0];
				int ny = pos_y + ns[i][1];
				if ( array_cell(array,nx,ny) != HALLCENTER )
					continue;
				array_cell(array,pos_x,pos_y) = HALLBORDER;
				break;
			}
		}
	}
	
	// Look for doors
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = pos_x + no[i][0];
				int ny = pos_y + no[i][1];
				if ( array_cell(array,nx,ny) != HALLBORDER )
					continue;
				array_cell(array,pos_x,pos_y) = DOOR;
				break;
			}
		}
	}
	
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int n = 0;
			int cheapest_x = 0;
			int cheapest_y = 0;
			var weight = 100000;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = pos_x + no[i][0];
				int ny = pos_y + no[i][1];
				if ( ( array_cell(array,nx,ny) >= OPEN ) || ( array_cell(array,nx,ny) == BONUS ) )
				{
					n += 1;
					if ( array_cell(array,nx,ny) < weight )
					{
						cheapest_x = nx;
						cheapest_y = ny;
						weight = array_cell(array,nx,ny);
					}
				}
			}
			if ( n >= 3 )
				array_cell(array,cheapest_x,cheapest_y) = DOOR;
		}
	}
	
	// Look for bonus
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int n = 0;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = pos_x + no[i][0];
				int ny = pos_y + no[i][1];
				if ( ( array_cell(array,nx,ny) >= OPEN ) || ( array_cell(array,nx,ny) == DOOR ) || ( array_cell(array,nx,ny) == BONUS ) || ( array_cell(array,nx,ny) == END ) || ( array_cell(array,nx,ny) == START ) )
					n += 1;
			}
			if ( n == 1 )
				array_cell(array,pos_x,pos_y) = BONUS;
		}
	}
	
	// Hall lights
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=1 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=1 )
		{
			if ( array_cell(array,pos_x,pos_y) != HALLCENTER )
				continue;
			int n = 0;
			int i = 0;
			for ( ; i<8; i+=1 )
			{
				int nx = pos_x + ns[i][0];
				int ny = pos_y + ns[i][1]; 
				if ( ( array_cell(array,nx,ny) == HALLCENTER ) || ( array_cell(array,nx,ny) == LIGHTWALL ) )
					n += 1;
			}
			if ( n < 2 )
			{
				int ni = integer ( random(4) );
				int roll_side = sign ( random(1)-0.5 );
				int nx = pos_x + no[ni][0];
				int ny = pos_y + no[ni][1];
				while ( array_cell(array,nx,ny) != HALLBORDER )
				{
					ni = cycle ( ni+1, 0, 4 );
					nx = pos_x + no[ni][0];
					ny = pos_y + no[ni][1];
				}
				int i = 1;
				for ( ; i<8; i+=2 )
				{
					int nx2 = nx + ns[i][0];
					int ny2 = ny + ns[i][1];
					if ( array_cell(array,nx2,ny2) == LIGHTWALL )
						break;
				}
				if ( i == 9 )
				{
					int i = 0;
					for ( ; i<4; i+=1 )
					{
						int nx2 = nx + ns[i][0] * 2;
						int ny2 = ny + ns[i][1] * 2;
						if ( ( nx2 < 0 ) || ( nx2 >= size_x ) || ( ny2 < 0 ) || ( ny2 >= size_y ) )
							continue;
						if ( array_cell(array,nx2,ny2) == LIGHTWALL )
							break;
					}
					if ( i == 4 )
						array_cell(array,nx,ny) = LIGHTWALL;
				}
			}
			if ( n == 8 )
				array_cell(array,pos_x,pos_y) = LIGHTHALL;
		}
	}
	
	// Corridor lights
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=2 )
	{
		int pos_y = 2;
		for ( ; pos_y<size_y-1; pos_y+=2 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = pos_x + no[i][0] * 2;
				int ny = pos_y + no[i][1] * 2;
				if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
					continue;
				int nx2 = pos_x + no[i][0];
				int ny2 = pos_y + no[i][1];
				if ( ( array_cell(array,nx,ny) == LIGHTCORRIDOR ) && ( array_cell(array,nx2,ny2) > OPEN ) )
					break;
			}
			if ( i == 4 )
			{
				i = 1;
				for ( ; i<8; i+=2 )
				{
					int nx = pos_x + ns[i][0];
					int ny = pos_y + ns[i][1];
					if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
						continue;
					if ( array_cell(array,nx,ny) == LIGHTCORRIDOR )
						break;
				}
				if ( i == 9 )
					array_cell(array,pos_x,pos_y) = LIGHTCORRIDOR;
			}
		}
	}
	
	int pos_x = 2;
	for ( ; pos_x<size_x-1; pos_x+=2 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=2 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = pos_x + no[i][0] * 2;
				int ny = pos_y + no[i][1] * 2;
				if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
					continue;
				int nx2 = pos_x + no[i][0];
				int ny2 = pos_y + no[i][1];
				if ( ( array_cell(array,nx,ny) == LIGHTCORRIDOR ) && ( array_cell(array,nx2,ny2) > OPEN ) )
					break;
			}
			if ( i == 4 )
			{
				i = 1;
				for ( ; i<8; i+=2 )
				{
					int nx = pos_x + ns[i][0];
					int ny = pos_y + ns[i][1];
					if ( ( nx < 0 ) || ( nx >= size_x ) || ( ny < 0 ) || ( ny >= size_y ) )
						continue;
					if ( array_cell(array,nx,ny) == LIGHTCORRIDOR )
						break;
				}
				if ( i == 9 )
					array_cell(array,pos_x,pos_y) = LIGHTCORRIDOR;
			}
		}
	}
	
	int pos_x = 1;
	for ( ; pos_x<size_x-1; pos_x+=2 )
	{
		int pos_y = 1;
		for ( ; pos_y<size_y-1; pos_y+=2 )
		{
			if ( array_cell(array,pos_x,pos_y) < OPEN )
				continue;
			int n = 0;
			int i = 0;
			for ( ; i<4; i+=1 )
			{
				int nx = pos_x + no[i][0];
				int ny = pos_y + no[i][1];
				if ( array_cell(array,nx,ny) == DOOR )
					n += 1;
				if ( ( array_cell(array,nx,ny) == LIGHTCORRIDOR ) || ( array_cell(array,nx,ny) == BONUS ) || ( array_cell(array,nx,ny) > OPEN ) )
					n -= 1;
			}
			if ( n == 2 )
				array_cell(array,pos_x,pos_y) = LIGHTCORRIDOR;
		}
	}
	
}

void main ()
{
//	video_mode = 8;
	video_set ( 700, 700, 32, 2 );
	random_seed ( 0 );
	fps_max = 30;
	wait(3);
	panMaze = pan_create ( "flags=SHOW;", 1 );
	panMaze->bmap = bmap_createblack ( 700, 700, 24 );
	
	int maze_x = integer ( make_odd ( bmap_width(panMaze->bmap) / 15 ) );
	int maze_y = integer ( make_odd ( bmap_height(panMaze->bmap) / 15 ) );
	
	var **maze = array_create ( maze_x, maze_y );
	maze_depth_first ( maze, maze_x, maze_y, make_odd ( maze_x / 2 ), make_odd ( maze_y / 2 ) );
	#ifdef WATCH_GENERATION
		wait_for ( maze_depth_first );
	#endif
	
	array_draw ( maze, maze_x, maze_y, panMaze->bmap );
	
	var keySpace = 0;
	var clock = total_ticks + 8;
	while ( !key_esc )
	{
		if ( key_space )
			keySpace = 1;
		else if ( keySpace ) //|| ( total_ticks > clock ) )
		{
			clock = total_ticks + 8;
			keySpace = 0;
			array_remove ( maze, maze_x );
			maze = array_create ( maze_x, maze_y );
			maze_depth_first ( maze, maze_x, maze_y, make_odd ( maze_x / 2 ), make_odd ( maze_y / 2 ) );
			#ifdef WATCH_GENERATION
				wait_for ( maze_depth_first );
			#endif
			
			array_draw ( maze, maze_x, maze_y, panMaze->bmap );
		}
		wait(1);
	}
	
	bmap_remove ( panMaze->bmap );
	pan_remove ( panMaze );
	array_remove ( maze, maze_x );
	
	sys_exit ( NULL );
}


Salud!
Posted By: xbox

Re: Maze generation algorithm - 10/06/13 20:36

@txesmi I've been playing with the code you originally converted on the first page of this thread and the last one you posted, and I'm just trying to mark all of the dead ends in the maze, but I can't figure it out. I've been tearing apart the code and trying to paste the parts I need in, (worst way to learn coding, I know) but I just can't understand the logic, and I don't know what the variables stand for.

Trust me, I'm not trying to make you write the program for me, I'm just lost with the logic and don't know where to start. grin
Posted By: txesmi

Re: Maze generation algorithm - 10/06/13 21:49

Let's start with the first code.

The briefly called variables are:
c -> column
cl -> column last
r -> row
rl -> row last

no -> neighbor offset
noi -> neighbor offset index

nx -> neighbor x coordinate
ny -> neighbor y coordinate

Once you have the maze constructed, you have to check the cells that has just one neighbor navigable. If you look at the cell style defines you will realize that all the navigable cells are bigger than WALL. Note that only odd cells (starting with 0) can be deadends.

So...
Code:
int pos_x = 1;
for ( pos_x=1; pos_x<size_x; pos_x +=2 ) // go trough every odd columns
{
   int pos_y = 1;
   for ( pos_y=1; pos_y<size_y; pos_y+=2 ) // go trough every odd row on each column
   {
      if ( array_cell(maze,pos_x,pos_y) > WALL ) // is the current cell a navigable cell?
      {
         int nc = 0; // neighbor count
         int noi = 0;
         for ( noi=0; noi<4; noi+=1 ) // go trough every couple of members of neighbor offset array
         {
            int nx = pos_x + no[noi][0]; // calculate the neighbor coords
            int ny = pos_y + no[noi][1]; 
            if ( array_cell(maze,nx,ny) > WALL ) // is the current neighbor a navigable cell?
            {
               nc += 1; // increase the neighbor count by one
            }
         }
         if ( nc == 1 ) // has the current cell just a single neighbor?
         {
            array_cell(maze,pos_x,pos_y) = DEADEND; // it is a deadend
         }
      }
   }
}


Salud!
Posted By: xbox

Re: Maze generation algorithm - 10/06/13 23:14

Wow, thanks man, I really appreciate the explanation and snippet. I got it working now. Thank you so much! laugh
Posted By: Nems

Re: Maze generation algorithm - 11/10/13 04:04

Hi guys, how would I go about generating the maze in 2D, would I need to use a txt file reference map?
Posted By: 3run

Re: Maze generation algorithm - 11/10/13 09:21

Nems@ maze generated randomly, and it's already 2D (the original example).
© 2024 lite-C Forums