Crickets Chirping

A while back I posted about my latest Proce55ing experiment, the Export Atlas.

Here’s a version you can actually play with:

In this screen grab, Mexico has been clicked to hightlight it. The green number is GDP in trillions of US dollars. The tinier percentage figures written over the node edges indicate percentage of exports from the node on the closer side of the edge to the node on the further side of the edge.

In response to Adam’s suggestion, I made the area of the nodes rather than the radii of the nodes proportional to GDP.

I still do not know what the distinction in this data set between the EU and its member nations is. This could be some residual book keeping from pre-EU transactions I suppose?

I do realize that GDP doesn’t all go into exports so what would make this better would be to get data on the gross exports and size the nodes to that value instead. Ugh. More homework.

(click on image to view the applet)

In a previous post, I mentioned something about implementing touchgraph-like graph rendering with Proce55ing. Today I will attempt to build credibility with my precious audience by actually doing what I said I was going to do. You know, it builds character and credibility and shit.

The applet I’ve posted today demonstrates the groundwork from which I will build my next few applets. It’s interactive, so you can click and drag nodes around. Hit the spacebar to generate a new random set of nodes and edges. Other than that, it’s totally featureless.

You may wonder why I’m not just using the Touchgraph code. There are a number of reasons. The first is threading. Touchgraph does the the layout algorithm in a thread that runs separately from the ui rendering loop. THREADSAFE CODE IS HARD TO WRITE. And I lack the discipline to get it right. Another reason is that it’s got an awkward API (to me personally; I make no judgements and consider API design to be more art than analysis or synthesis). My final and most important reason not to use Touchgraph is a severe case of NIH. I wanted to write it all myself. :)

Primary Considerations

• The choice of layout algorithm: Needs to be relatively fast because my intention is to build interactive applets that arrange edges and nodes in realtime. Simplicity is also a premium- I’d like it to be easy to implement because I’m mentally lazy.
• The data model: Try to present as simple a representation of nodes and edges as possible, and allow easy access to nodes from edges, to edges from nodes and get answers to basic questions like “hey are these two nodes connected”?
• Proce55ing-Friendly: doesn’t molest AWT or Swing.

The Algorithm: There is roughly a metric shitload of options from which to choose a graph layout algorithm, but the one I find simplest to implement (and most intuitive for end users) is the force-directed method. This is the same method used by Touchgraph. Force-directed graph layout borrows equations from physics to simulate springs and reverse-gravity (antigravity, you might say). With this method, edges are treated as though they were springs, and nodes are treated as though they are massive bodies.

The spring force equation:

(heh heh, stiffness. natural length. ahem. anyways) The spring wants to be a certain length and whenever it’s not that length there’s a force proportional to how much it’s compressed or stretched beyond it’s natural length pushing it back. In my implementation, edges can have distinct natural lengths. This is useful when you want to represent the different strengths of relationships as distance between two nodes.

The amount of time it takes to calculate all the spring forces is directly proportional to the number of edges. Adding edges doesn’t hurt much, time-wise.

Nodes are modelled in Bizarro World, where gravity works in reverse.

The gravitational equation:

That was Newton, right? Maybe Kepler? Anyhoo, r is the linear distance between two nodes. The closer two nodes get, the more they repel eachother. That also happens to be a fairly accurate way to describe most of my personal relationships. m1 and m2 are the masses of the two nodes. In my implementation, nodes may have different masses, and that can be used to represent data set attributes orthogonally to the strenth of edges between nodes.

Due to the N-body-problem-ness of gravity simulations, and my wanton ignorance of methods numerical that surely address the problem, the gravitational portion of the force calculations is relatively painful. The time required to calculate antigravitational forces is proportional to the square of the number of nodes. Ways to speed this up is an active research area.

[The above paragraph contains a reference to wikipedia, so that's minus one point. Later on though it links to citeseer, so that's plus one point. Final score: zero.]

Those are the two forces that push the nodes around. Dragging a node with the mouse trumps all forces from other nodes or edges.

Rendering

I love alpha blending. I don’t know why. I think it may just be a gratuitous indulgence that I’ll grow out of someday, but for now I’m fadin’-in and fadin’-away. Edges have different thicknesses, and this thickness is determined by how short the edge wants to be. Thick Edge = Wants to be Short. The nodes are rendered as circles whose radius is determined by the mass of the node. Big Node=Massive, Repugnant Node That Everybody Runs Away From.

The main loop of the app does the following twenty times every second:

for each node in the graph
  add up the spring forces applied by the node's edges using the spring force equation
  add up the effects of gravity from every other node (ouch)
  add those forces up and apply them to the node's current position

draw all the edges

draw all the nodes

The API

Like I said, it’s dirt simple. The one nicety that I have in this revision is that you can select nodes. At any point in time you can ask the Graph object for the currently selected node (if any), the currently moused-over node (if any) and the current dragged node (if any). That enables the nodes to draw themselves differently in each of those cases. Next rev I’ll probably have the same events for Edges as well.

At this point I think I’ve spent more time blabbing about this thing than actually writing the code.

I took some ideas y’all had and incorporated them into Fertilization, my last proce55ing experiment.

This time I actually made a game out of it.

Rules:

You get 1000 points for each egg that survives a round unfertilized. In rounds where you have two eggs, you can get 2000 points if you keep them both unfertilized. Clicking the mouse drops nonoxynol-9, and costs you 5 points (yes, your score can go negative). Every sperm you eliminate is worth one point. You can only support three kids, so once you have that many the game is over.

Also, this time stuff bounces off the edge of the screen instead of appearing on the other side. The toroidal topology (like Asteroids) made it difficult for me to play, and didn’t make much sense with the target seeking behavior of the swimmers. For instance, they could flip to the other side of the screen due to inertia, but they couldn’t use that route as an intentional shortcut.

(click image to view applet)

Another sunday, another proce55ing experiment.

This time I wanted to make something more interactive, so you can click on this one. Clicking creates new sperm. There’s a timer in the lower right corner that lets you know when ovulation is about to occur. This is not to time scale at all, since I think real a real ovum only lives for 24 hours in a 28-day cycle. For this applet, the egg will live for half the clock cycle. Sperm are shorter lived. If an egg is hit 20 times before its time is up, it becomes fertilized. And occasionally you get two eggs in the same cycle, which is how my brother and I happened.

I’d like to make an actual game out of this one. I’m just not sure if the point should be to fertilize the ovum or to avoid doing so.

Should I attempt a new one of these proce55ing applet things every week?

(click on the image to view the applet)

I’ve been playing around with Proce55ing because I’m too lazy dive into flash. P5 presents a wonderfully simple interface (and workflow) to develop visual toys like this. I wouldn’t even know where to begin with the Macromedia stuff.

Anyways about this applet. There was a party last night with an inflatable jousting ring and like five kegs. So I was kind of hungover this morning when I woke up. Above my bed, I have a poster of Several Circles by Vasily Kandinsky. So I stood there looking at the poster for a few minutes, head throbbing, feeling kinda dizzy, room still sorta spinning.

Then I thought hey, wouldn’t I be awesome if I could write code right now? The answer is yes. I can, and therefore I am awesome.

And that is how DrunKandinsky came to be.