[MOD 0.16.x] Eketek's Routing and Pathfinding Mod

Topics and discussion about specific mods
Post Reply
Eketek
Long Handed Inserter
Long Handed Inserter
Posts: 56
Joined: Mon Oct 19, 2015 9:04 pm
Contact:
Contact Eketek

[MOD 0.16.x] Eketek's Routing and Pathfinding Mod

Post by Eketek »

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
Usage
The Motivation
Recent Changes
Miscellaneous Details
License
Last edited by Eketek on Sat Feb 24, 2018 7:51 pm, edited 10 times in total.
Top
Eketek
Long Handed Inserter
Long Handed Inserter
Posts: 56
Joined: Mon Oct 19, 2015 9:04 pm
Contact:
Contact Eketek

Re: [MOD 0.16.22] Eketek's Routing and Pathfinding Mod

Post 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
Requester
Modular Intersection
Controller

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).
The blueprint book
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).
Top
Eketek
Long Handed Inserter
Long Handed Inserter
Posts: 56
Joined: Mon Oct 19, 2015 9:04 pm
Contact:
Contact Eketek

Re: [MOD 0.16.x] Eketek's Routing and Pathfinding Mod

Post 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)
Top
Post Reply

Return to “Mods”