Describe your suggestion

I have done some testing/research on how you can parallelize the pathfinding process.
So far the most promising options have been to have a pool of workers be poping items of the open list and performing the calculations. The other option that showed promise was executing the for loop that loops over the neighbors in parallel. I have only done testing in a 2d grid and have not tested it with any of the optimization baritone already does.
Depending on the amount of threads and cpu cores I have been able to reach variable speed increases. Increasing the number of threads over the number of physical cores does not add additional speed. Thread numbers that would utilize hyperthreading do not speed anything up, because no real i/o tasks are done.

Settings

Number of threads used.

Context

Would create a speedup of the pathfinding.

Final checklist

• I have not used any OwO's or UwU's in this issue.

bruh the pathfinding already has maximum fast. I can't understand why more fast is needed.

Its not and if you read the paper it explains how its not always the best path

https://www.youtube.com/watch?v=n14ZvyTJdOY

Pretty sure every time the line goes purple it has to pathfind again. If you watch his other videos you can see how that leads to suboptimal paths and pruning has to be used.... read the paper on it, its really interesting. And why dont you want it to be better and faster.

Maybe use Thread 1 for planning ahead,
Thread 2 for cost calculation,
Thread 3 for revising paths
This is an example, but you get what i mean.

If someone had more threads than used they would be wasted in that scenario

Also different operations may use less computing than others, wasting efficiency by having to wait for other threads, bottlenecking the whole idea

What operations? If you just have workers looking at the binary heap they all perform the same task.

Cost calulation is what "plans ahead"
Revising paths is just trying out more options. But by revising more and more paths the point of A* over a breadth-first search gets lots. The point of A* is to find the "best" path as fast as possible.

This sounds pretty intriguing to me, I'm by no means an experienced programmer, but this sounds like a decent idea, not sure why people are disagreeing with you outright when they haven't tried it themselves.

Yeah.. as ive said, I tried it and got a performace boost.

You're suggesting multiple threads pulling from the binary heap? This is impossible to do in a thread safe manner.

Worker 1 pulls the best node, worker 2 pulls the second best node, they both compute the edges and add to the heap. Problem is that worker 2 has no opportunity to get the result of worker 1.

For A* to guarantee the best path, the nodes have to be considered in order. It can't just skip around the binary heap. In this scenario, if there were 8 worker nodes, it would consider the 8 CURRENTLY best nodes, without realizing that considering one node adds dozens of new nodes, some of which would be better than the ones that the workers have already picked.

Also you seem to have a misconception about baritone finding nonoptimal paths. That paper refers to picking segments not paths. Every path that baritone executes is guaranteed to be optimal from start to finish. The only thing that that heuristic does is choose how far to go along the optimal path. Those heuristics are not used at all during path calculation. They only come into play once Baritone hits its time limit and it needs to decide what to do.

The only safe multithreading for A* like this would be one thread doing each possible move from a given node, but I've made baritone fast enough that this isn't plausible. Baritone averages in the hundreds of nanoseconds for a movement cost calculation, amortized over all other operations. Transfering the state to another thread would take longer than this.