Last active
March 18, 2023 16:55
-
-
Save digiwombat/fcb03946b8f79ba8477cd306413a1ddb to your computer and use it in GitHub Desktop.
An Org Chart Layout function
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 HashSet<DialogueEntry> subtreeWidthAdded = new(); | |
private Dictionary<DialogueEntry, float> subTreeWidths = new(); | |
private void ArrangeNodes() | |
{ | |
CalculatePositions(currentConversation.dialogueEntries[0], 0, 0); | |
visited.Clear(); | |
subtreeVisited.Clear(); | |
subTreeWidths.Clear(); | |
subtreeWidthAdded.Clear(); | |
} | |
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)) | |
{ | |
subtreeWidthAdded.Add(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]; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment