学校作业A*算法代码无报错但运行异常/无法可视化求助

问题描述 #

我正在为学校作业编写A算法代码，已修复所有语法错误，但代码无法正常运行：程序要么崩溃，要么无法正确可视化A路径。尝试调试但未找到问题，附上基于SFML实现的C++代码，恳请帮忙排查原因。

#include <SFML/Graphics.hpp>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <vector>
#include <limits> // 新增头文件

const int WIDTH = 10;
const int HEIGHT = 10;

struct Node
{
    int x;
    int y;
    mutable float gScore;
    mutable float fScore;
    mutable std::pair<int, int> parent; // 替换指针为坐标对，避免悬空指针

    Node(int _x, int _y) : x(_x), y(_y), 
                           gScore(std::numeric_limits<float>::infinity()), 
                           fScore(std::numeric_limits<float>::infinity()), 
                           parent({-1, -1}) {}

    bool operator==(const Node& other) const
    {
        return x == other.x && y == other.y;
    }
};

// Hash function for nodes，修复对称哈希冲突
struct NodeHash
{
    std::size_t operator()(const Node& node) const
    {
        std::size_t h1 = std::hash<int>()(node.x);
        std::size_t h2 = std::hash<int>()(node.y);
        return h1 ^ (h2 << 1); // 移位避免(x,y)和(y,x)哈希值相同
    }
};

// Overload the ">" operator for nodes
struct NodeGreater
{
    bool operator()(const Node& left, const Node& right) const
    {
        return left.fScore > right.fScore;
    }
};

class Grid
{
public:
    Grid()
    {
        for (int x = 0; x < WIDTH; x++)
        {
            for (int y = 0; y < HEIGHT; y++)
            {
                nodes[x][y] = true;
            }
        }
    }

    void setNode(int x, int y, bool walkable)
    {
        nodes[x][y] = walkable;
    }

    bool isNodeWalkable(int x, int y) const // 改为const成员函数
    {
        return nodes[x][y];
    }

private:
    bool nodes[WIDTH][HEIGHT];
};

float euclideanDistance(const Node& a, const Node& b) // 传const引用
{
    int xDist = b.x - a.x;
    int yDist = b.y - a.y;
    return std::sqrt(xDist * xDist + yDist * yDist);
}

float heuristicCostEstimate(const Node& start, const Node& end) // 传const引用
{
    return euclideanDistance(start, end);
}

std::vector<Node> getNeighbors(const Grid& grid, const Node& node) // 传const引用
{
    std::vector<Node> neighbors;

    for (int x = -1; x <= 1; x++)
    {
        for (int y = -1; y <= 1; y++)
        {
            if (x == 0 && y == 0)
            {
                continue;
            }

            int neighborX = node.x + x;
            int neighborY = node.y + y;

            if (neighborX >= 0 && neighborX < WIDTH && neighborY >= 0 && neighborY < HEIGHT)
            {
                if (grid.isNodeWalkable(neighborX, neighborY))
                {
                    neighbors.emplace_back(neighborX, neighborY); // 用emplace_back更高效
                }
            }
        }
    }

    return neighbors;
}

std::vector<Node> reconstructPath(const Node& end)
{
    std::vector<Node> path;
    Node current = end;

    while (current.parent.first != -1)
    {
        path.push_back(current);
        current = Node(current.parent.first, current.parent.second);
    }

    path.push_back(current);
    std::reverse(path.begin(), path.end());

    return path;
}

std::vector<Node> aStar(const Grid& grid, const Node& start, const Node& end) // 传const引用
{
    std::priority_queue<Node, std::vector<Node>, NodeGreater> openSet;
    std::unordered_map<Node, bool, NodeHash> closedSet;
    std::unordered_map<Node, float, NodeHash> openSetScores; // 记录openSet中节点的最优gScore

    Node startNode = start;
    startNode.gScore = 0;
    startNode.fScore = heuristicCostEstimate(startNode, end);
    openSet.push(startNode);
    openSetScores[startNode] = startNode.gScore;

    while (!openSet.empty())
    {
        Node current = openSet.top();
        openSet.pop();

        if (current == end)
        {
            return reconstructPath(current);
        }

        closedSet[current] = true;

        std::vector<Node> neighbors = getNeighbors(grid, current);

        for (Node& neighbor : neighbors) // 用非const引用修改属性
        {
            if (closedSet.count(neighbor) > 0)
            {
                continue;
            }

            float tentativeGScore = current.gScore + euclideanDistance(current, neighbor);

            bool neighborInOpenSet = openSetScores.count(neighbor) > 0;
            bool neighborIsBetter = false;

            if (!neighborInOpenSet || tentativeGScore < openSetScores[neighbor])
            {
                neighborIsBetter = true;
                neighbor.gScore = tentativeGScore;
                neighbor.fScore = tentativeGScore + heuristicCostEstimate(neighbor, end);
                neighbor.parent = {current.x, current.y};

                if (!neighborInOpenSet)
                {
                    openSet.push(neighbor);
                    openSetScores[neighbor] = neighbor.gScore;
                }
                else
                {
                    // 更新openSet中节点的分数：由于priority_queue无法直接更新，采用"重复入队"策略，后续处理旧节点时会忽略
                    openSet.push(neighbor);
                    openSetScores[neighbor] = neighbor.gScore;
                }
            }
        }
    }

    return std::vector<Node>();
}

int main()
{
    sf::RenderWindow window(sf::VideoMode(500, 500), "A*");
    Grid grid;

    grid.setNode(3, 3, false);
    grid.setNode(3, 4, false);
    grid.setNode(3, 5, false);
    grid.setNode(4, 3, false);

    Node start(1, 1);
    Node end(8, 8);

    std::vector<Node> path = aStar(grid, start, end);

    while (window.isOpen())
    {
        sf::Event event;
        while (window.pollEvent(event))
        {
            if (event.type == sf::Event::Closed)
                window.close();
        }

        window.clear();

        for (int x = 0; x < WIDTH; x++)
        {
            for (int y = 0; y < HEIGHT; y++)
            {
                sf::RectangleShape rect(sf::Vector2f(50, 50));
                rect.setPosition(x * 50, y * 50);
                rect.setOutlineColor(sf::Color::Black);
                rect.setOutlineThickness(1); // 增加网格线，方便观察
                if (grid.isNodeWalkable(x, y))
                {
                    rect.setFillColor(sf::Color::White);
                }
                else
                {
                    rect.setFillColor(sf::Color::Black);
                }
                window.draw(rect);
            }
        }

        for (const Node& node : path)
        {
            sf::RectangleShape rect(sf::Vector2f(50, 50));
            rect.setPosition(node.x * 50, node.y * 50);
            rect.setFillColor(sf::Color::Green);
            rect.setOutlineColor(sf::Color::Black);
            rect.setOutlineThickness(1);
            window.draw(rect);
        }

        sf::RectangleShape startRect(sf::Vector2f(50, 50));
        startRect.setPosition(start.x * 50, start.y * 50);
        startRect.setFillColor(sf::Color::Red);
        startRect.setOutlineColor(sf::Color::Black);
        startRect.setOutlineThickness(1);
        window.draw(startRect);

        sf::RectangleShape endRect(sf::Vector2f(50, 50));
        endRect.setPosition(end.x * 50, end.y * 50);
        endRect.setFillColor(sf::Color::Blue);
        endRect.setOutlineColor(sf::Color::Black);
        endRect.setOutlineThickness(1);
        window.draw(endRect);

        window.display();
    }

    return 0;
}

关键问题说明 #

1. 哈希函数冲突：原NodeHash用异或导致(x,y)和(y,x)哈希值相同，引发unordered_map节点识别错误，改用移位组合哈希解决。
2. 悬空指针：原代码中neighbor.parent = &current指向栈上临时变量，循环结束后指针失效，改用坐标对存储父节点。
3. 初始分数错误：原Node的gScore/fScore默认0，导致路径计算时错误判断更优路径，改为初始化为无穷大，仅起点设为0。
4. openSet状态不同步：原代码修改start分数后才push进队列，队列中是未修改的副本；同时检查节点是否在openSet的方式低效且无法获取当前分数，改用unordered_map记录openSet节点的最优gScore。
5. 传值拷贝问题：原函数参数传值导致Grid和Node频繁拷贝，状态不一致，改为传const引用提升效率和正确性。

内容的提问来源于stack exchange，提问作者Jonas Montonen