Type: Mod
Name: Eketek's Routing and Pathfinding Mod
Description: Adds a circuit-controlled routing and pathfinding mechanism to the game
License: MIT license
Version: 1.0.0
Release: 2018-02-06
Tested-With-Factorio-Version: 0.16.25
Category: Gameplay
Tags: Routing Combinators, Logistics, Circuit Network
Download-Url: https://mods.factorio.com/mod/EketechRouting
Description
The routing mod provides an implementation of the core functionality needed for per-item routing in the LUA programming language and makes this functionality useable in a factory through a set of combinator-like machines.
As a circuit-signal processor, the routing system does not do anything that can not already be done with complex combinator setups (can technically be implemented either by a dedicated pathfinding setup or by a combinator-computer that runs a pathfinding program). But it does so using much less space, with much less lag (combinator/gate-delays from processing logic), and [presumably] more efficiently.
The routing system supports routing of arbitrary or abstract resources (all signals other than the ones the mod adds are intended to be processable by the routing system). It supports complex network topologies (loops and one-way paths). It performs multi-source, multi-sink routing (items can be buffered anywhere and sent anywhere). It includes path cost (both general and per-item). It attempts to alleviate congestion by routing large requests across multiple paths. If there is a shortage of an item, it uses a weighted distribution.
Warning
This mod is a low-level processing component which, to be used effectively, requires a high level of proficiency with combinator-based logic. As such, it is not for everybody (at least not until a decent set of blueprints are drawn up and published).
That said, much of the difficulty in using this mod came about through the decision to keep the mod's interactions with the circuit-network to a minimum. I'd have liked to produce filter-inserter control signals directly, but that would involve making a lot of API calls every tick (this would probably work better as built-in functionality). The alternative was to implement a standardized form of the interactive logic with a hidden set of combinators, but I eventually settled on letting my low-level processing mod be a low-level processing mod and completely deferring the interactive logic to blueprintable combinator setups.
Usage
The routing system mostly uses pulsed signals. These should be captured and stored in accumulators. I recommend using a decider with the "each >0 each" configuration.
The routing system is defined by a set of nodes and links forming a directed graph and controlled by the very creatively titled "Controller" machine:
Controller - Routing system interface
Route Item - Sending a +1 signal for a resource causes the routing system to process the specified resource and schedule item transfers along all generated paths.
Cancel Item - Sending a -1 signal for a resource causes the routing system to send a cancel signal for the specified resource (-2,000,000,000)
Change configuration - various pulsed signals to adjust the routing system behavior or performance tuning.
Node - Defines a reachable network location.
It outputs a continuous nodeID signal.
It accepts a continuous signal indicating what is either buffered and or requested at the node. Requests are negative values. Buffered items are positive values. It does not support a node which has both a requester and a provider for a particular resource, so if that's needed, you'll need to add another node and move the conflicting requester or provider away.
When a routing function is triggered, the node will generate a pulse indicating what was scheduled for pickup (positive) or receipt (negative) at the node (this may be used to control filter inserters that move from the buffer to the network)
Link - Defines a one-way path from one node to an adjacent node.
It accepts two continuous ID signals. One ID is for the Source Node and the other is for the Destination node. the source node signal is just a nodeID copied over. The destination node signal is the nodeID of the destination converted into a "Link to Adjacent Node" signal. You have the option of either using wires to transfer these signals around or of *simply copying the appropriate ID signals into a connected constant combinator.
The link also accepts continuous path cost modifier signals. Per-resource path cost modifier is just a continuous signal for the resource input into the link machine. A general path cost modifier which applies to all resources is also available (added by the mod)
When a routing function is triggered, the link will generate a pulse indicating what was scheduled for transfer onto the link (this may be used to control filter inserters that move from the network to the link)
These machines alone are not sufficient. Combinator proficiency is required. Specifically, in typical usage, you need to feed supply and demand signals to the network components, extract and store transfer signals from it, use the transfer signals to control item movement, cancel or reduce the transfer signals as items are transferred, and [optionally] convert transfer signals into an appropriate path cost modifier.
Below is a test base with a basic usage or routing components. If you load this and rotate the inserter to the right of your starting position, it will move a bunch of items across a non-trivial network of belts and inserters.
Setup with basic usage (with some corrected logic)
(3.4 MiB) Downloaded 140 times
(*) Direct circuit connections between components are technically not required. The Eketech Routing System is quite advanced. It isn't wireless, but Eketek also isn't going to say just how the data gets moved from place to place when no wires are put between.
The Motivation
This mod came about mostly as a result of prior attempts to implement routing strictly with vanilla components (repeatedly concluded that a massively overcomplicated blueprint might as well be a mod...). But, the motivation to go ahead and actually make a mod of it came from the recent "belts vs. bots" controversy - This is an implementation of my proposal, which involved making belts more usable, not by a simple buff, but by adding a path-finding mechanism, so as to bring them somewhat more in line with the capabilities of bots.
Recent Changes
1.0.1
The reset signal has been changed to -2,000,000,000 (to make it easier to recognize and type, as well as to allow its direct use to cancel out signals in simple designs)
(the previous value (-2^31) underflows easily, which can cause simple transfer controllers to break when the reset signal is badly timed)
1.0.0
This mod is now considered stable and complete.
Upgraded the programmer-art. The routing machines now have color, texture, shadow, and no LEDs.
When processing multiple types of items within a single tick, the pathfinder now takes into account the estimated congestion caused by routing of previous items processed within that tick.
Miscellaneous Details
This would be my first time modding Factorio. I also haven't touched LUA in over 10 years.
I am unsure about the performance implications of the high amount of LUA tables and strings used with signal manipulation, so I went with very limited circuit network interaction from mod code and focused mainly on the routing and pathfinding logic for LUA code, deferring the more signal-intensive work back to conventional combinator setups.
License
License
Copyright 2018, "Eketek"
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Re: [MOD 0.16.22] Eketek's Routing and Pathfinding Mod
Posted: Thu Feb 15, 2018 9:05 am
by Eketek
I made a fair amount of progress with the mod. It seems to be stable and working properly. The biggest errors lately been turning out to only be errors in the combinator setup.
So, to help people get started with my routing mod (and perhaps make it a little easier to understand what it does and how it works), I am posting a set of blueprints I have developed [as part of testing] for basic usage of my mod: A provider, a requester, an intersection, and a simple controller.
For simplicity, the blueprints use the warehouses from Pynadon's mod. (the logic for managing "in-flight" items is far more complex, and it is harder and takes a lot more time to debug than what is needed for items which are sitting in a large circuit-readable chest)
Provider
This is a fairly simple. A node with a warehouse attached. It exposes the contents of the warehouse to the routing system. On request, the provider pulls items out of the warehouse and sends it to whichever node it is linked to. It does not fulfill orders precisely or perform any error correction - that is expected to be handled by more sophisticated components elsewhere on the network.
routingmod_basicprovider.png (679.67 KiB) Viewed 3305 times
Requester
This is a node with no outbound links, configured to grab whatever items are sent to it. Put requested amount of items in the constant combinator, and the routing system will do what it can to transfer the specified amount to the warehouse.
routingmod_basicrequester.png (517.34 KiB) Viewed 3305 times
Modular Intersection
This is a 4-way intersection. The complete 4-way intersection is not in the blueprint book. Instead, it is divided into a set of modular blueprints which may be rotated and composed on top of each other to build the intersection. Intersections built in this way may have 0-4 outputs and 0-4 inputs (or any number of inputs from your spaghetti-belts outside of the intersection, since no logic is required for inbound items).
The "frame" blueprint is required. It contains the node, node-specific logic, and all power poles.
The "linklogic" blueprint sets up the combinators needed for one outbound link.
The "belt.out" blueprint adds outbound belts and filter-inserters to put items onto those belts.
The "belt.in" blueprint adds 4 inbound belts to one side.
All 4 blueprints have the central warehouse in common and should all be positioned around that warehouse. All blueprints may be freely rotated and combined (Space within the intersection is reserved for each component).
At a high level, intersections are logically equivalent to nodes in a directed graph. They may be linked to each other to define a network with an arbitrarily complex topology or configuration: Loops, bidirectional links, one-way links, isolated networks - it all works (or at least is supposed to).
To define a one-way link between two nodes (or intersections), read the nodeID of the destination node (signal output by the circle-shaped machine at the destination of the link), and add a "Link to Adjacent Node" signal to the constant combinator attached to the "Link" (the triangle-shaped machines) with the value of the nodeID signal. A two-way link is just a loop formed from at least two one-way links.
The intersection also requires a signal indicating the stack size for stack inserters (S=<stacksize>) on green line on that large power pole that comes with the frame.
The intersection also provides error-correction for the aforementioned provider - Because it sends exact amounts, any extra items that come along will sit in the warehouse until something requests them. For this reason, the intersection also functions as a provider/dump (though if you fill the warehouse completely, you'll jam the network).
Fully built intersection
routingmod_4wayintersection_v2.png (1.37 MiB) Viewed 3267 times
Controller
This automates the routing system in a reasonably simple and configurable way. Once every 15 ticks (triggered by a combinator-based counter), the routing system will attempt to route one type of item which it has not recently performed routing for. If you turn on the combinator with the "Show Messages" signal set, it will also spam you with any error messages the routing system generates. The inserters set up nearby the controller activate routing system functions. The inserter at the bottom will cause the system to perform routing for items of the same type as whatever it grabs. The one on the left will cancel all routing for items of the same type as whatever it grabs. The inserter on the upper/right will cause the system to completely reset (cancel all transfers of everything) if it grabs anything.
routingmod_controller.png (460.49 KiB) Viewed 3305 times
All blueprints are set up to give the [parent] nodeID to the link entity. But, you'll have to supply the destination nodeID. That would be the "Link to adjacent node" virtual signal - just assign that to the constant combinator attached to the link entity. (Also, both positive and negative numbers are accepted - the mod uses absolute value). You also have the option to delete the combinators next to the link and use a wired connection to the destination node (taking the "Node ID" signal from the destination node, convert it to "Link to Adjacent Node", and connect it to the link entity). Also, to reduce the chances of errors from misconfiguration, all combinators attached to links on the blueprints are set to "off" for the blueprint - To safely configure a link, you should add the appropriate "Link to Adjacent Node" signal to the constant combinator, then turn the constant combinator on.
The blueprinted builds are not optimized. It is complete, only in the sense that you can build a functional logistic network out of just these three building blocks. A more complete blueprint set would, at the very least, modify the 4-way intersection to add a high path cost to it and add one or more high-throughput (presumably train-based) multi-way node(s) configured with a low path cost.
The blueprint book also contains copies of the requester, provider, and frame blueprints which are styled with 'concrete-floor-and-hazard-concrete-border' (with ".withfloor" appended to the blueprint names). Use them if you prefer it that way, or delete them if they get in your way too much.
A blueprint book is contained in the following spoiler block. You'll need the "Pynadon's Industry" mod to use the blueprints (or a other similar mod if you are able to make the appropriate adjustments).
EDIT: The "4-way Intersection" has been re-worked - compacted and modularized.
EDIT(2): Fixed a major error in the "linklogic" blueprint. The one I had earlier was defective (Due to an error in the blueprint, the node was failing to properly reserve items intended for transfer, which caused it to give bad data to the routing system). If you want to fix the routing system in an existing base, make a copy of the linklogic blueprint with the constant combinator removed (so that it leaves your settings alone), then, at every built link, de-construct the two decider combinators on the outside edge of the intersection (the ones which conflict with the new linklogic blueprint) and apply the altered ("patch") blueprint to the build, then once all your links are patched, reset the routing system data (send a pulse of 'Auto-select'=-1 to the controller). (a real hotfix)
EDIT (3): Updated the blueprint book again. The requester was broken completely by the 1.0.1 update (prior to the update, it could interfere with its own reset signal and break). I also took the opportunity to update the linklogic blueprint again to have the link raise its own path cost by the total amount of scheduled transfers (I forgot to put it in the first time).
Re: [MOD 0.16.x] Eketek's Routing and Pathfinding Mod
Posted: Mon Mar 05, 2018 10:25 pm
by Eketek
The routing mod is somewhat of a complicated beast (and can be quite rewarding). So, to make it a bit more useable to others, I wrote a brief technical description and guide.
Eketek's Routing and Pathfinding Mod: A Guide
Routing & Pathfinding guide, TLDR edition:
The blueprints and explanation thereof from the previous post should suffice for non-bulk logistics. Just build it, play around with it until it doesn't seem too incomprehensible, rebuild it, and fix it to your liking, and if at any point you break it, hit the data-reset button to clear out errors (that setup can accept unexpected insertions anywhere, so a simple data reset will suffice if everything is hooked up and configured correctly).
Routing & Pathfinding guide, for people who like complex custom builds:
The roting mod, at its core, is a LUA-based logistics processing system which has a circuit-network interface. The LUA code implements only the core logic and defers all the logic to make it useful to combinator-based setups (specifically, the setup demonstrated in the previous post).
The routing mod allows you to define a circuit-controlled logistics network. The network consists of a set of nodes and one-way links in any topology. Nodes are linked to each other by specifying the source and destination node at each link.
As input data, the routing system takes supply and requests signals are input into the system through "Node" interfaces (supply is positive, request is negative), and path information through "link" interfaces (parent node, destination node, path cost, per-item path cost, and a transfer limit).
The network "Controller" accepts pulsed command signals either to trigger routing functions or to set off system-wide data resets. (Custom-triggered processing is largely a performance consideration - the routing function is a heavyweight computation, but it can be useful even when triggered at infrequent intervals, so I decided it would be best to allow factory designer to determine how best to run the routing system)
When a routing function is triggered, the system will send a pulsed signal to every link which it selects for routing. The signal indicates how many items the link should transfer. For this guide (and the routing mod), this is called "Scheduling". A similar signal is sent to all provider and requester nodes, indicating how many items to pick up from the source node and how many items to receive at the destination node (the mod makes no distinction between node types, so the signal sent to provider nodes is positive and the signal sent to requester nodes is negative - and for this reason, a node can not act as both a provider and a requester). These pulses are intended to be captured by memory cells and used to control filters inserters (and decremented every time any items are transferred). This value can [and probably should] also be used to temporarily raise the path cost, making the network less likely to select congested paths.
The routing system provides a mechanism for sending system-wide data reset signals (either for resetting data for particular items or for resetting all data). It is optional and a convenience. Mainly, it is to allow you to build, rebuild, and fix the network in a messy and undirected manner, without having to add special circuits everywhere to fix any problems. The reset signal for any given item is a signal for that item with a value of -2,000,000,000 which is pulsed out of every node and link simultaneously, which should be easy to capture and make use of. once all the transfer signals are cancelled out, any "in-flight" items will reach the next node and may then be treated as freely available to the routing system (or sent along to a dump site or whatever you have in mind to do to unexpected deliveries)
Internally, the routing mod is as close to stateless as I could make it. The only retained information about the routing system is references to all constructed routing entities (so it doesn't have to search for them). Every time the routing system is activated, the network it processes against is defined by the configuration on that tick (such that if you can enable, disable, or change any link inputs, the routing system will accept the update on the next tick).
Routing algorithm:
The routing algorithm should ideally solve a variant of the transshipment problem in which shipments cause congestion (thus the solver should attempt to spread shipments across multiple routes). Presently, I don't have a good solver for this, but the compromise seems to work well enough for most purposes. (If I think of something better, I may revise the mod later.) The solution I have is a complex sweep of the network that attempts to prioritize short routes over longs ones, paired with iterated pathfinding (subdividing and individually scheduling shipments, with path costs rising as it works)
1: Scan the network for all providers and requesters for whatever is being routed.
2: Allocate items - if the amount of items available is equal to or greater than the amount requested, allocate the amounts requested. If there is a shortage, allocate all available items according to a weighted distribution (weighted by request amounts).
3: "Short-Haul Preferential Sweep" - Scan the network and route the items from individual requesters to individual providers, processing transfers involving the fewer hops before processing transfers which would require more. (This is also a performance compromise and may result in sub-optimal behaviour - most notably, routing of items both ways on two-way paths)
4: Route (run for every transfer by the requested preferential sweep) - Subdivide the transfer request into a set of sub-request
5. Schedule-Transfer (for each subrequest) - Use Dijstrka's algorithm to compute the approximately best available path, schedule transfers for the item along the entire path, and [for subsequent pathfinding operations within the tick] increase the cost of every link on the path
Entities and Signals
Controller - Main routing system interface
Inputs:
<item> = 1 (pulsed): Triggers routing function for the specified item
<item> = -1 (pulsed): Send a system-wide reset signal for the specified item
RouteAny = +N (pulsed): Causes the routing system to trigger routing for N items which have not recently been routed. (N being the number of items to process)
RouteAny = -1 (pulsed): Send a system-wide reset signals for all items (To avoid completely trashing performance for that tick, the routing system spreads this out over several ticks, and it will not accept any commands during the reset)
VarNodeID = 1 (pulsed): Regenerate all automatically assigned Unique IDs (needed if you assign an ID to a node which conflicts with an automatically assigned nodeID, otherwise this does nothing useful)
SubrequestMaximum (continuous): Set the maximum amount of sub-divisions to use when attempting to spread a request across multiple paths. default is 16
SubrequestThreshold (continuous): Minimum amount of items needed in a provider-requester transfer before the subdivision logic is triggered (and the target size of each sub-request). default is 200
PathCostModifier (continuous): Amount to add to all path costs on the network
Outputs:
None
Node - A source, destination, or junction (or any combination thereof)
Inputs:
<item> (continuous): If positive, declares this node to be a provider with the amount specified available. If negative, declares this node to be a requester requesting the specified amount.
*VarNodeID (continuous): Force the node to use the specified nodeID. (If you use this, you may need to send the above-mentioned re-assignment command to the controller)
<item> > 0 (continuous): Declare the node to be a provider with the specified type and amount available for transfer.
<item> < 0 (continuous): Declare the node to be a requester requesting the specified item type and amount
Outputs:
<item> > 0 (pulsed): Signal indicating amount of items scheduled for transfer from node storage (for a request elsewhere)
<item> < 0 (pulsed): Signal indicating amount of items scheduled to be received at the node (for a request here)
<item> = -2,000,000,000 (pulsed): Reset signal (should cancel any stored transfer signal in or out)
Link - A one-way path from one node to another node
Inputs:
*NodeID (continuous): Set the source node (NodeID of that node)
*LinkToAdjacentNode (continuous): Set the destination node
PathCostModifier (continuous): Increase the path cost of all transfers of all types of items through the path by the specified amount
<item> (continuous): Add a path cost modifier specifically for the specified item
Outputs:
<item> > 0 (pulsed): Signal indicating the amount of items scheduled for transfer along the path.
<item> = -2,000,000,000 (pulsed): Reset signal (should cancel any stored transfer signal in or out)
(*) For all identifier signals (NodeID, VarNodeID, and LinkToAdjacentNode), the routing system ignores the sign (uses absolute value). (This is to simplify certain designs)