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

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