Efficient graph based networks (electronics and transport)

User avatar
rubenwardy
Moderator
Posts: 6972
Joined: Tue Jun 12, 2012 18:11
GitHub: rubenwardy
IRC: rubenwardy
In-game: rubenwardy
Location: Bristol, United Kingdom
Contact:

Efficient graph based networks (electronics and transport)

by rubenwardy » Post

The Problem

Mods such as mesecons currently work on a per-node basis, and require the area to be loaded to operate. This results in inefficiency when the size of the circuit is particularly large.

Code: Select all

== Mesecons ==

S W W W W W L       S=Switch
            W       W=Wire
            W       L=Lamp
            W
            L
Concept

My idea is to automatically generate a graph from the world to use for quick calculations. This would be stored in memory separately from the world, and be able to work when the area is unloaded. This could even be offloaded to separate processes.

Code: Select all

== Graph-based electronics ==

S -- L    Letters are graph nodes
     |    Lines are graph edges
     L
There are some obvious limitations with such a mechanic. For example, you couldn't support anything that modifies the world, such as pistons or miners. You would only be able to do purer things such as logic, pipe transfer, storage, and crafting.

Such a graph builder would also be useful for transport networks and such.

In summary, this idea has multiple parts:
  • Building and maintaining a graph based on an ingame Mesecons-like network. This includes handling the merging of two networks, or the splitting of edges.
  • Updating the network efficiently in-memory.
  • Updating the world if loaded or when mapblocks load.
Questions

Has anything been done like this before? In Minetest or otherwise? Would anyone be interested in implementing this?

Related IRC discussion/rant by me: http://irc.minetest.net/minetest-hub/20 ... #i_5330612
Renewed Tab (my browser add-on) | Donate | Mods | Minetest Modding Book

Hello profile reader

User avatar
voxelproof
Member
Posts: 1087
Joined: Sat Aug 05, 2017 08:13
Location: Europe

Re: Efficient graph based networks (electronics and transpor

by voxelproof » Post

rubenwardy wrote: My idea is to automatically generate a graph from the world to use for quick calculations. This would be stored in memory separately from the world, and be able to work when the area is unloaded. This could even be offloaded to separate processes.
You've just conceived a 'binary game', something I have been thinkig about fore some time, however with focus on quite different aim - simulating simple societies. This would require doing some demographic statistic calculations for the entire world each time the game runs, separately from generating all the graphical stuff and then placing certain numbers of NPCs relevant to the chunks currently generated into the field of view. This would be just the first step which, if implemented successfully, would enable further development of the complexity of world population, featuring e.g. building simple houses, setting some of the inhabitants in their beds or in workplaces (like crop fields or mines) etc depending on the time of the day. Very interesting idea. I think that this would open immense opportunities cause separating certain computational processess from the graphical engine would allow to greatly increase the depth of created worlds in relatively easy way, if only the outcome of such independent data processing was properly set within the graphical representation of a world, and the models for these separated computations were good enough.
To miss the joy is to miss all. Robert Louis Stevenson

Xudo
Member
Posts: 162
Joined: Wed Nov 09, 2016 16:43
GitHub: akryukov92
In-game: Xudo

Re: Efficient graph based networks (electronics and transpor

by Xudo » Post

IRC discussion linked here has gone far away from this proposal.

Why graph-based network hasn't been already implemented in Mesecons and Pipes?
It sounds like huge boost to performance of mods of this type.
I assume, that graph should give an API like:
* is x,y belongs to graph?
* what is the shortest distance from x1,y1 to x2,y2?
* get list of connected nodes

Skulls
Member
Posts: 108
Joined: Thu Dec 21, 2017 17:41
In-game: Skulls

Re: Efficient graph based networks (electronics and transpor

by Skulls » Post

How would this work for the player? One of the big things about the node-to-node interactions is the ability of the player to specify the connections just by placing nodes down so they can route them around things. Logically it doesn't matter but the alternative is to have a GUI screen where the player types in the connections. Plus having a bunch of wires snaking around your build is half the fun.

One thing I thought of was to have the player specify the interconnections by placing nodes and then when the connection was complete the logical connection was abstracted out into something like you outlined above. The actual wire / connection nodes would never do the actual "connection" handling but they would need a callback on being removed to notify the grid logic that something had changed and that the graph needs to be checked. With a few clever patch-panel or switchbox nodes you could even run multiple "wires" in the same node.

User avatar
rubenwardy
Moderator
Posts: 6972
Joined: Tue Jun 12, 2012 18:11
GitHub: rubenwardy
IRC: rubenwardy
In-game: rubenwardy
Location: Bristol, United Kingdom
Contact:

Re: Efficient graph based networks (electronics and transpor

by rubenwardy » Post

As I said above:
rubenwardy wrote:Building and maintaining a graph based on an ingame Mesecons-like network. This includes handling the merging of two networks, or the splitting of edges.
The player will build a mesecons-like network like normal, and the code converts it into a graph behind the scenes. The graph design isn't visible at all, it's just an optimisation technique
Renewed Tab (my browser add-on) | Donate | Mods | Minetest Modding Book

Hello profile reader

Skulls
Member
Posts: 108
Joined: Thu Dec 21, 2017 17:41
In-game: Skulls

Re: Efficient graph based networks (electronics and transpor

by Skulls » Post

By storing the actual network in a memory structure rather than the nodes themselves you could have your machines / networks that function even when the nodes are not loaded, as you mentioned. I've been exploring a similar path but it ended up with me having to decouple the network and endpoints (the machines or whatever) from the nodes themselves and be much more abstract with the nodes basically only being the player interaction and 3d representation of the actual "thing". Timing caused issues as well. If a processing machine is unloaded but "active" in memory the input and output stacks have to also be abstracted.

But it would be pretty straightforward for just networks and loaded node machines.

User avatar
joe7575
Member
Posts: 851
Joined: Mon Apr 24, 2017 20:38
GitHub: joe7575
In-game: JoSto wuffi
Location: Germany, in the deep south

Re: Efficient graph based networks (electronics and transpor

by joe7575 » Post

Skulls wrote:One thing I thought of was to have the player specify the interconnections by placing nodes and then when the connection was complete the logical connection was abstracted out into something like you outlined above. The actual wire / connection nodes would never do the actual "connection" handling but they would need a callback on being removed to notify the grid logic that something had changed and that the graph needs to be checked.
This is almost exactly how TechPack and Hyperloop works. Both "transportation mods" have the same logic behind: to describe the connection by means of meta data in the head nodes of a tube connection. Each tube head node "knows" the position and the output direction of its counterpart.
To be able to use the same code for both mods, I am currently extracting the "tubeing logic" into a library called tubelib2 (https://github.com/joe7575/tubelib2).
Sent from my Commodore 64. Some of my Mods: Tech Age, TechPack, Hyperloop, Tower Crane, Lumberjack, vm16, Minecart, Signs Bot.

User avatar
GreenXenith
Member
Posts: 1356
Joined: Wed Oct 28, 2015 01:26
GitHub: GreenXenith
Location: UTC-8:00
Contact:

Re: Efficient graph based networks (electronics and transpor

by GreenXenith » Post

As far as I am aware, Technic somehow does something like this. I have tested the cables and found that you do not need the power source nor cable to be loaded in order to power things. I don't know how the system works because I haven't looked :P
YouTube | Mods | Patreon | Minetest Discord @greenxenith

You should not be able to read this message.

Skulls
Member
Posts: 108
Joined: Thu Dec 21, 2017 17:41
In-game: Skulls

Re: Efficient graph based networks (electronics and transpor

by Skulls » Post

GreenDimond wrote:As far as I am aware, Technic somehow does something like this. I have tested the cables and found that you do not need the power source nor cable to be loaded in order to power things. I don't know how the system works because I haven't looked :P
I think the network lookup and distribution is handled in the switching stations: https://github.com/minetest-mods/techni ... n.lua#L230

Based on a quick glance I would imagine that as long as ANY active switching station is loaded and the producer / consumer nodes on a network have been loaded at least once things would still work. But I could be wrong. I always have too much fun playing with Technic that I forget to really dig into the code.

If this were to be expanded and decoupled from an ABM I imagine you could stuff all this info into mod storage and shutdown and then re-init at load. Thats what I was thinking about, anyways.

neoh4x0r
Member
Posts: 82
Joined: Wed Aug 29, 2018 20:16
GitHub: neoh4x0r

Re: Efficient graph based networks (electronics and transpor

by neoh4x0r » Post

joe7575 wrote:
Skulls wrote:One thing I thought of was to have the player specify the interconnections by placing nodes and then when the connection was complete the logical connection was abstracted out into something like you outlined above. The actual wire / connection nodes would never do the actual "connection" handling but they would need a callback on being removed to notify the grid logic that something had changed and that the graph needs to be checked.
This is almost exactly how TechPack and Hyperloop works. Both "transportation mods" have the same logic behind: to describe the connection by means of meta data in the head nodes of a tube connection. Each tube head node "knows" the position and the output direction of its counterpart.
To be able to use the same code for both mods, I am currently extracting the "tubeing logic" into a library called tubelib2 (https://github.com/joe7575/tubelib2).
What you just described is known as a linked list where each node in the chain stores a link to the previous and the next node.
https://www.cs.cmu.edu/~adamchik/15-121 ... lists.html

PS: I assume that 3...7 are unused value for the number of connections and,
since they aren't being used, they could store other information in addition to the number of connections.

Otherwise, I'd recommend only using 2 bits (0...2) instead of 3 (which would allow freeing up the extra bit, for the above).

User avatar
joe7575
Member
Posts: 851
Joined: Mon Apr 24, 2017 20:38
GitHub: joe7575
In-game: JoSto wuffi
Location: Germany, in the deep south

Re: Efficient graph based networks (electronics and transpor

by joe7575 » Post

neoh4x0r wrote:What you just described is known as a linked list where each node in the chain stores a link to the previous and the next node.
Yes, but this double linked list is only used for the construction phase, when adding/removing nodes by players.
While in operational phase (technique mods moving items/power/players) only the meta data in the head nodes of the tube connection is used.
Sent from my Commodore 64. Some of my Mods: Tech Age, TechPack, Hyperloop, Tower Crane, Lumberjack, vm16, Minecart, Signs Bot.

User avatar
stu
Member
Posts: 923
Joined: Sat Feb 02, 2013 02:51
GitHub: stujones11
Location: United Kingdom

Re: Efficient graph based networks (electronics and transpor

by stu » Post

joe7575 wrote:While in operational phase (technique mods moving items/power/players) only the meta data in the head nodes of the tube connection is used.
Indeed, my experimental railnet mod also uses a very similar technique. Essentially, each junction ‘node’ stores the positions of all other connected junctions, the straight ‘sections’ in between each junction require no additional processing after placement. The carts simply move from junction to junction using predictive velocity and acceleration.

Since the track is stored in node metadata it is possible to make the carts travel virtually over a theoretically unlimited amount of unloaded map and still return on time. It actually works pretty well in singleplayer but falls down slightly in multiplayer. largely due to its heavy reliance on map metadata. What is needed is a fast data storage that will not cause OOM errors on LuaJIT.
neoh4x0r wrote:What you just described is known as a linked list where each node in the chain stores a link to the previous and the next node.
In electronics emulation (spice) these are also know as net-lists, something else I have often thought about trying to implement in MT.

User avatar
rubenwardy
Moderator
Posts: 6972
Joined: Tue Jun 12, 2012 18:11
GitHub: rubenwardy
IRC: rubenwardy
In-game: rubenwardy
Location: Bristol, United Kingdom
Contact:

Re: Efficient graph based networks (electronics and transpor

by rubenwardy » Post

stu wrote:What is needed is a fast data storage that will not cause OOM errors on LuaJIT.
I'd suggest using a Lua library such as lsqlite3 or something NoSQL for this. It could be optional, such that server owners would use it but singleplayer users won't https://rubenwardy.com/minetest_modding ... #databases
Renewed Tab (my browser add-on) | Donate | Mods | Minetest Modding Book

Hello profile reader

User avatar
stu
Member
Posts: 923
Joined: Sat Feb 02, 2013 02:51
GitHub: stujones11
Location: United Kingdom

Re: Efficient graph based networks (electronics and transpor

by stu » Post

rubenwardy wrote:I'd suggest using a Lua library such as lsqlite3 or something NoSQL for this.
Thanks, I might look into that sometime. I do hope to get back into modding once MT 5.0.0 is finally here.

Interesting topic, btw, I am curious to see where this is leading :)

sofar
Developer
Posts: 2146
Joined: Fri Jan 16, 2015 07:31
GitHub: sofar
IRC: sofar
In-game: sofar

Re: Efficient graph based networks (electronics and transpor

by sofar » Post

Something similar but perhaps simpler is how `mech` works from ITB. Essentially networks are mapped out and events are handled without traversing many nodes, although the method of making networks in ITB hugely simplifies things.

https://gitlab.com/sofar/insidethebox/b ... h/init.lua

Nore
Developer
Posts: 501
Joined: Wed Nov 28, 2012 11:35
GitHub: Ekdohibs

Re: Efficient graph based networks (electronics and transpor

by Nore » Post

I see this as a dynamic connectivity problem: https://en.wikipedia.org/wiki/Dynamic_connectivity. Although these algorithms use quite complicated data structures, they allow updates and accesses to be done efficiently (in polylogarithmic time). However, to get the full benefit of them, it would probably be better if such algorithms were implemented in the engine. There might even be some C/C++ libraries we can use for that.

User avatar
rubenwardy
Moderator
Posts: 6972
Joined: Tue Jun 12, 2012 18:11
GitHub: rubenwardy
IRC: rubenwardy
In-game: rubenwardy
Location: Bristol, United Kingdom
Contact:

Re: Efficient graph based networks (electronics and transpor

by rubenwardy » Post

Nore wrote:I see this as a dynamic connectivity problem: https://en.wikipedia.org/wiki/Dynamic_connectivity. Although these algorithms use quite complicated data structures, they allow updates and accesses to be done efficiently (in polylogarithmic time). However, to get the full benefit of them, it would probably be better if such algorithms were implemented in the engine. There might even be some C/C++ libraries we can use for that.
This sounds a lot like what I was looking for, thanks for giving the exact terminology. I knew this couldn't be a new problem

I'd certainly love such engine support, although I doubt it would make it into upstream - unless we can find a more prominent usecase. I would like to run this on a server, so I would be happy to run a shallow fork with this feature.
Renewed Tab (my browser add-on) | Donate | Mods | Minetest Modding Book

Hello profile reader

Skulls
Member
Posts: 108
Joined: Thu Dec 21, 2017 17:41
In-game: Skulls

Re: Efficient graph based networks (electronics and transpor

by Skulls » Post

For on/off is_connected/not_connected logic a simple set would work very well. So for electricity or "always on, all things at the same level" you just include the thing in the set and "is foo connected to bar" becomes "are foo and bar both in the set".

If you graph edges have a weight then some graph theory and shortest path style stuff might be in order. Check out https://en.wikipedia.org/wiki/Connectiv ... ph_theory) . The dynamic connectivity would be useful if the graphs were updated faster than placing or removing a node (switching stations or something).

But a general purpose graph/set tool would be useful.

Nore
Developer
Posts: 501
Joined: Wed Nov 28, 2012 11:35
GitHub: Ekdohibs

Re: Efficient graph based networks (electronics and transpor

by Nore » Post

rubenwardy wrote:
Nore wrote:I see this as a dynamic connectivity problem: https://en.wikipedia.org/wiki/Dynamic_connectivity. Although these algorithms use quite complicated data structures, they allow updates and accesses to be done efficiently (in polylogarithmic time). However, to get the full benefit of them, it would probably be better if such algorithms were implemented in the engine. There might even be some C/C++ libraries we can use for that.
This sounds a lot like what I was looking for, thanks for giving the exact terminology. I knew this couldn't be a new problem

I'd certainly love such engine support, although I doubt it would make it into upstream - unless we can find a more prominent usecase. I would like to run this on a server, so I would be happy to run a shallow fork with this feature.
Well, mesecons-like and technic are two important usecases already, so I could see it making into upstream, but it would depend on the implementation, of course.

User avatar
joe7575
Member
Posts: 851
Joined: Mon Apr 24, 2017 20:38
GitHub: joe7575
In-game: JoSto wuffi
Location: Germany, in the deep south

Re: Efficient graph based networks (electronics and transpor

by joe7575 » Post

Nore wrote:However, to get the full benefit of them, it would probably be better if such algorithms were implemented in the engine. There might even be some C/C++ libraries we can use for that.
I don't believe that you can implement that fully in C/C++.
To follow parallel lines at least you have to use a LUA function from the mod, something like:

Code: Select all

new_pos, new_dir = mod.get_next_tube_pos(pos, dir)
Otherwise it might be difficult to follow such lines:

Image
Attachments
screenshot_20181209_154937.png
screenshot_20181209_154937.png (112.35 KiB) Viewed 1745 times
Sent from my Commodore 64. Some of my Mods: Tech Age, TechPack, Hyperloop, Tower Crane, Lumberjack, vm16, Minecart, Signs Bot.

Nore
Developer
Posts: 501
Joined: Wed Nov 28, 2012 11:35
GitHub: Ekdohibs

Re: Efficient graph based networks (electronics and transpor

by Nore » Post

joe7575 wrote:
Nore wrote:However, to get the full benefit of them, it would probably be better if such algorithms were implemented in the engine. There might even be some C/C++ libraries we can use for that.
I don't believe that you can implement that fully in C/C++.
I was thinking along the lines of having the dynamic connectivity algorithm for general graphs implemented in C++, then mods can use it however they want, which should be compatible with the above code.

User avatar
joe7575
Member
Posts: 851
Joined: Mon Apr 24, 2017 20:38
GitHub: joe7575
In-game: JoSto wuffi
Location: Germany, in the deep south

Re: Efficient graph based networks (electronics and transpor

by joe7575 » Post

Sorry, I was not precise enough.
To build a vector based on placed tube nodes, you need information from the mod itself.
Otherwise you algorithm coming from the left (green nodes) would probably go onto the blue field instead of the red.

Image
Attachments
screenshot_20181209_154937.png
screenshot_20181209_154937.png (108.71 KiB) Viewed 1745 times
Sent from my Commodore 64. Some of my Mods: Tech Age, TechPack, Hyperloop, Tower Crane, Lumberjack, vm16, Minecart, Signs Bot.

Nore
Developer
Posts: 501
Joined: Wed Nov 28, 2012 11:35
GitHub: Ekdohibs

Re: Efficient graph based networks (electronics and transpor

by Nore » Post

Ah, we didn't mean the same thing by dynamic connectivity.
By that, I meant algorithms that maintain information as to which vertices are connected to which in a graph that can change with added or removed vertices and edges. It probably wouldn't be very useful for pipeworks-like mods, but very efficient for those with instant information transfer as mesecons, technic or digilines.

User avatar
rubenwardy
Moderator
Posts: 6972
Joined: Tue Jun 12, 2012 18:11
GitHub: rubenwardy
IRC: rubenwardy
In-game: rubenwardy
Location: Bristol, United Kingdom
Contact:

Re: Efficient graph based networks (electronics and transpor

by rubenwardy » Post

Part of my aims is to store the distances of edges to make things like Pipeworks and transport network work. It's fairly essential to me.
Renewed Tab (my browser add-on) | Donate | Mods | Minetest Modding Book

Hello profile reader

Nore
Developer
Posts: 501
Joined: Wed Nov 28, 2012 11:35
GitHub: Ekdohibs

Re: Efficient graph based networks (electronics and transpor

by Nore » Post

Hmmmm, that is a good question. I'm not sure we can even get something even remotely as good with dynamic shortest paths compared to dynamic connectivity; the problem seems much harder. There seems to be no polylogarithmic algorithm, unfortunately...

Post Reply

Who is online

Users browsing this forum: No registered users and 5 guests