Wow! This sounds great! I'm going to give it a shot! Maybe this will replace "Replicating Belts" for me!

Edit: Hahaha! This is madness! I'v tried it in my huge Krastorio 2 base from one end diagonally over my bus to the other end of the base. Not only life, but BeltRouter finds a way! So great!

Well, I cheered too soon. Here are some screenshots: https://imgur.com/a/KIQDAh0 (shortly after placing the build order, a detail view of the problem and the finished result)

I tried to route 8 lanes of copper in one swoop by shift right clicking the starting belts and then the ending belts at the splitter. Your algorithm doesn't seem to respect already existing entity ghosts. Notice the brighter-than-normal ghosts. I suspect the algorithm just places two ghosts on top of each other.

I'll have to test it further. I suspect that if I let one lane be built and then do the next one it would yield better results.

Apart from that, the algorithm totally stalls the server. Do you try to do the pathfinding in one tick? Because it seems the game is waiting until the path finder is done. Could you make the pathfinder asynchronous? So the game continues to run while the path finder chuggs along until it reaches a result or a timeout?

Great work though!

Edit: I'm not very well versed in the Factorio API, but in Lua you can have Coroutines (https://www.lua.org/pil/9.1.html), which seem like the pathfinder needs to be wrapped in.

Edit2: Damn! coroutine isn't accessible in Factorio API (https://lua-api.factorio.com/latest/Libraries.html)

Edit3: https://forums.factorio.com/viewtopic.php?t=51186 Apparently you'd have to break up your loop(s) to be executed over several ticks. Is this possible?

Edit4: Here's a very interesting read how to spread the load over multiple ticks: https://forums.factorio.com/viewtopic.php?t=53405

Edit5:
Regarding the issue with the invalid placement of ghosts:
I think you need to add

build_check_type = defines.build_check_type.ghost_place

after the "position" table entry here https://github.com/Seancheey/FactorioBeltRouter/blob/dd13c4e8de36ab7cc9c0b7595a5650be8261b9f7/control.lua#L102

After applying the change I described, it does work! The ghosts aren't placed on top of each other. Unfortunately now it doesn't respect underground lines and just places undergrounds overlapping each other (think belt weaving with just one color... doesn't work).

Edit: Added a Github pull request. Works fine for me! I hope you'll consider those additions.

Thanks a lot for those changes! Those are definitely in part of my future fixes list. I'll follow up with new version in the following days :D

FYI, the new version will address some of the issues mentioned above. So now routing 4-way belts at the same time might become possible :) Cheers

PS: Still caught some bugs in path finder, but generally good: https://imgur.com/a/RixRxmr

Looks great! Sure, the belts won't run parallel, but that's just the shortest way found, right?! Some people will definitely complain about this...

Yeah XD, that deserves another fix

Yeah XD, that deserves another fix

I don't know. I think it "works as intended". Because after placing a line of belts A* just finds another shortest path. This isn't always a parallel path to existing belts. I don't even know if this would be "fixable".

I think there probably should be some sort of disclaimer like, "Warning, this mod finds the shortest paths, not the most appealing. This won't solve your OCD."

:D

I already have a possible fix in my mind: When selecting multiple starting belts next to each other at the same time, we can check for ending belt's relative position to the starting belts and decide if the belt is in outer path or inner path, and prefer (if possible) going straight N-1 blocks for N outer path (N=number of selected belts).

image this:
---> First outer path prefers going straight 3 blocks
--> Second prefers going straight 2 blocks
-> and so on...

here is the target belts: VVVV

Edit: markdown messed my artistic drawing a little bit, anyway, here is just an idea xD

FWIW, the Jump Point Search variant of A* pathfinding tends to produce the sort of results you suggest, and can improve performance over long distances: https://harablog.wordpress.com/2011/09/07/jump-point-search/

The "Automatic Belt Planner" mod includes logic for running their A* search over multiple ticks; it mostly requires keeping state accessible and terminating after some fixed number of operations per tick, then resuming the next one. shrug

JPS looks like a really good stuff! This mod's new version is now supporting running A* for multiple ticks. I'll take a look at JPS and possibly integrate it into the path finding algorithm in my next version. Thanks

I read the paper about JPS algorithm overnight when you mentioned it haha. It's indeed a very smart algorithm for path finding, but there is a few caveats that made me stop using it:

1. JPS jumping is not bounded, which means for an open world like factorio, there is no terminating condition and a jump can go very long when there is no block in its way and degrade the performance.
2. JPS has a special handling for jump into barriers: It just ignores the jump. Since it assumes that adjacent blocks will handle the barrier corner as a jump point anyway. But in factorio, you can actually "route your way underground" and get pass the barrier. So things are little bit tricky to work with when we can do underground belts.

For 1's solution, there is a bounded JPS algorithm available, but I need to predefine the bound limit, which might again be tricky and add more jump points to the solution and slow the performance.
For 2, I haven't come up with a good solution for that. (Maybe I'm just not smart enough xD)

But thanks for mentioning JPS algorithm, I got a new idea for pruning some unnecessary underground belt candidates so in the new version 0.6.1 the searching speed is a lot faster.

So to summarize, I haven't find a very good way of integrating JPS into this specific factorio situation yet. Maybe with another few days I can come up with a good idea? Any suggestion is welcomed