Hey, I’ve tried to re-build the classic Force Directed Graph contribution by @tonfilm & @gregsn. It kinda works. I think there is still something wrong with the parents / children lists of the FDNodes or the order of From/To inside FDEdge respectively.
Also not quite sure if the forces are “translated” correctly.
The real problem is the performance (of calculating the Repulsion) though. The whole thing is way slower than the beta version and totally fails for spreadcounts >=200 on my machine.
Any feedback and ideas for improvement very much appreciated.
That you use delegates at the very core of the nested loop is probably not a good idea. The Repulse node is also a process node even though there’s no state involved - honestly the system should have given you an error/warning there, because that state gets re-created for each iteration. So my suggestion for a starter would be to get rid of that one.
Regarding the delegates, there’re two options - use an interface to pass the models (Attract/Repulse) or use adaptive nodes. Only found time for the adaptive version (which in theory should be the fastest), see attached patch. (not happy how I did it, as all those FD nodes became generic due to the attract operation - wanted to only have the graph generic over the used model, but out of time)
(Btw, your patch also shows an issue with the bang io boxes - will be fixed in upcoming builds, sorry for that)
Hey, played with it some more and made some minor changes. Still it performs worse than the beta version and breaks completely for larger spreadcounts and I really don’t get were the differences come from.
Don’t know it the ticks displayed in gamma and beta can be compared directly:
Perf
Graph Update
beta:
public void Update()
{
var edgeCount = FEdges.Count;
var nodeCount = FNodes.Count;
//attraction along edges
for(int i=0; i<edgeCount; i++)
{
FEdges[i].Update();
}
var nodeCountRep = 1.0/nodeCount;
//repulsion of the nodes
for(int i=0; i<nodeCount; i++)
{
var n = FNodes[i];
n.Velocity += CalcRepulsion(n);
n.Velocity *= Speed;
}
//update position
for(int i=0; i<nodeCount; i++)
{
var n = FNodes[i];
n.Update(GetTime());
}
}
gamma:
CalcRepulsion
beta:
private Vector3D CalcRepulsion(FDNode n)
{
var rep = new Vector3D(0);
if(n.Parent.Count == 0) return rep;
var oCount = FNodes.Count;
for(int i=0; i<oCount; i++)
{
var o = FNodes[i];
if (o != n)
{
var diff = n.Position - o.Position;
rep += Forces.Repulse(diff);
}
}
return rep/oCount;
}
gamma:
Fruchterman Reingold repulsion
beta:
private static Vector3D RepulseFR(Vector3D diff)
{
var l = !diff;
diff /= l;
return diff * ((ConstantsFR.y*ConstantsFR.y) / l);
}
The ticks can be compared directly - both represent µs. Just did a quick comparison and for N = 200, it’s ~900µs in beta vs ~2200µs in gamma. Reason is that the emitted code when running inside the editor is not as good as it could be. To name a few things which are different:
A class in VL comes with one level of indirection (proxy and target) in order to quickly exchange them in the object graph (hotswap) - in this case we pay for that one a lot I wager as it affects the inequality check, the position and model access.
The root patch carries the actual implementation of the Attract and Repulse methods (at least in the patch I posted they were implemented using the adaptive mechanism). But since it gets emitted in debug mode, also the JIT compilation of those generic methods will happen in debug → certain optimizations won’t apply. With a little workaround I was able to avoid this an the timings dropped to 1700µs.
Therefor a fair comparison would be to do an export and see how that performs compared to the plugin. I must admit it would be nice to have some sort of switch in the settings to enforce that everything tries to run as fast as possible (obviously losing any debugging features).
But all that being said, I’d say that for high spread counts this algorithm will perform poorly since it’s O(N²). Much better results would probably be achieved using Barnes-Hut algorithm for example The Barnes-Hut Galaxy Simulator
the first one for testing while developing the latter if you want to start a project in the runtime. Both should be connected to the same property, so one’s able to start with the command-line-flag but has the possibility to escape it later without restarting the HDE.
Out of curiosity I’ve tried to adapt a “textual version” of the Force Directed graph from the beta version.
Seemed pretty straight forward. But I am running into an issue I really can’t wrap my head around.
The graph has a List of Edges and a List of Nodes. When building the graph these lists are cleared and then Edges added. When an Edge is added it checks if the Nodes making up the Edge (From, To) already exist, if so fetch the existing Node, otherwise create a new one with random Position and an ID and add it to the nodes list. So far so good.
But when I add multiple Edges/Nodes at once the resulting nodes all have the same Position even though their IDs are correct.
When I do the same in Debug mode in Visual Studio, stepping through the Process of adding, the resulting Positions are also distinct. It also works when adding the Edges one after the other (frame by frame).
Any ideas?
I think both helppatches would be nice to include. one that shows the basic components and one that demonstrate how to spawn and render multiple viruses.
@schlonzo That’s the patched version we discussed further up. Björn replaced it with one written in C#, so I guess that error can be ignored as it’s not used anymore anyways.
