How do i implement FSearchNode from FGraphAStar?

[SophiaWolfie]

This just boggles my mind.
Normally i can interpret unreal code well. Or remake it myself.
But here im completely lost.

Im trying to build a pure 2d game, that is tile based.
Since its 2d and tile based, i dont need the expensive navigation mesh, and may not need collisions.
I only need an A Star algorithm that can calculate the best tile path to go through to reach a destination.

So i was told to check FGraphAStar, that supposedly has everything.
Though i cant even understand how to call this function because I cant dig into to FSearchNode.

I assume FSearchNode is supposed to be the tiles? My tiles are squares of 200 in size, starting at coordinates 0, 0 and going to like 80.000.

What should i do, and how do i build the FSearchNode and make this work?

Is there any example that shows how this works?
Will this be a very steep mountain to climb?

Cant even call the function FindPath or define its arguments FSearchNode even though i included the Module AIModule in the dependencies and the include “GraphAStar.h”. I dont know what to do here.

please help

[SophiaWolfie]

Bumpity bump? BUMP

[SophiaWolfie]

Im making some progress I could possibly call the function now, though i dont undersand how to create the super convoluted arguments it is asking for:

[Chatouille]

The framework provided is a generic templatized version that expects you to provide your own classes with implementations for a bunch of methods.

Intellisense is generally unhelpful due to the complexity of templates, so finding documentation in code or copying existing implementations is probably your best bet in this case.

Luckily there’s actually a decent documentation in GraphAStar.h

And there are a few implementations available in the engine to copy from.

I don’t know how your whole Grid system is set up, so I’m gonna try and give appropriate example based on what you’re trying to do.
I’m gonna assume AGrid is an actor that contains grid data. I made a simplified one with a SizeX and SizeY and a TMap<FIntPoint, float> where the float is the weight of the cell.

First I define some types to simplify readability

// Simplify types
class AGrid;
typedef FGraphAStar<AGrid> FGraph;
typedef FGraphAStarDefaultNode<AGrid> FSearchNode;
typedef FIntPoint FGridNodeRef;

The AGrid actor class

class AGrid : public AActor
{
public:

    // Dummy grid implementation
    int32 SizeX;
    int32 SizeY;
    TMap<FIntPoint, float> TheGrid; //map position -> weight

    // helper
    float CellWeight(const FIntPoint& Point) const { return TheGrid.FindRef(Point); }

    /////////////////////////////////
    // FGraphAStar: TGraph interface
    typedef FGridNodeRef FNodeRef; //= FIntPoint
    int32 GetNeighbourCount(FNodeRef NodeRef) const
    {
        return 8;
    }
    bool IsValidRef(FNodeRef NodeRef) const
    {
        return NodeRef.X >= 0 && NodeRef.X < SizeX && NodeRef.Y >= 0 && NodeRef.Y < SizeY;
    }
    FNodeRef GetNeighbour(const FSearchNode& NodeRef, const int32 NeighbourIndex) const
    {
        static const FIntPoint Directions[] = { FIntPoint(1, 0), FIntPoint(1, -1), FIntPoint(0, -1), FIntPoint(-1, -1), FIntPoint(-1, 0), FIntPoint(-1, 1), FIntPoint(0, 1), FIntPoint(1, 1) };
        return NodeRef.NodeRef + Directions[NeighbourIndex];
    }
    /////////////////////////////////
};

This is basic grid/neighbour system, but as you can see the TGraph interface does not include weights / travel costs. That part is done in the QueryFilter interface.

You could implement the filter interface in the same class, or a different one. I used a different one for this example.

struct FGridQueryFilter
{
    const AGrid& Grid;
    FGridQueryFilter(const AGrid& Grid) : Grid(Grid) {}

    ///////////////////////////////////////
    // FGraphAStar: TQueryFilter interface

    // used as GetHeuristicCost's multiplier
    FVector::FReal GetHeuristicScale() const
    {
        return 1.0;
    }
    // estimate of cost from StartNode to EndNode from a search node
    FVector::FReal GetHeuristicCost(const FSearchNode& NeighbourNode, const FSearchNode& EndNode) const
    {
        return (EndNode.NodeRef - NeighbourNode.NodeRef).Size();
    }
    // real cost of traveling from StartNode directly to EndNode from a search node
    FVector::FReal GetTraversalCost(const FSearchNode& CurrentNode, const FSearchNode& NeighbourNode) const
    {
        return Grid.CellWeight(NeighbourNode.NodeRef);
    }
    // whether traversing given edge is allowed from a NodeRef
    bool IsTraversalAllowed(const FGridNodeRef NodeA, const FGridNodeRef NodeB) const
    {
        // let's say negative weight means node cannot be crossed
        return Grid.CellWeight(NodeA) >= 0 && Grid.CellWeight(NodeB) >= 0;
    }
    // whether to accept solutions that do not reach the goal
    bool WantsPartialSolution() const
    {
        return false;
    }
    ///////////////////////////////////////
};

Now actual usage should be pretty straightforward :

    // your data
    AGrid* Grid = this;
    FIntPoint StartLoc(0, 0);
    FIntPoint EndLoc(5, 5);

    // using the implementation
    FGraph PathFinder(*Grid);
    FSearchNode StartNode(StartLoc);
    FSearchNode EndNode(EndLoc);
    FGridQueryFilter Filter(*Grid);
    TArray<AGrid::FNodeRef> OutPath;
    PathFinder.FindPath(StartNode, EndNode, Filter, OutPath);

    // result - note that AGrid::FNodeRef is basically FIntPoint
    for (int32 i = 0; i < OutPath.Num(); i++)
    {
        UE_LOG(LogTemp, Log, TEXT("Path: %02i = %s"), i, *OutPath[i].ToString());
    }

[SophiaWolfie]

Thanks a lot.
I thought nobody was going to answer after some time. So I went ahead and converted a solution from pure C++ A pathfinding tutorial on youtube.

It made me understand how it works.
Though this will be useful for someone who stumbles upon this with the same issue.