boxmanclass.cpp

推箱子游戏的源码。有很多关

{
	CPtrArray pos;
	CWordArray from;
	CPoint *pn = new CPoint;
	pn->x = x;//注意:这里是倒过来走的
	pn->y = y;
	pos.Add( pn );
	from.Add( 0x7fff );
//	unsigned short head = 0;
	unsigned short now = 0;
	unsigned short end = 0;
	
	while( now <= end ){
		pn = (CPoint*)pos.GetAt( now );
		for ( char d = 0; d<4; d++ ){
			char tx = (char)pn->x + dx[d];
			char ty = (char)pn->y + dy[d];
			if ( (tx == m_mx)&&(ty == m_my) ){
				CPtrArray *way = new CPtrArray;
				while( now != 0x7fff ){
					pn = (CPoint*)pos.GetAt( now );
					now = from.GetAt( now );
					CPoint* pe = new CPoint;
					pe->x = pn->x;
					pe->y = pn->y;
					way->Add( pe );
				}
				return way;
			}
			if ( (m_map[tx][ty] != '+') && (m_bnm[tx][ty] != '#') && (m_bnm[tx][ty] != '^') ){
				bool have = false;
				for ( unsigned short i=0; !have && (i<=end); i++ ){
					CPoint *tp = (CPoint*)pos.GetAt( i );
					if ( (tp->x == tx)&&(tp->y == ty) ) have = true;
				}
				if (!have){
					CPoint *pe = new CPoint;
					pe->x = tx;
					pe->y = ty;
					pos.Add( pe );
					from.Add( now );
					end++;
				}
			}
		}
		now++;
	}
	end = pos.GetSize();
	for(unsigned short i = 0; i<end; i++ ){
		pn = (CPoint*)pos.GetAt( i );
		delete pn;
	}
	pos.RemoveAll();
	from.RemoveAll();
	return NULL;
}

unsigned char BoxManClass::DoManMove()
{
	unsigned char result;
	for ( int i=0; i<m_pmanmoveway->GetSize(); i++ ){
		CPoint* p =(CPoint*)m_pmanmoveway->GetAt( i );
		char tx = p->x - m_mx;
		char ty = p->y - m_my;
		delete p;
		result=MoveTowards( tx, ty );
		::Sleep(50);
	}
	m_pmanmoveway->RemoveAll();
	m_pmanmoveway = NULL;
	return result;
}

bool BoxManClass::PrepareThinking(unsigned int index)
{
	//优化地图
	char x=m_x-1;
	char y=m_y-1;
	for ( char j=1; j<y; j++ ) for ( char i=1; i<x; i++ ) {
		if ( m_map[i][j] == ' ' ) {
			int u=0;
			for ( int d=0; d<4; d++ ){
				if ( m_map[i+dx[d]][j+dy[d]] == '+' ){
					u++;
					bool canputbox = false;
					int td=(d+3)%4;
					int tx=i;
					int ty=j;
					while ( !canputbox ){
						tx+=dx[td];
						ty+=dy[td];
						if ( m_map[tx][ty] == '+' ) break;
						if ( m_map[tx][ty] == '.' ) canputbox = true;
						else if ( m_map[tx+dx[d]][ty+dy[d]] != '+' ) canputbox = true;
					}
					td=(d+1)%4;
					tx=i;
					ty=j;
					while ( !canputbox ){
						tx+=dx[td];
						ty+=dy[td];
						if ( m_map[tx][ty] == '+' ) break;
						if ( m_map[tx][ty] == '.' ) canputbox = true;
						else if ( m_map[tx+dx[d]][ty+dy[d]] != '+' ) canputbox = true;
					}
					if ( !canputbox ) m_map[i][j] = '*';
				} else {//endof if '+'
					if (u>1) m_map[i][j] = '*';
					u = 0;
				}
			}//endof for (d~4)
			if ( (u>1) || ( (u>0) && (m_map[i+dx[0]][j+dy[0]] == '+') ) ) m_map[i][j] = '*';
		}//endof if map == ' '
	}//endof for (i , j)

	//分析moveway.dat文件
	char* p = (char*)::GlobalLock( m_hway );
	char str[256];
	bool ism = false;
	char i = 0;
	m_noanswerrecoded = false;
	for( DWORD n = 0; (n<m_wayfilelength); n++, p++ ){
		if ( ism ){
			if (*p != '\r') {
				str[i++] = *p;
			}else{
				str[i] = 0;
				unsigned int value = atoi(str);
				if (value == index) {
					//find the map way
					p+=2;
					if ( *p == '[' ) m_computerthinkout = true;
					else m_computerthinkout = false;
					for( char* tp = p; (*tp != ']') && (*tp != '}');  tp++ );//注:无循环体
					m_boxmovestepnumber = (tp-p) / 4;
					::GlobalUnlock( m_hway );
					return true;
				}
				i = 0;
				m_TheMapsMoveWaySavePoint=-1;
				ism = false;
			}
		}else if ( *p == 'M' ){
			ism = true;
			m_TheMapsMoveWaySavePoint=n;
		}
	}
	::GlobalUnlock( m_hway );
	m_noanswerrecoded = true;
	m_computerthinkout = false;
	return false;
}

void BoxManClass::ShowMoveWay()
{
	static CPtrArray path;
	static int TotalStep=0;

	if ( m_TheShowStep == 0 ){
		for( int it=0; it<path.GetSize(); it++ ){
			PathStruct* ps = (PathStruct*)path.GetAt( it );
			delete ps;
		}
		path.RemoveAll();
		TotalStep=0;
		if (m_CanUndo) {
			while(m_CanUndo) Undo();
			//::MessageBox( m_pDrawWnd->m_hWnd, "开始演示", "Message", 0 );
			PathStruct *ps1 = new PathStruct;
			ps1->manx = m_mx;
			ps1->many = m_my;
			ps1->boxx = m_mx;
			ps1->boxy = m_my;
			path.Add( ps1 );
			TotalStep++;
		}
		char* p = (char*)::GlobalLock( m_hway );
		for ( p+=m_TheMapsMoveWaySavePoint; (*p!='{')&&(*p!='['); p++ );//no body
		p++;
		//TRACE( "%d\t", path.GetSize() );
		for ( unsigned int i=0; i<m_boxmovestepnumber; i++ ){
			PathStruct *ps = new PathStruct;
			ps->manx = *p++;
			ps->many = *p++;
			ps->boxx = *p++;
			ps->boxy = *p++;
			path.Add( ps );
			TotalStep++;
		}
		//TRACE( "%d\n", path.GetSize() );
		::GlobalUnlock( m_hway );
	}
	PathStruct* ps = (PathStruct*)path.GetAt( m_TheShowStep );
	if ( (m_mx != ps->manx) || (m_my != ps->many) ){
		m_pmanmoveway = MoveManTo( ps->manx, ps->many );
		if ( m_pmanmoveway != NULL ) DoManMove();
	}
	::Sleep(50);
	MoveTowards( ps->boxx-ps->manx, ps->boxy-ps->many );
	::Sleep(50);
	m_RemainShewStep = TotalStep - ++m_TheShowStep;
	if ( path.GetSize() == m_TheShowStep ){
		for( int i=0; i<m_TheShowStep; i++ ){
			PathStruct* ps = (PathStruct*)path.GetAt( i );
			delete ps;
		}
		path.RemoveAll();
		m_TheShowStep = m_RemainShewStep = 0;
		::MessageBox( m_pDrawWnd->m_hWnd, "演示完毕!", "Message", MB_ICONASTERISK | MB_ICONINFORMATION );
	}
}

void BoxManClass::ThinkTheWay()
{
	if ( _ThreadCommand == BM_COMMAND_STOP_THREAD ) {
		_ThreadMessage = BM_MESSAGE_THINK_OUT;
		return;
	}
	_ThreadMessage = BM_MESSAGE_THINKING;
	unsigned char i, j;
	if ( _ThinkingMap == m_nowmap ) return;
	else _ThinkingMap = m_nowmap;
	_x = m_x-1;
	_y = m_y-1;
	_x2 = m_x-2;
	_y2 = m_y-2;
	_structSize = ( m_NumberOfBox + 1 ) + 4;
	for ( j=0; j<m_y; j++ ) for ( i=0; i<m_x; i++ ) _con[i][j]=m_bnm[i][j];
	//there must use 0 to m_x, can't use 1 to _x, but i don't know why.
	//TRACE("
	_InitData();
	bool tb = _ThinkIt();

	::GlobalFree( _head );
	if( _ThreadMessage == BM_MESSAGE_THINKING ) _ThreadMessage = 0;
}

void BoxManClass::_InitData()
{
	unsigned char *p, **ap;
	unsigned char i, j;
	//定义一个计算用的内存
	p = (unsigned char*)GlobalAlloc( GPTR, _structSize * BM_THREAD_BUFFER_SIZE );
	_head = _now = p;
	_end = p+_structSize;
	ap = (unsigned char**)(_end-4);
	*ap = NULL;

	for ( j=1; j<_y; j++ ) for ( i=1; i<_x; i++ ){
		if ( _con[i][j] == '#' ){
			//*p++ = i;
			//*p++ = j;
			*p++ = (j-1) * _x2 + (i-1);
		}
	}
	//用'^'着色
	bool havechange;
	do{
		havechange = false;
		for ( j=1; j<_y; j++ ) for ( i=1; i<_x; i++ ){
			if ( m_map[i][j]!='+' && _con[i][j]==0 &&
				( _con[i+1][j]=='^' || _con[i-1][j]=='^' || _con[i][j+1]=='^' || _con[i][j-1]=='^' ) ){
				_con[i][j] = '^';
				havechange = true;
			}
		}
		if ( !havechange ) break;
		havechange = false;
		for ( i=_x-1; i>0; i-- ) for ( j=_y-1; j>0; j-- ){
			if ( m_map[i][j]!='+' && _con[i][j]==0 &&
				( _con[i+1][j]=='^' || _con[i-1][j]=='^' || _con[i][j+1]=='^' || _con[i][j-1]=='^' ) ){
				_con[i][j] = '^';
				havechange = true;
			}
		}
	}while ( havechange );
	//纪录人的位置
	for ( j=1; j<_y; j++ ) for ( i=1; i<_x; i++ ){
		if ( _con[i][j] == '^' ){
			//*p++ = i;
			//*p = j;
			*p = (j-1) * _x2 + ( i-1 );
			return;
		}
	}
	return;
}

inline void BoxManClass::_UnpackData(unsigned char *p)
{
	unsigned char i, j;

	//注意:这里一定是MAXMAPSIZEY*(_x-1)
	::memset( MAXMAPSIZEY+(char*)_con, 0, MAXMAPSIZEY*(_x-1) );
	//for ( j=1; j<_y; j++ ) for ( i=1; i<_x; i++ ) _con[i][j] = 0;
	for ( i=0; i<m_NumberOfBox; i++, p++ ){
		_con[ *p % _x2 + 1 ][ *p / _x2 + 1 ] = '#';//放'#'
	}
	//放'^'
	_con[ *p % _x2 + 1 ][ *p / _x2 + 1 ] = '^';
	//用'^'着色
	bool havechange;
	do{
		havechange = false;
		for ( j=1; j<_y; j++ ) for ( i=1; i<_x; i++ ){
			if ( m_map[i][j]!='+' && _con[i][j]==0 &&
				( _con[i+1][j] == '^' || _con[i-1][j]=='^' || _con[i][j+1]=='^' || _con[i][j-1]=='^' ) ){
				_con[i][j] = '^';
				havechange = true;
			}
		}
		if ( !havechange ) break;
		havechange = false;
		for ( i=_x-1; i>0; i-- ) for ( j=_y-1; j>0; j-- ){
			if ( m_map[i][j]!='+' && _con[i][j]==0 &&
				( _con[i+1][j]=='^' || _con[i-1][j]=='^' || _con[i][j+1]=='^' || _con[i][j-1]=='^'  ) ){
				_con[i][j] = '^';
				havechange = true;
			}
		}
	}while ( havechange );
}

inline bool BoxManClass::_IsOk(unsigned char *p)
{
	bool ok=true;
	for ( int i=0; ok && (i<m_NumberOfBox); i++ , p++ ){
		ok = (m_map[ *p % _x2 + 1 ][ *p / _x2 + 1 ] == '.');
	}
	return ok;
}

bool BoxManClass::_ThinkIt()
{
	unsigned char *np, nx, ny, fx, fy, bx, by, k, d;
	int numberofnode=0;
	bool conChanged;
	bool Ok;

	Ok = _IsOk( _end - _structSize );
	if ( Ok ){
		//MsgBox( "ERROR", "The Map needn't think." );
		_ThreadMessage = BM_MESSAGE_THINK_OUT;
		::MessageBeep( MB_OK );
		return true;
	}
	while ( _now != _end && _ThreadCommand != BM_COMMAND_STOP_THREAD ){
		_UnpackData( _now );
		conChanged = false;
		//move
		np = _now;
		for ( k=0; k<m_NumberOfBox; k++, np++ ){
			//nx = *np++;
			//ny = *np++;
			nx = *np % _x2 + 1;
			ny = *np / _x2 + 1;
			for ( d=0; d<4; d++ ){
				fx = nx + dx[d];
				fy = ny + dy[d];
				bx = nx - dx[d];
				by = ny - dy[d];
				if (_ThreadCommand == BM_COMMAND_STOP_THREAD ){
					_ThreadMessage = BM_MESSAGE_THINK_STOPED;
					return false;
				}
				if ( conChanged ) { _UnpackData( _now ); conChanged = false; }
				if ( m_map[fx][fy]!='+' && m_map[fx][fy]!='*' && _con[fx][fy]!='#' && _con[bx][by]=='^' ){
					_con[fx][fy] = '#';
					_con[nx][ny] = '%';//移动后的人
					_con[bx][by] = '%';
					conChanged = true;
					_PackData();
					if ( !_AlreadyHave() ) {
						Ok = _IsOk( _end );
						_end += _structSize;
						if ( BM_THREAD_BUFFER_SIZE < ++numberofnode) {
							_ThreadMessage = BM_MESSAGE_BUFFER_FULL;
							::MessageBeep( MB_ICONHAND );
							return false;
						}
						if ( Ok ) {
							_OutputToFile();
							//char s[40];
							//wsprintf(s,"OK! 共产生了%d个节点",numberofnode);
							//MsgBox( "OK", s );
							_ThreadMessage = BM_MESSAGE_THINK_OUT;
							::MessageBeep( MB_OK );
							return true;
						}
					}
				}//endof can move
			}//endof for d<4
		}//endof for k<m_NumberOfBox
		_now += _structSize;
	}//endof while !IsOk
	//UnpackData( head );
	//char s[40];
	//wsprintf(s,"No Answer! 共产生了%d个节点",numberofnode);
	//MsgBox( "ERROR", s );
	if ( _now == _end  ){
		_ThreadMessage = BM_MESSAGE_NO_ANSWER;
		::MessageBeep( MB_ICONQUESTION );
	} else _ThreadMessage = BM_MESSAGE_THINK_STOPED;
	return false;
}

void BoxManClass::_OutputToFile()
{
	unsigned char *tp, **ap, *p;
	//将链表的方向颠倒
	p = _end - _structSize;
	tp = NULL;
	while ( p != _head ) {
		unsigned char *np = p;
		ap = (unsigned char**)(p+_structSize-4);
		p = *ap;
		*ap = tp;
		tp = np;
	}
	ap = (unsigned char**)(p+_structSize-4);
	*ap = tp;
	_now = _head;
	//将路径记入way中
	char pcon[MAXMAPSIZEX][MAXMAPSIZEY];
	unsigned char i, j;
	CPtrArray way;

	_UnpackData( _now );
	for ( j=1; j<_y; j++ ) for ( i=0; i<_x; i++ ) pcon[i][j]=_con[i][j];
//	char **
	ap = (unsigned char**)(_now+_structSize-4);
	_now = *ap;
	while ( _now != NULL ){
		_UnpackData( _now );
		PathStruct *ps = new PathStruct;
		for ( j=1; j<_y; j++ ) for ( i=1; i<_x; i++ ){
			if (_con[i][j]=='^' && pcon[i][j]=='#'){
				ps->boxx=i;
				ps->boxy=j;
			}
		}
		for ( j=1; j<_y; j++ ) for ( i=1; i<_x; i++ ){
			if (_con[i][j]=='#' && pcon[i][j]!='#'){
				ps->manx = ps->boxx * 2 - i;
				ps->many = ps->boxy * 2 - j;
			}
		}
		way.Add( ps );
		for ( j=1; j<_y; j++ ) for ( i=0; i<_x; i++ ) pcon[i][j]=_con[i][j];
//		char **
		ap = (unsigned char**)(_now+_structSize-4);
		_now = *ap;
	}
	//纪录入内存中
	BoxMoveOk( way );
	//清除way;
	for( i=0; i<way.GetSize(); i++ ){
		PathStruct *ps = (PathStruct*)way.GetAt( i );
		delete ps;
	}
	way.RemoveAll();
	PrepareThinking( m_nowmap );
}

inline bool BoxManClass::_AlreadyHave()
{
	unsigned char *p = _head , *nextp, *temp, *ep;
	bool equal = false;

	while ( !equal && (p != _end) ){
		nextp = p+_structSize;
		temp = nextp-4;
		equal = true;
		for ( ep=_end; equal && ( p<temp ); p++, ep++ )
			equal = ( *p == *ep );
		p = nextp;
	}
	return equal;
}

inline void BoxManClass::_PackData()
{
	//用'%'着色
	char i, j;
	bool havechange;

	do{
		havechange = false;
		for ( j=1; j<_y; j++ ) for ( i=1; i<_x; i++ ){
			if ( m_map[i][j]!='+' && ( _con[i][j]==0 || _con[i][j]=='^' ) &&
				( _con[i+1][j]=='%' || _con[i-1][j]=='%' || _con[i][j+1]=='%' || _con[i][j-1]=='%' ) ){
				_con[i][j] = '%';
				havechange = true;
			}
		}
		if ( !havechange ) break;
		havechange = false;
		for ( i=_x-1; i>0; i-- ) for ( j=_y-1; j>0; j-- ){
			if ( m_map[i][j]!='+' && ( _con[i][j]==0 || _con[i][j]=='^' ) &&
				( _con[i+1][j]=='%' || _con[i-1][j]=='%' || _con[i][j+1]=='%' || _con[i][j-1]=='%' ) ){
				_con[i][j] = '%';
				havechange = true;
			}
		}
	}while ( havechange );
	//endof 用'%'着色
	
	//加入新节点
	unsigned char *p = _end, **ap;
	//char manY, manX=0;
	unsigned char manXY;
	
	for ( j=1; j<_y; j++ ) for ( i=1; i<_x; i++ ){
		if ( _con[i][j] == '#' ){
			//*p++ = i;
			//*p++ = j;
			*p++ = (j-1) * _x2 + (i-1);
		} else if ( _con[i][j] == '%' ){
			//manX = i;
			//manY = j;
			manXY = (j-1) * _x2 + (i-1);
		}
	}
	*p++ = manXY;
	//*p++ = manY;
	ap = (unsigned char**)p;
	*ap = _now;
}