Electric network in a tile based game

Game Mechanics
#1

Around 2 years ago, I played FTB which has a collection of Minecraft modpacks. The modpack I played with had several mods that each had their own energy system of sorts.

An example is IndustrialCraft2. There were generators, batteries, and cables. There were also machines that required power to operate. How its energy system worked was energy was literally sent in “packets”: a cable could transfer an unlimited number of packets instantly but the only limitation was packet size. If a cable attempted to transfer an energy packet that it couldn’t handle it would explode/melt.

My favourite is Thermal Expansion. There were also generators, storage devices, conduits, and machines. However all energy-capable devices were limited by a transfer in/out rate of X units per tick (a tick is 1/20th of a second). This meant that a cable could only transfer some amount of power per second to its adjacent connections, be it a battery, another cable, or machine.

I poked around the forums and found an old post about how this would work. It used node connections to transfer electricity. It didn’t exactly have a way to throttle how much energy gets sent per second but it was a good start.

Any ideas about this? I was thinking of having a block that can accept/transfer energy. A generator would make energy, search the adjacent blocks for a conductor, and evenly spread as much energy as it can limited by transfer rate to all of the neighbouring conductors. This would probably work in practice except that cables may spread back and forth between each other.

#2

My original plan was to propagate a jolt of electricity through cables, at intersections it would be split and going on their separate paths. In a loop it would eventually keep splitting until there was no more power to move. It was essentially a recursive function which may hit a stack memory limit as local variables get preserved, which is bad for long-distance networks such as large power lines.

Another option was making a network map of all connected producers (including battery blocks) and consumers, and evenly distributing power to all the consumers. I am probably going to go with this method, but I don’t know how I would “throttle” energy transfer (some cables can only transfer X amount per update).

Some help on the network option would be greatly appreciated!

#3

You can sidestep this problem by not using a recursive “flood-fill” sort of algorithm. Instead, you add the starting point to a Queue. Then you call a “fill” method to discover unmarked neighboring points for the current point in the Queue. Add each of these neighboring points to the end of the Queue and mark them. Continue along each point of the Queue until you reach the end.

#4

You only need one queue, just add discovered neighbors (that aren’t already marked) in with the rest.

#5

True. I didn’t consider that you would never need to revisit past points, so clearing the queue would be pointless if you just add new neighbors to the end of the queue. Edited above post.

Edit: Here’s the general idea in pseudocode for reference: https://en.wikipedia.org/wiki/Flood_fill#Alternative_implementations

#6

Wouldn’t the queue method be relatively slow if each producer was searching every time it pulsed for an update? It seems really slow especially for larger-scale networks.

#7

You can keep a cache of all network producers and consumers, how much they produce or draw, etc. (similar to your second method with the network map), then only flood-fill when a change in the network is detected (or periodically update the network map) and update production and consumption values for each machine.

This method doesn’t have to be restricted to only sending power throughout the network. It could also be used to detect the network/changes, and be used in tandem with your second method.

However, this process should be relatively fast for up to a couple-hundred point networks if I’m thinking correctly. Are you anticipating larger networks?

#8

Instead of a separate cache (equivalent to an adjacency matrix?), every time the graph is updated, the the traversal is done and then the graph can be reduced:

A-■-■-■-■-■-B-■-■-■-D | ■ <- just added | ■ | C

Traversal outward from the updated point (DFS or BFS) finds A, B, and C, so they are all connected, and added to each other’s adjacency lists and can directly reference each other. Make sure to use a Set for the adjacencies or otherwise not allow duplicates. Might also include tags for “wire resistance/power capacity” so power limiting can be implemented.
The blocks connecting them still have references, but only to inform ABCD etc. when the graph is changed.
So there’s really two separate graphs: the ‘wires’ and the producers/consumers.
The wires graph is large but only has to be traversed when changes are made, the heavily used producer/consumer graph is much smaller.

#9

I kinda understand what you’re saying, but do you think you could elaborate a bit more/dumb it down? What I (think) I’m getting is that wires act as “adjacent connections” for producers/consumers. A wire merely connects some set of blocks together so they can interact with each other.

#10

[quote]A wire merely connects some set of blocks together
[/quote]
‘Connects’ being in active voice, yes. They are used to connect more important pieces together (or break them apart), otherwise they do nothing, the producer and consumer nodes don’t even have to know about them, if you use reference counting in the adjacency lists to implement breaking things apart.

Some code:


class Ref<A> {
    A data;
    int count;
    boolean equals(Ref<A> r) = (data.equals(r.data) && r.count == count); // some pseudojava
}

interface Node {
    boolean isMajor(); // such as a producer/consumer block, wires are minor
    boolean isMinor(); // ...
    Set<Ref<Node>> getAdjacents(); // might not be the best way, could have a set<Node> and a map<Node, Integer> for counts, etc.
    void addAdjacents(Collection<Node> c); // maintains some invariants like 'don't add self', also increments ref counts
    void removeAdjacents(Collection<Node> c); // decrements ref counts, doesn't actually remove things until their count == 0, etc.

    // might actually have to be an abstract class, or static methods or something
    onPlace() {
        addAdjacents(getNodesOnAdjacentMapTiles()); // make sure to increment ref counts
        // branch out from adj nodes, stopping on and collecting nodes that satisfy the predicate
        List<Node> majorConnectedNodes = traverse(getAdjacents(), Node::isMajor);
        majorConnectedNodes.foreach(n -> n.addAdjacents(majorConnectedNodes)); // remember, will automatically filter out self
    }
    onBreak() {
        List<Node> majorConnectedNodes = traverse(getAdjacents(), Node::isMajor);
        majorConnectedNodes.foreach(n -> n.removeAdjacents(majorConnectedNodes));
        // filter out majors because we don't want to double-remove ourselves
        getAdjacents().filter(Node::isMinor).foreach(wire -> wire.removeAdjacents(this)); // single-arg remove could be nice
    }
}

class WireNode implements Node {
/// make sure to call super.onPlace(), etc. is Node is actually an abstract class
}
class RedstoneFurnaceNode implements Node {
/// used by RestoneFurnaceBlock to do things like consume power from adjacents, etc.
}

Probably some more subtleties in there, but that’s the rough sketch.
EDIT: such as, major node classes should override onPlace/Break so as not to act as wires (unless they should…), or those impls of mine should just be in the WireBlock/Node class.

EDIT2: after some thought, a more robust albeit perhaps more expensive timewise option would be to have onPlace/onBreak for minor nodes simply find connected major nodes and tell them to recalculate their own major connected nodes. This is preferable because onPlace/Break is unified for minor nodes, and ref counting isn’t required. It does require more graph traversals though.

#11

Thanks for the clarification BurntPizza.

I actually decided to play with the redstone flux system in minecraft and I saw that it changed. It seems that their method is very similar to my first one: energy in a cable will attempt to spread it to its neighbours. It seems recursive (probably using iterative methods for speed and no stack overflow possibility). I’ll try this method first and implement a rough version of it and see what’s wrong.

#12

I implemented an iterative “splitting” version where it attempts to split at every connection it finds. It works quite well, although sometimes it will have leftover energy it didn’t ration. Another side effect is that the amount of energy a machine can take at a time isn’t limited by time, rather it’s per pulse of energy. It can take an infinite number of pulses at any time but each pulse is limited, which is totally okay for my game.

Thank you BurntPizza and Longarmx for the help!

#13

If you end up with ‘leftovers’ you could just push those back into the network, until it’s all ‘absorbed’.