A*算法实现

Question

这是一个A*算法的实现，我将在我的游戏中使用。

Navigation.hpp

#pragma once

#include <SFML\Graphics.hpp>
#include <algorithm>
#include <iostream>

#include <vector>
#include <list>
#include <set>

using namespace std;

class Field;

//Comparer using by set to allow priority
struct FieldComparer
{
    bool operator()(const Field *, const Field *) const;
};

using FieldSet = set<Field*, FieldComparer>;
using FieldContainer = vector<Field*>;

//Contains info about field, buildings builded on it and type of terrain
class Field
{
private:
    sf::Vector2i mapPosition{ 0, 0 };

    unsigned hCost{ 0 }; //to goal
    unsigned gCost{ 0 }; //to start

    Field *  parent;

    bool     isWalkable { true };
    bool     isPathPart { false };
public:
    void SetParent(Field&);
    Field * GetParent() const;

    unsigned GetFCost() const; //sum of hCost and gCost
    unsigned GetHCost() const;
    unsigned GetGCost() const;

    bool     IsWalkable() const;
    bool     IsPathPart() const;

    void SetHCost(unsigned);
    void SetGCost(unsigned);

    void SetWalkable(bool);
    void SetAsPartOfPath(bool);

    sf::Vector2i GetMapPosition() const;

    //compares positions
    bool operator == (const Field& other);

    Field(sf::Vector2i mapPosition, bool isWalkable) 
        : mapPosition(mapPosition), isWalkable(isWalkable) {}
};

//Contains fields and describes them
class Map
{
private:
    sf::Vector2u mapSize;
    Field *** fields; //two dimensional array of fields gives the fastest access
public:

    sf::Vector2u GetMapSize() const;
    Field *** GetFields();

    Map(sf::Vector2u);
    Map() {}
};

//Searching patch after giving a specified map
class PathFinder
{
private:
    //Calculate score between two fields
    unsigned CalcScore(Field&, Field&) const;

    //Get neighbours of field in specified map
    FieldContainer GetNeighbours(Field&, Map&) const;
public:

    //Find path that have the lowest cost, from a to b in map
    FieldContainer FindPath(Map&, Field&, Field&);

    //Reconstruct path using pointers to parent
    FieldContainer ReconstructPath(Field*, Field*) const;
};

Navigation.cpp

#include "Navigation.hpp"

#pragma region Field

    void Field::SetParent(Field & parent) { this->parent = &parent; }
    Field * Field::GetParent() const { return parent; }

    unsigned Field::GetFCost() const { return hCost + gCost; }
    unsigned Field::GetHCost() const { return hCost; }
    unsigned Field::GetGCost() const { return gCost; }

    bool Field::IsWalkable()   const { return isWalkable; }
    bool Field::IsPathPart()   const { return isPathPart; }

    void Field::SetHCost(unsigned value) { hCost = value; }
    void Field::SetGCost(unsigned value) { gCost = value; }

    void Field::SetWalkable(bool isWalkable)     { this->isWalkable = isWalkable; }
    void Field::SetAsPartOfPath(bool isPathPart) { this->isPathPart = isPathPart; }

    sf::Vector2i Field::GetMapPosition() const { return mapPosition; }
    bool Field::operator == (const Field& other)
    {
        return this->mapPosition == other.GetMapPosition();
    }

#pragma endregion Field

#pragma region Map

    sf::Vector2u Map::GetMapSize() const { return mapSize; }
    Field *** Map::GetFields() { return fields; }
    Map::Map(sf::Vector2u mapSize) : mapSize(mapSize)
    {
        //initialize map
        fields = new Field**[mapSize.x];

        //initialize all fields
        for (unsigned x = 0; x < mapSize.x; x++)
        {
            fields[x] = new Field*[mapSize.y];

            for (unsigned y = 0; y < mapSize.y; y++)
            {
                fields[x][y] = new Field({static_cast<int>(x), static_cast<int>(y)}, 
                { 
                    (!(y == 3 && x >= 1) || (x == 5 && y < 4))              
                });
            }
        }
    }

#pragma endregion Map

#pragma region PathFinder

    bool FieldComparer::operator()(const Field * l, const Field * r) const
    {
        return l->GetFCost() <  r->GetFCost() ||   //another field has smaller fcost
               l->GetFCost() == r->GetFCost() &&   //or fcost equals, and checked field is nearer to goal than current field
               l->GetHCost() <  r->GetHCost();

    }

    unsigned PathFinder::CalcScore(Field & a, Field & b) const
    {
        sf::Vector2u dst
        {
            static_cast<unsigned>(abs(b.GetMapPosition().x - a.GetMapPosition().x)),
            static_cast<unsigned>(abs(b.GetMapPosition().y - a.GetMapPosition().y))
        };

        return (dst.x > dst.y ? 14 * dst.y + 10 * (dst.x - dst.y) :
                                14 * dst.x + 10 * (dst.y - dst.x));
    }

    FieldContainer PathFinder::GetNeighbours(Field & f, Map & m) const
    {
        FieldContainer neighbours{};

        //cout << "checking neighbours for field: { " << f.GetMapPosition().x << ", " << f.GetMapPosition().y << " }\n";
        for (int x = -1; x <= 1; x++)
        {
            for (int y = -1; y <= 1; y++)
            {
                int xPos = f.GetMapPosition().x + x;
                int yPos = f.GetMapPosition().y + y;

                if (x == 0 && y == 0) //dont check the same field
                    continue;

                //check that field is in the map
                bool isInTheMap = (xPos >= 0 && yPos >= 0 && xPos < m.GetMapSize().x && yPos < m.GetMapSize().y);

                if (isInTheMap)
                {
                    neighbours.push_back(m.GetFields()[xPos][yPos]);
                }
            }
        }

        return neighbours;
    }

    FieldContainer PathFinder::FindPath(Map& map, Field& a, Field& b)
    {
        FieldSet open = {};   //not expanded fields
        FieldSet closed = {}; //expanded fields

        a.SetHCost(CalcScore(a, b)); //calculate h cost for start field, gcost equals 0
        open.insert(&a);             //add start field to open vector

        while (!open.empty()) //while we have unexpanded fields in open set
        {
            Field * current = *open.begin(); //set current field

            //if current checked field is our goal field
            if (*current == b)
            {
                return
                    ReconstructPath(&a, current); //return reversed path
            }

            closed.insert(current); //end of checking current field, add it to closed vector...
            open.erase(open.find(current)); //set solution

            //get neighbours of current field
            for (auto f : GetNeighbours(*current, map))
            {
                //continue if f is unavailable
                if (closed.find(f) != closed.end() || !f->IsWalkable())
                {
                    continue;
                }

                //calculate tentative g cost, based on current cost and direction changed
                unsigned tentativeGCost = current->GetGCost() + (current->GetMapPosition().x != f->GetMapPosition().x && current->GetMapPosition().y != f->GetMapPosition().y ? 14 : 10);

                bool fieldIsNotInOpenSet = open.find(f) == open.end();
                if (tentativeGCost < f->GetGCost() || fieldIsNotInOpenSet)
                {
                    f->SetGCost(tentativeGCost);
                    f->SetHCost(CalcScore(*f, b));
                    f->SetParent(*current);

                    if (fieldIsNotInOpenSet)
                    {
                        open.insert(f);
                    }
                }
            }
        }
        return {}; //no path anaviable
    }

    FieldContainer PathFinder::ReconstructPath(Field * a, Field * current) const
    {
        FieldContainer totalPath { current };

        while (!(current == a))
        {
            totalPath.push_back(current);
            current->SetAsPartOfPath(true);
            current = current->GetParent();
        }

        std::reverse(totalPath.begin(), totalPath.end()); //reverse the path
        return totalPath;
    }

#pragma endregion PathFinder

关于这个代码，我有几个问题：

• 你看到有什么不好的做法吗？
• 我能做得更好吗？
• 这个植入速度快吗？
• 我所选择的容器是这个算法的最佳选择吗？我的意思是:被设定为开放和封闭列表，其他一切的向量？

对我来说最重要的当然是速度。现在，map 1500x1500的代码需要~27 in才能找到路径(在发布模式下)。我认为这是相当好的结果，但我可能会使用它的大地图，与不同类型的领域，有不同的成本，所以我想要确定。

编辑

现在我认为表示封闭字段的容器不需要排序，所以我认为它可以是unordered_set。

重构

后的

这是修改后的代码，其中我采纳了“棘轮怪”和“Ben建议”。现在，150×150地图的代码大约快10毫秒，即1/5，所以效果很好。

Navigation.hpp

#pragma once

#include <SFML\Graphics.hpp>
#include <algorithm>
#include <iostream>

#include <vector>
#include <list>
#include <set>

class Field;

//Comparer using by set to allow priority
struct FieldComparer
{
    bool operator()(const Field *, const Field *) const;
};

using FieldSet = std::set<Field*, FieldComparer>;
using FieldContainer = std::vector<Field*>;
using FieldsVector = std::vector<std::vector<Field>>;

//Contains info about field, buildings builded on it and type of terrain
class Field
{
private:
    sf::Vector2i mapPosition{ 0, 0 };

    unsigned hCost{ 0 }; //to goal
    unsigned gCost{ 0 }; //to start

    Field *  parent;

    bool     isWalkable { true };
    bool     isPathPart { false };
    bool     isClosed   { false };
public:
    void SetParent(Field&);
    Field * GetParent() const;

    unsigned GetFCost() const; //sum of hCost and gCost
    unsigned GetHCost() const;
    unsigned GetGCost() const;

    bool     IsWalkable() const;
    bool     IsPathPart() const;
    bool     IsClosed() const;

    void SetHCost(unsigned);
    void SetGCost(unsigned);

    void SetWalkable(bool);
    void SetAsPartOfPath(bool);
    void SetClosedStatus(bool);

    sf::Vector2i GetMapPosition() const;

    //compares positions
    bool operator == (const Field& other);

    Field(sf::Vector2i mapPosition, bool isWalkable) 
        : mapPosition(mapPosition), isWalkable(isWalkable) {}

    Field() = default;
};

//Contains fields and describes them
class Map
{
private:
    sf::Vector2u mapSize;
    FieldsVector fields; //two dimensional array of fields gives the fastest access
public:

    sf::Vector2u GetMapSize() const;
    FieldsVector & GetFields();

    Map(sf::Vector2u);
    Map() {}

    ~Map();
};

//Searching patch after giving a specified map
class PathFinder
{
private:
    //Calculate score between two fields
    unsigned CalcScore(Field&, Field&) const;

    //Get neighbours of field in specified map
    FieldContainer GetNeighbours(Field&, Map&) const;
public:

    //Find path that have the lowest cost, from a to b in map
    FieldContainer FindPath(Map&, Field&, Field&);

    //Reconstruct path using pointers to parent
    FieldContainer ReconstructPath(Field*, Field*) const;
};

Navigation.cpp

#include "Navigation.hpp"

#pragma region Field

    void Field::SetParent(Field & parent) { this->parent = &parent; }
    Field * Field::GetParent() const { return parent; }

    unsigned Field::GetFCost() const { return hCost + gCost; }
    unsigned Field::GetHCost() const { return hCost; }
    unsigned Field::GetGCost() const { return gCost; }

    bool Field::IsWalkable()   const { return isWalkable; }
    bool Field::IsPathPart()   const { return isPathPart; }
    bool Field::IsClosed()     const { return isClosed;   }

    void Field::SetHCost(unsigned value) { hCost = value; }
    void Field::SetGCost(unsigned value) { gCost = value; }

    void Field::SetWalkable(bool isWalkable)     { this->isWalkable = isWalkable; }
    void Field::SetAsPartOfPath(bool isPathPart) { this->isPathPart = isPathPart; }
    void Field::SetClosedStatus(bool isClosed)   { this->isClosed = isClosed;     }

    sf::Vector2i Field::GetMapPosition() const { return mapPosition; }
    bool Field::operator == (const Field& other)
    {
        return this->mapPosition == other.GetMapPosition();
    }

#pragma endregion Field

#pragma region Map

    sf::Vector2u Map::GetMapSize() const { return mapSize; }
    FieldsVector & Map::GetFields() { return fields; }
    Map::Map(sf::Vector2u mapSize) : mapSize(mapSize)
    {
        //initialize map
        fields = {};

        //initialize all fields
        for (unsigned x = 0; x < mapSize.x; x++)
        {
            fields.push_back({});

            for (unsigned y = 0; y < mapSize.y; y++)
            {
                fields[x].push_back({ {static_cast<int>(x), static_cast<int>(y)},
                {
                    (!(y == 3 && x >= 1) || (x == 5 && y < 4))
                } });
            }
        }
    }

    Map::~Map() {}

#pragma endregion Map

#pragma region PathFinder

    bool FieldComparer::operator()(const Field * l, const Field * r) const
    {
        return l->GetFCost() <  r->GetFCost() ||   //another field has smaller fcost
               l->GetFCost() == r->GetFCost() &&   //or fcost equals, and checked field is nearer to goal than current field
               l->GetHCost() <  r->GetHCost();

    }

    unsigned PathFinder::CalcScore(Field & a, Field & b) const
    {
        sf::Vector2u dst
        {
            static_cast<unsigned>(abs(b.GetMapPosition().x - a.GetMapPosition().x)),
            static_cast<unsigned>(abs(b.GetMapPosition().y - a.GetMapPosition().y))
        };

        return (dst.x > dst.y ? 14 * dst.y + 10 * (dst.x - dst.y) :
                                14 * dst.x + 10 * (dst.y - dst.x));
    }

    FieldContainer PathFinder::GetNeighbours(Field & f, Map & m) const
    {
        FieldContainer neighbours{};

        //cout << "checking neighbours for field: { " << f.GetMapPosition().x << ", " << f.GetMapPosition().y << " }\n";
        for (int x = -1; x <= 1; x++)
        {
            for (int y = -1; y <= 1; y++)
            {
                int xPos = f.GetMapPosition().x + x;
                int yPos = f.GetMapPosition().y + y;

                if (x == 0 && y == 0) //dont check the same field
                    continue;

                //check that field is in the map
                bool isInTheMap = (xPos >= 0 && yPos >= 0 && xPos < m.GetMapSize().x && yPos < m.GetMapSize().y);

                if (isInTheMap)
                {
                    neighbours.push_back(&m.GetFields()[xPos][yPos]);
                }
            }
        }

        return neighbours;
    }

    FieldContainer PathFinder::FindPath(Map& map, Field& a, Field& b)
    {
        FieldSet open = {};   //not expanded fields

        a.SetHCost(CalcScore(a, b)); //calculate h cost for start field, gcost equals 0
        open.insert(&a);             //add start field to open vector

        while (!open.empty()) //while we have unexpanded fields in open set
        {
            auto currIt = open.begin();
            Field * current = *currIt; //set current field

            //if current checked field is our goal field
            if (*current == b)
            {
                return
                    ReconstructPath(&a, current); //return reversed path
            }

            current->SetClosedStatus(true); //end of checking current field, change closed status
            open.erase(currIt); //set solution

            //get neighbours of current field
            for (auto f : GetNeighbours(*current, map))
            {
                //continue if f is unavailable
                if (f->IsClosed() || !f->IsWalkable())
                {
                    continue;
                }

                //calculate tentative g cost, based on current cost and direction changed
                unsigned tentativeGCost = current->GetGCost() + (current->GetMapPosition().x != f->GetMapPosition().x && current->GetMapPosition().y != f->GetMapPosition().y ? 14 : 10);

                bool fieldIsNotInOpenSet = open.find(f) == open.end();
                if (tentativeGCost < f->GetGCost() || fieldIsNotInOpenSet)
                {
                    if (!fieldIsNotInOpenSet)
                    {
                        open.erase(open.find(f));
                    }

                    f->SetGCost(tentativeGCost);
                    f->SetHCost(CalcScore(*f, b));
                    f->SetParent(*current);

                    open.insert(f);
                }
            }
        }
        return {}; //no path anaviable
    }

    FieldContainer PathFinder::ReconstructPath(Field * a, Field * current) const
    {
        FieldContainer totalPath { current };

        while (!(current == a))
        {
            totalPath.push_back(current);
            current->SetAsPartOfPath(true);
            current = current->GetParent();
        }

        std::reverse(totalPath.begin(), totalPath.end()); //reverse the path
        return totalPath;
    }

#pragma endregion PathFinder

Answer 1

一些一般性建议：

1. 不要使用using namespace std;，特别是不要在头中使用。它可以引入一些微妙的bug。
2. 您的Map类没有析构函数，并且正在泄漏内存。通过new分配的所有东西都必须是deleted (或者，如果是数组，则是delete[]d)。
3. //two dimensional array of fields gives the fastest access没有任何意义，因为您的数组不是二维的(我怀疑二维数组的性能是否优于一维数组，但您可以自由地证明我错了)。如果这意味着以后要改进实现，那么您可能应该将其标记为这样(例如，使用众所周知的//TODO注释)。
4. 像//check that field is in the map这样的注释在后面跟着行(如bool isInTheMap = ... )时是多余的，因为变量名使其用途足够清楚。一般来说，使用注释是好的，但是它们也可能被过度使用(或者写得不好)；有效地使用它们是关键(而且也不容易)。
5. 通常您应该避免使用#pragma，至少当代码应该是可移植的时候。在这种情况下，#pragma region根本就不是可移植的(它是VS的)，而且通常也暗示代码分离不好。如果您认为没有文件是不可读的，则应该将其拆分为多个。

Answer 2

不要使用原始指针，而更愿意在Map中保留字段的值。每次取消对冷缓存的引用都有200个循环掉在地板上，您强迫cpu每次执行2次以获得一个Field。如果您有一个std：：mapSize*mapSize大小与y*mapSize+x索引的向量(您可以重载operator[]以保留接口)，那么您将获得更快的随机访问。

是否关闭Field可以通过将bool closed成员字段添加到默认为false的Field中来保持。

open.erase(open.find(current));等同于open.erase(open.begin());，而且您只在稍早的时候得到了begin()。你还不如暂时保留一下。

在更新Field时，应该从open集中删除Field并重新插入它。当您更新它的值并使相对排序无效时，您使用的std::set将不能正常工作。

if (tentativeGCost < f->GetGCost() || fieldIsNotInOpenSet)
{
    if (!fieldIsNotInOpenSet)
    {
        open.erase(open.find(f));
    }
    f->SetGCost(tentativeGCost);
    f->SetHCost(CalcScore(*f, b));
    f->SetParent(*current);

    open.insert(f);
}