Manual memory management in the binary heap used by YAPF.
Description
Just use a std::vector as back end. Also replace uint with size_t where applicable.
Limitations
This implementation does not actually use element 0 to keep the other logic much simpler (fewer potential off-by-one errors). I left the logic the same, as changing the logic will impact logic in other places of the code due to for example indices shifting.
I have tried replacing this implementation with std::priority_queue, but that is not feasible as for the current path finding purposes we want to be able to remove elements from the queue to insert another node with a lower cost. Or because the (previously best) node is only removed from the queue after a cycle of finding open nodes has been done.
Checklist for review
Some things are not automated, and forgotten often. This list is a reminder for the reviewers.
The bug fix is important enough to be backported? (label: 'backport requested')
This PR touches english.txt or translations? Check the guidelines
This PR affects the save game format? (label 'savegame upgrade')
This PR affects the GS/AI API? (label 'needs review: Script API')
ai_changelog.hpp, game_changelog.hpp need updating.
The compatibility wrappers (compat_*.nut) need updating.
This PR affects the NewGRF API? (label 'needs review: NewGRF')
Motivation / Problem
Manual memory management in the binary heap used by YAPF.
Description
Just use a
std::vectoras back end. Also replaceuintwithsize_twhere applicable.Limitations
This implementation does not actually use element 0 to keep the other logic much simpler (fewer potential off-by-one errors). I left the logic the same, as changing the logic will impact logic in other places of the code due to for example indices shifting.
I have tried replacing this implementation with
std::priority_queue, but that is not feasible as for the current path finding purposes we want to be able to remove elements from the queue to insert another node with a lower cost. Or because the (previously best) node is only removed from the queue after a cycle of finding open nodes has been done.Checklist for review
Some things are not automated, and forgotten often. This list is a reminder for the reviewers.