For the most part my Async pathfinding is working smoothly, but when I push it to the max and stress test it I’m still getting data race issues. I believe there are only 3 points where my threads COULD be accessing the same data (enqueue, dequeue, and executing the delegate). I can’t figure out how this is happening.
Ok had a quick look at your code. It could be improved in places.
First off your FindPath node has the problem that it checks if ThreadPool is valid, but it does not handle the situation when it’s invalid.
You should have a bool bInitialzed set to false.
During begin play where you do the threadpool init you should check if bInitialzed is false. if so initialze the pool and set bInitialzed to true. This should be extrapolated into a function, for instance testInit.
The same function should be called in findpath before you check if (ThreadPool)
I only got the code to work if I put in a slight delay before find path during begin play. Not a good sign.
If you do a direct call then ThreadPool is invalid and the pathfinding fails.
.cpp
void AAsyncPatherfinderActor::BeginPlay()
{
Super::BeginPlay();
// Initialize thread pool
InitThreadPool();
}
bool AAsyncPatherfinderActor::InitThreadPool()
{
if (bIsThreadPoolReady == false) {
ThreadPool = FQueuedThreadPool::Allocate();
ThreadPool->Create(7, 128 * 1024, TPri_Normal); // Adjust the number of threads and stack size as needed
bIsThreadPoolReady = true;
}
return bIsThreadPoolReady;
}
void AAsyncPatherfinderActor::FindPath(TMap<FIntPoint, FTileDataCPP> Grid, FIntPoint Start, FIntPoint Finish, TArray<ETileTypeCPP> ValidTileTypes, FString UnitID)
{
//UE_LOG(LogTemp, Warning, TEXT("findpath started"));
bool StartWalkable = IsTileWalkable(Grid, Start);
bool FinishWalkable = IsTileWalkable(Grid, Finish);
bool FinishValidTileType = ValidTileTypes.Contains(Grid.FindRef(Finish).Type);
if (Start != Finish && StartWalkable && FinishWalkable && FinishValidTileType) {
//UE_LOG(LogTemp, Warning, TEXT("C++: Input Valid"));
//CalcThread = new FAsyncPathfinder(Grid, Start, Finish, ValidTileTypes, UnitID, this);
//CurrentRunningThread = FRunnableThread::Create(CalcThread, TEXT("Calculation Thread"));
FAsyncPathfinder* PathfinderTask = new FAsyncPathfinder(Grid, Start, Finish, ValidTileTypes, UnitID, this);
if (InitThreadPool()) {
if (ThreadPool)
{
ThreadPool->AddQueuedWork(PathfinderTask);
ActiveTasks.Increment();
}
else
{
delete PathfinderTask;
UE_LOG(LogTemp, Error, TEXT("ThreadPool is null in AAsyncPatherfinderActor::FindPath"));
}
}
}
else {
UE_LOG(LogTemp, Warning, TEXT("Data is not valid"));
}
}
TQueue should work well with multi-threading. It’s noted as one of Unreal’s thread safe container classes. I’ll have to look into the logic more before I can say more.
This is a very good catch. Thank you. I think I may have found my data race issue. I didn’t have “void AAsyncPatherfinderActor::NotifyPathfindingCompleted(const FString& UnitID)” Tied to the same lock as the Thread pool logic.
You can maybe use the grid 2d macro as a start point to build your grid
You can do box traces of a set size. Set a cell size and use box traces of a half size of the trace (if I remember correctly) then you can catch obstacles and passable terrain.
You can the build the map dynamically via the x y coordinate and discovered contents of the trace. (probably best via actor tag checks)
You should probably try converting the find function to be an async function with a completed / fail state. On complete it should return the points of the path.
You could consider converting the actor to a blueprint library with static functions. Then it could be accessible from anywhere in the project with no instance.
The grid method is ok for smaller levels but it will get tougher to calculate on larger levels as the density of possible path sectors will increase dramatically especially on open terrains.
Also if you are still continuing the tower defense game from previous posts then if you are going to have many units then perhaps flow fields might be a better solution
Not to debunk your current work, just giving you a tool to the toolbox if it gets too complex with more units.
■■■■! I wish I would’ve discovered flow fields earlier. I have the game pretty optimized with the A* and can see easy wins to further optimize it, but this would eliminate units having to submit path requests and then retrieve their paths. They just read the tile and go the direction it tells them to. What I didn’t get from the videos - does each tile have its own flow field for the entire grid? If that’s the case, wouldn’t it be really computationally heavy if people are rapidly placing and removing towers?
This is all really great info. Thanks for taking the time to help.
I’m not sure if you played Line Tower Wars, the warcraft 3 custom game, but I’m remaking it with a ton of improvements
It was incorporated into “supreme commander 2” and “planetary annihilation”.
It is used for groups of units. It generates the flow fields and instead of calculating paths for each unit it sort of makes a “river” of vectors over which the units flow to their destination.
So 1 calculation can be used by even 20 units instead of calculating 20 paths as long as they share movement characteristics. The lack of many paths also means that they don’t recalculate on intersection.
Yea, this seems WAY more efficient for what I’m trying to do. I worked so hard on that pathfinding!!! D:
I’ll have to have 3 flow fields for each lane - 1 for flying, 1 for ethereal, and 1 for normal ground units.
The only thing I’m not sure about is this - Every time someone adds or removes a building ill have to recalculate the flow field. Each recalc requires calculating EVERY tile each time. Whereas A* only evaluates a subset of the entire grid
Depends on how far you extend the field. You don’t have to calculate the whole map.
It’ll be done the on a separate thread and can be queued. You could have an array of elements in the passed in grid and then do a check upon building change if the building plot overlaps the calculated path, to see if it needs an update.
