x

Search in
Sort by:

Question Status:

Search help

  • Simple searches use one or more words. Separate the words with spaces (cat dog) to search cat,dog or both. Separate the words with plus signs (cat +dog) to search for items that may contain cat but must contain dog.
  • You can further refine your search on the search results page, where you can search by keywords, author, topic. These can be combined with each other. Examples
    • cat dog --matches anything with cat,dog or both
    • cat +dog --searches for cat +dog where dog is a mandatory term
    • cat -dog -- searches for cat excluding any result containing dog
    • [cats] —will restrict your search to results with topic named "cats"
    • [cats] [dogs] —will restrict your search to results with both topics, "cats", and "dogs"

Recursive node-based pathfinding

In the image below, I have a set of nodes with splines connecting them together.

These nodes are basically just empty blueprints with a C++ parent class that manage the spline connections whenever a change is made in the editor.

In the character class, I've implemented the ability to raytrace (or "shoot to choose") a node.

When a node is chosen, the player is placed on the node closest to his current location.

The goal of this project is to try and figure out which paths are valid ones to take to reach the chosen node, starting at the node the player has been placed at. I am NOT just searching for the shortest path, I'm searching for all valid paths to the target node.

The problem I'm having is implementing a recursive function which does exactly that. The closest I've come was starting at NodeA, choosing NodeC2, and having the function return NodeB1 and then a bunch of empty values.

Here's the code that I've written so far:

 struct NodePathData
 {
     NodePathData(ANode *Node, int32 PathIndex) : Node(Node), PathIndex(PathIndex) {};
     ANode *Node;
     int32 PathIndex;
 };
 TArray<NodePathData> appendix;
 
 bool FindPathRecursive(ANode *From, ANode *To)
 {
     for (int32 i = 0; i < From->ConnectedNodes.Num(); i++)
     {
         auto node = From->ConnectedNodes[i];
         if (node == To || FindPathRecursive(node, To)) {
             appendix.Add(NodePathData(From, i));
         }
     }
 
     return From == To;
 }
 
 void ATestCharacter::FindAllPaths(ANode *Target)
 {
     auto currentNode = GetNearestNode(); // Not shown here, but trust me it works
     appendix.Empty();
     FindPathRecursive(currentNode, Target);
 }

  

Can anyone help me out?

Again, I'm not looking for Dijkstra's or an A* algorithm here, just trying to assemble valid pathing data.

Product Version: UE 4.11
Tags:
more ▼

asked Apr 29 '16 at 11:49 PM in C++ Programming

avatar image

MichaelWion
250 25 40 50

(comments are locked)
10|2000 characters needed characters left
Viewable by all users

0 answers: sort voted first
Be the first one to answer this question
toggle preview:

Up to 5 attachments (including images) can be used with a maximum of 5.2 MB each and 5.2 MB total.

Follow this question

Once you sign in you will be able to subscribe for any updates here

Answers to this question