A*是一种很常见的游戏寻路算法。
长久以来,我一直觉得A*是一种高大上的算法,因为听很多人说起此算法,然而,江湖一张纸,戳穿不值一毛钱,思路其实很简单通过估值函数决定下一步走向
估值函数
- 决定整个算法的效率,以及准确率。
- 可以根据实际需求,使用不同的估值函数。
实现
#pragma once
#include "base.h"
#include "math.h"
#include "priority_queue.h"
class AStar {
public:
struct Box {
MATH Vec2 parent;
MATH Vec2 self;
int G, H;
int F() const
{
return G + H;
}
Box()
{ }
explicit Box(const MATH Vec2 & pt1, const MATH Vec2 & pt2)
: parent(pt1)
, self(pt2)
{ }
explicit Box(const MATH Vec2 & pt1, const MATH Vec2 & pt2, int g, int h)
: parent(pt1)
, self(pt2)
, G(g)
, H(h)
{ }
bool operator==(const MATH Vec2 & point) const
{
return MATH equal(self, point);
}
bool operator<(const Box & other) const
{
return F() > other.F();
}
};
using NextFunc = STD function<void(const MATH Vec2 &)>;
using TestFunc = STD function<bool(const MATH Vec2 &)>;
public:
AStar()
{ }
~AStar()
{ }
bool IsFinish()
{
return _openList.empty() || MATH equal(_end, _openList.top().self);
}
const MATH Vec2 & GetQueryBeg() const
{
return _beg;
}
const MATH Vec2 & GetQueryEnd() const
{
return _end;
}
void SetQueryPoint(const MATH Vec2 & beg, const MATH Vec2 & end)
{
_beg = beg;
_end = end;
_closeList.clear();
_openList = priority_queue<Box>();
_openList.emplace(beg, beg, 0, 0);
}
bool GetQueryPath(STD vector<MATH Vec2> & path)
{
if (!MATH equal(_end, _closeList.back().self))
{
return false;
}
auto parent = _closeList.back().self;
for (; !_closeList.empty(); _closeList.pop_back())
{
if (MATH equal(parent, _closeList.back().self))
{
path.push_back(_closeList.back().self);
parent = _closeList.back().parent;
}
}
return true;
}
void SetTestFunc(const TestFunc & func)
{
_testFunc = func;
}
void SetNextFunc(const NextFunc & func)
{
_nextFunc = func;
}
bool QueryNext()
{
static const MATH Vec2 s_offset[] = {
{ 0, -1 },{ 1, 0 },{ 0, 1 },{ -1, 0 }, // 上,右,下,左。
//{ 1, -1 },{ 1, 1 },{ -1, 1 },{ -1,-1 }, // 右上,右下,左下,左上。
};
if (!MATH equal(_end, _openList.top().self))
{
auto top = _openList.top();
_closeList.push_back(top);
_nextFunc(top.self);
_openList.pop();
for (auto &offset : s_offset)
{
CheckPoint(top, MATH add(top.self, offset));
}
}
if (!_openList.empty() && MATH equal(_end, _openList.top().self))
{
_closeList.push_back(_openList.top());
_nextFunc(_openList.top().self);
}
return IsFinish();
}
private:
void CheckPoint(const Box & from, const MATH Vec2 & to)
{
if (Test(to))
{
_openList.emplace(from.self, to, from.G + 1, Distance(to));
}
}
int Distance(const MATH Vec2 & point)
{
return (int)(STD abs(point.x - _end.x) + STD abs(point.y - _end.y));
}
bool Test(const MATH Vec2 & point)
{
return _testFunc(point)
&& STD find(_openList.begin(), _openList.end(), point) == _openList.end()
&& STD find(_closeList.begin(), _closeList.end(), point) == _closeList.end();
}
private:
MATH Vec2 _beg;
MATH Vec2 _end;
NextFunc _nextFunc;
TestFunc _testFunc;
priority_queue<Box> _openList;
STD vector<Box> _closeList;
private:
AStar(const AStar &) = delete;
AStar(AStar &&) = delete;
AStar operator=(const AStar &) = delete;
AStar operator=(AStar &&) = delete;
};