What’s Going On

The SiteMap is generated by randomly placing the nodes on the map, and then running ~15000 ticks of a physics simulation. Broadly speaking, everything pushes away from everything else. But as you’ve probably seen, you can tweak the specifics of this to try and generate a better graph. Some of these terms are clearer than others, so I’ll briefly explain them here (and why they exist).

I haven’t played with these that much — if you find a set of values you think does consistently better than what I have, email/dm me and I’ll update the site with them!

Repulsion Strength, Linked Repulsion Factor, & Force Exponent

This is the core of the physics simulation. Nodes act as point masses pushing against each other (mass scales linearly with radius, which is kind of bad, but shh). The formula is strength / (distance ^ exponent) (if you want exact details on dimensions, look at the implementation — it’s pretty simple). Additionally, if nodes are connected (one or two ways), the repulsion is scaled by the linked repulsion factor. This is to incentivize shorter arrows, as well as naturally forming K_n clumps, both of which make for cleaner and nicer graphs. It doesn’t do this very well because things are tuned really badly right now, but that’s the idea.

Dampening

AKA friction. Each step, each node slows down by (1-dampening) * velocity.

Max Force

Creates a ceiling for acceleration. This is mainly important for when nodes get pushed really close to each other (or arrows) in one tick and get repelled massively.

Edge Repulsion Strength

Edges push against nodes too. The formula is the same — edge_strength / (distance ^ force_exponent) — except now distance is just the length of the perpendicular to each wall (as this implies, each node is acted on by four edge forces at all times). The purpose of this is pretty obvious: keep the nodes vaguely centered so that the graph doesn’t look too stupid.

Min Distance & Edge Margin

The minimum distance nodes can be from other nodes and the edges respectively. These two are not quite the same — min distance is purely a calculatory term. Nodes can be arbitrarily close together, but the distance term in node repulsion is secretly max(dist, min_dist). Edge margin is different; it acts as a real limit on how close nodes can get to the edges (this is similar to just shrinking the map, but it adds a constant term to every edge perpendicular, which I think is probably good).

Centering Force

Every tick, I find the center of mass of the nodes, take the vector from it to the center of the canvas, scale it by the centering force constant, and apply it to each node. The goal is to generally have a “centered” graph (this is already somewhat achieved by edge forces, but this helps). A brief debugging note: if all your points are in a corner, it’s probably because your centering force was too high and they started oscillating.

Center Repulsion Strength

This is similar to the centering force: each node is pushed away from the center. But because the centering force is based on center of mass, while the repulsion is individual, these two are only actually in opposition on points collinear with the center and the center of mass. I haven’t done any math, but briefly thinking through compositions of the two vector fields, my intuition is that the integral curve should have a parabolic shape (though not exactly a parabola), with the vector from center of mass to center acting as the axis of symmetry, opening in the direction of the constant force. In fact, for reasonable values, the integral curve should approximate a pretty good semicircle until reaching collinearity with the center of mass to center vector.

Formulaically, the center acts exactly like another node doing normal repulsion. The idea behind this is to (in tandem with the centering force) induce a more round structure on the nodes. But perhaps if I didn’t have it, you would just get a node in the middle, and an otherwise identical structure, which might be strictly better? I’m not sure this force is actually good, but you can always set it to 0, so I figured I’d leave it in. Play with it.

Orbital Force

Orbital force applies a tangential force to each node around the center of mass of the nodes. Note that the orbital force constant is an angular acceleration, not a linear one, so the actual magnitude of the acceleration will scale with distance from the center of mass.

Angular Separation Force & Collinear Threshold

This force pushes nodes apart when they’re on the same line. Specifically if the cosine of the angle is more than the threshold, a perpendicular force (to the other two points) is created on the middle node. There are, of course, two such vectors — I choose whichever one is more towards the center via dot product. The magnitude of the force scales purely with the angular separation force parameter.

I added this force to prevent a specific degenerate scenario. Broadly, it prevents a node from getting stuck between two other nodes despite opposition forces, and instead scoots it out so that the vectors don’t perfectly cancel and instead add, shooting it away. This very rarely happens randomly (except for a problematic case which I’ll get to in a bit). But it happens a lot when nodes get stuck on the edge of the map, which is a major issue (that’s why I have it push towards the center and not just pick either perpendicular). This force also just generally ensures arrows mostly don’t pass under other nodes (or are too collinear with each other), which massively adds to visual clutter.

This does induce another degenerate pattern, where a node is being pushed away from between two others towards a third, but once it gets out of the collinear threshold it is then pushed back, and oscillates. This is rarely seen stably, but it does happen. It does create the exact arrow collinearity this force is designed to mitigate, but it’s rare enough that it’s better to have this force than not, I think.

You do sometimes also end up with four collinear points such that the forces cancel, which is less than ideal, but it’s usually not actually that problematic (and because they have to go through the center such that the forces oppose, it’s rare).

Arrow Repulsion Strength, Exponent, and Range

This force pushes nodes away from arrows. The sole reason I want this is visual clarity — it’s awkward when arrows pass under text. The formula is exactly the same as if there was a node at the perpendicular from the target node on each arrow, however the force instead scales with arrow repulsion strength, and the distance is to the power of arrow repulsion exponent. The intent is to have both values be very high to have strong forces when overlapping with arrows, but mainly negligible forces otherwise. To ensure this, arrow repulsion is also not even considered for arrows further than range away.

Obviously nodes are not repelled by their own arrows — that would be stupid, and isn’t the point of this force anyway.

Implementation Details

First of all, a small note: recall that each node has a mass, and (while they’re all pretty similar), force is not quite the same as acceleration, and all of these calculations give force.

Because there are hard edges (and corners), you end up with nodes with distance 0 from each other (or more often, from arrows) sometimes. In these cases, a node considers the point it’s repelled away from the be its location shifted one pixel in each dimension away from the center.

I realize this might induce some degenerate patterns such as two groups of points oscillating between two corners, but this hasn’t happened yet — if it arises I’ll tweak things. It’s not super obvious how to fix this, because if possible you really want forces to be continuous with distance, and you need forces to be really high when nodes are right next to each other, otherwise you immediately get extremely problematic patterns.

Application order does not matter — every tick, each node updates its x and y velocities based on the state, and only once all velocities are calculated does each node step.

You may have found that sometimes when you edit a value, even a benign one, the graph explodes. This is because I freeze it after 15k ticks, and sometimes it's not actually stable. So when you edit a value, it resumes and goes back to being unstable regardless of your input.

Other Thoughts

There are, right now, a bunch of issues. One property is that things always end up in corners. This isn’t intrinsically bad — I think it actually looks kind of nice — but the fact that this is true indicates that max_force is almost always capping the acceleration, which is probably bad. This could theoretically be fixed by just finding perfect values for anything, but if I realistically wanted to fix this I would probably scale down distance so that different numbers are more comparable.

Another known problem is that sometimes all the nodes line up on the edges. This should not happen. I added MULTIPLE checks and features that should prevent this from happening. I do not understand it. If you can debug the issue you can have head or something, I don’t even care at this point (average developer after failing to debug a simple issue for multiple hours).