#include <stdio.h>
#include <stdlib.h>
#include <concorde.h>
#include <ysmaze2.h>
#include <time.h>


/*
  迷路構造体 *mz の,(bx,by)の向きdirに,壁種類wal,通過フラッグpasの
  壁を作る
*/
static void MazeCreateAddWall
     (MAZEMAP *mz,int bx,int by,int dir,int wal,int pas)
{
	int p= bx+(mz->lx)*by;
	int lx=mz->lx,ly=mz->ly;

	if(pas)pas=1;

	switch(dir)
	{
	case 0:
		mz->map[p] = (mz->map[p] & 0xfffc) | wal;
		mz->map[p] = (mz->map[p] & 0xffef) | (pas * 16);
		break;
	case 1:
		mz->map[p] = (mz->map[p] & 0xfff3) | (wal*4);
		mz->map[p] = (mz->map[p] & 0xffdf) | (pas * 32);
		break;
	case 2:
		if(by==ly-1)MazeCreateAddWall(mz,bx,0   ,0,wal,pas);
		       else MazeCreateAddWall(mz,bx,by+1,0,wal,pas);
		break;
	case 3:
		if(bx==lx-1)MazeCreateAddWall(mz,0   ,by,1,wal,pas);
		       else MazeCreateAddWall(mz,bx+1,by,1,wal,pas);
		break;
	}
}


/*
 迷路 *mz の,ブロック(x,y)の,左上の角から出ている壁の枚数を返す.
*/
static int MazeCreateWalls(MAZEMAP *mz,int x,int y)
{
	int ret=0;
	int bx,by;

	bx=x; by=y-1;
	if(by<0)by+=mz->ly;
	if( MazeWall(mz,bx,by,1) ) ret++;

	bx=x-1; by=y;
	if(bx<0)bx+=mz->lx;
	if( MazeWall(mz,bx,by,0) ) ret++;

	if( MazeWall(mz,x,y,1) )ret++;
	if( MazeWall(mz,x,y,0) )ret++;

	return ret;
}

/*
  迷路構造体 *mz の,(bx,by)の向きdirに,壁種類wal,通過フラッグpasの
  壁を作る
*/
static void MazeCreateAddWall2
     (MAZEMAP *mz,int x,int y,int dir,int wal,int pas)
{
	switch(dir)
	{
	case 0:
		y--; if(y<0)y+=mz->ly;
		MazeCreateAddWall(mz,x,y,1,wal,pas);
		break;
	case 1:
		x--; if(x<0)x+=mz->lx;
		MazeCreateAddWall(mz,x,y,0,wal,pas);
		break;
	case 2:
		MazeCreateAddWall(mz,x,y,1,wal,pas);
		break;
	case 3:
		MazeCreateAddWall(mz,x,y,0,wal,pas);
		break;
	}
}


/*
 迷路構造体 *mz に,壁を生成する.壁は,ブロック(x,y)の左上の角からスタート
 して,最大 l 枚まで伸びる.また,通過した角から,最大branch枚の枝壁が伸びる.
 伸ばす方向は乱数で,伸ばして ctr回他の壁にぶつかると,その時点で伸ばす処理
 を中断する.壁の種類はwal,通過フラッグがpasで, c は常に呼び出し元では0に
 する.
*/
static int MazeCreatePrg
       (MAZEMAP *mz,int x,int y,int l,int branch,int ctr,int wal,int pas,int c)
{
	int r;
	int bx,by;

	if(ctr==0 || l==0)
	{
		return c;
	}

	r=rand() % 4;
	bx=x; by=y;
	switch(r)
	{
	case 0:
		by--; if(by<0)by+=mz->ly;
		break;
	case 1:
		bx--; if(bx<0)bx+=mz->lx;
		break;
	case 2:
		by++; if(by==mz->ly)by=0;
		break;
	case 3:
		bx++; if(bx==mz->lx)bx=0;
		break;
	}

	if(MazeCreateWalls(mz,bx,by))
	{
		return MazeCreatePrg(mz,x,y,l,branch,ctr-1,wal,pas,c);
	}
	else
	{
		switch(r)
		{
		case 0:
			MazeCreateAddWall(mz,bx,by,1,wal,pas);
			break;
		case 1:
			MazeCreateAddWall(mz,bx,by,0,wal,pas);
			break;
		case 2:
			MazeCreateAddWall(mz,x,y,1,wal,pas);
			break;
		case 3:
			MazeCreateAddWall(mz,x,y,0,wal,pas);
			break;
		}
		return MazeCreatePrg(mz,bx,by,l-1,branch,4,wal,pas,c+1)+
		       MazeCreatePrg(mz, x, y,branch,0  ,4,wal,pas,0);
	}
}


/*
 迷路構造体 *mz に迷路を自動的に作成する.既に *mz に迷路がある場合は,その
 壁の情報は破壊せず,空いている部分に壁を作る.
*/
void MazeCreate(MAZEMAP *mz)
{
	int x,y,l;
	int t;

	t=clock();
	if(t!=-1)
	{
		while(clock()-t < CLK_TCK/4)rand();
	}

	l=(mz->lx + mz->ly)/2;

	for(x=0; x<mz->lx; x++)MazeCreateAddWall(mz,x,0,0,1,1);
	for(y=0; y<mz->ly; y++)MazeCreateAddWall(mz,0,y,1,1,1);

	for(x=0; x<mz->lx; x++)
	{
		MazeCreatePrg(mz,x,0,l,l/2,4,1,1,0);
	}
	for(y=0; y<mz->ly; y++)
	{
		MazeCreatePrg(mz,0,y,l,l/2,4,1,1,0);
	}

	for(y=0; y<mz->ly; y++)
	{
		for(x=0; x<mz->lx; x++)
		{
			if(MazeCreateWalls(mz,x,y)==0)
			{
				MazeCreatePrg(mz,x,y,l,l/2,4,1,1,0);
			}
		}
	}

	for(y=0; y<mz->ly; y++)
	{
		for(x=0; x<mz->lx; x++)
		{
			if(MazeCreateWalls(mz,x,y)==0)
			{
				int dir;

				dir=rand() % 4;
				MazeCreateAddWall2(mz,x,y,dir,1,1);
			}
		}
	}

	for(y=0; y<mz->ly; y++)
	{
		for(x=0; x<mz->lx; x++)
		{
			if(!MazeWall(mz,x,y,0) && (rand()%100)<20)
			{
				MazeCreateAddWall(mz,x,y,0,2,0);
			}
			if(!MazeWall(mz,x,y,1) && (rand()%100)<20)
			{
				MazeCreateAddWall(mz,x,y,1,2,0);
			}
		}
	}
}
