概 述
在游戲開發(fā)中，經(jīng)常會(huì)使用A*算法來實(shí)現(xiàn)尋路汪诉。本文主要介紹使用C++來簡(jiǎn)單實(shí)現(xiàn)A*算法白胀，便于理解椭赋。
算法原理
網(wǎng)上有關(guān)A*算法原理的講解很多，這里就不闡述了或杠。貼一個(gè)個(gè)人認(rèn)為講解比較好的鏈接：初學(xué)者的 A* 尋路哪怔。鏈接文章用圖文的方式，講解了算法原理廷痘、流程以及尋路算法相關(guān)的注意點(diǎn)和優(yōu)化蔓涧。
算法實(shí)現(xiàn)
根據(jù)算法原理，詳細(xì)的實(shí)現(xiàn)步驟如下：
- 將起點(diǎn)添加到open表中笋额；
- 從open表中取成本最低的結(jié)點(diǎn)，即F(G + H)值的最小結(jié)點(diǎn)篷扩；
- 判斷此結(jié)點(diǎn)是否是終點(diǎn)兄猩，若是則結(jié)束尋路；
- 將此結(jié)點(diǎn)從open表中移除鉴未，添加到close表枢冤；
- 依次判斷當(dāng)前結(jié)點(diǎn)各個(gè)方位的結(jié)點(diǎn)(下面稱為搜索結(jié)點(diǎn))：
5.1 若搜索結(jié)點(diǎn)超出世界范圍或不可達(dá)到，則跳過铜秆；
5.2 判斷搜索結(jié)點(diǎn)是否已存在于open表中淹真，若不存在，添加到open表中连茧；反之核蘸，若G值更小巍糯，更新結(jié)點(diǎn)； - 循環(huán)處理open表中的結(jié)點(diǎn)客扎，直到open表為空祟峦，則不存在路徑。
- 根據(jù)終點(diǎn)反推起點(diǎn)徙鱼，生成最終路徑
實(shí)現(xiàn)代碼如下：
// AStar.h
#include <vector>
struct Vec2
{
int x;
int y;
bool operator == (const Vec2 &rhs)
{
return (x == rhs.x && y == rhs.y);
};
};
struct Node
{
Vec2 coordinate_; //坐標(biāo)
int G; //起點(diǎn)到該位置的成本
int H; //該位置到終點(diǎn)的成本宅楞，啟發(fā)式
Node *parent_; //父結(jié)點(diǎn)
Node(Vec2 coordinate, Node *parent = nullptr)
{
coordinate_ = coordinate;
G = 0;
H = 0;
parent_ = parent;
};
int GetCost() { return G + H; } //獲取總成本
};
using CoordinateList = std::vector<Vec2>;
using NodeArr = std::vector<Node *>;
class AStar
{
public:
AStar();
void SetWorldSize(Vec2 size); //設(shè)置地圖大小
void SetWalls(CoordinateList walls); //設(shè)置墻體
CoordinateList FindPath(Vec2 source, Vec2 target); //A*尋路
private:
bool IfCollision(Vec2 coordinate); //判斷是否碰撞
Node* FindNodeInArr(NodeArr &arr, Vec2 coordinate);
int Manhattan(Vec2 source, Vec2 target); //曼哈頓距離
void ReleaseNodes(NodeArr& arr);
private:
Vec2 worldSize_; //地圖大小
int direction_; //搜索方位(4或8)
CoordinateList directions_; //方向
CoordinateList walls_; //墻
};
// AStar.cpp
#include "AStar.h"
Vec2 operator + (const Vec2 &lhs, const Vec2 &rhs)
{
return { lhs.x + rhs.x, lhs.y + rhs.y };
}
AStar::AStar()
{
worldSize_ = { 0, 0 };
direction_ = 8;
directions_ = {
{ 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 },
{ -1, -1 }, { 1, 1 }, { -1, 1 }, { 1, -1 }
};
walls_ = {};
}
void AStar::SetWorldSize(Vec2 size)
{
worldSize_ = size;
}
void AStar::SetWalls(CoordinateList walls)
{
walls_ = walls;
}
CoordinateList AStar::FindPath(Vec2 source, Vec2 target)
{
NodeArr openSet; //open表
NodeArr closedSet; //close表
Node* nodePtr = nullptr;
// 添加起點(diǎn)
openSet.emplace_back(new Node(source));
while (!openSet.empty()) {
// 獲取open表中總成本最小的結(jié)點(diǎn)
auto node = openSet.begin();
nodePtr = *node;
for (auto item = openSet.begin(); item != openSet.end(); ++item) {
if ((*item)->GetCost() < (*node)->GetCost()) {
node = item;
nodePtr = *item;
}
}
// 判斷是否到達(dá)目標(biāo)
if (nodePtr->coordinate_ == target) {
break;
}
// 添加到close表中，從open表中移除
closedSet.emplace_back(nodePtr);
openSet.erase(node);
// 依次判斷當(dāng)前結(jié)點(diǎn)的各個(gè)方位
for (int i = 0; i < direction_; ++i) {
Vec2 findCoordinate(nodePtr->coordinate_ + directions_[i]);
// 判讀是否超出世界范圍 是否不可達(dá)到(結(jié)點(diǎn)位置是墻體)
if (IfCollision(findCoordinate) || FindNodeInArr(closedSet, findCoordinate)) {
continue;
}
// 判斷搜索結(jié)點(diǎn)是否已存在于open表中
int gCost = nodePtr->G + ((i < 4) ? 10 : 14);
Node* findNode = FindNodeInArr(openSet, findCoordinate);
if (nullptr == findNode) { //不存在袱吆，添加添加新的結(jié)點(diǎn)
findNode = new Node(findCoordinate, nodePtr);
findNode->G = gCost;
findNode->H = Manhattan(findNode->coordinate_, target);
openSet.emplace_back(findNode);
} else { //存在厌衙，判斷是否需要更新
if (gCost < findNode->G) {
findNode->parent_ = nodePtr;
findNode->G = gCost;
}
}
}
}
// 生成最終路徑
CoordinateList path;
while (nodePtr != nullptr) {
path.emplace_back(nodePtr->coordinate_);
nodePtr = nodePtr->parent_;
}
// 釋放尋路結(jié)點(diǎn)
ReleaseNodes(openSet);
ReleaseNodes(closedSet);
return path;
}
bool AStar::IfCollision(Vec2 coordinate)
{
if (coordinate.x < 0 || coordinate.x >= worldSize_.x ||
coordinate.y < 0 || coordinate.y >= worldSize_.y ||
std::find(walls_.begin(), walls_.end(), coordinate) != walls_.end()) {
return true;
}
return false;
}
Node* AStar::FindNodeInArr(NodeArr& arr, Vec2 coordinate)
{
for (auto node : arr) {
if (node->coordinate_ == coordinate) {
return node;
}
}
return nullptr;
}
int AStar::Manhattan(Vec2 source, Vec2 target)
{
return 10 * (abs(source.x - target.x) + abs(source.y - target.y));
}
void AStar::ReleaseNodes(NodeArr& arr)
{
for (auto i = arr.begin(); i != arr.end();) {
delete *i;
i = arr.erase(i);
}
}
注：代碼中H值的計(jì)算，即啟發(fā)式绞绒，使用的是曼哈頓距離婶希。當(dāng)然，啟發(fā)式函數(shù)可以使用很多不同的計(jì)算方式处铛，這里不一一展示饲趋。
用法示例
#include <iostream>
#include "source/AStar.h"
using namespace std;
int main()
{
AStar aStar;
aStar.SetWorldSize({ 7, 7 }); //設(shè)置世界大小
std::vector<Vec2> walls = { { 2, 3 }, { 3, 3 }, { 4, 3 } };
aStar.SetWalls(walls); //設(shè)置墻體
auto path = aStar.FindPath({ 3, 1 }, { 3, 5 }); //尋路
for (auto &i : path) {
std::cout << i.x << " " << i.y << "\n";
}
}
GitHub地址：A-Star
