robotgrid.cpp

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

// RobotGrid.cpp : implementation file
//

#include "stdafx.h"
#include "Robot.h"
#include "RobotGrid.h"

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

/////////////////////////////////////////////////////////////////////////////
// CRobotGrid
ROBOTITEM WhiteRobot;
ROBOTITEM BlackRobot;
RECT  GridRect[MAX_OF_ROW][MAX_OF_COLUMN];
BOOL  bWhiteRobotExsit = FALSE;
BOOL  bBlackRobotExsit = FALSE;
BOOL  bSuccessful = FALSE;

CRobotGrid::CRobotGrid()
{
}

CRobotGrid::~CRobotGrid()
{
}


BEGIN_MESSAGE_MAP(CRobotGrid, CStatic)
	//{{AFX_MSG_MAP(CRobotGrid)
	ON_WM_PAINT()
	ON_WM_LBUTTONDOWN()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CRobotGrid message handlers

void CRobotGrid::DrawGrid(CDC *pdc)
{
	int i,j;
	CRect rect;
	GetClientRect(rect);
	RECT drawRect;
	CPen m_pen(PS_SOLID, 0, RGB(0,0,0));
	CPen *oldpen = pdc->SelectObject(&m_pen);
	int width = rect.Width() / MAX_OF_COLUMN;
	int height = rect.Height() / MAX_OF_ROW;
	for(i = 0; i < MAX_OF_ROW; i++)
	{
		for(j = 0; j < MAX_OF_COLUMN; j ++)
		{
			drawRect.left = rect.left + j * width;
			drawRect.right = drawRect.left + width;
			drawRect.top = rect.top + i * height;
			drawRect.bottom = drawRect.top + height;
			drawRect.right ++;
			drawRect.bottom ++;
			GridRect[i][j] = drawRect;
			pdc->Rectangle(&drawRect);
		}
	}
	pdc->SelectObject(oldpen);
}

void CRobotGrid::OnPaint() 
{
	CPaintDC dc(this); // device context for painting
	
	// TODO: Add your message handler code here
	DrawGrid(&dc);
	if(bBlackRobotExsit)
		DrawRobot(0, &dc);
	if(bWhiteRobotExsit)
		DrawRobot(1, &dc);
	// Do not call CStatic::OnPaint() for painting messages
}

void CRobotGrid::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	int i,j;
	CDC *pdc = GetDC();
	if(bSetWhitePos)
	{
		bSetWhitePos = FALSE;
		for(i = 0; i < MAX_OF_ROW; i ++)
		{
			for(j = 0; j < MAX_OF_COLUMN; j ++)
			{
				if( PtInRect(&GridRect[i][j], point) )
				{
					WhiteRobot.ColumnIndex = j;
					WhiteRobot.RowIndex = i;
					DrawRobot(1, pdc);
					bWhiteRobotExsit = TRUE;
					break;
				}
			}
		}
	}

	if(bSetBlackPos)
	{
		bSetBlackPos = FALSE;
		for(i = 0; i < MAX_OF_ROW; i ++)
		{
			for(j = 0; j < MAX_OF_COLUMN; j ++)
			{
				if( PtInRect(&GridRect[i][j], point) )
				{
					BlackRobot.ColumnIndex = j;
					BlackRobot.RowIndex = i;
					DrawRobot(0, pdc);
					bBlackRobotExsit = TRUE;
					break;
				}
			}
		}
	}

	CStatic::OnLButtonDown(nFlags, point);
}


void CRobotGrid::DrawRobot(int RobotType, CDC *pdc)
{
	CDC  memDC;
	memDC.CreateCompatibleDC(pdc);
	CBitmap bmp;
	BITMAP  bmpinfo;
	RECT    drawRect;
	if(RobotType == 0)//Black
	{
		drawRect = GridRect[BlackRobot.RowIndex][BlackRobot.ColumnIndex];
		bmp.LoadBitmap(IDB_BLACKBMP);
		memDC.SelectObject(&bmp);
		bmp.GetBitmap(&bmpinfo);
		pdc->StretchBlt(drawRect.left+1, drawRect.top+1, drawRect.right - drawRect.left-2,
			   drawRect.bottom - drawRect.top - 2, &memDC, 0, 0, bmpinfo.bmWidth, bmpinfo.bmHeight, SRCCOPY);
	}
	else
	{
		drawRect = GridRect[WhiteRobot.RowIndex][WhiteRobot.ColumnIndex];
		bmp.LoadBitmap(IDB_WHITEBMP);
		memDC.SelectObject(&bmp);
		bmp.GetBitmap(&bmpinfo);
		pdc->StretchBlt(drawRect.left+1, drawRect.top+1, drawRect.right - drawRect.left-2,
			   drawRect.bottom - drawRect.top -2, &memDC, 0, 0, bmpinfo.bmWidth, bmpinfo.bmHeight, SRCCOPY);
	
	}
	memDC.DeleteDC();
}

void CRobotGrid::EraseRobot(int RobotType)
{
	CDC *pdc = GetDC();
	RECT rect;
	CPen m_pen(PS_SOLID, 0, RGB(0, 0, 0) );
	CPen *oldpen = pdc->SelectObject(&m_pen);
	if(RobotType == 0)//black
	{
		rect = GridRect[BlackRobot.RowIndex][BlackRobot.ColumnIndex];
		pdc->Rectangle(&rect);
	}
	else
	{
		rect = GridRect[WhiteRobot.RowIndex][WhiteRobot.ColumnIndex];
		pdc->Rectangle(&rect);
	}
	pdc->SelectObject(oldpen);
	ReleaseDC(pdc);
}

void CRobotGrid::BlackCreateTree(SEARCHITEM *&pRoot)
{
	int TempValue;
	if(pRoot->Depth == 0)
	{
		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)
				BlackCreateTree(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)
				BlackCreateTree(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)
				BlackCreateTree(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)
				BlackCreateTree(pSearchItem);
		}
	}
	else if(pRoot->Depth ==1)
	{
		if(pRoot->White.ColumnIndex - 1 >= 0)
		{
			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[0] = pSearchItem;
			if(pSearchItem->Depth < 2)
				BlackCreateTree(pSearchItem);
		}

		if(pRoot->White.RowIndex - 1 >= 0)
		{
			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[1] = pSearchItem;
			if(pSearchItem->Depth < 2)
				BlackCreateTree(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)
				BlackCreateTree(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)
				BlackCreateTree(pSearchItem);
		}

	}

}


void CRobotGrid::WhiteCreateTree(SEARCHITEM *& pRoot)
{
	int TempValue;
	if(pRoot->Depth == 0)
	{
		if(pRoot->White.ColumnIndex - 1 >= 0)
		{
			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[0] = pSearchItem;
			if(pSearchItem->Depth < 2)
				WhiteCreateTree(pSearchItem);
		}

		if(pRoot->White.RowIndex - 1 >= 0)
		{
			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);