Improved Vertical Auto Arrange

[digiwombat]

Howdy once again, beautiful people.

NOTICE: The improved version is in 2.2.37+. No need to add it unless you're below that version.


This version is outdated, better version below, which is also integrated into 2.2.37+
I have been importing my larger conversations and the current auto arrange has always left something to be desired. With that in mind, I set out to make a very rough org-chart vibe. Really, it just ends up being a more human-readable grid-layout type thing that tries to make space for branches without thinking too hard about it.

NOTE
This works for vertical arranging only. It's also not perfect, but it is more human readable and organizable. Example screenshot after the instructions.

INSTRUCTIONS
In DialogueEditorWindowConversationNodeEditorAutoArrange.cs in the ArrangeTree function (line 126) we are commenting out the code inside

Code: Select all

if(vertically){}

and adding

Code: Select all

currentConversation.dialogueEntries[0].canvasRect = new Rect(2500, 1 * (canvasRectHeight + 24), canvasRectWidth, canvasRectHeight);

HandleChildren(currentConversation.dialogueEntries[0].outgoingLinks, currentConversation.dialogueEntries[0], 2);
nodeGridDict.Clear();
handledNodes.Clear();

Then, anywhere you want in the same file, you are going to add the following code:

Code: Select all

Dictionary<(int x, int y), DialogueEntry> nodeGridDict = new();
List<DialogueEntry> handledNodes = new();
private void HandleChildren(List<Link> links, DialogueEntry parent, int layer, int startX = 8, List<(int x, int y)> parentLocations = null)
{
	Rect leftMost = new Rect();
	Rect rightMost = new Rect();
	int leftIndex = 0;
	int rightIndex = 0;
	
	for (int i = 0; i < links.Count; i++)
	{
		DialogueEntry child = currentConversation.dialogueEntries.Find(x => x.id == links[i].destinationDialogueID);
		if(child == null || handledNodes.Contains(child))
		{
			continue;
		}

		while (nodeGridDict.ContainsKey((i + startX, layer)))
		{
			startX++;
		}

		int xIndex = i + startX;
		
		nodeGridDict[(xIndex,layer)] = child;
		handledNodes.Add(child);

		child.canvasRect = new Rect((xIndex * (canvasRectWidth+10)), layer * (canvasRectHeight + 24), canvasRectWidth, canvasRectHeight);

		if (child.outgoingLinks.Count > 0)
		{
			if(child.outgoingLinks.Count == 1)
			{
				if(parentLocations == null)
				{
					parentLocations = new();
				}
				parentLocations.Add((xIndex, layer));
				HandleChildren(child.outgoingLinks, child, layer + 1, xIndex, parentLocations);
			}
			else
			{
				int childIndexStart = xIndex - (child.outgoingLinks.Count / 2);

				if (parentLocations != null)
				{
					//Fill gaps above single stacks with branches below
					foreach(var location in parentLocations)
					{
						// Move parents in line with child, hypothetically
						if (nodeGridDict.ContainsKey(location))
						{
							DialogueEntry value = nodeGridDict[location];
							if (value != null)
							{
								value.canvasRect.x = (xIndex * (canvasRectWidth + 10));
							}
							nodeGridDict[(xIndex, location.y)] = value;
							nodeGridDict.Remove(location);
						}

						for (int j = 0; j < child.outgoingLinks.Count; j++)
						{
							nodeGridDict[(childIndexStart + j, location.y)] = null;
						}
					}
				}
				HandleChildren(child.outgoingLinks, child, layer + 1, childIndexStart);
			}
		}
		
		if(i == 0)
		{
			leftMost = child.canvasRect;
			leftIndex = xIndex;
		}
		rightMost = child.canvasRect;
		rightIndex = xIndex;

	}
	parent.canvasRect.x = ((leftIndex + rightIndex) * 0.5f) * (canvasRectWidth+10);
}

Here's a rough shot of out it'll look:

[Tony Li]

Thank you!

[digiwombat]

OKAY! I'm back. Back again. Wombat's back. Rest of song.

So, I wasn't happy with the layout results from the other thing and I am procrastinating on writing intro conversations for characters because why should my game ever come out? I mean, seriously, why? Why am I like this?

Anyway, here's a proper org-chart layout script because the hacked together one was gross and ugly and possibly wanted for armed robbery. This new one should work better for bigger conversations for sure. It should handle self-linking no problem. The only caveat is that it sometimes produces excess space in multi-linked child nodes, but it's hard to avoid that without creating some esoteric tree walk rules. Nevermind, I figured out what I was doing wrong there.

Here's a picture of the output of the newer, sexier older brother:



Same deal as above, you're injecting a call into the

Code: Select all

if(vertically){}

situation just as above.

Comment out the code in there, and add

Code: Select all

CalculatePositions(currentConversation.dialogueEntries[0], 0, 0);
visited.Clear();
subtreeVisited.Clear();
subTreeWidths.Clear();

After that, we're doing the same thing as above. In your file, add these functions:

Code: Select all

private float HorizontalSpacing => canvasRectWidth * 0.3f; // The horizontal spacing between nodes
private float VerticalSpacing => canvasRectHeight + 24; // The vertical spacing between nodes

private HashSet<DialogueEntry> visited = new();
private HashSet<DialogueEntry> subtreeVisited = new();
private Dictionary<DialogueEntry, float> subTreeWidths = new();
// Calculate the positions of all nodes recursively
private void CalculatePositions(DialogueEntry node, int level, float offset)
{
	if (node == null) return;

	// If the node has been visited before, return
	if (visited.Contains(node)) return;

	// Mark the node as visited
	visited.Add(node);

	// Calculate the width of the subtree rooted at this node
	float subtreeWidth = GetSubtreeWidth(node);

	node.canvasRect = new Rect(0, 0, canvasRectWidth, canvasRectHeight);
	// Set the X position of this node to be the center of its subtree
	node.canvasRect.x = offset + subtreeWidth / 2;

	// Set the Y position of this node to be based on its level
	node.canvasRect.y = level * (canvasRectHeight + VerticalSpacing) + 50;
	// Recursively calculate the positions of the child nodes
	float childOffset = offset;
	foreach (Link childLink in node.outgoingLinks)
	{
		if(childLink.destinationConversationID != currentConversation.id)
		{
			continue;
		}
		DialogueEntry child = currentConversation.GetDialogueEntry(childLink.destinationDialogueID);
		CalculatePositions(child, level + 1, childOffset);
		childOffset += GetSubtreeWidth(child) + HorizontalSpacing;
	}
}

// Calculate the width of the subtree rooted at a node
private float GetSubtreeWidth(DialogueEntry node)
{
	if (node == null) return 0;

	// If the node has no children, return its own width
	if (node.outgoingLinks.Count == 0) return canvasRectWidth;

	// Check if we've been to this subtree before so we don't infinite loop
	if (subtreeVisited.Contains(node))
	{
		if (subTreeWidths.ContainsKey(node))
		{
			return subTreeWidths[node];
		}
		else
		{
			return canvasRectWidth;
		}
	}

	subtreeVisited.Add(node);
	// Otherwise, return the sum of the widths of its children and the spacings between them
	float width = 0;
	foreach (Link childLink in node.outgoingLinks)
	{
		if(childLink.destinationConversationID != currentConversation.id)
		{
			continue;
		}
		DialogueEntry child = currentConversation.GetDialogueEntry(childLink.destinationDialogueID);
		if (!subtreeVisited.Contains(child))
                {
                    width += GetSubtreeWidth(child) + HorizontalSpacing;
                }
	}
	width -= HorizontalSpacing; // Subtract the extra spacing at the end

	// Return the maximum of the node's own width and its children's width
	subTreeWidths[node] = Mathf.Max(width, canvasRectWidth);
	return subTreeWidths[node];
}

Here's a bonus shot of a bigger conversation:



Here's a double bonus of the the layout of a conversation with loopbacks and multi-linked subtrees and stuff: