// AmazeDoc.cpp : implementation of the CAmazeDoc class
//

#include "stdafx.h"
#include "Amaze.h"

#include "AmazeDoc.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAmazeDoc

IMPLEMENT_DYNCREATE(CAmazeDoc, CDocument)

BEGIN_MESSAGE_MAP(CAmazeDoc, CDocument)
	//{{AFX_MSG_MAP(CAmazeDoc)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CAmazeDoc construction/destruction

CAmazeDoc::CAmazeDoc()
{
	// TODO: add one-time construction code here
	m_pData = NULL;
	m_pDisData = NULL;
	m_nDisNum = 0;
	m_nWidth = 40;
	m_nHeight = 25;
}

CAmazeDoc::~CAmazeDoc()
{
	DeleteAmaze();
}

BOOL CAmazeDoc::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;

	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)

	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CAmazeDoc serialization

void CAmazeDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		// TODO: add storing code here
	}
	else
	{
		// TODO: add loading code here
	}
}

/////////////////////////////////////////////////////////////////////////////
// CAmazeDoc diagnostics

#ifdef _DEBUG
void CAmazeDoc::AssertValid() const
{
	CDocument::AssertValid();
}

void CAmazeDoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CAmazeDoc commands

void CAmazeDoc::CreateAmaze()
{
    int Ptr=0;
	int X, Y, Xn, Yn;
    int Dir, Dir2;
    int i, k;
	long Count0 = (2*m_nWidth+2) * (2*m_nHeight+2);
    
	DeleteAmaze();
	m_pData = new long[Count0];
	m_pDisData = new long[Count0];
    //初始化數組
	memset(m_pData, 0, sizeof(long) * Count0);
    //畫上下邊界
	for( i = 0 ; i <= 2 * m_nWidth; i++){
        AMAZEDATA(i, 0) = 1;
        AMAZEDATA(i, m_nHeight * 2) = 1;
    }
    
    //畫左右邊界
    for( i = 0 ; i <= 2 * m_nHeight; i++){
        AMAZEDATA(0, i) = 1;
        AMAZEDATA(m_nWidth * 2 , i) = 1;
	}

    Count0 = m_nWidth * m_nHeight;
    //畫迷宮循環
    for( i = 0 ; i<= Count0; i++){
        Ptr = (Ptr + 997) % Count0;
        X = Ptr / m_nHeight;
        Y = Ptr - X * m_nHeight;
        if(!AMAZEDATA(2 * X, 2 * Y)){
            Dir = 4.0 * rand() / RAND_MAX + 1;
            Dir2 = Dir;
            do{
                Dir = Dir % 4 + 1;
                Xn = ((Dir == 1) - (Dir == 3)) + X;
                Yn = ((Dir == 2) - (Dir == 4)) + Y;
                if( AMAZEDATA(2 * Xn, 2 * Yn) )
                    break;
                if( Dir == Dir2 ){
                    X = Xn;
                    Y = Yn;
                }
            }while(true);
			AMAZEDATA(2 * X , 2 * Y) = 1;
			AMAZEDATA(2 * Xn , 2 * Yn) = 1;
			AMAZEDATA(X + Xn , Y + Yn) = 1;
            Dir = 4.0 * rand() / RAND_MAX + 1;
            k = 0;
            do {
                k = k + 1;
                Dir = Dir % 4 + 1;
                Xn = ((Dir == 1) - (Dir == 3)) + X;
                Yn = ((Dir == 2) - (Dir == 4)) + Y;
				if(! AMAZEDATA(2 * Xn, 2 * Yn) ){
                    //Call LineA(X, Y, Xn, Yn)
			AMAZEDATA(2 * X , 2 * Y) = 1;
			AMAZEDATA(2 * Xn , 2 * Yn) = 1;
			AMAZEDATA(X + Xn , Y + Yn) = 1;
                    X = Xn;
                    Y = Yn;
                    Dir = 4.0 * rand() / RAND_MAX + 1;
                    k = 0;
                }
            }while(k <= 4);
        }
    }
    
    //迷宮上邊開口
    X = m_nWidth - 1;
    do {
        X = X + 1;
    }while( AMAZEDATA(X, 1) );
    AMAZEDATA(X, 0) = 0;
    
    //迷宮下邊開口
    X = m_nWidth - 1;
    do {
        X = X + 1;
    }while( AMAZEDATA(X, 2 * m_nHeight - 1) );
    AMAZEDATA(X, 2 * m_nHeight) = 0;
	DisAmaze();
}

void CAmazeDoc::DisAmaze()
{
    int X, Y=1, Xn, Yn, k=0, n, n1, i;
    
    if(!m_pData)
        //無迷宮
        return;
    
    for( X = 0 ;X <= m_nWidth * 2; X++)
        //尋找迷宮入口
        if(! AMAZEDATA(X, 0) )
			break;

	*(m_pDisData) = X;
	*(m_pDisData+1) = 0;
	*(m_pDisData+2) = X;
	*(m_pDisData+3) = 1;
	m_nDisNum = 2;

    do{
    //由于迷宮一定有出口，
    //所以按固定方向搜索，必然會找到出口
    //當前Do循環即按一定方向遍歷迷宮。
		for( n = 0 ; n<4; n++){ 
			n1 = (k + n) % 4;
			Xn = (n1 == 2) - (n1 == 0) + X;
			Yn = (n1 == 1) - (n1 == 3) + Y;
			if(! AMAZEDATA(Xn, Yn) ){
				for(i=0;i<m_nDisNum;i++)
					if(*(m_pDisData + 2*i) == Xn && *(m_pDisData + 2*i+1) == Yn)
						break;
				m_nDisNum = i;
				*(m_pDisData + 2*m_nDisNum) = Xn;
				*(m_pDisData + 2*m_nDisNum+1) = Yn;
				m_nDisNum++;
				X = Xn;
				Y = Yn;
				k = (n1 + 3) % 4;
				break;
			}
		}
    //當Y方向大于迷宮邊界時，結束
    }while( Y != 2 * m_nHeight && Y > 0);
}