winmain.cpp

这是一个自动走迷宫的寻路算法。 可能会有人需要

#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <list>

using namespace std;

#define WINDOW_CLASS_NAME "WINCLASS1"

#define KEYDOWN(vk)		(GetAsyncKeyState(vk)&0x8000 ? 1 : 0)
#define EDGE_WIDTH 30
#define CELL_NUM 10

#define ID_BUTTON 1


struct Node
{
	int x,y;
	int b;//表示当前点是否能通过
};
#define  INIT_NODE(x) {-1,-1,x}

struct list_node
{
	int x,y;
};

list<list_node> list_path;
list<list_node>::iterator iter;

Node mapArray[CELL_NUM][CELL_NUM] = {0};

bool bKillTimer = false;

class Button
{
private:
	HWND m_hwnd;
public:
	Button(LPCTSTR str, DWORD style, RECT rect, HWND hwndParant, HINSTANCE hinst, int identify);
};

Button::Button(LPCTSTR str, DWORD style, RECT rect, HWND hwndParant, HINSTANCE hinst, int identify)
{
	m_hwnd = CreateWindow("button", str, style, rect.left, rect.top, rect.right-rect.left, rect.bottom-rect.top, hwndParant, (HMENU)identify,hinst,NULL);
}



void FindPath(Node (*pmap)[CELL_NUM], int i, int j, int m, int n)
{
	static bool found = true;
	if(i<0 || i>=CELL_NUM || j<0 || j>=CELL_NUM)
		return;
	if(i==CELL_NUM-1 && j==CELL_NUM-1)
	{
		pmap[i][j].b = 2;
		pmap[i][j].x = m;
		pmap[i][j].y = n;
		found = false;
		return;
	}
	if(pmap[i][j].b==0 && found)
	{
		pmap[i][j].x = m;
		pmap[i][j].y = n;
		pmap[i][j].b = 2;//表示当前结点已经被走过了。

		FindPath(pmap,i+1,j, i,j);
		FindPath(pmap,i,j+1, i,j);
		FindPath(pmap,i,j-1, i,j);
		FindPath(pmap,i-1,j, i,j);
	}
}


void doPath(Node (*pmap)[CELL_NUM])
{
	list_node * ptemp;
	int i=CELL_NUM-1,j=CELL_NUM-1,temp=0;
	while (pmap[i][j].x != -1 && pmap[i][j].y != -1)
	{
		ptemp = new list_node;
		ptemp->x = i;ptemp->y = j;
		list_path.push_back(*ptemp);

		temp = pmap[i][j].x;
		j = pmap[i][j].y;
		i = temp;
		delete ptemp;
	}
	ptemp = new list_node;
	ptemp->x = 0;ptemp->y = 0;

	list_path.push_back(*ptemp);
	delete ptemp;

	//return plist;

}

void InitMap()
{
	Node map_temp[CELL_NUM][CELL_NUM] = {	{INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0)},			//INIT_NODE(1)行
											{INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1)},			//2行
											{INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0)},			//3行
											{INIT_NODE(1),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(0)},			//4行
											{INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0)},			//5行
											{INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(0)},			//6行
											{INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0)},			//7行
											{INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1)},			//8行
											{INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(1),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(0)},			//9行
											{INIT_NODE(0),INIT_NODE(0),INIT_NODE(0),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(1),INIT_NODE(0)}};			//10行
	memcpy(mapArray, map_temp, sizeof(map_temp));
}

void DrawMap(HWND hwnd, HDC hdc, bool draw_path)
{
	RECT rect;
	GetClientRect(hwnd, &rect);
	int x = (rect.right-EDGE_WIDTH*10)/2;
	int y = (rect.bottom-EDGE_WIDTH*10)/2;

	for(int j=0;j<=CELL_NUM;++j)
	{
		MoveToEx(hdc, x+EDGE_WIDTH*j, y, NULL);
		LineTo(hdc, x+EDGE_WIDTH*j, y+EDGE_WIDTH*CELL_NUM);
	}
	for(int j=0;j<=CELL_NUM;++j)
	{
		MoveToEx(hdc, x, y+EDGE_WIDTH*j, NULL);
		LineTo(hdc, x+EDGE_WIDTH*CELL_NUM, y+EDGE_WIDTH*j);
	}

	RECT rct;
	HBRUSH hbrush = CreateSolidBrush(RGB(0,0,0));
	for (int i=0;i<CELL_NUM;++i)
	{
		for(int j=0;j<CELL_NUM;++j)
		{
			if(mapArray[i][j].b == 1)
			{
				rct.left = x+EDGE_WIDTH*j;
				rct.top = y+EDGE_WIDTH*i;
				rct.right = x+EDGE_WIDTH*(j+1);
				rct.bottom = y+EDGE_WIDTH*(i+1);
				FillRect(hdc, &rct, hbrush);
			}
		}
	}
	DeleteObject(hbrush);
	
	
	static int count = 0;
	if(draw_path)
	{
		HBRUSH hbrush_path = CreateSolidBrush(RGB(0,255,255));
		if (count<list_path.size())
		{
			++count;
		}
		else
		{
			bKillTimer = true;
		}
		iter = list_path.end();
		--iter;
		for( int i=0; i++<count; --iter)
		{
			rct.left = x+EDGE_WIDTH*(iter->y);
			rct.top = y+EDGE_WIDTH*(iter->x);
			rct.right = x+EDGE_WIDTH*(iter->y+1);
			rct.bottom = y+EDGE_WIDTH*(iter->x+1);
			FillRect(hdc, &rct, hbrush_path);
		}
		DeleteObject(hbrush_path);
	}
	
	
}

LRESULT CALLBACK WindowProc(HWND hwnd, UINT msg, WPARAM wparam, LPARAM lparam)
{
	PAINTSTRUCT		ps;		// used in WM_PAINT
	HDC				hdc;	// handle to a device context

	RECT rect;
	static bool beginDrawPath = false;
	switch(msg)
	{
	case WM_CREATE:

		return 0;
	case WM_COMMAND:
		FindPath(mapArray, 0, 0, -1, -1);
		doPath(mapArray);
		beginDrawPath = true;
		if(!bKillTimer)
			SetTimer(hwnd, 1, 1000, NULL);
		return 0;
	case WM_TIMER:
		//GetClientRect(hwnd, &rect);
		InvalidateRect(hwnd, NULL, TRUE);
		if(bKillTimer)
			KillTimer(hwnd, 1);
		return 0;
	case WM_PAINT: 
		hdc = BeginPaint(hwnd,&ps);	 
		DrawMap(hwnd, hdc,beginDrawPath);
		EndPaint(hwnd,&ps);
		return 0;

	case WM_DESTROY: 
		PostQuitMessage(0);
		return 0;
	}
	return DefWindowProc(hwnd, msg, wparam, lparam);
}
int WINAPI WinMain(	HINSTANCE hinstance,HINSTANCE hprevinstance,LPSTR lpcmdline,int ncmdshow)
{
	HBRUSH hbrush = CreateSolidBrush(RGB(212,208,200));
	WNDCLASSEX winclass;
	winclass.cbSize         = sizeof(WNDCLASSEX);
	winclass.style			= CS_OWNDC | CS_HREDRAW | CS_VREDRAW;
	winclass.lpfnWndProc	= WindowProc;
	winclass.cbClsExtra		= 0;
	winclass.cbWndExtra		= 0;
	winclass.hInstance		= hinstance;
	winclass.hIcon			= LoadIcon(NULL, IDI_APPLICATION);
	winclass.hCursor		= LoadCursor(NULL, IDC_ARROW); 
	winclass.hbrBackground	= hbrush;
	winclass.lpszMenuName	= NULL;
	winclass.lpszClassName	= WINDOW_CLASS_NAME;
	winclass.hIconSm        = LoadIcon(NULL, IDI_APPLICATION);
	

	if (!RegisterClassEx(&winclass))
		return(0);
	
	HWND	hwnd;
	if (!(hwnd = CreateWindowEx(NULL,
								WINDOW_CLASS_NAME,
								"走迷宫",
								(WS_OVERLAPPEDWINDOW | WS_VISIBLE)&~(WS_MAXIMIZEBOX|WS_MINIMIZEBOX),
								200,200,
								600,400,
								NULL,
								NULL,
								hinstance,
								NULL)))	
	return 0;

	RECT rect, btnRect;
	GetClientRect(hwnd, &rect);

	btnRect.left = (rect.right-EDGE_WIDTH*10)/2+EDGE_WIDTH*(CELL_NUM+1);
	btnRect.top = (rect.bottom-EDGE_WIDTH*10)/2;
	btnRect.right = btnRect.left + 100;
	btnRect.bottom = btnRect.top + 30;
	Button btn("开始", (WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON), btnRect, hwnd, hinstance, ID_BUTTON);
	InitMap();

	MSG msg;
	while(GetMessage(&msg, NULL, 0,0))
	{
		TranslateMessage(&msg);
		DispatchMessage(&msg);
		if (KEYDOWN(VK_ESCAPE))
		{
			PostMessage(hwnd, WM_CLOSE, 0, 0);
		}
	}
	DeleteObject(hbrush);
	UnregisterClass(WINDOW_CLASS_NAME, hinstance);
	return 0;
}