robotgrid.cpp

该程序实现两个机器人在一个二维网格中的自动追捕。通过方向键手动控制机器人A走步

			if(TempValue > pRoot->MaxValue)
				pRoot->MaxValue = TempValue;
			if(TempValue < pRoot->MinValue)
				pRoot->MinValue = TempValue;
			pRoot->pChildItem[1] = pSearchItem;
			if(pSearchItem->Depth < 2)
				WhiteCreateTree(pSearchItem);
		}	

		if(pRoot->White.ColumnIndex + 1 < MAX_OF_COLUMN)
		{
			SEARCHITEM *pSearchItem = new SEARCHITEM;
			memset(pSearchItem, 0, sizeof(SEARCHITEM));
			pSearchItem->MaxValue = -1000;
			pSearchItem->MinValue = 1000;
			
			pSearchItem->Depth = pRoot->Depth + 1;
			pSearchItem->White.ColumnIndex = pRoot->White.ColumnIndex + 1;
			pSearchItem->White.RowIndex = pRoot->White.RowIndex;
			pSearchItem->Black = pRoot->Black;
			TempValue = abs(pSearchItem->White.ColumnIndex - pSearchItem->Black.ColumnIndex) +
				     abs(pSearchItem->White.RowIndex - pSearchItem->Black.RowIndex);
			if(TempValue > pRoot->MaxValue)
				pRoot->MaxValue = TempValue;
			if(TempValue < pRoot->MinValue)
				pRoot->MinValue = TempValue;
			pRoot->pChildItem[2] = pSearchItem;
			if(pSearchItem->Depth < 2)
				WhiteCreateTree(pSearchItem);
		}

		if(pRoot->White.RowIndex + 1 <	MAX_OF_ROW)
		{
			SEARCHITEM *pSearchItem = new SEARCHITEM;
			memset(pSearchItem, 0, sizeof(SEARCHITEM));
			pSearchItem->MaxValue = -1000;
			pSearchItem->MinValue = 1000;
			
			pSearchItem->Depth = pRoot->Depth + 1;
			pSearchItem->White.ColumnIndex = pRoot->White.ColumnIndex;
			pSearchItem->White.RowIndex = pRoot->White.RowIndex + 1;
			pSearchItem->Black = pRoot->Black;
			TempValue = abs(pSearchItem->White.ColumnIndex - pSearchItem->Black.ColumnIndex) +
				     abs(pSearchItem->White.RowIndex - pSearchItem->Black.RowIndex);
			if(TempValue > pRoot->MaxValue)
				pRoot->MaxValue = TempValue;
			if(TempValue < pRoot->MinValue)
				pRoot->MinValue = TempValue;
				pRoot->pChildItem[3] = pSearchItem;
			if(pSearchItem->Depth < 2)
				WhiteCreateTree(pSearchItem);
		}
	}
	else if(pRoot->Depth ==1)
	{
		if(pRoot->Black.ColumnIndex - 1 >= 0)
		{
			SEARCHITEM *pSearchItem = new SEARCHITEM;
			memset(pSearchItem, 0, sizeof(SEARCHITEM));
			pSearchItem->MaxValue = -1000;
			pSearchItem->MinValue = 1000;
			
			pSearchItem->Depth = pRoot->Depth + 1;
			pSearchItem->Black.ColumnIndex = pRoot->Black.ColumnIndex - 1;
			pSearchItem->Black.RowIndex = pRoot->Black.RowIndex;
			pSearchItem->White = pRoot->White;
			TempValue = abs(pSearchItem->White.ColumnIndex - pSearchItem->Black.ColumnIndex) +
				     abs(pSearchItem->White.RowIndex - pSearchItem->Black.RowIndex);
			if(TempValue > pRoot->MaxValue)
				pRoot->MaxValue = TempValue;
			if(TempValue < pRoot->MinValue)
				pRoot->MinValue = TempValue;
			pRoot->pChildItem[0] = pSearchItem;
			if(pSearchItem->Depth < 2)
				WhiteCreateTree(pSearchItem);
		}

		if(pRoot->Black.RowIndex - 1 >= 0)
		{
			SEARCHITEM *pSearchItem = new SEARCHITEM;
			memset(pSearchItem, 0, sizeof(SEARCHITEM));
			pSearchItem->MaxValue = -1000;
			pSearchItem->MinValue = 1000;
			
			pSearchItem->Depth = pRoot->Depth + 1;
			pSearchItem->Black.ColumnIndex = pRoot->Black.ColumnIndex;
			pSearchItem->Black.RowIndex = pRoot->Black.RowIndex - 1;
			pSearchItem->White = pRoot->White;
			TempValue = abs(pSearchItem->White.ColumnIndex - pSearchItem->Black.ColumnIndex) +
				     abs(pSearchItem->White.RowIndex - pSearchItem->Black.RowIndex);
			if(TempValue > pRoot->MaxValue)
				pRoot->MaxValue = TempValue;
			if(TempValue < pRoot->MinValue)
				pRoot->MinValue = TempValue;
			pRoot->pChildItem[1] = pSearchItem;
			if(pSearchItem->Depth < 2)
				WhiteCreateTree(pSearchItem);
		}	

		if(pRoot->Black.ColumnIndex + 1 < MAX_OF_COLUMN)
		{
			SEARCHITEM *pSearchItem = new SEARCHITEM;
			memset(pSearchItem, 0, sizeof(SEARCHITEM));
			pSearchItem->MaxValue = -1000;
			pSearchItem->MinValue = 1000;
			
			pSearchItem->Depth = pRoot->Depth + 1;
			pSearchItem->Black.ColumnIndex = pRoot->Black.ColumnIndex + 1;
			pSearchItem->Black.RowIndex = pRoot->Black.RowIndex;
			pSearchItem->White = pRoot->White;
			TempValue = abs(pSearchItem->White.ColumnIndex - pSearchItem->Black.ColumnIndex) +
				     abs(pSearchItem->White.RowIndex - pSearchItem->Black.RowIndex);
			if(TempValue > pRoot->MaxValue)
				pRoot->MaxValue = TempValue;
			if(TempValue < pRoot->MinValue)
				pRoot->MinValue = TempValue;
			pRoot->pChildItem[2] = pSearchItem;
			if(pSearchItem->Depth < 2)
				WhiteCreateTree(pSearchItem);
		}

		if(pRoot->Black.RowIndex + 1 <	MAX_OF_ROW)
		{
			SEARCHITEM *pSearchItem = new SEARCHITEM;
			memset(pSearchItem, 0, sizeof(SEARCHITEM));
			pSearchItem->MaxValue = -1000;
			pSearchItem->MinValue = 1000;
			
			pSearchItem->Depth = pRoot->Depth + 1;
			pSearchItem->Black.ColumnIndex = pRoot->Black.ColumnIndex;
			pSearchItem->Black.RowIndex = pRoot->Black.RowIndex + 1;
			pSearchItem->White = pRoot->White;
			TempValue = abs(pSearchItem->White.ColumnIndex - pSearchItem->Black.ColumnIndex) +
				     abs(pSearchItem->White.RowIndex - pSearchItem->Black.RowIndex);
			if(TempValue > pRoot->MaxValue)
				pRoot->MaxValue = TempValue;
			if(TempValue < pRoot->MinValue)
				pRoot->MinValue = TempValue;
				pRoot->pChildItem[3] = pSearchItem;
			if(pSearchItem->Depth < 2)
				WhiteCreateTree(pSearchItem);
		}

	}


}

BOOL CRobotGrid::CheckIfSamePos(ROBOTITEM item1, ROBOTITEM item2)
{
	if(item1.ColumnIndex == item2.ColumnIndex && item1.RowIndex == item2.RowIndex)
		return TRUE;
	else
		return FALSE;
}


void CRobotGrid::BlackNextStep(SEARCHITEM *pRoot)
{
	int  MaxTemp = -10000;
	ROBOTITEM Temp;
	if(pRoot->pChildItem[0] != NULL)
	if(pRoot->pChildItem[0]->MinValue > MaxTemp && !CheckIfSamePos(pRoot->pChildItem[0]->Black, WhiteRobot) )
	{
		MaxTemp = pRoot->pChildItem[0]->MinValue;
		Temp = pRoot->pChildItem[0]->Black;
	}

	if(pRoot->pChildItem[1] != NULL )
	if(pRoot->pChildItem[1]->MinValue > MaxTemp && !CheckIfSamePos(pRoot->pChildItem[1]->Black, WhiteRobot))
	{
		MaxTemp = pRoot->pChildItem[1]->MinValue;
		Temp = pRoot->pChildItem[1]->Black;
	}

	if(pRoot->pChildItem[2] != NULL)
	if(pRoot->pChildItem[2]->MinValue > MaxTemp && !CheckIfSamePos(pRoot->pChildItem[2]->Black, WhiteRobot))
	{
		MaxTemp = pRoot->pChildItem[2]->MinValue;
		Temp = pRoot->pChildItem[2]->Black;
	}

	if(pRoot->pChildItem[3] != NULL)
	if(pRoot->pChildItem[3]->MinValue > MaxTemp && !CheckIfSamePos(pRoot->pChildItem[3]->Black, WhiteRobot))
	{
		MaxTemp = pRoot->pChildItem[3]->MinValue;
		Temp = pRoot->pChildItem[3]->Black;
	}
/*	CString str;
	str.Format("Col:%d Row:%d", Temp.ColumnIndex, Temp.RowIndex);
	AfxMessageBox(str);
*/
	CDC *pdc = GetDC();
	EraseRobot(0);
	BlackRobot = Temp;
	DrawRobot(0, pdc);
	
	ReleaseDC(pdc);
}


void CRobotGrid::WhiteNextStep(SEARCHITEM *pRoot)
{
	int  MinTemp = 10000;
	ROBOTITEM Temp;
	if(pRoot->pChildItem[0] != NULL)
	if(pRoot->pChildItem[0]->MaxValue < MinTemp)
	{
		MinTemp = pRoot->pChildItem[0]->MaxValue;
		Temp = pRoot->pChildItem[0]->White;
	}

	if(pRoot->pChildItem[1] != NULL)
	if(pRoot->pChildItem[1]->MaxValue < MinTemp)
	{
		MinTemp = pRoot->pChildItem[1]->MaxValue;
		Temp = pRoot->pChildItem[1]->White;
	}

	if(pRoot->pChildItem[2] != NULL)
	if(pRoot->pChildItem[2]->MaxValue < MinTemp)
	{
		MinTemp = pRoot->pChildItem[2]->MaxValue;
		Temp = pRoot->pChildItem[2]->White;
	}

	if(pRoot->pChildItem[3] != NULL)
	if(pRoot->pChildItem[3]->MaxValue < MinTemp)
	{
		MinTemp = pRoot->pChildItem[3]->MaxValue;
		Temp = pRoot->pChildItem[3]->White;
	}
/*	CString str;
	str.Format("Col:%d Row:%d", Temp.ColumnIndex, Temp.RowIndex);
	AfxMessageBox(str);
*/
	CDC *pdc = GetDC();
	EraseRobot(1);
	WhiteRobot = Temp;
	DrawRobot(1, pdc);
	if(WhiteRobot.ColumnIndex == BlackRobot.ColumnIndex && WhiteRobot.RowIndex == BlackRobot.RowIndex)
	{
		AfxMessageBox("White已抓住Black了！", MB_ICONINFORMATION);
		bStart = FALSE;
	}
	ReleaseDC(pdc);
}

void CRobotGrid::BlackAutoEscape()
{
	SEARCHITEM *pRoot = new SEARCHITEM;
	memset(pRoot, 0, sizeof(SEARCHITEM));
	pRoot->Black = BlackRobot;
	pRoot->White = WhiteRobot;
	pRoot->MaxValue = -1000;
	pRoot->MinValue = 10000;
	pRoot->Depth = 0;
	BlackCreateTree(pRoot);
	BlackNextStep(pRoot);
	ReleaseMem(pRoot);
}


void CRobotGrid::WhiteAutoCatch()
{
	SEARCHITEM *pRoot = new SEARCHITEM;
	memset(pRoot, 0, sizeof(SEARCHITEM));
	pRoot->Black = BlackRobot;
	pRoot->White = WhiteRobot;
	pRoot->MaxValue = -1;
	pRoot->MinValue = 10000;
	pRoot->Depth = 0;
	WhiteCreateTree(pRoot);
	WhiteNextStep(pRoot);
	ReleaseMem(pRoot);
}


BOOL CRobotGrid::PreTranslateMessage(MSG* pMsg) 
{
	// TODO: Add your specialized code here and/or call the base class
	if( bStart)
	{
	CDC *pdc = GetDC();
	if(pMsg->message == WM_KEYDOWN)
	{
		if(pMsg->wParam == VK_LEFT)
		{
			if(RobotType == 0 && BlackRobot.ColumnIndex - 1 >= 0)
			{
				EraseRobot(0);
				BlackRobot.ColumnIndex -= 1;
				DrawRobot(0, pdc);
				WhiteAutoCatch();
			}
			if(RobotType == 1 && WhiteRobot.ColumnIndex - 1 >= 0)
			{
				EraseRobot(1);
				WhiteRobot.ColumnIndex -= 1;
				DrawRobot(1, pdc);
				if( CheckIfSamePos(WhiteRobot, BlackRobot) )
				{
					AfxMessageBox("White已经抓住Black了！");
					bStart = FALSE;
				}
				else
					BlackAutoEscape();
			}
		}
		if(pMsg->wParam == VK_RIGHT)
		{
			if(RobotType == 0 && BlackRobot.ColumnIndex + 1 < MAX_OF_COLUMN)
			{
				EraseRobot(0);
				BlackRobot.ColumnIndex += 1;
				DrawRobot(0, pdc);
				WhiteAutoCatch();
			}
			if(RobotType == 1 && WhiteRobot.ColumnIndex + 1 < MAX_OF_COLUMN)
			{
				EraseRobot(1);
				WhiteRobot.ColumnIndex += 1;
				DrawRobot(1, pdc);
				if( CheckIfSamePos(WhiteRobot, BlackRobot) )
				{
					AfxMessageBox("White已经抓住Black了！");
					bStart = FALSE;
				}
				else
					BlackAutoEscape();
			}

		}
		if(pMsg->wParam == VK_UP)
		{
			if(RobotType == 0 && BlackRobot.RowIndex - 1 >= 0)
			{
				EraseRobot(0);
				BlackRobot.RowIndex -= 1;
				DrawRobot(0, pdc);
				WhiteAutoCatch();
			}
			if(RobotType == 1 && WhiteRobot.RowIndex -1 >= 0)
			{
				EraseRobot(1);
				WhiteRobot.RowIndex -= 1;
				DrawRobot(1, pdc);
				if( CheckIfSamePos(WhiteRobot, BlackRobot) )
				{
					AfxMessageBox("White已经抓住Black了！");
					bStart = FALSE;
				}
				else
					BlackAutoEscape();
			}

		}
		if(pMsg->wParam == VK_DOWN)
		{	
			if(RobotType == 0 && BlackRobot.RowIndex + 1 < MAX_OF_ROW)
			{
				EraseRobot(0);
				BlackRobot.RowIndex += 1;
				DrawRobot(0, pdc);
				WhiteAutoCatch();
			}
			if(RobotType == 1 && WhiteRobot.RowIndex + 1 < MAX_OF_ROW)
			{
				EraseRobot(1);
				WhiteRobot.RowIndex += 1;
				DrawRobot(1, pdc);
				if( CheckIfSamePos(WhiteRobot, BlackRobot) )
				{
					AfxMessageBox("White已经抓住Black了！");
					bStart = FALSE;
				}
				else
					BlackAutoEscape();
			}

		}
		return TRUE;
	}
	ReleaseDC(pdc);
	}
	return CStatic::PreTranslateMessage(pMsg);
}


void CRobotGrid::ReleaseMem(SEARCHITEM *pRoot)
{
	if(pRoot->Depth <= 2)
	{
		if(pRoot->pChildItem[0] != NULL)
			ReleaseMem(pRoot->pChildItem[0]);
		if(pRoot->pChildItem[1] != NULL)
			ReleaseMem(pRoot->pChildItem[1]);
		if(pRoot->pChildItem[2] != NULL)
			ReleaseMem(pRoot->pChildItem[2]);
		if(pRoot->pChildItem[3] != NULL)
			ReleaseMem(pRoot->pChildItem[3]);
		TRACE("Column:%d Row:%d\n", pRoot->White.ColumnIndex, pRoot->White.RowIndex); 
		delete pRoot;
	}
}