c++ - C++ 中的 QHashIterator

Question

我用 C++ 开发了一个游戏，想确保一切都正确完成。使用 QHashIterator 检查列表中的哪个项目具有最低值(寻路的 F 成本)是否是一个好的解决方案。

我的代码片段:

 while(!pathFound){ //do while path is found

        QHashIterator<int, PathFinding*> iterator(openList);
        PathFinding* parent;
        iterator.next();
        parent = iterator.value();

        while(iterator.hasNext()){ //we take the next tile, and we take the one with the lowest value
            iterator.next();
            //checking lowest f value
            if((iterator.value()->getGcost() + iterator.value()->getHcost()) < (parent->getGcost() + parent->getHcost())){
                parent = iterator.value();
            }
        }

        if(!atDestionation(parent,endPoint)){ //here we check if we are at the destionation. if we are we return our pathcost.
            clearLists(parent);
            filllists(parent,endPoint);
        }else{
            pathFound = true;
            while(parent->hasParent()){
                 mylist.append(parent);
                 parent = parent->getParent();
            }
            pathcost = calculatePathCost(mylist);    //we calculate what the pathcost is and return it
        }
     }

如果没有？有更好的改进吗？

我还发现了一些关于 std::priority_queue 的信息。它比 QHashIterator 好这么多吗？

这对于游戏世界来说可能不是什么大问题。但是当游戏世界很大时(比如 + 10000 次计算)，我正在寻找合适的解决方案。有什么标记吗？

Answer 1

这里基本上是扫描整个 map ，根据一些值找到最小的元素:

while(iterator.hasNext()){ //we take the next tile, and we take the one with the lowest value
    iterator.next();
    //checking lowest f value
    if((iterator.value()->getGcost() + iterator.value()->getHcost()) < (parent->getGcost() + parent->getHcost())){
        parent = iterator.value();
    }
}

所有这些代码，如果你有一个 STL 容器，例如一张 map ，可以简化为:

auto parent = std::min_element(iterator.begin(), iterator.end(), [](auto& lhs, auto& rhs)
  { lhs.value()->getGcost() + lhs.value()->getHcost()) < (rhs.value()->getGcost() + rhs.value()->getHcost() }

一旦你有了更容易理解的东西，你就可以尝试不同的容器，例如，在这种情况下，保存一个排序的 vector 可能会更快。 )

您的代码本身并没有出现任何明显的问题，通常优化小循环并不能提高性能，更多的是您的代码组织方式。例如，我看到您有很多间接寻址，这些间接寻址会导致缓存未命中。或者，如果您必须始终找到最小元素，您可以将它缓存在另一个结构中，并且您将在恒定时间始终拥有它。