​

class StarLane {

  constructor(src, tgt) {

    this.src = Math.min(src, tgt);

    this.tgt = Math.max(src, tgt);

  }

  isEqual(other) {

    return this.src === other.src && this.tgt === other.tgt;

  }

  toString() {

    return `${this.src}-${this.tgt}`;

  }

}

​

class Galaxy {

  constructor(size, armCount) {

    this.size = size;

    this.coreSize = this.size / 7;

​

    this.armCount = armCount;

​

    const nodeCount = this.size * 3;

    this.coreNodeCount = nodeCount / 2;

    this.armNodeCount = (nodeCount - this.coreNodeCount) / this.armCount;

    this.minNodeDistance = this.size / 40;

    this.spread = this.size / 40;

    this.nodes = [];

    this.edges = new Set();

  }

  generate() {

    this._genArmsNodes();

    this._genCoreNodes();

    this._pruneNodes();

    this._generateEdges();

  }

  _genArmsNodes() {

    const angleIncrement = TWO_PI / this.armCount;

    for (let i = 0; i < this.armCount; i++) {

      const armAngle = angleIncrement * i;

      for (let j = 0; j < this.armNodeCount; j++) {

        const r = j / this.armNodeCount;

        const armRadius = (this.size / 2) * sqrt(r);

        const theta = armAngle + r * PI;

        const nodeX = width / 2 + armRadius * cos(theta) + random(-this.spread, this.spread);

        const nodeY = height / 2 + armRadius * sin(theta) + random(-this.spread, this.spread);

        this.nodes.push(createVector(nodeX, nodeY));

      }

    }

  }

  _genCoreNodes() {

    for (let i = 0; i < this.coreNodeCount; i++) {

      const r = random(this.coreSize);

      const theta = random(TWO_PI);

      const nodeX = width / 2 + r * cos(theta);

      const nodeY = height / 2 + r * sin(theta);

      this.nodes.push(createVector(nodeX, nodeY));

    }

  }

  _pruneNodes() {

    const prunedNodes = [];

    for (const node of this.nodes) {

      const tooClose = prunedNodes.some(

        other => dist(node.x, node.y, other.x, other.y) < this.minNodeDistance

      );

      if (!tooClose) {

        prunedNodes.push(node);

      }

    }

    this.nodes = prunedNodes;

  }

  _generateEdges() {

    this._generateMST();

    this._addExtraEdges(3);

  }

  _generateMST() {

    const connected = new Array(this.nodes.length).fill(false);

    connected[0] = true;

    while (connected.some(isConnected => !isConnected)) {

      const nearestEdge = this._findNearestUnconnectedEdge(connected);

      if (nearestEdge) {

        this.edges.add(nearestEdge.toString());

        connected[nearestEdge.src] = true;

        connected[nearestEdge.tgt] = true;

      }

    }

  }

  _addExtraEdges(count) {

    for (let i = 0; i < this.nodes.length; i++) {

      const nearestNeighbors = this._findNearestNeighbors(i, count);

      nearestNeighbors.forEach(neighborIndex => {

        const lane = new StarLane(i, neighborIndex);

        this.edges.add(lane.toString());

      })

    }

  }

  _findNearestUnconnectedEdge(connected) {

    let nearestEdge = null;

    let nearestDistance = Infinity;

    for (let i = 0; i < connected.length; i++) {

      if (connected[i]) {

        for (let j = 0; j < this.nodes.length; j++) {

          if (!connected[j]) {

            const nodeA = this.nodes[i];

            const nodeB = this.nodes[j];

​

            const d = dist(nodeA.x, nodeA.y, nodeB.x, nodeB.y);

            if (d < nearestDistance) {

              nearestDistance = d;

              nearestEdge = new StarLane(i, j);

            }

          }

        }

      }

    }

    return nearestEdge;

  }

​

  _findNearestNeighbors(nodeIdx, count) {

    const node = this.nodes[nodeIdx];

    const distances = this.nodes.map((other, index) => ({

      index,

      distance: dist(node.x, node.y, other.x, other.y)

    }));

    distances.sort((a, b) => a.distance - b.distance);

    return distances.slice(1, count + 1)

      .filter(d => d.distance < (this.minNodeDistance * 2))

      .map(d => d.index);

  }

  getNodes() {

    return this.nodes;

  }

  getEdges() {

    return this.edges;

  }

}

​

let galaxy = new Galaxy(500, 4)

​

function setup() {

  createCanvas(600, 600);

  noLoop();

  galaxy.generate();

}

​

function draw() {

  background(0);

​

  const nodes = galaxy.getNodes();

  const edges = galaxy.getEdges();

  stroke(255);

  strokeWeight(1);

  noFill();

  edges.forEach(edgeStr => {

    const [srcIdx, tgtIdx] = edgeStr.split('-').map(Number);

    let srcNode = nodes[srcIdx];

    let tgtNode = nodes[tgtIdx];

    line(srcNode.x, srcNode.y, tgtNode.x, tgtNode.y)

  });

​

  fill(255, 255, 0);

  noStroke();

​

  nodes.forEach(node => {

    ellipse(node.x, node.y, 5, 5);

  });

}