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.

Pseudo code: All nodes start with the properties

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


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

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

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

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
    is_already_in_list = false
    for node_in_list in node_list:
        if node_in_list.id == root.id
            is_already_in_list = true;
    if( !is_already_in_list )
        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.

  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Perky May 30 '12 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.