return (v2.x - v1.x) ** 2 + (v2.y - v1.y) ** 2;

}

​

function dist(v1, v2) {

  return sqrt((v2.x - v1.x) ** 2 + (v2.y - v1.y) ** 2);

}

​

function sub(v1, v2) {

  return createVector(v1.x - v2.x, v1.y - v2.y);

}

​

function add(v1, v2) {

  return createVector(v1.x + v2.x, v1.y + v2.y);

}

​

function mult(v, s) {

  return createVector(v.x * s, v.y * s);

}

​

// returns true if the line from (a1)->(a2) intersects with (p,q)->(r,s)

function intersects(a1, a2, b1, b2) {

  return intersectsPoints(a1.x, a1.y, a2.x, a2.y, b1.x, b1.y, b2.x, b2.y);

}

​

function intersectsPoints(a, b, c, d, p, q, r, s) {

  let det, gamma, lambda;

  det = (c - a) * (s - q) - (r - p) * (d - b);

  if (det === 0) {

    return false;

  } else {

    lambda = ((s - q) * (r - a) + (p - r) * (s - b)) / det;

    gamma = ((b - d) * (r - a) + (c - a) * (s - b)) / det;

    return 0 < lambda && lambda < 1 && 0 < gamma && gamma < 1;

  }

}

​

function intersectsResult(x1, y1, x2, y2, x3, y3, x4, y4) {

  // Check if none of the lines are of length 0

  if ((x1 === x2 && y1 === y2) || (x3 === x4 && y3 === y4)) {

    return false;

  }

​

  denominator = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);

​

  // Lines are parallel

  if (denominator === 0) {

    return false;

  }

​

  let ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator;

  let ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator;

​

  // is the intersection along the segments

  if (ua < 0 || ua > 1 || ub < 0 || ub > 1) {

    return false;

  }

​

  // Return a object with the x and y coordinates of the intersection

  let x = x1 + ua * (x2 - x1);

  let y = y1 + ua * (y2 - y1);

​

  return { x, y };

}

​

//                                                _

//   __ _  __ _ _ __ ___   ___    ___ _ __   __ _(_)_ __   ___

//  / _` |/ _` | '_ ` _ \ / _ \  / _ \ '_ \ / _` | | '_ \ / _ \

// | (_| | (_| | | | | | |  __/ |  __/ | | | (_| | | | | |  __/

//  \__, |\__,_|_| |_| |_|\___|  \___|_| |_|\__, |_|_| |_|\___|

//  |___/                                   |___/

//

// ############################################################

// ############################################################

​

class Game {

  constructor() {

    this.city = new City();

  }

​

  run() {

    this.city.run();

  }

}

​

// ############################################################

// ############################################################

​

class Graph {

  constructor() {

    this.edges = [];

    this.nodes = [];

  }

}

​

class HalfEdge {

  constructor(a, b) {

    this.a = a;

    this.b = b;

    this.next = undefined;

    this.prev = undefined;

  }

  setFlip(flip) {

    this.flip = flip;

  }

  getFlip() {

    return this.flip;

  }

​

  setNext(next) {

    this.next = next;

  }

  getNext() {

    return this.next;

  }

​

  setPrev(prev) {

    this.prev = prev;

  }

  getPrev() {

    return this.prev;

  }

​

  setNode(node) {

    this.node = node;

  }

  getNode() {

    return this.node;

  }

}

​

class Node {

  constructor(x, y) {

    this.x = x;

    this.y = y;

  }

}

​

// ############################################################

// ############################################################

​

class City {

  constructor() {

    // # generate parent street

    let origin = createVector(width / 2, height / 2);

    let angle = random(TWO_PI);

    let direction = p5.Vector.fromAngle(angle);

    let iterations = 4;

​

    this.streets = new Street(this, origin, direction, iterations);

​

    // # generate starting streets

    let startingStreets = 3;

​

    for (let i = 0; i < startingStreets - 1; i++) {

      let leftOrRight = random([-1, 1]);

      let imprecision = 0.2 * leftOrRight;

​

      let step = TWO_PI / startingStreets;

      angle = angle + step + imprecision;

      direction = p5.Vector.fromAngle(angle);

​

      this.streets.children.push(

        new Street(this, origin, direction, iterations)

      );

​

      this.halfEdges = [];

    }

  }

​

  run() {

    this.streets.run(); // run streets

  }

}

​

class Street {

  constructor(

    city = undefined,

    origin,

    direction,

    iteration,

    parent = undefined

  ) {

    this.city = city;

    this.origin = origin;

    this.direction = direction;

    this.current = origin.copy();

    this.speed = 0.01;

    this.iteration = iteration;

​

    this.parent = parent;

    this.children = [];

    this.reached = false;

​

    this.he = undefined;

  }

​

  run() {

    if (!this.reached) {

      this.advance();

    }

​

    this.display();

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

      this.children[i].run();

    }

  }

​

  checkIntersections(city, street) {

    //let lookAhead = 0;

    let origin;

    let current;

​

    // when streets are just born dont make them collide // for now // just dirty bugfix

    if (distSq(this.origin, this.current) < 2) {

      return false;

    } else {

      // for others, check if only their head collides with another street

      origin = add(this.current, this.direction.copy().setMag(-1));

      //current = add(this.current, this.direction.copy().setMag(lookAhead));

      current = this.current;

    }

​

    // check intersection

​

    if (intersects(origin, current, street.origin, street.current)) {

      this.updateToReached(); // update the state to be true so that we don't recheck that

​

      // should now split the touched edge into four half edges

      return true;  // return truuuuuue and leave this fucking recursion

    } else {

      for (let child of street.children) {

        let success = this.checkIntersections(city, child);

        if (success) return true; // bubble up the happy result!

      } // using some() could be better and faster

    }

  }

​

  updateToReached() {

    this.reached = true;

    this.he = new HalfEdge(this.origin, this.current);

    this.city.halfEdges.push(this.he);

  }

​

  checkReachedMax() { // function to stop if we reached the border of the canvas

    let border = 20;

​

    if (

      this.current.x > width - border ||

      this.current.x < border ||

      this.current.y > height - border ||

      this.current.y < border

    ) {

      this.updateToReached();

      return true;

    }

    return false;

  }

​

  advance() {

    let maxDistanceReached = this.checkReachedMax(); // # check if moved maxDistance

    let overlaps = this.checkIntersections(this.city, this.city.streets); // # check if willOverlap

​

    if (!maxDistanceReached && !overlaps) { // # if not max distance reached and no overlap

      this.current.add(this.direction); // move

​

      // probability of making child

      let probability = false;

​

      let distanceBetweenChildren = map(this.iteration, 5, 0, 100, 25); // distance smaller after each iteration

​

      if ( // if there is no children to this street, check distance of current with origin

        this.children.length == 0 &&

        distSq(this.origin, this.current) > distanceBetweenChildren ** 2

      ) {

        probability = random([-1, 1]);

      } else if ( // if there is a children to this street, check distance of current with child

        this.children.length > 0 &&

        distSq(this.current, this.children.at(-1).origin) >

          distanceBetweenChildren ** 2

      ) {

        // check distance with last child

        probability = random([-1, 1]);

      }

​

      // make child number one

​

      if (this.iteration > 0 && probability) {

        let leftOrRight = random([1, -1]); // choose wether child should go left or right

        let imprecision = random(0.3); // offsets a tiny bit the angle so that it isnt a perfect 90 degrees

​

        // copy old direction, set its magnitude to half, then rotate it

        let direction = this.direction

          .copy()

          .setMag(this.direction.mag() / 1)

          .rotate(leftOrRight * (PI / 2 + imprecision));

​

        this.children.push(

          new Street(

            this.city,

            this.current.copy(),

            direction,

            this.iteration - 1,

            this // parent

          )

        );

​

        this.updateToReached(); // update parent of child 2 to reached

        // stop line and make child number 2 in the same direction as the parent 

​

        this.children.push(

          new Street(

            this.city,

            this.current.copy(),

            this.direction.copy(),

            this.iteration,

            this // parent

          )

        );

      }

    }

  }

​

  display() {

    strokeWeight(map(this.iteration, 6, 0, 2, 1));

    stroke(map(this.iteration, 6, 0, 0, 200));

    line(this.origin.x, this.origin.y, this.current.x, this.current.y);

​

    //noStroke()

    //fill(255,100,100);

    //ellipse(this.current.x, this.current.y,3,3);

  }

}

​