A component to find a path to a certain node

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.

• What is ActorComponent? What is Vector2? What is in the mango namespace? Where are your includes? In the current state, this code is not really fit for review. Please add all components required to get a full overview of the code and a minimal compilable example. – Ben Steffan Apr 26 '18 at 15:21
• @Ben Steffan Vector2 is a 2DVector (in openGL that one would be called Float2 but in this case it contains 2 integter), ActorComponent is a Component attached to an Actor which can handle different functionalities. Actors are the main entities in the Engine which interact with eachother (a player or an NPC if we stick to game examples). Mango is a utility library I am using and the includes won't tell you anything about the algorithm. If I would add all components, actors or libraries I would just add a giant wall of code. – Mango Apr 26 '18 at 15:41
• Then it will be hard for us to review your code. There are some issues here which can not be resolved without knowing the underlying structure of your program. I highly recommend you to add at least some more of the underlying structure code (at the very least the definition of (ActorComponent)) or you might not be satisfied with what we can do for you. Also, without seeing your includes, how are we supposed to verify that your code works or even compiles? – Ben Steffan Apr 26 '18 at 15:50
• You aren't ;) but I can tell you it will work on windows (and that's where it's supposed to work). The question was more about this component and the way the algorithm is looking for it's next target. :) ActorComponent is nothing but an interface. – Mango Apr 26 '18 at 17:13

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.

• He’s not using the neighbor values anywhere else, so you don’t even need an array to hold them. (I analyzed it further in my post) – JDługosz Apr 26 '18 at 21:33

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…

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.

• A lot of good points, but one thing. I will stick to the mango::bind<xyz> construct since it is configurable with an allocator and it's also used by the underlying thread pool. If I would rather use std::bind it would end up in a mango::bind(std::bind)) like statement (internally) which would remove the benefit of the underlying allocator. That's why I use the non-standard version. (just for clarification. Since I didn't give you the lib you couldn't know). The mango::int types are there since there are some non standard extension types like float16 and I don't want to draw types from n libs. – Mango Apr 27 '18 at 6:47