GML Custom Event Ordering with a Tree Structure

[samspade]

I'm trying to create a custom event order for a group of objects that runs each step as each object down the chain needs its predecessor to run their event before it runs its own. More specifically there is a main object which runs calculations, then there can be n number of sub objects which run calculations off of that which in turn can have n number of sub objects which run calculations off of their immediate parent and so on.

So

main object runs its calculations

first layer of sub objects run calculations on main

second layer of sub object run calculations on first layer

.....repeat as far as necessary
​

Essentially it is a tree structure where nodes farther down the branches require calculations farther up to be completed first and there can be any number of nodes at any depth.

The catch is that I was trying to accomplish this without the parent nodes knowing about their children. If the parents know about their children then I can just have each parent run its code then run the code for all its children.

One solution is to have each node track whether it has run its code that step and then loop through all the nodes and if it has not run its code, traverse up the tree until it finds either the source or a node which has run its code and then traverse backwards running the code at every step.

​

The other alternative I see seems like it would be to maintain a separate structure (likely map or list) that tracks the tree structure. So the parents don't know about their children, but the structure does and can then do the simple thing of traversing down the tree.

Code isn't necessary but I'm wondering if there is a basic design pattern or method of doing this that I am missing.

 

[FrostyCat]

Put the step actions in a User Event. At the end of each User Event, loop through its subsidiaries and make each execute their own User Event. Then in the top-level owner's Step event, execute its own User Event.

 

[CloseRange]

for a tree structure you'd normally have a parent know about the children and as you said once the code has been run for the parent it just calls on the code for the children objects.
I think your second suggestion might lead to a lot of problems down the line and might not be very efficient.

However to make it simple all you really need is an array with every object. At the very start of the array should be all the objects in the first layer (order of them doesn't matter) then the next chunk of the array should be filled with anything in the second layer (again order doesn't matter)
then you just have every object in the array based on what layer it's in. Within each layer the order doesn't matter as long as all the objects in the previous layer is called. So that means you just iterate over the array and call each objects code.

Objects then don't need to know about who their parents are or who their children are just what layer they are in (this is easier to figure out though if they know their parent)

 

[samspade]

for a tree structure you'd normally have a parent know about the children and as you said once the code has been run for the parent it just calls on the code for the children objects.
I think your second suggestion might lead to a lot of problems down the line and might not be very efficient.

However to make it simple all you really need is an array with every object. At the very start of the array should be all the objects in the first layer (order of them doesn't matter) then the next chunk of the array should be filled with anything in the second layer (again order doesn't matter)
then you just have every object in the array based on what layer it's in. Within each layer the order doesn't matter as long as all the objects in the previous layer is called. So that means you just iterate over the array and call each objects code.

Objects then don't need to know about who their parents are or who their children are just what layer they are in (this is easier to figure out though if they know their parent)

The array structure would work for simple versions, and I want is pretty simple so I might go with it, but it won't work for more complicated versions that would allow for re-arranging the tree structure. As moving a 'branch' would require moving all it's children as well if the branch moved to a different level.

I do think that traversing up then down is too much work. In the end I decided to go with the parents knowing about their children but only because the children tell them (children add and remove themselves from their parents lists). This makes traversal easy and while the parents 'know' their children they don't have to maintain their own list. It seems to be working.