QHashIterator in c++

Question

我用c++开发了一款游戏，我想确保一切都做得很好。使用QHashIterator来检查列表中哪个项目的值最低(寻路的F-cost)是一个好的解决方案吗?

我的代码片段:

 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

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

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() }

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

你的代码本身没有出现任何明显的问题，通常性能的提高不是通过优化小循环来克服的，它更多地取决于你的代码是如何组织的。例如，我看到你有很多间接，它们在缓存失败中花费很多。或者，如果你总是需要找到最小元素，你可以把它缓存到另一个结构中，这样你就可以一直以一个常数时间保存它