Maze generation algorithm

Gamestudio Links

Zorro Links

Newest Posts

Data from CSV not parsed correctly
by EternallyCurious. 04/18/24 10:45

StartWeek not working as it should
by Zheka. 04/18/24 10:11

folder management functions
by VoroneTZ. 04/17/24 06:52

♪♫♪ [For hire] VOLKOVSTUDIO - Music, SFX, Voice over, implementa
by Volkovstudio. 04/16/24 09:54

lookback setting performance issue
by 7th_zorro. 04/16/24 03:08

zorro 64bit command line support
by 7th_zorro. 04/15/24 09:36

Zorro FIX plugin - Experimental
by flink. 04/14/24 07:48

Zorro FIX plugin - Experimental
by flink. 04/14/24 07:46

AUM Magazine

Latest Screens

Who's Online Now

1 registered members (AndrewAMD), 677 guests, and 2 spiders.

Key: Admin, Global Mod, Mod

Newest Members

EternallyCurious, howardR, 11honza11, ccorrea, sakolin
19047 Registered Users

Print Thread

Rate Thread

Page 3 of 3

Re: Maze generation algorithm [Re: 3run] #430645
09/30/13 12:50 09/30/13 12:50

Joined: Jun 2007
Posts: 1,337
Hiporope and its pain

txesmi

Serious User

txesmi

Serious User

Joined: Jun 2007
Posts: 1,337
Hiporope and its pain

glad to help

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!

Re: Maze generation algorithm [Re: txesmi] #430647 09/30/13 14:08 09/30/13 14:08
Joined: Jun 2009 Posts: 2,210 Bavaria, Germany Kartoffel Expert
Kartoffel Expert Joined: Jun 2009 Posts: 2,210 Bavaria, Germany	wow, great ( I'll implement it into my 1st person maze for practise ) POTATO-MAN saves the day! - Random

Re: Maze generation algorithm [Re: Kartoffel] #430650 09/30/13 15:08 09/30/13 15:08
Joined: May 2009 Posts: 5,370 Caucasus 3run OP Senior Expert
3run OP Senior Expert Joined: May 2009 Posts: 5,370 Caucasus	txesmi@ damn! it's so freaking awesome dude! I'll create fps shooter with it (or horror), as I've said before! 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 Looking for free stuff?? Take a look here: http://badcom.at.ua Support me on: https://boosty.to/3rung

Re: Maze generation algorithm [Re: 3run] #430652 09/30/13 15:23 09/30/13 15:23
Joined: Jun 2009 Posts: 2,210 Bavaria, Germany Kartoffel Expert
Kartoffel Expert Joined: Jun 2009 Posts: 2,210 Bavaria, Germany	@3run some kind of flood fill algorithm should be enough to place keys POTATO-MAN saves the day! - Random

Re: Maze generation algorithm [Re: 3run] #430658
09/30/13 16:05 09/30/13 16:05

Joined: Jun 2007
Posts: 1,337
Hiporope and its pain

txesmi

Serious User

txesmi

Serious User

Joined: Jun 2007
Posts: 1,337
Hiporope and its pain

@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!

Re: Maze generation algorithm [Re: txesmi] #430956 10/06/13 20:36 10/06/13 20:36
Joined: Nov 2006 Posts: 497 Ohio xbox Senior Member
xbox Senior Member Joined: Nov 2006 Posts: 497 Ohio	@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.

Re: Maze generation algorithm [Re: xbox] #430959
10/06/13 21:49 10/06/13 21:49

Joined: Jun 2007
Posts: 1,337
Hiporope and its pain

txesmi

Serious User

txesmi

Serious User

Joined: Jun 2007
Posts: 1,337
Hiporope and its pain

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!

Re: Maze generation algorithm [Re: txesmi] #430961 10/06/13 23:14 10/06/13 23:14
Joined: Nov 2006 Posts: 497 Ohio xbox Senior Member
xbox Senior Member Joined: Nov 2006 Posts: 497 Ohio	Wow, thanks man, I really appreciate the explanation and snippet. I got it working now. Thank you so much!

Re: Maze generation algorithm [Re: xbox] #432635 11/10/13 04:04 11/10/13 04:04
Joined: Mar 2003 Posts: 4,264 Wellington Nems .
Nems . Joined: Mar 2003 Posts: 4,264 Wellington	Hi guys, how would I go about generating the maze in 2D, would I need to use a txt file reference map?

Re: Maze generation algorithm [Re: Nems] #432638 11/10/13 09:21 11/10/13 09:21
Joined: May 2009 Posts: 5,370 Caucasus 3run OP Senior Expert
3run OP Senior Expert Joined: May 2009 Posts: 5,370 Caucasus	Nems@ maze generated randomly, and it's already 2D (the original example). Looking for free stuff?? Take a look here: http://badcom.at.ua Support me on: https://boosty.to/3rung

Page 3 of 3

Moderated by HeelX, Lukas, rayp, Rei_Ayanami, Superku, Tobias, TWO, VeT