Factorio Forums

This is an archive of old versions since there's an attachment limit of 10/post. See the current release thread for newer versions.

Automate yet another aspect of constructing your factory!

Finding a way for a new transport belt through the maze of your factory has never been easier. Simply place a pair of transport belt start and end markers on the ground. This automatic belt planner will create transport belt ghosts between them for your construction robots to fill in. The path finding process runs in the background while you're free to take care of other more interesting things.
Known issues

• Not well tested, especially in multiplayer.
• Programmer's placeholder graphics.
• Could be faster.
• Possibly invalid/non-optimal paths could be found if you remodel your factory too heavily while the path finder is running. Modified tiles won't be re-evaluated.

LOL. This mod represents the best sort of cosmic joke. Some poor modder goes to all the work to implement pathfinding in lua (I task I've intentionally avoided in the past), and it has 2 downloads (well, 3 now).

Excellent work. You wrote a masterpiece on a napkin. Also, you're not following the mod posting rules.

Conflicted on this; laying down beltlines is part of the fun, isn't it?

janook wrote:Conflicted on this; laying down beltlines is part of the fun, isn't it?

You say that, but 0.13 has the rail tool that looks a lot like this.

I can see a much more ideal path for both belts if a human were to think of a path . The underground belts being avoided could be changed to something like a user-defined setting. I don't see any examples on how your mod took a longer path to conserve underground belts.

This is a great mod and has a bit of potential. Although it isn't as optimal as you think, even if you think it isn't optimal. The program just "giving up" can't be an option for it to take. The result from the program should be either that it found a path or it didn't. This mod may not wasn't written well well if it doesn't find a path even though there might clearly be one (if this happens at all, which it shouldn't if it was a fully functional path finding system). If your program is "giving up" then it should only stop trying to find a path after an amount of tiles has been reached, and this could be another user variable. The program would also have to make sure it can't make a path below the max number of tiles (making sure it didn't miss a path (this doesn't need to be handled if written correctly)) before it gives up. The timing of the program from activation to termination could be taken into consideration and modified based on this. I recommend writing some timing code and relating this to the Big-O notation from other path finding systems. You will also find that this would be useful when making changes to your code.

I hope you plan to make updates to it, as well as clean things up and make the results more of a yes or no. Also, I think more pictures of more examples would help people better understand the mod before downloading.

saneman wrote:I can see a much more ideal path for both belts if a human were to think of a path .

Well this is (supposed to be) an A* implementation, so it should find a minimal cost path according to the assigned edge weights for straight belts, corners and underground belts. You can certainly disagree with the choice of those weights, so the solution found could look different from what you'd consider ideal. Admittedly, in the first picture the path finder made a choice that I can't quite explain, but this doesn't result in a large difference to what I would have found manually. I can't see anything wrong with the second picture though, what would you have done better?

saneman wrote:The underground belts being avoided could be changed to something like a user-defined setting. I don't see any examples on how your mod took a longer path to conserve underground belts.

Right, seems like there wasn't such an opportunity in those examples. They were just meant to give an idea of how the mod works, not explain everything in detail.

saneman wrote:This is a great mod and has a bit of potential. Although it isn't as optimal as you think, even if you think it isn't optimal. The program just "giving up" can't be an option for it to take. The result from the program should be either that it found a path or it didn't. This mod may not wasn't written well well if it doesn't find a path even though there might clearly be one (if this happens at all, which it shouldn't if it was a fully functional path finding system). If your program is "giving up" then it should only stop trying to find a path after an amount of tiles has been reached, and this could be another user variable.

If a path exists, it would be found eventually. But I don't want to make the user stare at a frozen screen for several minutes so I'm just giving up once the open set reaches a certain size. I think this can be very well an option because the alternative would be a lot worse.

saneman wrote:The program would also have to make sure it can't make a path below the max number of tiles (making sure it didn't miss a path (this doesn't need to be handled if written correctly)) before it gives up. The timing of the program from activation to termination could be taken into consideration and modified based on this. I recommend writing some timing code and relating this to the Big-O notation from other path finding systems. You will also find that this would be useful when making changes to your code.

Not sure what you're trying to say here (and yes, I've heard of the big O notation)

saneman wrote:I hope you plan to make updates to it, as well as clean things up and make the results more of a yes or no. Also, I think more pictures of more examples would help people better understand the mod before downloading.

Just published an update. More pictures, more settings.

Factorio is about imagination and automation I like the idea and just added it to my collection - robots got slightly more intelligent just now.

New version featuring background path finding! This should now be able to find arbitrarily long paths if you're willing to wait long enough.

Also removed blueprints from crafting ingredients. Thought this would be a nice touch, but turns out this also readily consumes already populated blueprints, not only fresh ones. Oops.

prg wrote:This mod should be usable in multiplayer. At least it didn't blow up immediately this one time I tried it for two minutes in a LAN game.

The minor problem here is that path finding produces quite a lot of state. Too much state to be put in the save game ("Error while running deserialisation: [...] function or expression too complex" which is a won't fix.) This is not much of a problem in a single player game: when a game is loaded while there is a running path finding attempt, it will get aborted and you'll be refunded the start marker so you can try again.

The same thing happens when someone joins a multiplayer game: the game gets loaded and the path finding aborted for the new player. It keeps running for everyone else already playing though, since I haven't yet found a "player tries to join the game" event. The resulting desync will be accompanied by this helpful log entry: "Belt planner running while game was loaded. Path finding aborted. If you just got desynced while joining a multiplayer game, this is the reason. Wait a minute, then try again." So the new player just needs to wait till path finding is finished for everyone else, then the game should be joinable again.

This is not very nice of course, but the path finder will probably not run that often and hopefully not for a very long time.If anyone has an idea how to handle this better, I'd be very interested.

I wrote** an A-star pathfinder for Misanthrope that can be run partially, so you can spread the calculation over several ticks. I did not have any problems storing the state. I haven't used it extensively, but I've verified it works.

**I ported one.

Pathfinder: https://github.com/Afforess/Misanthrope ... finder.lua
Basic usage:

pathfinder.a_star(surface, start_pos, end_pos) will generate a path between the two points, if one exists. Tries to solve it immediately. Returns the path or nil if none exists.

pathfinder.partial_a_star(surface, start_pos, end_pos, max_iterations) will start generating a path between two points, and stop after max_iterations has been reached. It returns a table with the state of the current path search. You can store this table in global data, or discard it. To resume pathfinding in a later tick, call pathfinder.resume_a_star(data, max_iterations), with the table returned from partial_a_star and the max_iterations. Will return the table back with the latest state. When data.completed is true, there will be a data.path field in the table you can use to get the path or nil.

The state of the partial path finder is a table with the minimum amount of information to create the path, essentially the f_score, g_score, and current examined tiles. There are no recursive data structures, just 1d arrays or variables, so there should be no risk of storing too much state for global to handle.

Afforess wrote:I wrote** an A-star pathfinder for Misanthrope that can be run partially, so you can spread the calculation over several ticks. I did not have any problems storing the state. I haven't used it extensively, but I've verified it works.

**I ported one.

Pathfinder: https://github.com/Afforess/Misanthrope ... finder.lua
Basic usage:

pathfinder.a_star(surface, start_pos, end_pos) will generate a path between the two points, if one exists. Tries to solve it immediately. Returns the path or nil if none exists.

pathfinder.partial_a_star(surface, start_pos, end_pos, max_iterations) will start generating a path between two points, and stop after max_iterations has been reached. It returns a table with the state of the current path search. You can store this table in global data, or discard it. To resume pathfinding in a later tick, call pathfinder.resume_a_star(data, max_iterations), with the table returned from partial_a_star and the max_iterations. Will return the table back with the latest state. When data.completed is true, there will be a data.path field in the table you can use to get the path or nil.

The state of the partial path finder is a table with the minimum amount of information to create the path, essentially the f_score, g_score, and current examined tiles. There are no recursive data structures, just 1d arrays or variables, so there should be no risk of storing too much state for global to handle.

Ah, that was a great hint. I thought this node.prev pointer/reference/whatever it's called in Lua was such a clever and elegant solution. Now reverted to a came_from array again and suddenly the save games are loadable even with 30k nodes in the open set. Awesome! So it turns out that the total amount of data stored isn't important, just how deeply it's nested. Thanks for pointing me in the right direction.

BTW you seem to be doing a linear search through the whole open set for the lowest f_score on every iteration. Might consider looking into minheaps to keep it sorted, made things quite a bit faster for me (though I'm still doing linear searches in some places. Should come up with a way to profile this and see if it's worth optimizing)

prg wrote: Ah, that was a great hint. I thought this node.prev pointer/reference/whatever it's called in Lua was such a clever and elegant solution. Now reverted to a came_from array again and suddenly the save games are loadable even with 30k nodes in the open set. Awesome! So it turns out that the total amount of data stored isn't important, just how deeply it's nested. Thanks for pointing me in the right direction.

Yeah... It sorta sucks because you can never use the linked list data stucture, it nests deeply very quickly. I've had to use a circular buffer data structure in another factorio mod to work around the lack of linked lists. Anyway, I have Misanthrope storing as much 5MB of lua data and it has not had any major problems, besides the need for constant awareness of data structure depth.

prg wrote: BTW you seem to be doing a linear search through the whole open set for the lowest f_score on every iteration. Might consider looking into minheaps to keep it sorted, made things quite a bit faster for me (though I'm still doing linear searches in some places. Should come up with a way to profile this and see if it's worth optimizing)

Yeah, I'm aware a linear search is less ideal, I considered fixing that, but I haven't actually needed to use the pathfinder much, so it's fallen off my list of things to tinker with.

New version! Less godawfully slow and less broken than ever!

You wouldn't believe how fast it is not to do a linear search through thousands of items on almost every iteration. A path finding operation that was previously dragging down the UPS at five steps/tick now runs smoothly at 50. New users will now get a higher default value for this setting. If you've already used the belt planner before, you might want to increase it manually as already existing user settings will be preserved during updates.

Also fixed a couple issues that make me wonder how the old version was able to yield somewhat usable results at all most of the time.

I'm trying to use v.40, but it says I need base .12.30, which I don't think has been released yet.

machotacoman wrote:I'm trying to use v.40, but it says I need base .12.30, which I don't think has been released yet.

Version 0.12.30 has been released a while ago, but it might still be marked as experimental. You'd need to enable experimental updates in Options -> Other for the DRM-free version or opt into beta or something like that somewhere in the Steam settings.

(While this mod was developed and tested on .30, it should actually already work with earlier Factorio versions. There weren't any relevant changes in .30 but I bumped the version when I updated Factorio myself. Not sure why it isn't marked stable yet. It's been out a while and working great so far.)

You removed blueprints from recipes and solved the hangups now? Nice! I'll try it out again. It's weird that the planner is used up in the process though.

A* is certainly doable in Lua, and it's fast even without LuaJIT. Further, Lua's flexibility enables a few optimizations which other languages make obtuse. I say this from experience. IIRC, my implementation was only 120 lines or so.

That being said, I, too, easily see much better paths in those pictures... Chemical Plant (length) + 1 pipe = 4 tiles, which can be belted under. Thus:

Might be a bit hard to see, but
there's an inserter in the way. The first found path isn't *that* terrible, though the current implementation manages to do a bit better. I still can't see anything wrong with the second path.

The fact that it's used up is a problem. When I use it it is moved from my toolbar to my main inventory which makes it impossible to use it with your toolbar hotkeys. I just gave up on it because of this. The cost doesn't really matter to me at this stage. But I see it as a deconstruction planner or similar tool. Why is the planner used up? Makes it a bit less qonvinient to use.

Also it would be nice if the path it will take when you click was shown before you click, like a dynamic blueprint.
It's a bit russian roulette to use it at the moment: "Will it take a nice short path or will it go one lap around my entire base for endless cleanup fun?"
Yes, it takes the shortest path. What if the shortest path is insanely long and will mess up my factory? Then I might prefer to move something else instead of routing the new belt all over the place. Clicking and hoping the shortest path is something reasonably isn't fun.

It seems like it could be useful sometimes but these small problems are frustrating and it makes manual placing quicker and less scary.

janook wrote:Conflicted on this; laying down beltlines is part of the fun, isn't it?

This can't replace you. You can plan multiple belts at once. This will greedily choose the shortest path for each belt in sequence, which can me much longer in total and will not give you beautiful layouts and patterns. You will not use this when you are trying to compress your factory as much as possible.

Qon wrote:The fact that it's used up is a problem. When I use it it is moved from my toolbar to my main inventory which makes it impossible to use it with your toolbar hotkeys. I just gave up on it because of this. The cost doesn't really matter to me at this stage. But I see it as a deconstruction planner or similar tool. Why is the planner used up? Makes it a bit less qonvinient to use.

Hm, yeah, that's somewhat annoying indeed. The problem is that I'm switching the cursor stack to the end marker once a start marker has been placed and any additional start markers that were held in the cursor don't find their proper place anymore for some reason. I'll look into how this can be handled better.

Qon wrote:Also it would be nice if the path it will take when you click was shown before you click, like a dynamic blueprint.
It's a bit russian roulette to use it at the moment: "Will it take a nice short path or will it go one lap around my entire base for endless cleanup fun?"
Yes, it takes the shortest path. What if the shortest path is insanely long and will mess up my factory? Then I might prefer to move something else instead of routing the new belt all over the place. Clicking and hoping the shortest path is something reasonably isn't fun.

Guess I might just simplify the whole thing to only use a single, re-usable start marker and show a confirmation dialog once a path has been found that lets you select "yep, create blueprints for basic/fast/express belts." or "no, not like that! cancel."

prg wrote:

Qon wrote:Also it would be nice if the path it will take when you click was shown before you click, like a dynamic blueprint.
It's a bit russian roulette to use it at the moment: "Will it take a nice short path or will it go one lap around my entire base for endless cleanup fun?"
Yes, it takes the shortest path. What if the shortest path is insanely long and will mess up my factory? Then I might prefer to move something else instead of routing the new belt all over the place. Clicking and hoping the shortest path is something reasonably isn't fun.

Guess I might just simplify the whole thing to only use a single, re-usable start marker and show a confirmation dialog once a path has been found that lets you select "yep, create blueprints for basic/fast/express belts." or "no, not like that! cancel."

Would be an improvement. But not exactly what I would like. I imagined something more like how the v0.13 rail laying is shown to work in the one of the FFF's.
GIF in the bottom of the post: http://www.factorio.com/blog/post/fff-114
The path that will be used is shown in green just like a blueprint, and updates automatically when you move the mouse to new tiles when you are choosing where to place the end marker. No confirmation dialogue would be necessary then. Instead of choosing which belt is placed with the confirmation dialogue you would then have the option in a toolbar at the top of your screen like many other similar tools.
Examples: Filtered deconstruction planner: viewtopic.php?f=97&t=19548&
If you are going to place a lot of belts one ofter another with this tool you don't want to press ok after every single belt segment construction.

Might not be as easy to implement, but I think it's what is needed to make it convinient enough.

Another idea: The lowest underground belt avoidance level still prefers belts over underground belts. Maybe add a level that uses underground belts for all straight paths where the underground distance is >0. Sometimes I prefer to use normal belts only for trivially short straight paths (<=2) because I don't get moved around by the belts as much then. Also I've heard that underground belts are better for performance reasons so megafactory builders would also prefer a "normal belt avoidance"-level.