Efficient graph based networks (electronics and transport)

User avatar
Posts: 778
Joined: Wed Jun 24, 2015 18:45
Location: Raxacoricofallapatorius
GitHub: orwell96
IRC: orwell96_mt
In-game: orwell

Re: Efficient graph based networks (electronics and transpor

by orwell » Thu Dec 13, 2018 13:22

I have plans for an advanced electrics mod (called advelectric) since about a year, that would use exactly that system. There would be "distribution boxes" or other actors that would correspond to Graph nodes and cables between them, forming the graph edges. Each connected sub-graph would then form a "network" of a certain voltage, as it was described here.
However, I've not progressed because I had been obsessed with Advtrains and real-life things.
Lua is great!
List of my mods
I like singing. I like dancing. I like ... niyummm...

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

Re: Efficient graph based networks (electronics and transpor

by neoh4x0r » Sun Dec 16, 2018 04:49

Nore wrote: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...

Pre-calculating the shortest path (or doing so on the fly) would be an intensive cpu-bound operation and depending on the path-finding algorithm would be done in polynomial time: O(n^2) or greater (way too slow).

I personally think the problem would be more approachable and manageable by treating it as an OO (object-oriented) problem; something is passed into a node and this node is responsible for sending it onto the next node such that the passage from one node to next would eventually narrow-down to the ultimate destination.

If the shortest path is still needed at that point, then the algorithm for selecting the next-best node is greatly simplified.


Return to Modding Discussion

Who is online

Users browsing this forum: Extex and 2 guests