# A\* Pathfinding test code

**URL:** <https://forums.unrealengine.com/t/a-pathfinding-test-code/70614>\
**Category:** C++\
**Tags:** unreal-engine\
**Created:** [August 4, 2016, 1:27am UTC](https://forums.unrealengine.com/t/a-pathfinding-test-code/70614 "2016-08-04T01:27:53Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![Fishy418](https://d3kjluh73b9h9o.cloudfront.net/original/4X/2/8/5/28502927f1d97ba1051b3b47ccfe17233bf41ef0.png) [@Fishy418](https://forums.unrealengine.com/u/Fishy418)\
**Post date:** [August 4, 2016, 1:27am UTC](https://forums.unrealengine.com/t/a-pathfinding-test-code/70614/1 "2016-08-04T01:27:53Z")

</div>

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 hings 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,

```auto

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

```

```auto

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

```

```auto

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

```
