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"

Office Holiday

Epic Games' offices will be on holiday from June 22nd to July 7th. During this period support will be limited. Our offices will reopen on Monday, July 8th. 

A Star Pathfinding Code and C++ best practice

Hi,

First disclaimer: I am newbie C++ and could make some stupid mistakes with following code! and that is why I'm posting here as I learn best when I try things myself. I still have some basics I probably need to learn but is much easier if I have my own example and can get feedback\suggestion on what I do different or what could cause memory leaks etc.

So here is the code I've done so far, I won't paste all classes related but it should give enough details to understand whats happening.

Here some example feedback\things I have no idea if is best practice or not:

  • I didn't set NodePoint as a UCLASS as this class is only needed in C++ and as many could be created destroyed for each pathfind thought the less overhead the better?

  • is the NodePoint destructor relevant and required for this type of use?

  • the docos say emplace is nearly always better to use than add but from my tests it still makes a copy of the data to put in the array should I be doing OpenList.Add(&LNode), use pointers, etc , mostly just thinking of optimization here?

  • garbage collection, do I need to destroy or delete the LNodes I create but don't use or will C++ automatically clean them up even though they aren't a UCLASS()?

  • Same line as above is OpenList.Empty() required and for non-UCLASS classes will that clear memory or will I need to do manually?

  • when looping through an TArray is it better to use references (eg NodePoint& CNode : OpenList), does this prevent it making\displaying copies of the data?

  • with the below code it seems to crash when trying to display all the nodes (OpenList.Num() = 27) in the open list "DrawDebugSphere(GetWorld(), FVector(0), 50, 32, FColor(200, 255, 200), false, 4000);" if I comment this out it doesn't crash, don't quite understand why here?

The couple of only basic tests I've done shows this code works the way I'm using it but want to learn any good C++ habits now plus understand a bit more for optimization and memory management. I'm only returning a dummy Int from getpath at the moment, later it will return a TArray with a USTRUCTs that blueprints can use. Let me know if any more details or information would be more helpful to understand this?

Thanks,

     class NodePoint
     {
     
     
     public:
     
     
         float FCost;
     
         float GCost;
     
         float HCost; 
     
         int32 PathLength;
     
         FVector2D GridIndex;
     
         NodePoint* ParentNode;
     
     
         FORCEINLINE bool operator==(const NodePoint &Other) const
         {
             if (Other.GridIndex == GridIndex)
             {
                 return true;
             }
             return false;
         }
     
     
     
         // blank initializer
         NodePoint() {    };
     
         NodePoint(const FVector2D CreateIndex)
         {
             GridIndex = CreateIndex;
             GCost = 0;
             FCost = 0;
             HCost = 0;
     
         }
     
         // only to be used for initializing the first (start) path node
         NodePoint(const FVector2D CreateIndex, UGrid* TargetGrid, AGalaxy* Galaxy)
         {
             GridIndex = CreateIndex;
             GCost = 0;
             UGrid* ThisGrid = Galaxy->GetGrid(CreateIndex);
             HCost = ThisGrid->GetWorldDistance(TargetGrid);
             FCost = HCost + GCost;
         }
     
         // destructor
         ~NodePoint()
         {
             ParentNode = nullptr;
         }
     };
     

Main Function

 int32 UPathfinder::GetPath(AUnit* Unit, UGrid* EndPoint, bool EmergencyJump) const
 {
 
 
     //set the start grid as the Units current location
     NodePoint CurrentNode = NodePoint(Unit->Grid->GridIndex, EndPoint, Galaxy);
     UE_LOG(LogTemp, Warning, TEXT("Start Grid %s"), *CurrentNode.GridIndex.ToString())
     int32 CurrentJRange = 2;
     int32 LoopCount = 1;
 
     TArray<NodePoint> OpenList;
     TArray<NodePoint> ClosedList;
 
     // set the array size initially to save recreating the array each add() you do
     OpenList = TArray<NodePoint>();
     OpenList.Reserve(Galaxy->GalaxySize);
 
     // set the array to hold at least 100 nodes initially to save recreating the array each add() you do
     ClosedList = TArray<NodePoint, TInlineAllocator<100>>();
 
     // add the start node to the list of nodes you are checking
     OpenList.Emplace(CurrentNode);
     NodePoint LNode;
     // while you still have options to move too
     while (LoopCount < 8 && OpenList.Num() > 0)
     {
         
         CurrentNode = *GetNewClosest(OpenList, EndPoint);
         TArray<UGrid*> SurroundingGrids = Galaxy->GetGridsInRange(CurrentNode.GridIndex, CurrentJRange);
 
         if (CurrentNode.GridIndex == EndPoint->GridIndex) UE_LOG(LogTemp, Warning, TEXT("Found End %s"), *CurrentNode.GridIndex.ToString());
         // if you found the end point then exit the check loop
         if (CurrentNode.GridIndex == EndPoint->GridIndex) break;
 
         // remove from list so you can't check for this as waypoint again
         OpenList.RemoveSingleSwap(CurrentNode, false);
         ClosedList.Emplace(CurrentNode);
 
         // loop through all grids you can reach from here
         for (UGrid* CGrid : SurroundingGrids)
         {
             bool AlreadyContains = false;
             LNode = NodePoint(CGrid->GridIndex);
 
             // if you have already checked this grid the go to next item
             AlreadyContains = ClosedList.Contains(LNode);
 
             // if item was not already in the closed list
             if (AlreadyContains == false)
             {
                 AlreadyContains = OpenList.Contains(LNode);
 
                 // if item was not already in the open list
                 if (AlreadyContains == false)
                 {
                     
                     LNode.ParentNode = &CurrentNode;
                     LNode.HCost = CGrid->GetWorldDistance(EndPoint);
                     LNode.GCost = CurrentNode.GCost + (CGrid->GetWorldDistance(Galaxy->GetGrid(CurrentNode.GridIndex)) * 0.5);  // dist from previous node to this one + prev nodes current GCost
                     LNode.FCost = LNode.HCost + LNode.GCost;
 
                     UE_LOG(LogTemp, Warning, TEXT("adding node %s %f %f %f"), *LNode.GridIndex.ToString(), LNode.HCost, LNode.GCost, LNode.FCost)
                     //LNode.GCost = CurrentNode.GCost + Galaxy->GridSize.X;
                     //LNode.FCost = LNode.GCost + CGrid->GetWorldDistance(EndPoint);
                     LNode.PathLength = CurrentNode.PathLength + 1;
 
                     OpenList.Emplace(LNode);
 
                 }
             }
 
             // remove any nodes that aren't added to a list immediatly (don't need to do this because it wasn't assigned using pointers?)
             //LNode.Destroy();
             //delete LNode;
         }
 
         
         LoopCount++;
     }
     
     UE_LOG(LogTemp, Warning, TEXT("OpenList %d"), OpenList.Num());
     // loop through all grids you can reach from here
     for (NodePoint& CNode : OpenList)
     {
         GetWorld();   // just had this to make sure I could call a function in the loop without issues, didn't cause crash
         //if (CNode) {
                         //DrawDebugSphere(GetWorld(), Galaxy->GetGrid(CNode.GridIndex)->WorldLocation, 100, 32, FColor(0, 255, 0), false, 4000);   // both this and the below seem to crash UE4.exe invalid memory reference?
             //DrawDebugSphere(GetWorld(), FVector(0), 50, 32, FColor(200, 255, 200), false, 4000);
         //}
     }
 
     // loop through all grids you can reach from here
 //    for (NodePoint& CNode : ClosedList)
 //    {
 //        DrawDebugSphere(GetWorld(), Galaxy->GetGrid(CNode.GridIndex)->WorldLocation, 100, 32, FColor(0, 255, 0), false, 4000);
 //    }
     // clear all arrays used
 
     OpenList.Empty();
     ClosedList.Empty();
 
     return LoopCount;
 };

Function

     NodePoint* UPathfinder::GetNewClosest(TArray<NodePoint>& OpenList, UGrid* TargetGrid) const
     {
     
         float BestScore = 99999999;
         NodePoint* BestNode = nullptr;
     
         // loop through all grids you can reach from here
         for (NodePoint& CNode : OpenList)
         {
             UE_LOG(LogTemp, Warning, TEXT("Check Node %s %f"), *CNode.GridIndex.ToString(), CNode.FCost);
             if (CNode.FCost < BestScore)
             {
                 BestScore = CNode.FCost;
                 BestNode = &CNode;
             }
     
         }
         UE_LOG(LogTemp, Warning, TEXT("Best Node  %s %f"), *BestNode->GridIndex.ToString(), BestNode->FCost);
         return BestNode;
     };
     


Product Version: UE 4.12
Tags:
more ▼

asked Aug 04 '16 at 03:25 AM in C++ Programming

avatar image

Fishy418
48 6 6 8

avatar image Fishy418 Aug 04 '16 at 10:48 PM

Found the crash when trying to DrawDebugSphere... seems objects can't call GetWorld()? so for my example I used the Galaxy Actor passed to the function and Galaxy->GetWorld() seems to work. Guess this is an example of why I should always check pointers are valid. Is it normal that calling GetWorld for an UObject wouldn't return anything?

Would still love to hear any feedback or answers to other questions.

Thanks,

(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