0

我正在根据维基百科的伪代码执行 A* 寻路算法，并且正在尝试优化性能。我注意到大部分时间都浪费在处理“开放”节点集中的节点（基本上是要检查的节点）上，所以我一直在尽我所能让它更快。

（背景，随意跳到代码）基本上，我有一组节点，我用它做什么如下：

  • 找到得分最低的节点
  • 检查一个节点是否包含在集合中
  • 从集合中删除一个节点
  • 将节点添加到集合

通过使用排序链表，查找最低分数从检查所有元素到获取第一个元素。添加节点变得更加复杂，但通常不需要遍历整个列表，因此可以节省时间。无论如何，删除都是一样的。为了检查一个节点是否在集合中，我使用了一个可以直接访问的数组映射，因此可以以一些额外的内存为代价快速完成。

class OpenNodeSet
{
public:
    OpenNodeSet(void);
    ~OpenNodeSet(void);

    void add(GraphNode *n);
    void remove(GraphNode *n);
    void reinsert(GraphNode *n);
    bool contains(GraphNode *n);
    GraphNode* top(void);

    int size(void)          {   return elements;    }
    bool empty(void)        {   return (elements == 0); }

private:
    typedef struct listNode {
        GraphNode *node;
        struct listNode *next;
    } listNode_t;

    listNode_t *root;
    int elements;
    unsigned __int8 map[1024][1024];
};

OpenNodeSet::OpenNodeSet(void)
{
    root = NULL;
    elements = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
            map[i][j] = 0;
}

OpenNodeSet::~OpenNodeSet(void)
{
    while (root != NULL) {
        listNode_t *tmp = root->next;
        free(root);
        root = tmp;
    }
}

void OpenNodeSet::add(GraphNode *n)
{
    listNode_t **head;
    for (head = &root; *head != NULL; head = &(*head)->next)
        if ((*head)->node->f_score > n->f_score)
            break;

    listNode_t *newNode = (listNode_t*)malloc(sizeof(listNode_t));
    newNode->node = n;
    newNode->next = *head;
    *head = newNode;
    map[n->x][n->y] = 1;
    elements++;
}

void OpenNodeSet::remove(GraphNode *n)
{
    listNode_t **head;
    for (head = &root; *head != NULL; head = &(*head)->next)
        if ((*head)->node == n) {
            listNode_t *tmp = *head;
            *head = (*head)->next;
            free(tmp);
            map[n->x][n->y] = 0;
            elements--;
            return;
        }
}

void OpenNodeSet::reinsert(GraphNode *n)
{
    listNode_t **head, **bookmark = NULL;
    listNode_t *ln = NULL;
    int pos = 0;
    for (head = &root; *head != NULL; head = &(*head)->next, pos++) {
        if (bookmark == NULL && (*head)->node->f_score > n->f_score)
            bookmark = head;
        if (ln == NULL && (*head)->node == n) {
            ln = *head;
            *head = (*head)->next;
        }
        if (bookmark && ln)
            break;
    }

    ln->next = (*bookmark)->next;
    *bookmark = ln;
}

bool OpenNodeSet::contains(GraphNode *n)
{
    return map[n->x][n->y]==1;
}

GraphNode* OpenNodeSet::top(void)
{
    return root->node;
}

代码在某些地方并不像它应该的那样干净/高效，现在我只是处于 get-it-to-work 模式。问题是，它不起作用。

重新插入功能在那里，因为我经常需要更改节点的分数，因此也需要更改它在列表中的位置。我没有使用一个列表遍历来删除它，另一个用于插入它，而是使用一个遍历来找到重新插入节点的位置，以及节点本身，这应该可以节省我分配内存和另一个遍历。问题是，有时reinsert函数找不到要重新插入的节点，也就是说该节点不存在（也不存在，我手动检查过）。但这不应该发生。如果我忽略它，最终会出现分段错误（或 Visual Studio 中的等效错误），但我不确定这是否只是忽略它的结果。这是查找路径的函数：

void Graph::findPath(int start_x, int start_y, int goal_x, int goal_y)
{
    GraphNode *start = map[start_x][start_y];
    GraphNode *goal = map[goal_x][goal_y];
    OpenNodeSet open;
    NodeSet closed;

    open.add(start);
    start->g_score = 0;
    start->f_score = distance(start, goal);

    while (!open.empty()) {
        //FIND MIN F_SCORE NODE AND REMOVE NODE FROM OPEN LIST
        GraphNode *curr = open.top();
        open.remove(curr);

        //REACHED GOAL?
        if (curr == goal) {
            reconstructPath(curr);
            break;
        }

        //ADD MIN COST NODE TO CLOSED LIST
        closed.add(curr);

        //FOR EACH NEIGHBOR OF NODE
        for (int i = 0; i < curr->neighbor_count; i++) {
            GraphNode *neighbor = curr->neighbors[i].node;
            float cost = curr->neighbors[i].cost;

            float tmp_g = curr->g_score + cost;
            if (closed.contains(neighbor) && tmp_g >= neighbor->g_score)
                continue;

            bool inOpenSet = open.contains(neighbor);
            if (!inOpenSet || tmp_g < neighbor->g_score) {
                neighbor->parent = curr;
                neighbor->g_score = tmp_g;
                neighbor->f_score = tmp_g + distance(neighbor, goal);

                if (inOpenSet)
                    open.reinsert(neighbor);
                else
                    open.add(neighbor);
            }
        }
    }
}

我的列表实现显然发生了一些事情，但我不知道是什么。当我尝试用其他值测试它时，它的行为就像它应该的那样。我不知道reinsert()它是否应该像它那样工作，因为它不应该得到输入。有趣的是，如果我使用以下而不是reinsert()/add()调用：

        if (inOpenSet) {
            open.remove(neighbor);
        }
        open.add(neighbor);

……一切似乎都很好。我什至检查了 remove 是否在某个时候发现了一个不存在的元素，显然，它不是。这让我怀疑这个reinsert()功能，但我并不像我想的那样确定。据我所知，使用 remove/add 可以使程序正常工作，但会给出不正确的结果。不管怎样，我一直在盯着自己看，需要另一个视角。

有人能看到这里发生了什么吗？这似乎是某种特殊情况，因为问题很少见，但我无法重现它。当我用人工价值对其进行测试时，它会按照reinsert()我的期望去做而不会抱怨。

PS。任何其他优化技巧或比节点之间的距离更好的启发式成本估计也是受欢迎的。大多数情况下，这个特定部分都是关于速度的，而不是关于内存使用的，但两者都很好。哦，堆栈溢出的童贞消失了。

编辑：

结果是一顿美味的晚餐，我只需要几个小时的空闲时间。reinsert() 的最后两行应该是：

ln->next = *bookmark;
*bookmark = ln;

不确定我在测试时是否做对了并且没有注意到代码不匹配，但是你去吧。与常规删除+添加操作相比，在我的特定测试用例中修复重新评分节点所花费的时间减少了 25%。

尽管如此，仍然欢迎更多关于如何使其变得更好的想法。我希望能够进行二进制搜索以找到插入位置，但我想不出一个好的方法来做到这一点，而不必在巨大的固定大小数组或常量 realloc 中铲除大量内存() 调用。

4

0 回答 0