ET9_WebGL_Dev/CSharp/Modules/BehaviorTree/BehaviorTreeLayout.cs

using NLog;

namespace BehaviorTree
{
	public static class BehaviorTreeLayout
	{
		private const double XGap = 20;
		private const double YGap = 10;
		private static readonly Logger logger = LogManager.GetCurrentClassLogger();

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

			double prelim = 0;
			double modify = 0;

			double childrenCenter = 0;
			if (!treeNode.IsLeaf)
			{
				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;

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

		public 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;
		}

		public 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 AjustTreeGap(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;

			// TODO:要通知right的所有父节点位置改变
		}

		private static void AjustTreeGap(TreeNodeViewModel treeNode)
		{
			if (treeNode.IsLeaf)
			{
				return;
			}
			foreach (var child in treeNode.Children)
			{
				AjustTreeGap(child);
			}
			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];
					AjustTreeGap(left, right);
				}
			}
		}

		private static void ApplyXY(TreeNodeViewModel treeNode, int level, double totalModify)
		{
			foreach (TreeNodeViewModel node in treeNode.Children)
			{
				ApplyXY(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);
		}

		public static void ExcuteLayout(TreeNodeViewModel root)
		{
			if (root == null)
			{
				return;
			}
			logger.Debug("----------------------------------");
			CountPrelimAndModify(root);
			AjustTreeGap(root);
			ApplyXY(root, 0, 0);
		}
	}
}