[MOD 0.12.30] Automatic Belt Planner (old version archive)

[prg]

beltplanner-example.jpg (346.73 KiB) Viewed 12076 times

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.

basic usage

Place the belt planner to create a start marker. Adjust settings to taste.



Place the belt planner again to set the end position. Wait.



Review found path, select belt type and click create ghosts.



Optional continuous build mode: if "place new start marker on end position" is enabled, continue this process by selecting the next end position.

Settings GUI explanation

Path finder behavior can be modified by clicking the settings button shown in the GUI when a start marker is placed.



Always place underground belts if possible; place underground belts if necessary; avoid underground belts if possible.



If an underground belt is placed, should it be as long or as short as possible?



Prefer straight lines, or just do whatever?



Are underground belts on the start and end position acceptable? Yes, on both; not on start; not on end; on neither.



Reduce the steps/tick setting if path finding kills your UPS. Increase it if you want path finding to finish faster and think your system can handle it. This setting is also available while the path finder is running.

Debug mode

To see how the path finder is doing the path finding, you can enable a debug mode which lets you watch the open and closed sets grow, if that is your thing.

debug.jpg (160.88 KiB) Viewed 12076 times

As this is not intended for end user consumption, there's no button in the GUI to enable this and you need to set place_debug_marker = true in control.lua manually. The markers won't be automatically removed anymore, so make sure to have a backup before attempting this.

beltplanner_0.5.1.zip

(56.91 KiB) Downloaded 322 times

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.

Changelog

beltplanner_0.5.1.zip

(56.91 KiB) Downloaded 322 times

Released 2016-05-12

• Fixed that self-intersecting paths could be found in certain situations.
• Updated technology icon.

beltplanner_0.5.0.zip

(29.34 KiB) Downloaded 195 times

Released 2016-05-10

• Less clutter in the inventory: removed belt type specific start markers and config widget. Now there's only a single belt planner item to do everything with.
• No more worries that the belt might be placed exactly where you don't want it: added a preview that lets you accept or cancel the found path before ghosts are placed.
• Start markers don't collide with units and can't be blueprinted and deconstructed anymore.
• Added option to always place underground belts if possible. (You probably also want to use the "underground belts should be as long as possible" setting with that.)
• Continuous build mode: a new start marker can automatically be placed on the end position of a previous path so you can easily build a belt piece by piece.
• Paths won't be placed through existing entity ghosts anymore.

beltplanner_0.4.0.zip

(54.56 KiB) Downloaded 327 times

Released 2016-04-15

• Added config option to allow underground belts on start and end position.
• Fixed several issues that caused subtly flawed to completely nonsensical paths at times.
• Removed last remaining linear search, tremendous speed improvement.
• Lots of internal restructuring.

beltplanner_0.3.1.zip

(52.86 KiB) Downloaded 225 times

Released 2016-04-12

• Already in progress path finding now keeps running when a game is loaded.
• Adjusted "as long as possible" underground belt setting to be more reasonable in certain cases.

beltplanner_0.3.0.zip

(53.14 KiB) Downloaded 211 times

Released 2016-04-11

• Background path finding.
• Removed blueprints from crafting ingredients.
• Added debug mode showing open and closed set markers.

beltplanner_0.2.1.zip

(48.9 KiB) Downloaded 227 times

Released 2016-04-04

• Settings widget item is only given back to the player when the GUI is closed, not when it's opened, so the item doesn't uselessly sit around in the cursor stack the whole time.

beltplanner_0.2.0.zip

(48.92 KiB) Downloaded 198 times

Released 2016-04-04

• Added settings GUI.
• Configurable underground belt avoidance.
• Configurable underground belt length.
• Configurable corner penalty.

beltplanner_0.1.0.zip

(45.95 KiB) Downloaded 275 times

Released 2016-03-23

• Initial release.

[Afforess]

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.

[janook]

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

[Afforess]

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.

[saneman]

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.

[prg]

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?

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.

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.

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)

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.

[GrimerX]

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

[prg]

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.

[Afforess]

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.

[prg]

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)

[Afforess]

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.

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.

[prg]

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.

[machotacoman]

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

[prg]

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.)

[Qon]

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.

[Taehl]

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:

[prg]

Might be a bit hard to see, but

no.jpg (41.26 KiB) Viewed 8495 times

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.

[Qon]

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.

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.

[prg]

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.

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."

[Qon]

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.