astarview.cpp

最经典的A星寻路算法,自己写的,感觉很好!

// ASTARView.cpp : implementation of the CASTARView class
//

#include "stdafx.h"
#include "ASTAR.h"

#include "ASTARDoc.h"
#include "ASTARView.h"
#include "FindPath.h"

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

/////////////////////////////////////////////////////////////////////////////
// CASTARView

IMPLEMENT_DYNCREATE(CASTARView, CView)

BEGIN_MESSAGE_MAP(CASTARView, CView)
	//{{AFX_MSG_MAP(CASTARView)
	ON_COMMAND(ID_FINDPATH, OnFindpath)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CASTARView construction/destruction

CASTARView::CASTARView()
{
	// TODO: add construction code here
}

CASTARView::~CASTARView()
{
}

BOOL CASTARView::PreCreateWindow(CREATESTRUCT& cs)
{
	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CASTARView drawing

/////////////////////////////////////////////////////////////////////////////
// CASTARView printing

BOOL CASTARView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CASTARView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CASTARView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

#ifdef _DEBUG
void CASTARView::AssertValid() const
{
	CView::AssertValid();
}

void CASTARView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CASTARDoc* CASTARView::GetDocument()
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CASTARDoc)));
	return (CASTARDoc*)m_pDocument;
}
#endif

void CASTARView::OnDraw(CDC* pDC)
{
	CASTARDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	int i,j;
	for (i=0;i<10;i++)
	{
		for (j=0;j<10;j++)
		{
			if (map[i][j])
			{
				pDC->SelectStockObject(BLACK_BRUSH);
				pDC->Rectangle(j*20,i*20,(j+1)*20,(i+1)*20);
			}
			else
			{
				pDC->SelectStockObject(NULL_BRUSH);
				pDC->Rectangle(j*20,i*20,(j+1)*20,(i+1)*20);
			}
		}
	}
}

void CASTARView::OnFindpath() 
{
	CDC *pDC = GetDC();
	Start.x = 0;
	Start.y = 0;
	End.x = 9;
	End.y = 9;
	pDC->SelectStockObject(BLACK_BRUSH);
	pDC->Ellipse(Start.x*20,Start.y*20,
		(Start.x+1)*20,(Start.y+1)*20);
	pDC->Ellipse(End.x*20,End.y*20,
		(End.x+1)*20,(End.y+1)*20);

	POINT	currentpos, temppos;
	Node	*node, *tempnode;
	List	openlist;
	List	closelist;
	openlist.head=(Node *)malloc(sizeof(Node));
	closelist.head=(Node *)malloc(sizeof(Node));
	openlist.head->next = NULL;
	openlist.head->father = NULL;
	closelist.head->next = NULL;
	closelist.head->father = NULL;

	openlist.Insert(Start, NULL);
	
	pDC->SelectStockObject(NULL_BRUSH);
	while(!openlist.Empty())
	{
		node = openlist.GetTop(&currentpos);
		
		if (currentpos.y>0)	//上
		{
			temppos.x = currentpos.x;
			temppos.y = currentpos.y - 1;
			if (!map[temppos.y][temppos.x])	//若不为阻碍
			{
				if (!openlist.Exsit(temppos) && !closelist.Exsit(temppos))
				{
					openlist.Insert(temppos, node, GetAssess(temppos, Start, End));
					if (temppos.x == End.x && temppos.y == End.y)
						break;
				}
			}
		}
		if (currentpos.y<9)	//下
		{
			temppos.x = currentpos.x;
			temppos.y = currentpos.y + 1;
			if (!map[temppos.y][temppos.x])	//若不为阻碍
			{
				if (!openlist.Exsit(temppos) && !closelist.Exsit(temppos))
				{
					openlist.Insert(temppos, node, GetAssess(temppos, Start, End));
					if (temppos.x == End.x && temppos.y == End.y)
						break;
				}
			}
		}
		if (currentpos.x>0)	//左
		{
			temppos.x = currentpos.x - 1;
			temppos.y = currentpos.y;
			if (!map[temppos.y][temppos.x])	//若不为阻碍
			{
				if (!openlist.Exsit(temppos) && !closelist.Exsit(temppos))
				{
					openlist.Insert(temppos, node, GetAssess(temppos, Start, End));
					if (temppos.x == End.x && temppos.y == End.y)
						break;
				}
			}
		}
		if (currentpos.x<9)	//右
		{
			temppos.x = currentpos.x + 1;
			temppos.y = currentpos.y;
			if (!map[temppos.y][temppos.x])	//若不为阻碍
			{
				if (!openlist.Exsit(temppos) && !closelist.Exsit(temppos))
				{
					openlist.Insert(temppos, node, GetAssess(temppos, Start, End));
					if (temppos.x == End.x && temppos.y == End.y)
						break;
				}
			}
		}	
		openlist.Delete(currentpos);
		closelist.Insert(node);
				
	}

	if (openlist.Empty())
	{
		MessageBox("没有找到终点");
		return;
	}

	tempnode = node;
	while (tempnode->father!=NULL)
	{		
		pDC->Ellipse(tempnode->pos.x*20,tempnode->pos.y*20,
			(tempnode->pos.x+1)*20,(tempnode->pos.y+1)*20);
		tempnode = tempnode->father;
	}
}