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

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