astar.cpp

寻径算法演示平台~~提供给计算机博弈爱好者参考学习

// AStar.cpp: implementation of the CAStar class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "SearchPath.h"
#include "AStar.h"


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

extern map[Height][Width];

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CAStar::CAStar()
{
	for(int i=0;i<Height;i++)
	{
		for(int j=0;j<Width;j++)
		{
			m_close[i][j]=0;
			m_open[i][j]=0;
			m_element[i][j] = &node[i][j];
			m_element[i][j]->close=0;
			m_element[i][j]->open=0;
			m_element[i][j]->parent=NULL;
			m_element[i][j]->fore=NULL;
			m_element[i][j]->next=NULL;
			m_element[i][j]->f=-1;
		}
	}
	targetX=0;
	targetY=0;
}

CAStar::~CAStar()
{

}

int CAStar::A()
{
	while(head!=NULL)
	{
		as_node *tempHead;
		
		if(head->next==NULL)
		{
			tempHead=NULL;
		}
		else
		{
			tempHead=head->next;//head下一个节点作为新的链表头指针
			
			head->next->fore=NULL;
		}
		m_element[head->y][head->x]->open=0;
		m_element[head->y][head->x]->close=1;//把head放进close表
		
		if(map[head->y][head->x+1]!=-1)//如果临近的方格不是墙壁
		{
			if(m_element[head->y][head->x+1]->close)
			{}
			else if(m_element[head->y][head->x+1]->open)
			{
				int temp = m_element[head->y][head->x]->g+1+m_element[head->y][head->x+1]->h;
				if(m_element[head->y][head->x+1]->f > temp)
				{
					m_element[head->y][head->x+1]->g = m_element[head->y][head->x]->g+1;
					m_element[head->y][head->x+1]->f = temp;
					m_element[head->y][head->x+1]->parent = m_element[head->y][head->x];
					tempHead=adjustNode(tempHead,m_element[head->y][head->x+1]);
				}
			}	
			else
			{
				if(head->x+1==targetX && head->y==targetY){return 1;}//找到终点！//修改这里
				
				//as_node *node=new as_node;
				as_node *node=m_element[head->y][head->x+1];
				node->x=head->x+1;//修改这里
				node->y=head->y;//修改这里
				node->open=1;
				node->close=0;
				node->parent=m_element[head->y][head->x];
				node->g=node->parent->g+1;
				node->h=abs(node->x - targetX) + abs(node->y - targetY);
				node->f=node->g + node->h;
				tempHead=insertNode(tempHead,node);
			}
			//最后记住把head放进close表
		}
		
		if(map[head->y][head->x-1]!=-1)//如果临近的方格不是墙壁
		{
			if(m_element[head->y][head->x-1]->close)
			{}
			else if(m_element[head->y][head->x-1]->open)
			{
				int temp = m_element[head->y][head->x]->g+1+m_element[head->y][head->x-1]->h;
				if(m_element[head->y][head->x-1]->f > temp)
				{
					m_element[head->y][head->x-1]->g = m_element[head->y][head->x]->g+1;
					m_element[head->y][head->x-1]->f = temp;
					m_element[head->y][head->x-1]->parent=m_element[head->y][head->x];
					tempHead=adjustNode(tempHead,m_element[head->y][head->x-1]);
				}
			}	
			else
			{
				if(head->x-1==targetX && head->y==targetY){return 1;}//找到终点！//修改这里
				
				//as_node *node=new as_node;
				as_node *node=m_element[head->y][head->x-1];
				node->x=head->x-1;//修改这里
				node->y=head->y;//修改这里
				node->open=1;
				node->close=0;
				node->parent=m_element[head->y][head->x];
				node->g=node->parent->g+1;
				node->h=abs(node->x - targetX) + abs(node->y - targetY);
				node->f=node->g + node->h;
				tempHead=insertNode(tempHead,node);
			}
			//最后记住把head放进close表
		}
		
		if(map[head->y+1][head->x]!=-1)//如果临近的方格不是墙壁
		{
			if(m_element[head->y+1][head->x]->close)
			{}
			else if(m_element[head->y+1][head->x]->open)
			{
				int temp = m_element[head->y][head->x]->g+1+m_element[head->y+1][head->x]->h;
				if(m_element[head->y+1][head->x]->f > temp)
				{
					m_element[head->y+1][head->x]->g = m_element[head->y][head->x]->g+1;
					m_element[head->y+1][head->x]->f = temp;
					m_element[head->y+1][head->x]->parent=m_element[head->y+1][head->x];
					tempHead=adjustNode(tempHead,m_element[head->y+1][head->x]);
				}
			}	
			else
			{
				if(head->x==targetX && head->y+1==targetY){return 1;}//找到终点！//修改这里
				
				//as_node *node=new as_node;
				as_node *node=m_element[head->y+1][head->x];
				node->x=head->x;//修改这里
				node->y=head->y+1;//修改这里
				node->open=1;
				node->close=0;
				node->parent=m_element[head->y][head->x];
				node->g=node->parent->g+1;
				node->h=abs(node->x - targetX) + abs(node->y - targetY);
				node->f=node->g + node->h;
				tempHead=insertNode(tempHead,node);
			}
			//最后记住把head放进close表
		}
		
		
		if(map[head->y-1][head->x]!=-1)//如果临近的方格不是墙壁
		{
			if(m_element[head->y-1][head->x]->close)
			{}
			else if(m_element[head->y-1][head->x]->open)
			{
				int temp = m_element[head->y][head->x]->g+1+m_element[head->y-1][head->x]->h;
				if(m_element[head->y-1][head->x]->f > temp)
				{
					m_element[head->y-1][head->x]->g = m_element[head->y][head->x]->g+1;
					m_element[head->y-1][head->x]->f = temp;
					m_element[head->y-1][head->x]->parent=m_element[head->y-1][head->x];
					tempHead=adjustNode(tempHead,m_element[head->y-1][head->x]);
				}
			}	
			else
			{
				if(head->x==targetX && head->y-1==targetY){return 1;}//找到终点！//修改这里
				
				//as_node *node=new as_node;
				as_node *node=m_element[head->y-1][head->x];
				node->x=head->x;//修改这里
				node->y=head->y-1;//修改这里
				node->open=1;
				node->close=0;
				node->parent=m_element[head->y][head->x];
				node->g=node->parent->g+1;
				node->h=abs(node->x - targetX) + abs(node->y - targetY);
				node->f=node->g + node->h;
				tempHead=insertNode(tempHead,node);
			}
			//最后记住把head放进close表
		}		
		head=tempHead;
	}
	return 0;//如果head是NULL表示open表已为空，所以找不到路径
}


as_node *CAStar::adjustNode(as_node *head,as_node *node)
{
	if(node->next != NULL && node->fore != NULL)//如果node存在与open链表中，而且在中间
	{
		if(node->f >= node->fore->f && node->f <= node->next->f)
		{
			return head;
		}
		else
		{
			//把node取出链表
			node->fore->next = node->next;
			node->next->fore = node->fore;
			return insertNode(head,node);
		}
	}
	else if(node->next!=NULL)//如果node存在于open链表中，而且处于头部
	{
		if(node->f <= node->next->f)
		{
			return head;
		}
		else
		{
			//把node取出链表
			node->next->fore=NULL;
			return insertNode(head,node);
		}
	}
	else if(node->fore!=NULL)//如果node存在于open链表中，而且处于尾部
	{
		if(node->f >= node->fore->f)
		{
			return head;
		}
		else
		{
			//把node取出链表
			node->fore->next=NULL;
			return insertNode(head,node);
		}
	}
	//前面如果没有返回值就代表node不适合原来链表中的位置
	return insertNode(head,node);
}


//向open链表插入一个新的节点包括排序工作，但是不负责把原来的节点从open表中取出
as_node *CAStar::insertNode(as_node *head,as_node *node)
{
	as_node *realHead=head;
	if(head==NULL)//如果open表已经为空
	{
		node->fore=NULL;
		node->next=NULL;
		return node;
	}
	if(node->f <= head->f)//把node插入open表的头部
	{
		node->fore=NULL;
		node->next=head;
		head->fore=node;
		return node;
	}

	while(head->next != NULL)
	{
		if(node->f >= head->f && node->f <= head->next->f)
		{
			//把node接入链表的中间
			head->next->fore=node;
			node->next=head->next;
			head->next=node;
			node->fore=head;
			return realHead;
		}
		head=head->next;
	}
	//while结构后head不再是原来的头指针了

	//如果经过以上的操作还没返回，则表示node应该至于open表的末尾
	head->next=node;
	node->fore=head;
	node->next=NULL;
	return realHead;
}

int CAStar::searchThePath()
{
	for(int i=0;i<Height;i++)
	{
		for(int j=0;j<Width;j++)
		{
			if(map[i][j]==0)
			{
				head = m_element[i][j];
				head->x=j;
				head->y=i;
				head->fore=NULL;
				head->next=NULL;
				head->g=0;
				//head->h=
				head->close=0;
				head->open=1;
				//head->f=
				head->parent=NULL;
			}
			else if(map[i][j]==-3)
			{
				targetX=j;
				targetY=i;
			}
		}
	}
	return A();
}

void CAStar::showThePath(CDC *pDC , int showMode)
{
	
	as_node *tempHead=head;

	CBitmap bm1,bm2,bm3,bm4,bm5,bm6, *pbm;
	BITMAP bmMetric1,bmMetric2;

	bm1.LoadBitmap(IDB_BITMAP7);
	bm2.LoadBitmap(IDB_BITMAP8);
	bm3.LoadBitmap(IDB_BITMAP9);
	bm4.LoadBitmap(IDB_BITMAP11);
	bm5.LoadBitmap(IDB_BITMAP12);//起点
	bm6.LoadBitmap(IDB_BITMAP13);//终点

	bm1.GetBitmap(&bmMetric1);
	bm2.GetBitmap(&bmMetric2);

	CDC memDC;
	memDC.CreateCompatibleDC(pDC);

	pbm = memDC.SelectObject(&bm1);

	memDC.SelectObject(&bm2);




//显示地图
	for(int i = 0; i < Height; i ++)
	{
		for(int j = 0; j < Width;  j ++)
		{
			if(map[i][j]==-1)
			{
				memDC.SelectObject(&bm1);
				pDC->BitBlt(j*bmMetric2.bmWidth, i*bmMetric2.bmHeight,bmMetric1.bmWidth,bmMetric1.bmHeight,&memDC,0,0,SRCCOPY);
				
			}
			
			else if(map[i][j]==0)
			{
				memDC.SelectObject(&bm5);
				pDC->BitBlt(j*bmMetric2.bmWidth, i*bmMetric2.bmHeight,bmMetric2.bmWidth,bmMetric2.bmHeight,&memDC,0,0,SRCCOPY);
			}
			else if(map[i][j]==-3)
			{
				memDC.SelectObject(&bm6);
				pDC->BitBlt(j*bmMetric2.bmWidth, i*bmMetric2.bmHeight,bmMetric2.bmWidth,bmMetric2.bmHeight,&memDC,0,0,SRCCOPY);
			}
			
			
		}
	}


/*
//显示搜索过的点的f值
	CFont *poldfont,*newfont=new CFont;
	TEXTMETRIC tm;
	newfont->CreateFont(3,0,0,0,FW_NORMAL,0,0,0,GB2312_CHARSET,OUT_DEFAULT_PRECIS,CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,DEFAULT_PITCH,"宋体");
	poldfont=pDC->SelectObject(newfont);
	pDC->GetTextMetrics(&tm);
	
	for(i=0;i<Height;i++)
	{
		for(int j=0;j<Width;j++)
		{
			if(m_element[i][j]->f!=-1)
			{