#ifndef _ASTAR_FLY_H__
#define _ASTAR_FLY_H__
#include "Coordinate.h"
#include <map>
#include <set>
using namespace std;
typedef struct
{
int x;
int y;
int f; // f = g + h
int g;
int h;
void Init(int _x,int _y)
{
f = 0;
g = 0;
h = 0;
x = _x;
y = _y;
}
} APoint, *PAPoint;
class CAStarFly
{
public:
typedef std::list<CIntPoint> PosList;
CAStarFly();
~CAStarFly();
bool CalcPath(PosList& pathList, const CIntPoint& from, const CIntPoint& to);
protected:
virtual int GetMapWidth();
virtual int GetMapHeight();
virtual CIntSize GetRoleSize();
virtual bool GetNearPos(int curX,int curY,PosList &nearPos);
virtual bool IsCanFly(int x,int y);
virtual void OnAddBestPoint(int x, int y);
virtual void OnUnAddBestPoint(int x, int y);
private:
PAPoint CalcNextPoint(PosList& pathList, PAPoint ptCalc); // 應(yīng)用遞歸的辦法進(jìn)行查詢
void SetStartPoint(int x, int y);
void SetEndPoint(int x, int y);
void SetOpened(int x, int y);
void SetClosed(int x, int y);
void SetCurrent(int x, int y);
int32 GetPosIndex(int x, int y);
int32 GetFValue(const CIntPoint &pos);
bool IsNotClosePos(int x, int y);
private:
APoint m_startPoint; //起始點(diǎn)
APoint m_endPoint; //結(jié)束點(diǎn)
APoint m_curPoint; //當(dāng)前移到點(diǎn)
set<int32> m_setClosePos;
int m_curGValue; //當(dāng)前G值
};
#endif/*_ASTAR_FLY_H__*/
#include "stdafx.h"
#include "AStarFly.h"
CAStarFly::CAStarFly()
{
}
CAStarFly::~CAStarFly()
{
}
bool CAStarFly::CalcPath(PosList& pathList, const CIntPoint& from, const CIntPoint& to)
{
//1.先設(shè)置開始與目標(biāo)
SetStartPoint(from.x, from.y);
SetEndPoint(to.x, to.y);
m_curPoint = m_startPoint;
SetClosed(m_startPoint.x, m_startPoint.y); //路徑搜索不再經(jīng)過
m_curGValue = 0;
//從起點(diǎn)開始計(jì)算路徑點(diǎn)
return CalcNextPoint(pathList, nullptr)!=nullptr;
}
PAPoint CAStarFly::CalcNextPoint(PosList& pathList, PAPoint ptCalc)
{
if (nullptr == ptCalc)
{
ptCalc = &m_startPoint;
}
int curX = ptCalc->x;
int curY = ptCalc->y;
int destX = m_endPoint.x;
int destY = m_endPoint.y;
//判斷是否已經(jīng)到了最終位置
if ((curX == destX && abs(curY - destY) == 1) || (curY == destY && abs(curX - destX) == 1))
{
pathList.push_back(CIntPoint(m_endPoint.x, m_endPoint.y));
OnAddBestPoint(m_endPoint.x, m_endPoint.y);
return &m_endPoint;
}
// 最優(yōu)步驟的坐標(biāo)和值
int xmin = curX;
int ymin = curY;
int fmin = 0;
//獲得當(dāng)前周邊點(diǎn)的的坐標(biāo)
PosList nearPos;
if (GetNearPos(curX,curY,nearPos) == false)
{
return nullptr;
}
//刪除不能飛的區(qū)塊
//找出最優(yōu)f值
for (auto itPos : nearPos)
{
int fValue = GetFValue(itPos);
if (fmin == 0 || fValue<fmin)
{
fmin = fValue;
xmin = itPos.x;
ymin = itPos.y;
}
}
if (fmin > 0)
{
SetCurrent(xmin, ymin);
SetClosed(xmin, ymin); //路徑搜索不再經(jīng)過
pathList.push_back(CIntPoint(xmin,ymin));
OnAddBestPoint(xmin, ymin);
PAPoint pAPoint= CalcNextPoint(pathList,&m_curPoint);
if (nullptr == pAPoint)
{
SetCurrent(curX, curY);
SetClosed(xmin, ymin); //路徑搜索不再經(jīng)過
//將最后一次入的隊(duì)刪除
pathList.pop_back();
OnUnAddBestPoint(xmin, ymin);
return CalcNextPoint(pathList, &m_curPoint);
}
return pAPoint;
}
return nullptr;
}
CIntSize CAStarFly::GetRoleSize()
{
return CIntSize(1,1);
}
int CAStarFly::GetMapWidth()
{
return -1;
}
int CAStarFly::GetMapHeight()
{
return -1;
}
void CAStarFly::SetStartPoint(int x, int y)
{
m_startPoint.Init( x,y);
}
void CAStarFly::SetEndPoint(int x, int y)
{
m_endPoint.Init(x,y);
}
void CAStarFly::SetClosed(int x, int y)
{
m_setClosePos.insert(GetPosIndex(x,y));
}
void CAStarFly::SetCurrent(int x, int y)
{
m_curPoint.Init( x, y);
}
int32 CAStarFly::GetPosIndex(int x,int y)
{
return y * GetMapWidth() + x;
}
bool CAStarFly::GetNearPos(int curX, int curY, PosList &nearPos)
{
int newX;
int newY;
//1.上
if (curY > 0)
{
newX = curX;
newY = curY - 1;
if (IsNotClosePos(newX, newY) && IsCanFly(newX, newY))
{
nearPos.push_back(CIntPoint(newX, newY));
}
}
//3.左
if (curX > 0)
{
newX = curX - 1;
newY = curY;
if (IsNotClosePos(newX, newY) && IsCanFly(newX, newY))
{
nearPos.push_back(CIntPoint(newX, newY));
}
}
//4.右
if (curX < GetMapWidth())
{
newX = curX + 1;
newY = curY;
if (IsNotClosePos(newX, newY) && IsCanFly(newX, newY))
{
nearPos.push_back(CIntPoint(newX, newY));
}
}
//2.下
if (curY < GetMapHeight())
{
newX = curX;
newY = curY + 1;
if (IsNotClosePos(newX, newY) && IsCanFly(newX, newY))
{
nearPos.push_back(CIntPoint(newX, newY));
}
}
return nearPos.size()>0;
}
bool CAStarFly::IsCanFly(int x, int y)
{
return true;
}
int32 CAStarFly::GetFValue(const CIntPoint &pos)
{
int xDis = abs(pos.x - m_endPoint.x)*100;
int yDis = abs(pos.y - m_endPoint.y)*100;
return m_curGValue + (int32)sqrt(xDis*xDis + yDis*yDis);
}
bool CAStarFly::IsNotClosePos(int x, int y)
{
return m_setClosePos.find(GetPosIndex(x, y)) == m_setClosePos.end();
}
void CAStarFly::OnAddBestPoint(int x, int y)
{
m_curGValue += 100;
}
void CAStarFly::OnUnAddBestPoint(int x, int y)
{
m_curGValue -= 100;
}
#include "AStarFly.h"
#include <memory>
class CNewMap;
class CMobAStarFly : public CAStarFly
{
public:
static CMobAStarFly& GetInstance();
bool FindPath(const std::shared_ptr<CNewMap>& pMap, const CIntPoint& from, const CIntPoint& to, CAStarFly::PosList& pathList, const CIntSize& roleSize = CIntSize(1, 1));
void setpath(int x, int y);
void show();
virtual int GetMapWidth() override;
virtual int GetMapHeight() override;
virtual CIntSize GetRoleSize() override;
virtual bool IsCanFly(int x, int y) override;
void OnAddBestPoint(int x, int y) override;
void OnUnAddBestPoint(int x, int y) override;
private:
weak_ptr<CNewMap> m_pNewMap;
CIntSize m_roleSize;
};
#include "stdafx.h"
#include "MobFlyAStar.h"
#include "NewMap.h"
CMobAStarFly& CMobAStarFly::GetInstance()
{
static CMobAStarFly s_Instance;
return s_Instance;
}
bool CMobAStarFly::FindPath(const std::shared_ptr<CNewMap>& pMap, const CIntPoint& from, const CIntPoint& to, CAStarFly::PosList& pathList, const CIntSize& roleSize)
{
m_pNewMap = pMap;
m_roleSize = roleSize;
return CalcPath(pathList, from, to);
}
int CMobAStarFly::GetMapWidth()
{
if (m_pNewMap.lock() == nullptr)
return 0;
return m_pNewMap.lock()->GetWidth();
}
int CMobAStarFly::GetMapHeight()
{
if (m_pNewMap.lock() == nullptr)
return 0;
return m_pNewMap.lock()->GetHeight();
}
CIntSize CMobAStarFly::GetRoleSize()
{
return m_roleSize;
}
bool CMobAStarFly::IsCanFly(int x, int y)
{
for (int w = 0; w < m_roleSize.width; ++w)
{
for (int h = 0; h < m_roleSize.height; ++h)
{
if (m_pNewMap.lock()->IsPosBlock(m_pNewMap.lock()->PosToWorldX(x + w), m_pNewMap.lock()->PosToWorldY(y - h))) {
return false;
}
}
}
return true;
}
void CMobAStarFly::setpath(int x, int y)
{
}
void CMobAStarFly::show()
{
}
void CMobAStarFly::OnAddBestPoint(int x, int y)
{
}
void CMobAStarFly::OnUnAddBestPoint(int x, int y)
{
}