I want to make an A* pathfinding algorithm.

[fair thorn]

I have an idea how to find a good path while maintainjng some amount of performance, but once I reach the target I don't know how I'm going to trace back the best route. I was thinking of giving each marker 3 scores which contain the coordinates of the previous block it was on, so it can trace back easily. The problem is it will require macros, which will crush the performance. Another problem is if there isn't any path that will lead to the target, how do I prevent it from going on forever

[fair thorn]

Ping in reply please

[glossy trench]

you don't need any macros

just store the data in the markers custom data tag, or in a data storage.

[fair thorn]

How would I trace back from the target to the source and tag all the markers in that path then kill the others without:

Everytime I take a step and summon a marker, I give that marker 3 scores: the x, y, and z positions of the previous marker it came from

When I reach the target, use those scores, use a macro to keep positioning at those scores until I reach the source

Do you have any suggestions?

[pearl tree]

No need to store the xyz positions, since the previous node is in one of the adjacent blocks. You could just make it face the previous node and backtrack with ^ ^ ^1

[fair thorn]

How would I know which node was the previous node without the coordinates? There may be several nodes adjacent to the current block, but only 1 of them has the most optimal path

[pearl tree]

Rotate it towards the previous node at the time of summoning, e.g.

execute positioned ~ ~ ~-1 if block ~ ~ ~ air unless entity @e[type=marker,tag=node,distance=..0.1,limit=1]:
  summon marker ~ ~ ~ {Tags:["node"]}
  rotate @e[type=marker,tag=node,distance=..0.1,limit=1] facing entity @s eyes

[fair thorn]

awesome, thanks!