astar.cpp

推箱子游戏 为研究A*寻路算法的实现

// Astar.cpp: implementation of the CAstar class.
//A*寻路算法
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Astar.h"

//////////////////////////////////////////////////////////////////////
// A*算法构造函数说明：
//starpoint参数：      人物起始点
//endpoint参数：       A*寻路终点
//////////////////////////////////////////////////////////////////////


CAstar::CAstar(POINT starpoint,POINT endpoint)
{
	astarpoint = starpoint;
	aendpoint = endpoint;
}

CAstar::~CAstar()
{

}

//backpoint[]参数：  A*找到的最佳路径返回点数组,若地图不能到达返回0
//map[9][8]参数：      地图信息
//返回值为到达终点所需步数
int CAstar::GetWay(int astarmap[9][8],POINT backpoint[])
{
	n=0;
	bn=0;
	bspt = astarpoint;
	cpt[n].point = astarpoint;
	cpt[n].ckclient = FALSE;
	cpt[n].pv = 100;
	cpt[n].fp = bn;
	POINT cpoint;
	int minpv=0;       //最小pv值的点的索引号
	int err=n;         //检查是否无点可加
    for(int j=0;j<56;j++)
	{
		for(int i=0;i<4;i++)    //循环查找上、下、左、右四点
		{
			switch(i)
			{
			case 0:
				cpoint = LPoint(bspt);  
				break;
			case 1:
				cpoint = RPoint(bspt);
				break;
			case 2:
				cpoint = UPoint(bspt);
				break;
			case 3:
				cpoint = DPoint(bspt);
				break;
			}
			
			if(SAPoint(cpoint))     //检索左点是否是地图许可范围内
			{
				if(OWolk(astarmap,cpoint))//检查地图是否允许通行
				{
					if(!SSPoint(cpoint))  //检索左点是否在结构体内
					{						
						n+=1;
						FSPoint(cpoint);    //填充结构体
						
						if(CTwoPt(cpoint, aendpoint))    //判断该点是否是终点
						{
							return BackPath(backpoint,n);  
						}				
					}
				}
			}
		}
		if(err == n)                //检查是否已无点可查
		{
			int e = -1;
			for(int i=0;i<=n;i++)
			{
				if(!cpt[i].ckclient)
					e+=1;
			}
			if(e == n)
			{
				backpoint[0] = astarpoint;
				return 0;
			}
		}
		else
			err = n;
		minpv = SFMinPv();
		cpt[minpv].ckclient = FALSE;    //将具有最小pv值的点移出待查点
		bspt = cpt[minpv].point;         //将其置为基点
		bn = minpv;         //设置基点记录  
	}	
	return 0;
}

//比较两点是否相等
BOOL CAstar::CTwoPt(POINT point1, POINT point2)
{
	if((point1.x == point2.x) && (point1.y == point2.y))
		return TRUE;
	return FALSE;
}

//返回左点
POINT CAstar::LPoint(POINT point)
{
	POINT lpoint;
    lpoint.x=point.x-1;
	lpoint.y=point.y;
	return lpoint;
}
//返回右点
POINT CAstar::RPoint(POINT point)
{
	POINT rpoint;
	rpoint.x=point.x+1;
	rpoint.y=point.y;
	return rpoint;
}
//返回上点
POINT CAstar::UPoint(POINT point)
{
	POINT upoint;
	upoint.x=point.x;
	upoint.y=point.y-1;
	return upoint;
}
//返回下点
POINT CAstar::DPoint(POINT point)
{
	POINT dpoint;
	dpoint.x=point.x;
	dpoint.y=point.y+1;
	return dpoint;
}

//检查一点是否在地图允许范围之内
BOOL CAstar::SAPoint(POINT point)
{
    if(point.x>0 && point.x<8 && point.y>0 && point.y<9)
		return TRUE;
	return FALSE;
}
//检查一点是否允许通行
BOOL CAstar::OWolk(int astarmap[9][8],POINT point)
{
	if(!astarmap[point.y][point.x])
		return TRUE;
	return FALSE;
}

//检查一个点是否在结构体中
BOOL CAstar::SSPoint(POINT point)
{
    for(int i=0;i<=n;i++)
	{
		if(CTwoPt(point,cpt[i].point))
			return TRUE;
	}
	return FALSE;
}

//计算一个点的PV值
int CAstar::KclaterPv(POINT point)
{
	int pv;
	return pv=abs(point.x-aendpoint.x)+abs(point.y-aendpoint.y);
}

//用一个点填充结构体
void CAstar::FSPoint(POINT point)
{
    cpt[n].point = point;              //加载点
	cpt[n].ckclient = TRUE;            //置待查为真                 
	cpt[n].fp = bn;
	cpt[n].pv = KclaterPv(point);
}

//查找最小PV值，返回结构记录
int CAstar::SFMinPv()
{
	int minpv=100,minsn = 0;
	for(int i=0;i<=n;i++)
	{
		if(cpt[i].ckclient)
		{
			if(cpt[i].pv<minpv)
			{
				minpv = cpt[i].pv;
				minsn = i;
			}
		}
	}
	return minsn;

}
//取得返回路径,函数返回步数
//path[56] 路径数组
//lastn 终点结构索引号
int CAstar::BackPath(POINT backpoint[],int lastn)   
{
	int cout = 0;
	POINT npoint[56];

	for(int i=0;i<56;i++)
	{
		npoint[i] = cpt[lastn].point;
		lastn = cpt[lastn].fp ;
		cout+=1;
		if(lastn == 0)
		{
			npoint[cout]=astarpoint;
			i=56;
		}
	}	
    int k=cout;
	for(i=0;i<=k;i++)
	{
		backpoint[i] = npoint[cout];
		cout-=1;
	}
	return k;
}