Skip to content

Instantly share code, notes, and snippets.

@openroomxyz
Last active April 19, 2020 16:13
Show Gist options
  • Select an option

  • Save openroomxyz/b18669723d9b3ab7bf458fe5dd97efe6 to your computer and use it in GitHub Desktop.

Select an option

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]?
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;
}
}
}
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