Implement automatic arrangement tools for Nodes in GraphEdit, VisualScript and VisualShaders

[fire]

Describe the project you are working on:

Multiplayer 3d game.

Describe the problem or limitation you are having in your project:

Visual Shader graphs in Godot can become extremely messy and there's even a bug that scrambles the graph randomly.

Describe the feature / enhancement and how it helps to overcome the problem or limitation:

Looking for collaborators.

Co-Authored with theoway#7853

The proposal aims to organize the node's position in graph edit, visual shader editor and visual script editor.

This proposal is inspired by Sugiyama's methodology, which is very popular and commonly used in software to draw directed graphs automatically. The method has been modified to fit the needs of the users, keeping in mind the design architecture and implementation of the graph editing system in Godot Engine.

This feature will find its use in Visual Script Editor and Visual Shader Editor. Users can use this feature to auto-arrange the node positions, in a horizontal-block layout. This will help the users save time from rearranging the nodes while editing to get clarity and better organization, especially when the visual scripts and visual shaders have a large number of nodes.

https://www.youtube.com/watch?v=LY3E5VGnAuQ

https://www.youtube.com/watch?v=plafUnYKhu4

Describe how your proposal will work, with code, pseudocode, mockups, and/or diagrams:

Design Abstract

The idea is to add functionality to the graph edit system that will automatically rearrange the nodes, dividing them into layers and blocks, making them comprehensive and easy to read. This functionality can be used in Visual Script Editor and Visual Shader Editor (as they also use graph edit system) to automatically reorganize the nodes. The feature will also handle the cases when the grid is turned on/off or when its scaling is changed.

Preliminaries

The references below are made according to the graph edit, visual script and visual shaders of Godot.

1. Graph: Graph here implies the structure that consists of vertices and their corresponding edges.
   Note: At some places, it implies the canvas of the visual script/visual shader editing system where the nodes are placed. It will be indicated to avoid confusion.
2. Layer: The vertices of the graph are partitioned into non-empty layers, each having an ordering of vertices. Layering is the process of dividing the vertices into different layers.
3. Nodes: Nodes here imply the graph nodes of Godot. However, it is used interchangeably with vertices, when talking in terms of graph theory.
4. Edges: An ordered pair of nodes. Edges between nodes are decided based on their sequence and data connections(in Visual Script) / scalar, vector, transform etc. connections(in visual shaders). Since there can be one or more connections between two nodes, it will be considered a single edge with priority to sequence connection and, in case of a visual shader node, the top port connection. As nodes in VisualScript/VisualShaders can have multiple input and output sequence/data ports, the edges will carry the information of the involved input/output ports.
5. In the pictures shown, edges are directed downwards from top to bottom layers. But since the flow of visual script/visual shader connections is left to right, the layering will be from left to right, which implies that the layers will be numbered from left to right from 1 to n(Number of layers). If Li is the upper layer of Lj , this implies that Li lies to the left of Lj.

Methodology

This methodology consists of three phases

1. Converting a Directed Acyclic Graph to Layered Graph:

The node layout in graph edit is a Directed Acyclic Graph (DAG) with the nodes being the vertices and the sequence, data connections being the edges. The auto-arrangement procedure only works for layered graphs. That's why the DAG obtained from the graph edit system(or visual script/visual shaders) is converted into a layered graph by following the Layering and Ordering and Cross-Minimisation methods.

2. Vertical Alignment:

Once we have a layered graph with a minimum number of edge crossings, we then place the vertices(nodes of the visual script) in horizontal blocks. Edges between the blocks will be drawn straight. To achieve this, Preprocessing, Horizontal Alignment and Inner Shift methods will be used.

3. Vertical Compaction:

In the final phase, the blocks are moved as close as possible, while keeping the edges straight inside the blocks, and assigning explicit y coordinates to the nodes. The method used for this phase is Place Block With Straightening.

The various techniques mentioned in the methodology are explained below

1. Layering:

In this process, the graph will be divided into non-empty layers. Layering is done in such a way that an edge will always point from the node of the upper layer to the lower layer node. There will be no edges (connections) between nodes of the same layers. The direction of edges is orthogonal to the layers. To do this, the Longest Path Layering algorithm will be used.

Algorithm:
Requires: G = (V,E) //  V- Set of vertices, E- Set of edges

// V is the set of vertices, U is the set of vertices that will be assigned to the current layer 
// Z is the set of vertices that have been assigned to the previous layers
// current_layer is the layer that will be receiving the vertices // N+(v) is the set of upper neighbours of the vertex v.

Initialisation: U ← NULL , Z ← NULL , current_layer ← 1
1. while U ≠ V do
2.     Select vertex v ϵ V - U with N+(v) ⊆ Z
3.     if  v has been selected then
4.         Assign v to the layer with a number current_layer
5.         U ← U ∪ {v}
6.     end if
7.    if no vertex has been selected then
8.        current_layer ← current_layer + 1
9.        Z ← Z ∪ U
10.    end if
11. end while

Result: This will result in the layering of the graph. Each vertex will be assigned a layer.

2. Ordering and Cross-Minimisation:

This process involves ordering vertices in each layer so that a minimum number of edge crossings occur. This is achieved by going layer by layer and trying to minimize the inner-crossings between adjacent layers. Inner-crossings is the crossing of two inner edges(edges that have starting points and ending points at the two adjacent layers) between adjacent layers.

Algorithm:

Requires two layers L1 and L2, with L1 having a fixed ordering. L1 is the upper layer.

Initialization: A crossing-matrix is computed, which keeps the count of crossing among the edges of adjacent vertices of the lower layer, L2. 

//c(u,v) gives the number of crossings of the edges of the vertices of u and v.

1. Choose an initial ordering of L2
2. repeat 
3.     for each adjacent pair of vertices i, j <- i + 1  ϵ L2
4.         if c(i,j) > c(j,i) do
5.             exchange vertices i, j 
6.       until the number of crossings is not reduced anymore

Result:  A layered graph with a reduced number of inner-crossings is obtained.

3. Preprocessing:

This method resolves the crossing on non-inner segments and inner-segments(Inner-segments are the edges between two adjacent layers). It also marks the non-inner segments to favour the horizontal alignment of edges inside the blocks.

Algorithm:
// h is the total number of layers in the layered graph
// |Li| gives the number of vertices present in the layer Li
// v(l)i gives the vertex at order 'l' in the ordering of layer i

1. for i ←2, ..., h−2 do
2.     k0 ← 0;  l ←1; 
3.     for l1  ← 1,...,|Li+1| do
4.         if l1 = |Li + 1| or v(l1)(i+1)  is incident to inner segment between Li+1  and Li  then
5.             k1 ←| Li |
6.        if  v(l1)(i+1)  is incident to inner segment between Li+1  and Li then
7.            k1 ← pos[upper neighbor of v(l1)(i+1) ] 
8.            while l <= l1 do
9.                for each upper neighbor v(k)i of v(l)i+1 do
10.                      if k < k0 or k > k1 then
11.                          mark segment ( v(k)i , v(l)i+1 )
12.                          l ← l +1
13.                         k0 ← k1

Result: Non-inner segments are marked so that they can be avoided during block formation.

The left image shows a layered graph. The right image shows the same layered graph with inner crossings and non-inner segments removed.
Note:- See Preliminaries point 5.

4. Horizontal Alignment: After the preprocessing is done, the nodes are placed inside blocks in a bottommost alignment with their median, upper neighbours. (upper neighbour means the nodes that lie to the left because we are considering horizontal alignment)

Algorithm:
//h is the number of layers
//pos[v] gives the order of the vertex v in the ordering diagram layer to which it belongs
//v(k)i means the vertex at the order k in the ordering of layer i.
//ui < uj means that uj belongs to the upper layer.

1. Initialize root[v] ←  v, v ∈ V
2. Initialize align[v]← v, v ∈ V
3. for i ←1 ,... ,h do
4.     r ← 0
5.     for k ← 1 ,..., |Li| do if v(k)i has upper neighbours u1 ≺ ...≺ ud with d>0 then
6.         for m ← ⌊(d+1) / 2⌋, ⌈(d+1) / 2)⌉ do
7.             if align[ v(k)i ] = v(k)i then
8.                 if (um, v(k)i) not marked and r < pos[um] then
9.                     align[um ] ← v(k)i
10.                     root[ v(k)i ] ← root[um]
11.                     align[v(k)i ]←root[v(k)i ]
12.                     r = pos[um];

Now the vertices with similar roots are placed in the same blocks.Each block holds the following content:

1. The root node(vertex) of the block.
2. Vertices with their inner_shifts(Tells how much they'll be shifted inside the block). It is initialized to 0 for all vertices belonging to the block.
3. It contains the width of a vertex(size of a node in the visual script), the position of ports of the nodes(vertices), edges.

Result: The nodes of the visual script are now divided into blocks.

Note:- See Preliminaries point 5.

5. Inner Shift: This method tries to achieve straight edges within each block by shifting individual nodes inside a block. When calculating inner_shift(The shift in the offset of the node is termed as inner_shift), it considers different sizes of the nodes and port connections, which tells which output port is connected to which input port, because nodes in the visual script can have multiple input/output ports.

Algorithm:
//B is the collection of blocks, b is a block and b ϵ B
//If (u,v) is the edge, then output_port((u,v)) gives the output port of u  from which edge emerges and 
//input_port((u,v)) gives the input port of v at which the edge ends.
//yp gives the position of the port(y-coordinate from the bottom of the
// node perimeter)
//width(u) gives the width of the node u.

1. for b ∈ B do 
2.     left ← 0, right ← 0 
3.     for (u,v) ∈ b do 
4.         s ← innerShift[u] + yp( output_port((u,v)) ) − yp( input_port _port((u,v)) )
5.         innerShift[v] ← s 
6.         left ← min(left,s)
7.         right ← max(right, s+ width(v)) f
8.      for all nodes v in block b do 
9.         innerShift[v] =  innerShift[v] - left 

Result: The nodes in each block are aligned horizontally with straight edges between each node(vertex) inside each block.

6. Place Block With Straightening:

These blocks that are formed can further be divided into classes. A class is defined by a unique sink that is reachable by all of the class's nodes(See the figure below for clarification). In this final process, the blocks and classes are compacted vertically. While iterating through each block, the inner_shifts and sizes of blocks are considered; this allows the block to 'flow' into each other, leaving little free space. But this can lead to overlapping, that's why a threshold value is calculated to prevent the nodes from moving further, resulting in a straight edge. But the threshold of a block cannot be calculated until it's connected block has already been placed. To handle such cases, a queue data structure is used to store edges of such blocks. When all the blocks have been placed, edges are fetched from the Queue and check how far the concerned block can be moved without exceeding the threshold value.

Algorithm:
//pos[w] gives the order of the vertex(node) w in the ordering of its corresponding layer.
//pred[u] gives the preceding node of u in the block to which u belongs.
//y[v] gives the y-coordinate of the node(vertex) v.
//root[v] gives the root of the block to which v belongs.
//align[w] used from the Preprocessing method

function place_block(v)
1. if y[v] undefined then 
2.     y[v] ← 0, initial ← true, w ← v 
3.      thresh ← −∞
4.     repeat 
5.         if pos[w]  > 0 then 
6.             n ← pred[w], u ← root[n] 
7.             place_block(u) 
8.             thresh ← calculate_threshold(v, u, thresh)
9.             if sink[v]=v then 
10.                 sink[v] ← sink[u] 
11.             if sink[v] ≠ sink[ u] then 
12.                 sc ←  y[v] + innerShift[w] − x[u] − innerShift[n] − width[n] − δl 
13.                 shift[sink[u]] ← min(shift[sink[u]], sc) 
14.             else sb ← max(thresh, y[u] + inner_shift[n] + width[n] − inner_shift[w] + δl) 
15.                     if initial then y[v] ← sb 
16.                     else y[v] ← max(y[v], δl)
17.                     initial ← false 
18.          else thresh ← calculate threshold(v, u, thresh)
19.          w ← align[w] 
20.      until w = v

//v- root node of the block
//w- current node
//ot- current threshold value 
//Q- Queue
function calculate_threshold(v, w, ot)
1. thresh ← ot 
2. if v = w then
3.     (u,w) ← pick incoming edge of w 
4.     if block of root[u] placed then 
5.         thresh ← y[root[u]] + inner_shift[u] + yp(output_port((u,w))) − inner_shift[u] − yp(input_port((u,w))) 
6.      else if w has incoming edges then 
7.          enqueue w to Q 
8. if thresh = −∞ and align[w]=v then 
9.     symmetric to before, this time picking an outgoing edge 
10. return thresh

function post_process() 
1. while Q not empty do 
2.     w ← dequeue from Q 
3.     (u,w) ← previously picked edge for w //(line 3, in calculate_threshold) 
4.      t1 ← y[u] + inner_shift[u] + yp(output_port((u,w))) − y[root[w] − inner-shift[w] - yp(input_port((u,w)))
5.      t2 ← minimum distance between block of w and its neighbors
6.      t ← if abs(t1) < abs (t2) then t1 else  t2 
7. move all nodes v in w’s block by t

//V- set of vertices
1) initialize sink[v]← v,  v ∈ V
2) initialize shift[v] ← ∞ , v ∈ V
3) initialize y[v] to be undefined, v ∈ V 

// root coordinates relative to sink 
4) for each b ∈ B do 
5)    place_block(root[b]) 

// absolute coordinates 
6) for each v ∈ b do 
7) y[v]← y[root[v]]
8) if shift[sink[root[v]]] < ∞ then 
9)     y[v] ← y[v] + shift[sink[root[v]]]

//Post-processing
10) post_process()

Result: The blocks and classes have been compacted vertically without introducing bends within the blocks.

Without Straightening

place_block() with thresholding

After post_process()

Time Complexities:

Time complexities of the various methods given above are listed below:

Method Time-Complexity (Worst-case)

1. Layering
    O(|V|)
2. Crossing-Minimisation
    O(|V|2)
3. Preprocessing
    O(|V|)
4. Horizontal Alignment
    O(|V|)
5. Inner Shift
    O(|V|)
6. Place Block with Straightening
   Linear in terms of |V| & |E|
    Note:- |V| is the number of vertices, and |E| is the number of edges in the layered graph.

Results

Here, the visual script is used as an example; results will be similar for graph editing and visual shaders.

The horizontal blocks have been circled out, with the arrows pointing to the starting node of the block (With in-degree 0). This is when the grid is turned off.

When the grid is turned on, they will snap like this, always to the leftmost edge(with some gap for clarity). The starting node(pointed with the arrow) will snap to the leftmost corner of the grid, and the other nodes will be placed relative to that.

Another case is when the scaling is changed.

Known Problems and Solutions

1. When a visual script is reorganized, the nodes enclosed by a comment node might get positioned out of that after reorganization.
   Solution:- Constraints can be applied when ordering the nodes and making the blocks to keep the nodes belonging to a comment node together.

2. Overlapping of nodes due to different horizontal lengths, like shown below

Solution: A check can be performed for overlapping when placing the node to make necessary adjustments.

References

1. Patrick Healy, Nikola S. Nikolov: How to layer a Directed Acyclic Graph, from Graph Drawing, 9th International Symposium
2. Ulrik Brandes, Boris Köpf: Fast and simple horizontal coordinate assignment, Part of the Lecture Notes in Computer Science book series (LNCS, volume 2265)
3. Ulf Ruegg, Christoph Daniel Schulze, John Julian Carstens, Reinhard von Hanxleden: Size and Port Aware Horizontal Node Coordinate Assignment, Part of the Lecture Notes in Computer Science book series (LNCS, volume 9411)
4. Hierarchical Drawing Algorithms, Chapter 13, Handbook of Graph Drawing & Visualisation by Robert Tamassia

Timeline

1. Implement layering and Crossing-Minimisation implementation.
2. Implement the Preprocessing method.
3. Implement the process to extract information from a Visual Script / Visual Shader to build its corresponding layered graph, with minimum crossings and marked non-inner segments.
4. Start horizontal alignment and refactoring.
5. Start implementing the undo feature.
6. Implement the Inner Shift method, followed by the last phase, which is the vertical alignment of the formed blocks.

If this enhancement will not be used often, can it be worked around with a few lines of script?:

This is not a small number of lines.

Is there a reason why this should be core and not an add-on in the asset library?:

Modifying graph edit requires core c++. Runtime performance might be a problem in gdscript. This solves a common problem that should be in core.

[jonbonazza]

Excellent job on this proposal.

[Norrox]

Very good proposal!

[setzer22]

Amazing writeup! Sorry to comment without adding more information but I had to ask: Is this being worked on right now? If there's a fork I could try out with the suggested changes I'd love to at least contribute by testing them!

[theoway]

Amazing writeup! Sorry to comment without adding more information but I had to ask: Is this being worked on right now? If there's a fork I could try out with the suggested changes I'd love to at least contribute by testing them!

@setzer22 Thanks! I'm the author of this proposal. I had made it for GSOC 2020, but didn't get selected. Anyways, I'll start implementing it soon. I'll make a PR and mention it here, so that you guys can see it anytime :)
And if you're interested, you can contribute to it once I open the PR.

[rishabhabhani]

Thanks! I'm the author of this proposal. I had made it for GSOC 2020, but didn't get selected. Anyways, I'll start implementing it soon. I'll make a PR and mention it here, so that you guys can see it anytime :)

@theoway were you able to work on this proposal? I am planning to take this up for my GSOC application. I would really love to see some improvements on the VS.

[theoway]

@theoway were you able to work on this proposal? I am planning to take this up for my GSOC application. I would really love to see some improvements on the VS.

@rishabhabhani As a matter of fact, Yes. I'm extending my previous proposal, that is this one, with some improvements as discussed by the members. See, I've been already working on this for quite some time. There are other issues that you can apply for.

[rishabhabhani]

@theoway Ah, that's great to hear you're still on it. I just didn't see any updates here so I was wondering. Anyways, All the best with this proposal.

[theoway]

godotengine/godot#49343
PR for the proposal. I'll be adding visuals and examples so that you guys can be see the progress.

[aaronfranke]

Removing "archived" since this was implemented in godotengine/godot#49343