Tree Layout Algorithm

Creation context

Created on June 10th 2021 for the game "Alternia".

My goal

My goal for this project was to create a viable algorithm to position the nodes of a data tree in an intelligible way in a single traversal, in order to simplify the rendering of the skill tree of the game "Alternia" while reducing as much as possible the resource cost of this process.

Project description

Prerequisites

The function requires at least 3 parameters :

• the node to position,
• the leftmost horizontal position of the tree,
• the depth of the current node.

as well as a way to store the rightmost horizontal position for each depth level (a dictionary using depth as a key for example).

Explanation of the algorithm

In order to make a single traversal of the tree without losing simplicity, this algorithm makes a post-order traversal (children then root).

If the number of children of the current node is greater than zero :

• For each child :
  • If the current child is not the first one and has more than one child, and the previous child doesn't have children&nbsp: the target horizontal position is the horizontal position of the previous child.
  • Else, if the last horizontal position at the next depth (current depth + 1) is set and the horizontal position received as a parameter is less than the aforementioned + the width of the current child&nbsp: the target horizontal position is the last horizontal position at the next depth + the width of the current child.
  • Finally, we position each child of the current node with as parameters the target horizontal position and the following depth.
• Then, we save the respective horizontal positions of the child furthest to the left and the child furthest to the right,
• And we set the target horizontal position at the center of the two previously saved positions.

Else, if the last horizontal position at the current depth is set and the horizontal position received as a paramter is less than the aforementioned&nbsp: we set the target horizontal position at the last horizontal position for the current depth.

Else, if the last horizontal position for the previous depth (current depth - 1) is set and the horizontal position received as a paramter is less than the aforementioned&nbsp: we set the target horizontal position at the last horizontal position for the previous depth.

At last, we set the last horizontal position for the current depth as well as the horizontal position of the current node at the target horizontal position and the vertical position at the current depth multiplied by the height of a node.

Example of use

To facilitate the understanding of the algorithm, I also made an example of use in python (the game is coded in C# but I chose python for the example as it is easier to read and transpose in another language).

Pseudo-code of the algorithm

Dictionary<int, float> lastXAtDepth

FUNCTION Instantiate(node, xPosition = 0, depth)

    IF depth < 0 THEN
        RAISE EXCEPTION : Depth shouldn't be negative
    END IF

    IF node.childCount > 0 THEN
        FOR i IN range(0, node.childCount) DO
            child = node.children[i]

            IF i > 0 AND child.childCount > 1 AND node.children[i - 1].childCount EQUALS 0 THEN
                xPosition = node.children[i - 1].xPosition
            ELSE IF lastXAtDepth CONTAINS KEY depth + 1 AND xPosition &lt lastXAtDepth[depth + 1] + child.width
                xPosition = lastXAtDepth[depth + 1] + child.width
            END IF

            Instantiate(child, xPosition, depth + 1)
        END FOR

        minX = node.children[0].xPosition
        maxX = node.children[node.childCount - 1].xPosition

        xPosition = (minX + maxX) / 2
    ELSE IF lastXAtDepth CONTAINS KEY depth AND xPosition < lastXAtDepth[depth] THEN
        xPosition = lastXAtDepth[depth]
    ELSE IF lastXAtDepth CONTAINS KEY depth - 1 AND xPosition < lastXAtDepth[depth - 1] THEN
        xPosition = lastXAtDepth[depth - 1]
    END IF

    lastXAtDepth(depth) = xPosition
    node.xPosition = xPosition
    node.yPosition = depth * nodeHeight

END FUNCTION

What I learned

When creating this project, I had to make an easily scalable and easy to use algorithm taking into account specific technical limitations. This exercise allowed me to improve my analytical and problem solving as well as optimization skills which can be essential during the development of an application.

You are free to use this algorithm as you wish and add your personal touch as long as you credit me !

Tags

Unity, C#, Algorithm, UI Programming