ET9_WebGL_Base/CSharp/App/Modules/Tree/BehaviorTreeLayout.cs

using Logger;

namespace Tree
{
	public static class BehaviorTreeLayout
	{
		private const double XGap = 20;
		private const double YGap = 10;
		private static double rootOrigX;
		private static double rootOrigY;
		private static double rootOffsetX;
		private static double rootOffsetY;

		private static TreeNodeViewModel LeftMostOffspring(
			TreeNodeViewModel treeNode, int currentLevel, int searchLevel)
		{
			if (currentLevel == searchLevel)
			{
				return treeNode;
			}
			for (int i = 0; i < treeNode.Children.Count; ++i)
			{
				var child = treeNode.Children[i];
				child.AncestorModify = treeNode.Modify + treeNode.AncestorModify;
				var offspring = LeftMostOffspring(child, currentLevel + 1, searchLevel);
				if (offspring == null)
				{
					continue;
				}
				return offspring;
			}
			return null;
		}

		private static TreeNodeViewModel RightMostOffspring(
			TreeNodeViewModel treeNode, int currentLevel, int searchLevel)
		{
			if (currentLevel == searchLevel)
			{
				return treeNode;
			}
			for (int i = treeNode.Children.Count - 1; i >= 0; --i)
			{
				var child = treeNode.Children[i];
				child.AncestorModify = treeNode.Modify + treeNode.AncestorModify;
				var offspring = RightMostOffspring(child, currentLevel + 1, searchLevel);
				if (offspring == null)
				{
					continue;
				}
				return offspring;
			}
			return null;
		}

		private static void AjustSubTreeGap(TreeNodeViewModel left, TreeNodeViewModel right)
		{
			double offset = 0;
			TreeNodeViewModel tLeft = left;
			TreeNodeViewModel tRight = right;
			left.AncestorModify = 0;
			right.AncestorModify = 0;
			for (int i = 0; tLeft != null && tRight != null; ++i)
			{
				double tGap = (tRight.Prelim + tRight.AncestorModify) - (tLeft.Prelim + tLeft.AncestorModify);
				if (XGap + TreeNodeViewModel.Width - tGap > offset)
				{
					offset = XGap + TreeNodeViewModel.Width - tGap;
				}
				tLeft = RightMostOffspring(left, 0, i + 1);
				tRight = LeftMostOffspring(right, 0, i + 1);
			}
			right.Modify += offset;
			right.Prelim += offset;
		}

		private static void AjustTreeGap(TreeNodeViewModel treeNode)
		{
			for (int i = 0; i < treeNode.Children.Count - 1; ++i)
			{
				for (int j = i + 1; j < treeNode.Children.Count; ++j)
				{
					var left = treeNode.Children[i];
					var right = treeNode.Children[j];
					AjustSubTreeGap(left, right);
				}
			}
		}

		private static void CalculatePrelimAndModify(TreeNodeViewModel treeNode)
		{
			foreach (TreeNodeViewModel node in treeNode.Children)
			{
				CalculatePrelimAndModify(node);
			}

			double prelim = 0;
			double modify = 0;

			if (treeNode.IsLeaf)
			{
				if (treeNode.LeftSibling == null)
				{
					// 如果没有左邻居，不需要设置modify
					prelim = 0;
				}
				else
				{
					prelim = treeNode.LeftSibling.Prelim + TreeNodeViewModel.Width + XGap;
				}
			}
			else
			{
				// 调整子树间的间距
				AjustTreeGap(treeNode);
				double childrenCenter = (treeNode.FirstChild.Prelim + treeNode.LastChild.Prelim) / 2;
				if (treeNode.LeftSibling == null)
				{
					// 如果没有左邻居，不需要设置modify
					prelim = childrenCenter;
				}
				else
				{
					prelim = treeNode.LeftSibling.Prelim + TreeNodeViewModel.Width + XGap;
					modify = prelim - childrenCenter;
				}
			}
			treeNode.Prelim = prelim;
			treeNode.Modify = modify;

			Log.Debug("Num: " + treeNode.Num + " Prelim: " + treeNode.Prelim + " Modify: " +
				treeNode.Modify);
		}

		private static void CalculateRelativeXAndY(
			TreeNodeViewModel treeNode, int level, double totalModify)
		{
			foreach (TreeNodeViewModel node in treeNode.Children)
			{
				CalculateRelativeXAndY(node, level + 1, treeNode.Modify + totalModify);
			}
			if (treeNode.IsLeaf)
			{
				treeNode.X = treeNode.Prelim + totalModify;
			}
			else
			{
				treeNode.X = (treeNode.FirstChild.X + treeNode.LastChild.X) / 2;
			}
			treeNode.Y = level * (TreeNodeViewModel.Height + YGap);
		}

		private static void FixXAndY(TreeNodeViewModel treeNode)
		{
			treeNode.X += rootOffsetX;
			treeNode.Y += rootOffsetY;
			foreach (var node in treeNode.Children)
			{
				FixXAndY(node);
			}
		}

		public static void ExcuteLayout(TreeNodeViewModel root)
		{
			if (root == null)
			{
				return;
			}
			rootOrigX = root.X;
			rootOrigY = root.Y;
			CalculatePrelimAndModify(root);
			CalculateRelativeXAndY(root, 0, 0);

			rootOffsetX = rootOrigX - root.X;
			rootOffsetY = rootOrigY - root.Y;
			FixXAndY(root);
		}
	}
}