haxis/Source/UnrealProject/GUI/SkillTree/SkillTreeState.h

#pragma once
#include "SkillTreeState.Generated.h"

USTRUCT(BlueprintType)
struct FSkillTreeStateObject
{
	GENERATED_BODY();
	UPROPERTY()
	FVector2D gridIndex;
	UPROPERTY()
	float rotation;
	UPROPERTY()
	TArray<FIntPoint> placedPoints;
	UPROPERTY()
	UClass* skillObject;
	UPROPERTY()
	int32 selectedEffect;

	bool ContainsRoot(FIntPoint root)
	{
		for (int32 i = 0; i < placedPoints.Num(); i++)
		{
			if (placedPoints[i] == root) return true;
		}
		return false;
	}
	TArray<FSkillTreeStateObject*> ConnectedSkills( TMap<FIntPoint, FSkillTreeStateObject*>& skillsMap )
	{
		TArray<FSkillTreeStateObject*> result;
		const FIntPoint offsets[2][6]{
			{ FIntPoint(0, -1), FIntPoint(1, -1), FIntPoint(1, 0), FIntPoint(0, 1), FIntPoint(-1, 0), FIntPoint(-1, -1) },
			{ FIntPoint(0, -1), FIntPoint(1, 0), FIntPoint(1, 1), FIntPoint(0, 1), FIntPoint(-1, 1), FIntPoint(-1, 0) } };
		for (int32 i = 0; i < placedPoints.Num(); i++)
		{
			int32 k = placedPoints[i].X & 1;
			for (int32 j = 0; j < 6; j++)
			{
				FIntPoint checkPoint = placedPoints[i] + offsets[k][j];
				if (placedPoints.Contains(checkPoint)) continue;
				if (skillsMap.Contains(checkPoint))
				{
					FSkillTreeStateObject* skill = *skillsMap.Find(checkPoint);
					if (result.Contains(skill)) continue;
					result.Push(skill);
				}
			}
		}
		return result;
	}
};

USTRUCT(BlueprintType)
struct FSkillTreeState
{
	GENERATED_BODY();

	UPROPERTY(BlueprintReadOnly)
	TArray<FSkillTreeStateObject> objects;

private:
	void WalkTree(TMap<FSkillTreeStateObject*, TArray<FSkillTreeStateObject*>>* a_map, TArray<FSkillTreeStateObject*>* a_checked, TArray<FSkillTreeStateObject*> a_nodes)
	{
		for (int32 i = 0; i < a_nodes.Num(); i++)
		{
			if (a_checked->Contains(a_nodes[i])) continue;
			a_checked->Push(a_nodes[i]);
			TArray<FSkillTreeStateObject*>* connected = a_map->Find(a_nodes[i]);
			if (!connected)
			{
				YERROR("Could not find the connected skills.");
				continue;
			}
			WalkTree(a_map, a_checked, *connected);
		}
	}

public:
	bool ValidateSkillTree()
	{
		bool rootResult = false;
		bool connectResult = true;

		if (objects.Num() == 0) return true;


		TMap<FSkillTreeStateObject*, TArray<FSkillTreeStateObject*>> connectedSkillsMap;
		TMap<FIntPoint, FSkillTreeStateObject*> skillsMap;
		FSkillTreeStateObject* rootSkill = NULL;
		for (int32 i = 0; i < objects.Num(); i++)
		{
			TArray<FIntPoint> points = objects[i].placedPoints;
			for (int32 j = 0; j < points.Num(); j++)
			{
				skillsMap.Add(points[j], &objects[i]);
			}
		}

		for (int32 i = 0; i < objects.Num(); i++)
		{
			TArray<FIntPoint> points = objects[i].placedPoints;
			if (!rootResult)
			{
				bool rootTest = objects[i].ContainsRoot(FIntPoint(6,15));
				if (rootTest)
				{
					rootResult = true;
					rootSkill = &objects[i];
				}
			}
			TArray<FSkillTreeStateObject*> connectedSkills = objects[i].ConnectedSkills(skillsMap);
			connectedSkillsMap.Add(&objects[i], connectedSkills);
			if (connectedSkills.Num() == 0)
			{
				connectResult = false;
				break;
			}
		}

		if (connectResult && rootResult)
		{
			if (!rootSkill)
			{
				YERROR("Root Skill is NULL!");
				return false;
			}
			TArray<FSkillTreeStateObject*> checkedSkills;
			checkedSkills.Push(rootSkill);
			TArray<FSkillTreeStateObject*>* connected = connectedSkillsMap.Find(rootSkill);
			if (!connected)
			{
				YPRINT("Root Skill is not attached to any skills!");
				return false;
			}
			WalkTree(&connectedSkillsMap, &checkedSkills, *connected);
			if (objects.Num() != checkedSkills.Num())
				connectResult = false;
			else
			{
				for (int32 i = 0; i < objects.Num(); i++)
				{
					if (!checkedSkills.Contains(&objects[i]))
					{
						connectResult = false;
					}
				}
			}
		}
		bool isValid = false;
		if (objects.Num() == 1 && rootResult)
			isValid = true;
		else
			isValid = (rootResult && connectResult);
		return isValid;
	}
};