Created
May 30, 2013 23:20
-
-
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
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
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Great looking script, would you mind sharing to the version of NGenerics and the namespaces you're using?