UE4-27: Home-rolled Dijkstra's Blueprint algorithm on a 3400 node grid is really slow. What can I do to speed it up?

First post! Apologies if I screwed something up or if this is in the wrong location. Blueprint is below. The way how this works is, I have three Actors in my project: 1) a GridMgr that takes a level and generates a grid of GridPt Actors. Then a Dijkstra Actor uses those GridPts to do the pathfinding.

The Gridpt nodes themselves are simple Actor BPs with tick disabled, and they just store their location data and a list of what adjacent nodes they are walkable to. On the third person default map, it generates about 3400 node actors with the tile size I’d like.

This function uses a Start node and End node for the start and goal, and using a BFS, it updates PtsToVisitG and VisitedGridPts arrays of node actors to update the weight/distance value of each node, as it iteratively checks every single node. Then a map of positions to weights is created, and a path is later built with that map by sorting through that map starting from End’s location, and polling the node’s adjacent connections.

Thing is, with 3400 nodes, I use that float variable Timer to track how long this call takes, and on my machine it takes about 0.48 seconds to update the maps weights for a given “Start” node.

Eventually, I’d like to make it so that the player can select a character, and it updates the path as you move the mouse around or as the player moves to different tiles, but if this gets called every frame, we’re limited down to about 2 fps or a lot of 0.5sec pauses, so that’s no bueno. :slight_smile:

I’ve seen some toolkits around that do something like this with reasonable speed, and I could just pop open visual studio and try this all in C++, but if blueprints really are about 10x faster, well, that still only gets me to 20 fps. What am I missing? Should I not be using actors for the nodes? Is searching through a 3400 item list really that slow? I can add heuristics and try A*, but I feel like that’s not going to radically improve things. Is this something to try to use multithreading for?

If you’re wondering why I’m not using UE’s navmesh, it doesn’t really do exactly what I want for some other stuff, and in prior experience I’ve had weird issues with it before. And hey, figured I’d brush up on my algorithms while I’m at it.