Efficient algorithm for simultaneously updating game objects which need to be updated

Question

I have a grid of objects like this:

 1
      +
 F

1 is equal to the constant 1, F flickers between 0 and 1 each tick, and + is equal to the sum of the 1 and the F.

I want to update these values as described above. The 1 won't change, the F will change from 0 to 1 and vice-versa, and the + will change to the sum.

I could just do a loop:

for node in nodes {
    if(node.type == '+') {
        node.value = node.input1.value + node.input2.value;
    }
    if(node.type == '1') { ... }
    if(node.type == 'F') { ... }
}

but the problem is that this will depend on the order of iteration. If the F is iterated on first, then it will be set to 1 from an initial value of 0, then the + would equal 1 + 1, i.e. 2. But if the + was first, the result would be 1 + 0 = 0 and the NEXT tick would be 1 + 1 = 2.

I want to do this simultaneously. So I thought I could have a map of new values:

global map = new HashMap<Node, double>();
...
map.clear();
for node in nodes {
    if(node.type == '1') {}
    if(node.type == 'F') {
        map.set(node, node.value == 1 ? 0 : 1);
    }
    if(node.type == '+') {
        map.set(node, node.input1.value + node.input2.value);
    }
}
map.forEach(k, v -> k.value = v);

but this is probably inefficient as all values have to be looped over and entries in the map must be created for each node (node count is expected to be alot, around 10,000).

How do I do this? I probably need a list of "update required" nodes but I'm not sure what to do exactly, especially to do it simultaneously.

Examples:

1
 \
  == + === + === + == (flickers between 6 and 7 starting at 6 due to F flickering)
 /        /     /
F        3     2

// Nodes can be created by the player

1 => + <= 2
     |
     |
     (equals 3)

// Player creates a node:

1 => + <= 2
     |
     |
     (factorial) ===> (equals 6)

There can be multiple of these connected nodes at a time:

1 => + <= 2
     |
     |
     (equals 3)

2 => + <= 3
     |
     |
     (equals 5)

// If the player chooses, they can connect these 2 together:

1 => + <= 2
     |
     |
     -===========
                |
2 => + <= 3     |
     |          + =====> (equals 8)
     |          |
     -===========

Nodes can be inputs to themselves, or have no inputs (in which case the inputs default to 0):

     =====> (starts at 1 in the first tick, then keeps incrementing.)
     |
1 => + <==
     |   |
     =====

What do you mean by "simultaneously"? Your example loop updates the nodes sequentially, one after another. Do you mean "in a single pass"? — DMGregory
– DMGregory ♦, Commented Apr 19, 2019 at 14:13
@DMGregory I mean that updating the nodes in a different order should give the same result. Yes. — kepe
– kepe, Commented Apr 19, 2019 at 14:15
Have you considered ordering your updates using a dependency graph? — DMGregory
– DMGregory ♦, Commented Apr 19, 2019 at 14:16
@DMGregory Wouldn't creating a dependency graph each time a new node is added be a bit inefficient especially since I have lots of nodes to create a graph from? — kepe
– kepe, Commented Apr 19, 2019 at 14:18
Does adding a new node change the dependencies of your whole collection, or just the nodes dependent on it? — DMGregory
– DMGregory ♦, Commented Apr 19, 2019 at 14:19

DMGregory · Accepted Answer · 2019-04-19 14:55:45Z

I'd recommend ordering your nodes based on their dependencies, into a sequence of generations. You can store the nodes of each generation as a list, and your generations collection is a list of lists.

A node with no inputs (other than its own state) is in generation 0
- A constant node is a special case of generation 0 that needs no updates at all. You can store them in a separate list to skip re-processing them each tick.
A node with one input (other than its own state) is in generation node.input.generation + 1
A node with multiple inputs (other than its own state) is in generation max(node.input[i].generation) + 1, where we've taken the maximum generation out of all of its inputs.

Now you can process your nodes in a single pass, one generation at a time.

If you start at generation zero and work up to the last generation, then each node's value reflects the latest values of its inputs, so a change at the leaf of the tree propagates all the way to the root in one pass.
If you start at the last generation and work down to generation zero, then each node's value reflects the values of its inputs in the previous tick, similar to your map solution, so a change in a leaf value advances one generation further in each tick.

When you change a node's inputs, you'll need to re-evaluate the generation it belongs in. If it changes generations, then you'll need to re-evaluate the generation of any nodes that use it as an input. Order within a single generation list doesn't matter, so you can use swapping to insert/remove nodes efficiently, or even have multiple threads working on separate chunks of a single generation in parallel if you have thousands or millions to update.

Also, I forgot to mention in the question, but nodes can be inputs to themselves. How can I assign a generation to a node with itself as one (or both) of its inputs? — kepe
– kepe, Commented Apr 19, 2019 at 14:52
This is called Topological Sorting. For deciding on a node's generation, you need to look only at its inputs that are not itself. Any self-feedback can be handled in the node's own update function, and doesn't need generational help with the ordering (since a node can't be in a different generation than itself). — DMGregory
– DMGregory ♦, Commented Apr 19, 2019 at 14:58
For future googlers, this is a graphical version of this answer. — kepe
– kepe, Commented Apr 19, 2019 at 15:17

Stack Exchange Network

Efficient algorithm for simultaneously updating game objects which need to be updated

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

Efficient algorithm for simultaneously updating game objects which need to be updated

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions