A component to find a path to a certain node

Question

Recently I started fiddling around with pathfinding. I created a WayPoint component to determin a possible way to another actor which is defined over other waypoints. My grid is looking somewhat like this:

The goal was to find a way to the red circled waypoint. A waypoint can have up to eight neigbours. I didn't include the SelectionController or any other component to save some space ;)

The target-actor has a component which implements a similar interface as WayPointComponent but with some minor differences in functionality attached to it.

class WayPointComponent : public ActorComponent
{
public:
    WayPointComponent(Engine* game, mango::int32 dist)
        : ActorComponent("WayPointComponent"), m_Game(game), m_MinPointDistance(dist)
    {}

    virtual void Update()
    {
        
    }

    virtual void Move(Vector2 motion)
    {

    }

    virtual void SetPosition(Vector2 pos)
    {

    }

    static void FindPath_th(WayPointComponent* wp)
    {
        wp->FindPath();
    }

    virtual void FindPath()
    {
        SelectionController* selection = (SelectionController*)GetOwner()->FindComponent("SelectionController"); //the selection controller is used to identify the selected waypoint
        Actor* target                  = &selection->GetSelectedActor();

        if (target && GetOwner()->GetActorName() != target->GetActorName())
        {
            Actor* bestNeighbour  = GetClosestNeghbourTo(target);

            WayPointComponent* wp = (WayPointComponent*)bestNeighbour->FindComponent("WayPointComponent");

            //wp->FindPath();
            Util::LaunchBackgroundTask(mango::bind<void>(FindPath_th, wp)); //The actor who is selected won't launch a new task.

            GraphicProperties* graphics = (GraphicProperties*)bestNeighbour->FindComponent("GraphicProp");

            if (graphics->GetOwner()->GetActorName() != target->GetActorName())
            {
                graphics->SetActiveAnimation(AnimationIDs::idleOnWay); //Sets the animation of every element on the part to a purple flashing square
            }
        }
    }

    virtual void Init()
    {
        Vector2 pos = GetOwner()->GetPosition();

        std::string neighbour1 = std::string("square(") + mango::to_string(pos.X - m_MinPointDistance) + std::string("|") + mango::to_string(pos.Y                     ) + std::string(")");
        std::string neighbour2 = std::string("square(") + mango::to_string(pos.X + m_MinPointDistance) + std::string("|") + mango::to_string(pos.Y                     ) + std::string(")");
        std::string neighbour3 = std::string("square(") + mango::to_string(pos.X                     ) + std::string("|") + mango::to_string(pos.Y - m_MinPointDistance) + std::string(")");
        std::string neighbour4 = std::string("square(") + mango::to_string(pos.X                     ) + std::string("|") + mango::to_string(pos.Y + m_MinPointDistance) + std::string(")");

        std::string neighbour5 = std::string("square(") + mango::to_string(pos.X - m_MinPointDistance) + std::string("|") + mango::to_string(pos.Y - m_MinPointDistance) + std::string(")");
        std::string neighbour6 = std::string("square(") + mango::to_string(pos.X + m_MinPointDistance) + std::string("|") + mango::to_string(pos.Y + m_MinPointDistance) + std::string(")");
        std::string neighbour7 = std::string("square(") + mango::to_string(pos.X - m_MinPointDistance) + std::string("|") + mango::to_string(pos.Y + m_MinPointDistance) + std::string(")");
        std::string neighbour8 = std::string("square(") + mango::to_string(pos.X + m_MinPointDistance) + std::string("|") + mango::to_string(pos.Y - m_MinPointDistance) + std::string(")");

        if (m_Game->FindActor(neighbour1))
        {
            m_Neighbours.push_back(m_Game->FindActor(neighbour1));
        }

        if (m_Game->FindActor(neighbour2))
        {
            m_Neighbours.push_back(m_Game->FindActor(neighbour2));
        }

        if (m_Game->FindActor(neighbour3))
        {
            m_Neighbours.push_back(m_Game->FindActor(neighbour3));
        }

        if (m_Game->FindActor(neighbour4))
        {
            m_Neighbours.push_back(m_Game->FindActor(neighbour4));
        }

        if (m_Game->FindActor(neighbour5))
        {
            m_Neighbours.push_back(m_Game->FindActor(neighbour5));
        }

        if (m_Game->FindActor(neighbour6))
        {
            m_Neighbours.push_back(m_Game->FindActor(neighbour6));
        }

        if (m_Game->FindActor(neighbour7))
        {
            m_Neighbours.push_back(m_Game->FindActor(neighbour7));
        }

        if (m_Game->FindActor(neighbour8))
        {
            m_Neighbours.push_back(m_Game->FindActor(neighbour8));
        }
    }

private:
    virtual Actor* GetClosestNeghbourTo(Actor* target)
    {
        Actor* favorite = m_Neighbours.front();
        Vector2 favWay = target->GetPosition() - favorite->GetPosition();
        float favDist = sqrtf((float)mango::power(favWay.X, 2) + (float)mango::power(favWay.Y, 2));

        for (mango::int32 current = 0; m_Neighbours.size() > current; ++current)
        {
            Vector2 newWay = target->GetPosition() - m_Neighbours.at(current)->GetPosition();
            float newDist = sqrtf((float)mango::power(newWay.X, 2) + (float)mango::power(newWay.Y, 2));

            if (newDist < favDist)
            {
                favDist = newDist;
                favorite = m_Neighbours.at(current);
            }
        }

        return favorite;
    }

    mango::vector<Actor*> m_Neighbours;
    Engine*               m_Game;
    mango::int32          m_MinPointDistance;
};

Is there a better way to determine the path to the target or is looking for the actor with the smallest distance the best approach for this?

Edit

Vector2 is a 2DVector (x, y). Vector3 would be (x, y, z)

ActorComponent is the BaseComponent class all components have to inherit from

Components are attached to actors and will be activated, updated or addressed by the owning actor.

Actor is the base type of all non-Component entities in the Engine which can interact with each other.

mango:: is a utility namespace with a number of math and utility functions like a custom::vector, a power function and a lot of typedefs.

Answer 1

Some comments on your Init function, which has a lot of duplicated code in it.

You call FindActor twice for each direction check. You can save the value of the first call and add that to the vector:

if (auto a = m_Game->FindActor(neighbour1))
    m_Neighbours.push_back(a);

This saves the result of the FindActor call in a variable, tests that variable for a nullptr, then stores the non-null value into the vector. An optimizer will probably eliminate the use of an actual variable and just reuse the value in a register.

Further deduplication of code can be achieved by using an array of strings instead of 8 named string variables for the neighbour names. Then you can have a loop to call FindActor and add it to m_Neighbors rather than 8 if statements.

The construction of the neighbour names can use a loop if a couple of helper arrays to hold the two offsets used in the name building.

The repeated construction of temporary string variables can be avoided by defining a local string variable to hold them.

Put it all together and you build the neighbor name in one place, call FindActor in only one place, and add to the neighbour vector in one place.

Answer 2

Why are you making everything virtual? I don’t see any derived classes.

How is mango:int32 different from std::int32_t? I assume something is rather different for you to not be using standard types!

Likewise, to_string, power etc. Especially since you are casting to (float) (using C-style casts) rather than having a suitable overload.

    std::string neighbour1 = 
        std::string("square(") + mango::to_string(pos.X - m_MinPointDistance) + std::string("|") + mango::to_string(pos.Y                     ) + std::string(")");

Wow…

Start with use auto (almost everywhere).

You only need one std::string object in the summation for it to work; then it will take a mixture of anything that can be implicitly converted to string.

So far, that gives us:

    using std::to_string;

    auto neighbour1 = 
         "square(" + 
         to_string(pos.X - m_MinPointDistance) + 
         "|" + 
         to_string(pos.Y                     ) + 
         ")" ;

Normally I would do this with a formatting library rather than individual to_string calls and literals concatenated together.

Right out of the box (I normally use a wrapper around Boost.Format, and am looking into a new "modern" performant library):

using boost::format;

auto neighbor1 = str (format("square(%d|%d)") % (pos.X-m_MinPointDistance) % pos.Y);

Next, you have a whole bunch of nearly identical lines! Neighbors 1 through 8 should be formatted with a subroutine. At the very least, passing in 8 separate expressions as parameters but nothing else repeated:

auto neighbor1 = showdisp (pos.X-m_MinPointDistance, pos.Y);
auto neighbor2 = showdisp (pos.X+m_MinPointDistance, pos.Y);
    ⋮

This is followed by 8 identical sections of code with only the digit changed:

    if (m_Game->FindActor(neighbour1))
    {
        m_Neighbours.push_back(m_Game->FindActor(neighbour1));
    }

Don’t do that. If you have a section of code repeated with only the variable changing, and they are numbered in consecutive order, you are crying out for a loop.

In this case, since you are not doing anything with the string other than this action, just make it part of the subroutine.

process (pos.X-m_MinPointDistance, pos.Y);
process (pos.X+m_MinPointDistance, pos.Y);
   ⋮

where you define

void process (int x, int y)
{
    auto neighbor = format ⋯
    if (m_Game->FindActor(neighbour))
        m_Neighbours.push_back(m_Game->FindActor(neighbour));
}

Hmm, you are finding the actor twice? Find it once, throw away the result, find it again to push it? No.

That conditional use-if-exists construct is directly supported by C++.

    if (auto actor = m_Game->FindActor(neighbour))
        m_Neighbours.push_back(actor);

casting

Generally, casting is bad. And old-style casts in the code are always a code review issue. If a cast is actually needed, use a new-style cast or more specific construct such as a helper function. But normally these should be eliminated.

        WayPointComponent* wp = (WayPointComponent*)bestNeighbour->FindComponent("WayPointComponent");

I’m guessing that this is an (evil) down cast due to having a collection of base class pointers.

In this case, since you can’t change the architecture of your library, use a dynamic_cast. And, don’t name the type twice.

        auto wp = dynamic_cast<WayPointComponent*>(bestNeighbour->FindComponent("WayPointComponent"));

(also, does the library require some special (and highly limited) mango::bind construct? I notice you are bouncing through a static function FindPath_th. The std::bind (and boost::bind before it) will work on member functions just as well as free functions. std::bind(&WayPointComponent::FindPath, wp) works just fine without help. So does the modern equivalent, a lambda expression. )

float newDist = sqrtf((float)mango::power(newWay.X, 2) + (float)mango::power(newWay.Y, 2));

Is Vector2 not using float? Do you need to intentionally limit your comparison of newDist and favDist to this precision? Why not use double and not cast anything?

And someone pointed out on a different post that there is a std::hypot function, so just use that!

But I wonder if you need to go to the effort of taking the square root. If comparing distances to see which is smaller/larger, comparing the squares of the distances work just as well! That is a trick of old, when such operations were truly expensive. Since the values exist only inside this function, you can do the tests using quadrance instead of distance.