#include "A_star.h"#include#include

using namespacestd;void A_star::Map::addCollision(Point coordinates)//添加墻

{

walls.push_back(coordinates);

}void A_star::Map::removeCollision(Point coordinates)//刪除墻

{

vector::iterator it =walls.begin();while(it !=walls.end())

{if (coordinates.x == (*it).x && coordinates.y == (*it).y)

{

walls.erase(it);

}

it++;

}

}void A_star::Map::clearCollisions()//清除墻

{

walls.clear();

}

A_star::Point A_star::Map::getDelta(Point source, Point target)

{return{ abs(source.x - target.x), abs(source.y -target.y) };

}int A_star::Map::manhattan(Point source, Point target)//曼哈頓距離

{//auto delta = std::move(getDelta(source, target));//以非常簡單的方式將左值引用轉換為右值引用，不懂為什么這么做

Point delta =getDelta(source, target);return static_cast(10 * (delta.x +delta.y));

}bool A_star::Map::Detect_collision(Point coordinates)//是否是墻

{if (coordinates.x >= 0 && coordinates.x <= size_.x &&coordinates.y>= 0 && coordinates.y <=size_.y)

{

vector::iterator it =walls.begin();while (it !=walls.end())

{if (coordinates.x == (*it).x && coordinates.y == (*it).y)

{return true;

}

it++;

}return false;

}else

return true;

}void A_star::Map::releaseNodes(vector nodes)//移除節點

{for (auto it = nodes.begin(); it !=nodes.end();) {delete *it;

it=nodes.erase(it);

}

}

A_star::Node* A_star::Map::findNodeOnList(vector nodes, Point coordinates)//判斷是否 在列表中

{for(auto node : nodes) {//Point s = node->coordinates_;

if (node->coordinates_.x == coordinates.x && node->coordinates_.y ==coordinates.y) {returnnode;

}

}returnnullptr;

}

vector<:point> A_star::Map::findPath(Point source, Point target)//尋路

{

vectorpath;if(Detect_collision(source) || Detect_collision(target))//判斷起點和終點是否是墻

{

cout<< "please input orgin and target again" <

}

Node*current =nullptr;

vector<:node>openSet, closedSet;

openSet.push_back(newNode(source));while (!openSet.empty()) {

current= *openSet.begin();for(auto node : openSet) {if (node->Get_score() <= current->Get_score()) {

current=node;

}

}if (current->coordinates_.x == target.x && current->coordinates_.y ==target.y) {break;

}

closedSet.push_back(current);

openSet.erase(std::find(openSet.begin(), openSet.end(), current));for (int i = 0; i < directions; ++i) {

Point newCoordinates((current->coordinates_.x + current->direction[i].x),(current->coordinates_.y + current->direction[i].y));if (Detect_collision(newCoordinates) ||findNodeOnList(closedSet, newCoordinates)) {//判斷墻和是否在關閉隊列里面

continue;

}int totalCost = current->G + ((i < 4) ? 10 : 14);

Node*successor =findNodeOnList(openSet, newCoordinates);if (successor == nullptr) {//不在開隊列里面

successor = newNode(newCoordinates, current);

successor->G =totalCost;

successor->H = manhattan(successor->coordinates_, target);

openSet.push_back(successor);

}else if (totalCost < successor->G) {//已經在開隊列里了

successor->parent_ =current;

successor->G =totalCost;

}

}

}while (current !=nullptr) {

path.push_back(current->coordinates_);

current= current->parent_;

}

releaseNodes(openSet);

releaseNodes(closedSet);returnpath;

}

總結

以上是生活随笔為你收集整理的astar算法c语言实,Astar寻路算法C++实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。