A* pathfinding implementation

So I’m making my own pathfinding because unreal doesn’t have it’s own for 2D. It’s a 2D sidescroller so I used a spline map for the AI to navigate so I have smooth level traversal instead of blocks. In the spline map all nodes are traversable and I only need the fastest route. Currently engine crashes with output log that I have too many loop iterations.
So I have 2 questions:

  1. How would I implement a heuristic in a spline map so I can lower the loop count?
  2. Does the engine crash because it tries to do a lot in a single tick? Should I spread out the load and how?

A simple trick that you can perform to execute your logic on several frames is to add very small delays in your loop (you would implement you own loop macro to make you life easier). The delay shall be smaller than the delta time in a typical 60 frames scenario. This way you will force the graph to skip the current frame and continue on the next frame.

The best way is probably to just try to reduce the number of nodes in your graph. If you can’t to that you can try to group nodes and then you use the interior nodes to pathfind within the group, but you’d use the graph of the groups to pathfind between groups.

You can also say any node that’s larger than a fixed world distance from your current node doesn’t need to be calculated at all and calculate its cost as something huge. Maybe if it’s more than 1000 units away from you and the vector from you to it dotted with the vector between you and your target is negative (it’s far away and in the wrong direction) instantly gets maxed.

How many iterations are you getting? Are you sure you implemented it correctly? Maybe it’s a bug with your code rather than just a huge amount of calculations.

I dunno. I’m just brainstorming.

Pretty sure it’s not my code as I’ve been through it back and forth. Was thinking my approach was wrong. So pretty much a recursive function is a no go, can’t afford that ram. So should I have made some finicky tick function so it calculates as it ticks. Because now it’s a single event function with hella for loops inside. I’m only checking adjecant and connected nodes, but I’m constructing the path in that one event. How would I most efficiently implement that grouping? With an overlayed group spline or circle, or simply and array with construction logic?

You can’t put a delay in a function

I know but you can implement your loop body in a function and have the rest in the graph. That’s how I did a A* in BP btw xD.

How are you constructing your graph now? how many nodes does it have?

I’m remaking the pathfinder to be tied in with tick. and in the meantime the ai will use a partially made path before the calculations are completed. then i can easily add to the tick for him to check more until i stress it enough. will keep you posted and probably have more questions.

Thank you for the help. I’ve managed to make it work. It seems my heuristics calculations were too heavy and in wishing to make the pathfinder efficient I made it extremely innefficient. Now it makes a few more calculations but they are lighter in general. Will post another question if thing go out of hand again. Thanks!

Premature optimization something something :stuck_out_tongue: