qt — QHashIterator в переполнении стека
Я разработал игру на 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 вычислений). Любые оценки?
Решение
Здесь вы в основном сканируете всю карту, чтобы найти минимальный элемент по некоторым значениям:
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, например карта, может быть уменьшен до:
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() }
Если у вас есть что-то более простое для понимания, вы можете поэкспериментировать с разными контейнерами, например, в этом случае может быть быстрее хранить отсортированный вектор.
)
Ваш код сам по себе не представляет каких-либо очевидных проблем, часто выигрыш в производительности не компенсируется оптимизацией небольших циклов, это больше зависит от того, как организован ваш код. Например, я вижу, что у вас много косвенных ссылок, которые стоят очень много в промахах кэша. Или, если вам нужно всегда находить минимальный элемент, вы можете кэшировать его в другой структуре, и вы будете иметь его в постоянное время, все время.
Другие решения