Finds a Character based on distance and health

Question

I need to improve the efficiency of my program and, using the profiler, have narrowed the problem down to 2 key areas, but I am having trouble coming up with ways to make the program run better.

Based on my profiler's report, it seems to be telling me that my if functions are inefficient. Whats a better way to achieve a better result?

Character* FindAttackTarget() const
        {
            float weakestHp = FLT_MAX;
            Character* weakestEnemy = nullptr;
            uint64_t weakestCharId = INT64_MAX;

            //Only attack characters that are within attack range
            auto& gameChars = m_pGame->m_gameCharacters;


            for (size_t i = 0; i < gameChars.size(); ++i)
            {
                auto& c = gameChars[i];
                if (Location.Dist(c.GetLocation()) <= AttackRange &&
                    c.HP > 0 &&
                    c.Team != Team)
                {
                    //We want the weakest with the lowest ID number - this keeps consistent results when re-playing the same part of the game (eg. after a load game)
                    if (c.HP < weakestHp || (c.HP == weakestHp && c.ID < weakestCharId))
                    {
                        weakestEnemy = &gameChars[i];
                        weakestHp = c.HP;
                        weakestCharId = c.ID;
                    }
                }
            }

            return weakestEnemy;
        }

Answer 1

The tests c.HP > 0 and c.Team != Team are probably blazingly fast tests. Location.Dist(c.GetLocation()) <= AttackRange probably involves the square-root of the sum of the squares of the difference of coordinates in two or three dimensions. Plus, GetLocation() may involve memory allocation and/or copying constructors. It is by far the slowest test, yet you are testing it first! Take advantage of the short-circuit logical and operators by reordering the tests so the fastest tests are done first, so the slowest test may not even need to be executed, resulting in faster execution.

Since all conditions must pass before you update weakestEnemy, you could even test whether or not the target passes the “weakest with lowest ID” test before checking the attack range.

Bonus: the square-root can be avoided; simply compute the square distance, and compare against the \$AttackRange^2\$ (computed outside of the loop) for another speed gain.

Answer 2

The most obvious target for improvement is the outer loop:

Currently, you loop over all characters. If there are few characters, that's fine. If there are many, it's unconscionable.

Consider dividing your play-area into a grid, and adding a std::unordered_multimap to find all characters in a cell. Depending on the range and your cell-size, you won't have to search too many cells, and they won't have that many characters each.

Answer 3

Since you tagged c++, we should make use of C++ features, and not pretend c++ being c with classes.

No raw loops (see Sean Parent's talk on C++ Seasoning)

auto& c = gameChars[i];
if (Location.Dist(c.GetLocation()) <= AttackRange &&
                  c.HP > 0 &&
                  c.Team != Team)
{
    //We want the weakest with the lowest ID number - this keeps consistent results when re-playing the same part of the game (eg. after a load game)
    if (c.HP < weakestHp || (c.HP == weakestHp && c.ID < weakestCharId))
    {
        weakestEnemy = &gameChars[i];
        weakestHp = c.HP;
        weakestCharId = c.ID;
    }
}

The body of the for loop is basically finding the minimum element in a range of Characters, where the range is represented by Characters, which satisfy a pre-condition. There is already a function for that in the STL called std::min_element.

In order to use std::min_element you only have to provide a comparison functor or a pre-define a comparison function for Character, e.g.

bool operator<(const Character& lhs, const Character& rhs)
{
    return lhs.HP < rhs.HP || (lhs.HP == rhs.HP && lhs.ID < rhs.ID);
}

Now considering std::min_element and including the pre-check, we can rewrite FindAttackTarget to:

Character* FindAttackTarget() const
{
    auto& gameChars = m_pGame->m_gameCharacters;
    auto min_it = std::min_element(gameChars.begin(), gameChars.end(), [&](auto& lhs, auto& rhs) {
        // also changed the order of evaluation since Location.Dist() is most likely the slowest to evaluate
        if(lhs.HP > 0 && lhs.Team != Team && Location.Dist(lhs.GetLocation()) <= AttackRange)
        {
            return lhs < rhs;
        }
        return false;
    }));
    if(min_it == gameChars.end()) // no target found
        return nullptr;
    return &(*min_it);
}

Et voila, no raw loops, only using STL algorithms. Now everyone can reason about your program without having to worry about any loop shenanigans you might have mixed up.

From here on, there can only be one bottleneck, and that is the Location.Dist() function as @AJNeufeld already mentioned.

Addon: range-v3

With the range-v3 library, which will be included in c++20, you can pre-filter your attackable targets like this:

bool isAttackable(const Character& c) {
  return c.HP > 0 && c.Team != Team && Location.Dist(c.GetLocation()) <= AttackRange;
}

auto attackableChars = gameChars | ranges::view::filter(isAttackable);

resulting in code for FindAttackTarget:

Character* FindAttackTarget() const {
    auto attackableChars = m_pGame->m_gameCharacters | ranges::view::filter(isAttackable);
    if(attackableChars.empty()) // no target found
        return nullptr;
    return &(*std::min_element(attackableChars.begin(), attackableChars.end()));
}