# Power Distribution amongst connected nodes

In my game the map is represented by connected nodes, each node has a number of connected nodes. The nodes represent a system in which players can build structures and move units about. If you're familiar with Sins of a Solar Empire the game map is very similar.

I want each node to be able to produce power and share it with all connected nodes. For example if A, B, C & D are all connected and produce 100 power units, then each system should have 400 power units available. If node B builds a structure that consumes 100 power units then A, B, C & D should then have 300 power units available.

I've been working on this system all day and haven't been able to get it working quite the way I want.

My current implementation is to first recurse through each nodes's connected node adding up the power, I keep a list of closed nodes so it doesn't loop, it's quite similar to A* actually.

node.power = 0
node.basePower = 100 // could be different for each node.
node.initialPower = node.basePower


-

function propagatePower( node, initialPower, closedNodes )
node.power += initialPower
connectedNodes = connected_nodes_except_from( closedNodes )
foreach node in connectedNodes do
propagatePower( node, initialPower, closedNodes )
end
end


After this I iterate through all power consumers.

foreach consumer in consumers do
node = consumer.parentNode
if node.power >= consumer.powerConsumption then
consumer.powerConsumed += consumer.powerConsumption
node.producedPower -= consumer.powerConsumption
end
end


Then I adjust the initial power for the next propagation cycle.

foreach node in nodes do
node.initialPower = node.basePower - node.producedPower
node.displayPower = node.power // for rendering the power.
node.power = 0
end


This seemed to work at first but then I came into a problem.

• Say two nodes A & B produce 100Pu each, it's shared so both A & B have 200Pu.
• I then make two structures that consume 80Pu each on A (160Pu).
• Then the nodes power is adjusted to basePower - producedPower (100-160 = -60).
• Nodes are propagated, both nodes now have 40Pu (A: -60 + B: 100 = 40).
• Which is correct because they started with 200Pu - 160Pu = 40Pu.
• However now node.power >= consumer.powerConsumption is false.
• Whats worse is it's false for any structure that uses more that 40Pu, so the whole system goes down.

I could deduct from consumer.powerConsumption but what do I do if power is reduced elsewhere? I don't have the correct data to perform the necessary checks.

It's late so I'm probably not thinking straight but I thought to ask on here to see if anyone has any other implementations, better or worse I'd be interested to know.

Hm, I think you are making it too complicated.

Your nodes can either be producing power or consuming it. And they can either have enough power or not. So can I suggest just having a single "power" variable and +ve is producing power and -ve is consuming it. Then you can calculate how much power each connected node needs with:

(pseudo-code, sorry I don't know lua)

node {
int id;
int power;
node_list children; // This assumes a stingily linked list
}

node_list root_nodes;

// Gather a list of all unique connected nodes
void gather_nodes( node root, list & node_list )

// Check the node is not in the list already
for node_in_list in node_list:
if node_in_list.id == root.id
node_list.push_back( root )

// iterate over the children and add them to the list
for child in root.children:
gather_nodes( child, node_list )

for n in root_nodes:
int overall_power = 0;
node_list nodes;
gather_nodes( n, nodes )

// Calculate the power
for connected_node in nodes:
overall_power += connected_node.power;

// If overall_power is +ve then all connected_nodes have enough power
// otherwise all connected_nodes do not have enough power


And of course you only need to recalcuate this when the power changes or you add/remove a node.

• Thanks, this is a WAY more elegant solution. The gather_nodes method is pretty much the same as i've got but I never thought to simply compare the sum of power against the sum of consumers. – Perky May 30 '12 at 14:05