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;
};