#include "StdAfx.h"
#include "GameMir.h"

CGameMir::CDStar::CDStar(CGameMir::CGameMap& map, CGameMir&game) : m_Map(map) , m_DStarArray(NULL) , m_DStarWidth(0) , m_DStarHeight(0) , m_Game(game)
{
	m_DStarTarget.x=0;
	m_DStarTarget.y=0;
}

CGameMir::CDStar::~CDStar(void)
{
	Free();
}

void CGameMir::CDStar::Free(void)
{
	m_DStarWidth=m_DStarHeight=0;
	DWORD*tmp=m_DStarArray;
	m_DStarArray=NULL;
	if(tmp != NULL) delete[]tmp;
}

QWORD CGameMir::CDStar::Init( DWORD x, DWORD y, long dis, long range)
{
	QWORD starttick=timestamp();
	//初始化D*数组时 不考虑地图上的活动物体 争取比较高的效率
	m_DStarTarget.x=x;
	m_DStarTarget.y=y;

	long count;
	if(!m_Map.TestMap(m_DStarTarget.x,m_DStarTarget.y))
	{
		CString str;
		str.Format("当前点不可行走\n(%d,%d)",m_DStarTarget.x,m_DStarTarget.y);
		AfxMessageBox(str);
		return 0; //如不可到达则取消计算
	}

	//释放数据
	Free();

	//地图大小为0退出
	m_Map.GetSize(m_DStarWidth,m_DStarHeight);
	if(m_DStarWidth <= 0 || m_DStarHeight <= 0)
	{
		AfxMessageBox("地图大小错误");
		return 0;
	}

	count = m_DStarWidth * m_DStarHeight;
	m_DStarArray = new DWORD[count];
	memset(m_DStarArray,-1,count*sizeof(DWORD));

	std::vector<POINT> OpenList;
	std::vector<POINT> OpenList2;
	std::vector<POINT>::iterator pos;

	POINT current;
	DWORD g;
	range--;
	for ( long i=m_DStarTarget.x-range;i<=m_DStarTarget.x+range;i++ )
		for ( long j=m_DStarTarget.y-range;j<=m_DStarTarget.y+range;j++ )
	{
		if(m_Map.TestMap(i,j))
		{
			current.x=i;
			current.y=j;
			OpenList.push_back(current);
			m_DStarArray[current.x * m_DStarHeight + current.y] = 0;
		}
	}
	while(!OpenList.empty())
	{
		for(pos = OpenList.begin();pos != OpenList.end();pos ++)
		{
			current=*pos;
			g = m_DStarArray[current.x * m_DStarHeight + current.y] + 1;
			for(int i = 0; i < 8; i ++)
			{
				current=*pos;
				for(int j = 0; j < dis; j ++)
				{
					current.x += xofs_walk[i];
					current.y += yofs_walk[i];
					if(m_Map.TestMap(current.x,current.y))
					{
						if(m_DStarArray[current.x * m_DStarHeight + current.y] > g)
						{
							m_DStarArray[current.x * m_DStarHeight + current.y] = g;
							OpenList2.push_back(current);
						}
					}
					else
						break;
				}
			}
		}
		OpenList.clear();
		OpenList.swap(OpenList2);
	}
	return timestamp()-starttick;
}

DWORD CGameMir::CDStar::GetDist(DWORD x, DWORD y)
{
	if(m_DStarArray==NULL) return MAXDWORD; //D*还没有初始化 返回失败
	if(x>=m_DStarWidth)
		return MAXDWORD;
	if(x<0)
		return MAXDWORD; 
	if(y>=m_DStarHeight)
		return MAXDWORD;
	if(y<0)
		return MAXDWORD;
	return m_DStarArray[x * m_DStarHeight + y];
}

//取路径
//返回TRUE 成功
BOOL CGameMir::CDStar::GetPath(const POINT& Start, std::vector<POINT>& Path)
{
	//取路径的时候需要全面考虑地图环境 以及活动物体
	if(m_DStarArray==NULL) return FALSE; //D*还没有初始化 返回失败
	if(!m_Map.TestMap(Start.x,Start.y)) return FALSE; //起始点不可达 失败 //一般这个判断都为false 考虑稳定

	//清空路径
	Path.clear();

	POINT current,search;
	long i,dir;
	DWORD g_min;
	bool isRun,Action;

	current.x = Start.x;
	current.y = Start.y;
	Path.push_back(current);
	while(true)
	{
		Action = false;
		g_min = MAXDWORD;
		//if( (current.x == m_DStarTarget.x) && (current.y == m_DStarTarget.y)) //查找到了终点 路径完成 返回TRUE
		if( m_DStarArray[current.x * m_DStarHeight + current.y]==0 )
		{
			return TRUE;
		}
		for(i = 0;i < 8;i ++)
		{
			//走
			//GeneratePoint(current,i,false,search);
			search.x = current.x + xofs_walk[i];
			search.y = current.y + yofs_walk[i];
			if(m_Game.CanMove(search.x,search.y))//检测NPC
			{
				if( (m_DStarArray[search.x * m_DStarHeight + search.y] < g_min) && NotInPath(search,Path) )
				{//更近 并且 还未被添加到路径
					g_min = m_DStarArray[search.x * m_DStarHeight + search.y];
					dir = i;
					isRun = false;
					Action = true;
				}
				//跑
				//GeneratePoint(current,i,true,search);
				search.x = current.x + xofs_run[i];
				search.y = current.y + yofs_run[i];
				if(m_Game.CanMove(search.x,search.y))//检测NPC
				{
					if( (m_DStarArray[search.x * m_DStarHeight + search.y] < g_min) && NotInPath(search,Path) )
					{//更近 并且 还未被添加到路径
						g_min = m_DStarArray[search.x * m_DStarHeight + search.y];
						dir = i;
						isRun = true;
						Action = true;
					}
				}
			}
		}
		if(Action)
		{
			//GeneratePoint(current,dir,isRun,current);
			if(isRun)
			{
				current.x = current.x + xofs_run[dir];
				current.y = current.y + yofs_run[dir];
			}
			else
			{
				current.x = current.x + xofs_walk[dir];
				current.y = current.y + yofs_walk[dir];
			}
			Path.push_back(current);//将点加入路径
		}
		else
		{
			break;
		}
	}

	//如果查找路径失败 清空路径
	Path.clear();

	return FALSE;
}

//还没有被添加到路径中
inline bool CGameMir::CDStar::NotInPath(const POINT& Point, const std::vector<POINT>& Path)
{
	return (Path.end()==std::find(Path.begin(),Path.end(),Point));
}

void CGameMir::CDStar::GetTarget(POINT& t)
{
	t.x=m_DStarTarget.x;
	t.y=m_DStarTarget.y;
}