Last active
April 19, 2020 16:13
-
-
Save openroomxyz/b18669723d9b3ab7bf458fe5dd97efe6 to your computer and use it in GitHub Desktop.
Unity : How to find right order of instructions automatically with dependency graph [Example with interpolations]?
This file contains hidden or 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
| using System.Collections; | |
| using System.Collections.Generic; | |
| using UnityEngine; | |
| namespace DependencyGraphSolver | |
| { | |
| public class DependencyGraphSolver | |
| { | |
| Dictionary<int, Node> nodes; | |
| public DependencyGraphSolver() | |
| { | |
| nodes = new Dictionary<int, Node>(); | |
| } | |
| public void addNode(int id, int[] depends, string command) | |
| { | |
| nodes.Add(id, new Node(depends, command)); | |
| } | |
| public List<string> SolveForAll(int max_steps=99999) | |
| { | |
| List<string> program = new List<string>(); | |
| bool countinues_solving = true; | |
| int steps = 0; | |
| while(countinues_solving) | |
| { | |
| steps += 1; | |
| countinues_solving = false; | |
| foreach (KeyValuePair<int, Node> element in nodes) | |
| { | |
| if (!element.Value.isSolved()) | |
| { | |
| countinues_solving = true; | |
| if (element.Value.hasDependencies()) | |
| { | |
| if (GraphHasSolved_Dependency(element.Value.getDependencies())) | |
| { | |
| program.Add(element.Value.getCommandString()); | |
| element.Value.SetAsSolved(); | |
| } | |
| } | |
| else | |
| { | |
| program.Add(element.Value.getCommandString()); | |
| element.Value.SetAsSolved(); | |
| } | |
| } | |
| } | |
| if(steps > max_steps) | |
| { | |
| Debug.LogError("We were unable to solve the graph!"); | |
| return program; | |
| } | |
| } | |
| return program; | |
| } | |
| bool GraphHasSolved_Dependency(int[] dep) | |
| { | |
| foreach(int d in dep) | |
| { | |
| if(nodes.ContainsKey(d)) | |
| { | |
| if(nodes[d].isSolved()) | |
| { | |
| } | |
| else | |
| { | |
| return false; | |
| } | |
| } | |
| else | |
| { | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| } | |
| class Node | |
| { | |
| int[] depends; | |
| string command; | |
| bool solved; | |
| public Node(int[] set_depends, string set_command) | |
| { | |
| depends = set_depends; | |
| command = set_command; | |
| solved = false; | |
| } | |
| public bool isSolved() | |
| { | |
| return solved; | |
| } | |
| public void SetAsSolved() | |
| { | |
| solved = true; | |
| } | |
| public bool hasDependencies() | |
| { | |
| if(depends.Length == 0) | |
| { | |
| return false; | |
| } | |
| return true; | |
| } | |
| public int[] getDependencies() | |
| { | |
| return depends; | |
| } | |
| public string getCommandString() | |
| { | |
| return command; | |
| } | |
| } | |
| } |
This file contains hidden or 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
| using System.Collections; | |
| using System.Collections.Generic; | |
| using UnityEngine; | |
| public class Example | |
| { | |
| public void Usage() | |
| { | |
| //OrderFinder ordf = new OrderFinder(); | |
| DependencyGraphSolver.DependencyGraphSolver dgs = new DependencyGraphSolver.DependencyGraphSolver(); | |
| dgs.addNode(0, new int[] { }, "vp[0] = a;"); | |
| dgs.addNode(1, new int[] { 0, 2 }, "vp[1] = Vector3.Lerp(vp[0], vp[2], mid);"); | |
| dgs.addNode(2, new int[] { }, "vp[2] = b;"); | |
| dgs.addNode(3, new int[] { 2, 8 }, "vp[3] = Vector3.Lerp(vp[2], vp[8], mid);"); | |
| dgs.addNode(4, new int[] { 3, 5 }, "vp[4] = Vector3.Lerp(vp[3], vp[5], mid);"); | |
| dgs.addNode(5, new int[] { 6, 0 }, "vp[5] = Vector3.Lerp(vp[6], vp[0], mid);"); | |
| dgs.addNode(6, new int[] { }, "vp[6] = d; "); | |
| dgs.addNode(7, new int[] { 8, 6 }, "vp[7] = Vector3.Lerp(vp[8], vp[6], mid);"); | |
| dgs.addNode(8, new int[] { }, "vp[8] = c;"); | |
| dgs.addNode(9, new int[] { 0, 18 }, "vp[9] = Vector3.Lerp(vp[0], vp[18], mid);"); | |
| dgs.addNode(10, new int[] { 9, 11 }, "vp[10] = Vector3.Lerp(vp[9], vp[11], mid);"); | |
| dgs.addNode(11, new int[] { 2, 20 }, "vp[11] = Vector3.Lerp(vp[2], vp[20], mid);"); | |
| dgs.addNode(12, new int[] { 11, 17 }, "vp[12] = Vector3.Lerp(vp[11], vp[17], mid);"); | |
| dgs.addNode(13, new int[] { 12, 14 }, "vp[13] = Vector3.Lerp(vp[12], vp[14], mid);"); | |
| dgs.addNode(14, new int[] { 15, 9 }, "vp[14] = Vector3.Lerp(vp[15], vp[9], mid);"); | |
| dgs.addNode(15, new int[] { 6, 24 }, "vp[15] = Vector3.Lerp(vp[6], vp[24], mid);"); | |
| dgs.addNode(16, new int[] { 15, 17 }, "vp[16] = Vector3.Lerp(vp[15], vp[17], mid);"); | |
| dgs.addNode(17, new int[] { 8, 26 }, "vp[17] = Vector3.Lerp(vp[8], vp[26], mid);"); | |
| dgs.addNode(18, new int[] { }, "vp[18] = f;"); | |
| dgs.addNode(19, new int[] { 18, 20 }, "vp[19] = Vector3.Lerp(vp[18], vp[20], mid);"); | |
| dgs.addNode(20, new int[] { }, "vp[20] = g;"); | |
| dgs.addNode(21, new int[] { 20, 26 }, "vp[21] = Vector3.Lerp(vp[20], vp[26], mid);"); | |
| dgs.addNode(22, new int[] { 21, 23 }, "vp[22] = Vector3.Lerp(vp[21], vp[23], mid);"); | |
| dgs.addNode(23, new int[] { 24, 18 }, "vp[23] = Vector3.Lerp(vp[24], vp[18], mid);"); | |
| dgs.addNode(24, new int[] { }, "vp[24] = e;"); | |
| dgs.addNode(25, new int[] { 26, 24 }, "vp[25] = Vector3.Lerp(vp[26], vp[24], mid);"); | |
| dgs.addNode(26, new int[] { }, "vp[26] = h;"); | |
| List<string> res = dgs.SolveForAll(); | |
| System.IO.File.WriteAllLines(@"C:\Users\X\Desktop\X\out.txt", res); | |
| //Result that we get | |
| /* | |
| vp[0] = a; | |
| vp[2] = b; | |
| vp[6] = d; | |
| vp[8] = c; | |
| vp[18] = f; | |
| vp[20] = g; | |
| vp[24] = e; | |
| vp[26] = h; | |
| vp[1] = Vector3.Lerp(vp[0], vp[2], mid); | |
| vp[3] = Vector3.Lerp(vp[2], vp[8], mid); | |
| vp[5] = Vector3.Lerp(vp[6], vp[0], mid); | |
| vp[7] = Vector3.Lerp(vp[8], vp[6], mid); | |
| vp[9] = Vector3.Lerp(vp[0], vp[18], mid); | |
| vp[11] = Vector3.Lerp(vp[2], vp[20], mid); | |
| vp[15] = Vector3.Lerp(vp[6], vp[24], mid); | |
| vp[17] = Vector3.Lerp(vp[8], vp[26], mid); | |
| vp[19] = Vector3.Lerp(vp[18], vp[20], mid); | |
| vp[21] = Vector3.Lerp(vp[20], vp[26], mid); | |
| vp[23] = Vector3.Lerp(vp[24], vp[18], mid); | |
| vp[25] = Vector3.Lerp(vp[26], vp[24], mid); | |
| vp[4] = Vector3.Lerp(vp[3], vp[5], mid); | |
| vp[10] = Vector3.Lerp(vp[9], vp[11], mid); | |
| vp[12] = Vector3.Lerp(vp[11], vp[17], mid); | |
| vp[14] = Vector3.Lerp(vp[15], vp[9], mid); | |
| vp[16] = Vector3.Lerp(vp[15], vp[17], mid); | |
| vp[22] = Vector3.Lerp(vp[21], vp[23], mid); | |
| vp[13] = Vector3.Lerp(vp[12], vp[14], mid); | |
| */ | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment