c++ - C++ 中的 A* 探路者

Question

我正在尝试编写一个 A* 探路者来学习 C++，并且正在努力解决一个特定的错误。

这些是程序的功能/假设：

• 路径包含无法通过的“墙”
• 所有路径的成本相同 (1)
• 允许对角线移动
• 只有一个目标

这是我的代码：

#include <algorithm>
#include <iostream>
#include <vector>
#include <tuple>
#include <cmath>
#include <set>


using Graph = std::vector<std::vector<int>>;
using Position = std::tuple<int, int>;
class Node;
using Nodes = std::vector<Node>;


constexpr int WALL_BLOCK = 1;
constexpr int USER_BLOCK = 3;
constexpr int GOAL_BLOCK = 2;


class Node {
    private:
        int row;
        int column;
        Node* parent = nullptr;

        int f = 0;
        int g = 0;
        int h = 0;

    public:
        Node() : row(-1), column(-1) {}
        Node(int row, int column) : row(row), column(column)  {}
        Node(int row, int column, Node *parent) : row(row), column(column) {
            if (this->parent != nullptr && *this->parent == *this) {
                throw "Node cannot be parented to itself";
            }

            this->parent = parent;
        }
        ~Node() {}

        Node* get_parent() const { return this->parent; }
        int get_f() const { return this->f; }
        int get_g() const { return this->g; }
        int get_h() const { return this->h; }
        Position get_position() const { return std::make_tuple(row, column); }

        void set_f(int f) { this->f = f; }
        void set_g(int g) { this->g = g; }
        void set_h(int h) { this->h = h; }

        bool operator==(Node const &node) const {
            return this->row == node.row && this->column == node.column;
        }

        bool operator<(Node const &node) const {
            return this->row < node.row && this->column < node.column;
        }

        friend std::ostream& operator<<(std::ostream& os, Node const &node);
};


std::ostream& operator<<(std::ostream& os, Node const &node) {
    auto row = node.row;
    auto column = node.column;
    os << "Node(("
        << row << ", "
        << column << "), "
        << node.get_g() << ", "
        << node.get_h() << ", "
        ;

    Node* parent = node.get_parent();

    if (parent != nullptr) {
        os << parent;
    } else {
        os << "nullptr";
    }

    os << ")";

    return os;
}


inline bool is_walkable(Node const &node, Graph const &graph) {
    int column;
    int row;
    std::tie(row, column) = node.get_position();

    return graph[row][column] != WALL_BLOCK;
}


Position get_first_index(Graph const &graph, int block);


Position get_end(Graph const &graph) {
    return get_first_index(graph, GOAL_BLOCK);
}


Position get_first_index(Graph const &graph, int block) {
    for (int row = 0, max = graph.size(); row < max; ++row) {
        auto line = graph[row];
        auto found = std::find(line.begin(), line.end(), block);

        if (found != line.end()) {
            return std::make_tuple(row, found - line.begin());
        }
    }

    return {-1, -1};
}


inline int get_h(Node const &node, Node const &reference) {
    auto node_position = node.get_position();
    auto reference_position = reference.get_position();
    auto node_position_row = std::get<0>(node_position);
    auto node_position_column = std::get<1>(node_position);
    auto reference_position_row = std::get<0>(reference_position);
    auto reference_position_column = std::get<1>(reference_position);

    return (
        std::pow((node_position_row - reference_position_row), 2) +
        std::pow((node_position_column - reference_position_column), 2)
    );
}


Position get_start(Graph const &graph) {
    return get_first_index(graph, USER_BLOCK);
}


Nodes get_children(Node &node, Graph const &graph) {
    Nodes children;

    int row;
    int column;
    std::tie(row, column) = node.get_position();

    for (int row_offset = -1; row_offset < 2; ++row_offset) {
        for (int column_offset = -1; column_offset < 2; ++column_offset) {
            if (row_offset == 0 and column_offset == 0) {
                // (0, 0) will always be `node`. We can't let `node` be a child
                // of itself so we have to `continue` here
                //
                continue;
            }

            Graph::size_type node_row = row + row_offset;
            Graph::size_type node_column = column + column_offset;

            if (node_row >= graph.size()) {
                continue;
            }

            if (node_column >= graph[node_row].size()) {
                continue;
            }

            children.push_back({
                static_cast<int>(node_row),
                static_cast<int>(node_column),
                &node
            });
        }
    }

    return children;
}


Nodes trace(Node const &node) {
    Node* parent = node.get_parent();
    Nodes path;
    std::set<Node> seen;

    while (parent != nullptr) {
        auto parent_node = *parent;
        if (std::find(seen.begin(), seen.end(), parent_node) != seen.end()) {
            // If this happens, `parent` is already in `path`. To avoid
            // a cyclic loop from happening, we will break out, instead.
            //
            break;
        }

        seen.insert(parent_node);
        path.push_back(parent_node);
        parent = parent->get_parent();
    }

    return path;
}


Nodes a_star(Graph const &graph, Node const &user, Node const &goal) {
    Nodes open_list {user};
    Nodes closed_list;

    while (open_list.size() != 0) {
        Node current_node = open_list[0];
        unsigned int current_index = 0;

        for (int index = 0, max = open_list.size(); index < max; ++index) {
            auto node = open_list[index];
            if (node.get_f() < current_node.get_f()) {
                current_node = node;
                current_index = index;
            }
        }

        if (current_node == goal) {
            auto path = trace(current_node);
            std::reverse(path.begin(), path.end());
            return path;
        }

        open_list.erase(open_list.begin() + current_index);
        closed_list.push_back(current_node);

        auto children = get_children(current_node, graph);
        for (auto &child : children) {
            if (std::find(closed_list.begin(), closed_list.end(), child) != closed_list.end()) {
                continue;
            }

            if (!is_walkable(child, graph)) {
                continue;
            }

            child.set_g(child.get_parent()->get_g() + 1);
            child.set_h(get_h(child, goal));
            child.set_f(child.get_g() + child.get_h());

            bool add = true;
            for (auto const &open : open_list) {
                if (child == open && child.get_g() > open.get_g()) {
                    add = false;
                    break;
                }
            }

            if (add) {
                open_list.push_back(child);
            }
        }
    }

    return {};
}


int main() {
    Graph graph = {
        {0, 0, 0, 0, 1, 0, 0},
        {0, 3, 0, 0, 1, 0, 2},
        {0, 0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 1, 0, 0},
    };

    int start_row = 0;
    int start_column = 0;
    std::tie(start_row, start_column) = get_start(graph);

    int end_row = 0;
    int end_column = 0;
    std::tie(end_row, end_column) = get_end(graph);

    auto user = Node(start_row, start_column);
    auto goal = Node(end_row, end_column);

    std::cout << user << std::endl;
    std::cout << goal << std::endl;

    auto nodes = a_star(graph, user, goal);

    std::cout << "Path: [";
    for (auto const &node : nodes) {
        std::cout << "("
            << std::get<0>(node.get_position())
            << ", "
            << std::get<1>(node.get_position())
            << "), ";
    }
    std::cout << "]" << std::endl;

    return 0;
}

当我在我的计算机上运行它时，我得到这个输出：

Node((1, 1), 0, 0, nullptr)
Node((1, 6), 0, 0, nullptr)
Path: [(1, 6), ]

Path:应该返回从(1, 1)到 目标的完整列表，(1, 6)但不是[(1, 1), (1, 2), (2, 3), (3, 3), (4, 4), (3, 5), (2, 6), (1, 6), ]. 我们得到了[(1, 6), ]。我认为这是因为current_node包含自己作为父母。所以trace提前休息以避免循环。这就是为什么输出中只有一个。奇怪的是，任何 Node 都会将自己作为父节点，因为如果发生这种情况，构造函数会抛出异常。

事实上，在我的机器上，每个节点的每个父节点都是同一个地址0x7fffffff9140，这不应该发生。

我对此的唯一猜测是current_node在 while 循环中被初始化，所以即使节点位置 / f / g / h 正在改变，内存中的指针永远不会改变。所以所有节点最终都会以这种方式获得相同的父节点。

这可能是问题，也可能不是问题，但无论哪种方式，我都不确定如何解决它。任何意见将是有益的。谢谢！

标签： c++

Answer 1

这个构造函数体完全搞砸了，您正在从this->parent始终初始化为nullptr（由大括号或相等初始化器）初始化的成员中读取。

 Node(int row, int column, Node *parent) : row(row), column(column)
 {
    if (this->parent != nullptr && *this->parent == *this) {
        throw "Node cannot be parented to itself";
    }

    this->parent = parent;
}

current_node第二个主要问题，这是传递对生命周期不足的对象的引用：

auto children = get_children(current_node, graph);

当您从列表中读取任何“孩子”时，其成员指向的节点parent已经被销毁。

in 的副本closed_list会继续存在，但也不能用于存储parent指针，因为std::vector. 如果您更改closed_list为，std::list<Node>则元素地址将是稳定的。

但是当a_star返回时，实例parent指针指向的所有对象无论如何都会死掉。 trace(current_node)产生一个节点集合，其parent成员指向集合之外。

您最好的选择可能是为整个graph实例预分配足够的 Node 对象，使用索引而不是指针作为父级，并parent在构造期间更新成员而不是设置它。与指针不同，索引值无论复制数据结构多少次都保持有意义。

（此外，字符串文字会产生错误的异常对象）