Skip to content

Instantly share code, notes, and snippets.

@radiatoryang
Created May 30, 2013 23:20
Show Gist options
  • Star 6 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save radiatoryang/5682034 to your computer and use it in GitHub Desktop.
Save radiatoryang/5682034 to your computer and use it in GitHub Desktop.
method for doing force directed graph stuff with NGenerics + Unity... to make it 3D, just change Vector2's to Vector3's
IEnumerator ForceDirectGraph<T>( Graph<T> graph, Dictionary<T, Vector3> graphPositions ) {
// settings
float attractToCenter = 15f;
float repulsion = 10f;
float spacing = 0.1f;
float stiffness = 100f;
float damping = 0.9f;
// initialize velocities and positions
Dictionary<Vertex<T>, Vector2> velocity = new Dictionary<Vertex<T>, Vector2>();
Dictionary<Vertex<T>, Vector2> position = new Dictionary<Vertex<T>, Vector2>();
foreach ( Vertex<T> vert in graph.Vertices ) {
velocity.Add( vert, Vector2.zero );
Vector3 bestGuess = Random.onUnitSphere * spacing * 0.5f;
if ( graphPositions.ContainsKey( vert.Data ) ) {
bestGuess += graphPositions[vert.Data];
} else {
bestGuess += graphPositions[vert.IncidentEdges[0].GetPartnerVertex( vert ).Data];
}
position.Add( vert, new Vector2( bestGuess.x, bestGuess.z ) );
}
float totalEnergy = 10f; // initial
while ( totalEnergy > 1f ) {
totalEnergy = 0f;
foreach ( Vertex<T> thisVert in graph.Vertices ) {
Vector2 netForce = Vector2.zero; // running total of kinetic energy for thisVert
// Coulomb repulsion
foreach ( Vertex<T> otherVert in graph.Vertices ) {
if ( otherVert == thisVert )
continue;
Vector2 direction = position[thisVert] - position[otherVert];
netForce += ( direction.normalized * repulsion ) / ( Mathf.Pow( direction.magnitude + 0.1f, 2f ) * 0.5f );
}
// Hooke attraction
foreach ( Edge<T> neighbor in thisVert.EmanatingEdges ) {
Vector2 direction = position[neighbor.ToVertex] - position[thisVert];
float displacement = spacing - direction.magnitude;
netForce += direction.normalized * ( stiffness * displacement * -0.5f );
}
// attract to center
netForce += -position[thisVert].normalized * attractToCenter;
// apply velocity to position
velocity[thisVert] = ( velocity[thisVert] + ( netForce * Time.deltaTime ) ) * damping;
position[thisVert] += velocity[thisVert] * Time.deltaTime;
// update running totals too, in case we want to use them outside of this coroutine
graphPositions[thisVert.Data] = new Vector3( position[thisVert].x, 0f, position[thisVert].y );
// add thisVert's energy to the running total of all kinetic energy
totalEnergy += velocity[thisVert].sqrMagnitude;
}
Debug.Log( "TOTAL ENERGY: " + totalEnergy.ToString() );
yield return 0;
}
}
@miketucker
Copy link

Great looking script, would you mind sharing to the version of NGenerics and the namespaces you're using?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment