// LL 2021

// TODO: station names using random first and second words

const line_count = 3; // min=1 max=10 step=1
const stations_per_line = 5; // min=2 max=10 step=1
const station_size = 4; // min=0.1 max=10 step=0.1
const coded_stations = 0; // min=0 max=1 step=1 (No,Yes)
const show_names = 1; // min=0 max=1 step=1 (No,Yes)
const alignment = 0.5; // min=0.1 max=10 step=0.1
const seed = 0; // min=0 max=100 step=1
const style = 1; // min=0 max=1 step=1 (Polygons (fast),Polygons (slow))

const first_words = [ "Picadilly", "Oxford", "Covent", "Euston", "Warren", "Marble", "Green", "King's", "Leicester", "Charing", "Regent's", "Tower", "Mornington", "St James'" ];
const second_words = [ "Circus", "Square", "Garden", "Street", "Road", "Park", "Arch", "Cross", "Bridge", "Crescent" ];

const iterations = 10000;

const hole_size = station_size / 2;
const track_size = station_size / 3;

Canvas.setpenopacity(1);

const turtle = new Turtle();
var rng;
var map;
var polygons;

var available_first_words = [], available_second_words = [];

console.clear();

function walk(i) {
    if (i==0) {
        rng = new RNG(seed);
        polygons = new Polygons();
        map = new Map(line_count);
        
        map.drawStations();
    } else {
        map.doIteration();
    }
    
    return (i < iterations && !map.isDone());
}

class Map {
    constructor(train_line_count) {
        this.train_lines = [];
        this.all_stations = [];
        
        for (var i=0; i<train_line_count; i++) {
            this.train_lines.push(new TrainLine(i));
        }

        const station_count = line_count * stations_per_line;
        var attempts = station_count * 10;
        while (attempts-- > 0 && this.all_stations.length < station_count) {
            const newly_added = [];
            const station_list = [ [ (rng.nextFloat() - 0.5) * 200, (rng.nextFloat() - 0.5) * 200 ] ];
            for (var pi=0; pi<station_list.length && this.all_stations.length < station_count; pi++) {
                var x = station_list[pi][0];
                var y = station_list[pi][1];
                
                x = Math.round(x / (station_size * alignment * 2)) * station_size * alignment * 2;
                y = Math.round(y / (station_size * alignment * 2)) * station_size * alignment * 2;
                
                if (x > 70) continue;
                if (Math.abs(x) > 100 - station_size * 1.5) continue;
                if (Math.abs(y) > 100 - station_size * 1.5) continue;
                
                //if (Math.hypot(x, y) > 100) continue;
                
                const new_s = new Station(x, y);
                
                var collision = false;
                for (var i=0; i<this.all_stations.length && !collision; i++) {
                    const dist = distance_stations(this.all_stations[i], new_s);
                    if (dist < station_size * 2) collision = true;
                }
                if (collision) continue;
                
                this.all_stations.push(new_s);
                newly_added.push(this.all_stations.length - 1);
            }
        }
        
        var current_index = 0;
        for (var i=0; i<train_line_count; i++) {
            const station_list = this.all_stations.slice(current_index, current_index + stations_per_line);
            this.train_lines[i].setStationList(station_list);
            current_index += stations_per_line;
        }
    }
    
    doIteration() {
        var found_one = false;
        for (var i=0; i<this.train_lines.length && !found_one; i++) {
            if (!this.train_lines[i].isDone()) {
                found_one = true;
                this.train_lines[i].doIteration();
            }
        }
    }
    
    drawStations() {
        this.train_lines.forEach(tl => tl.drawStations());
    }
    
    isDone() {
        var is_done = true;
        this.train_lines.forEach(tl => is_done &= tl.isDone());
        return is_done;
    }
}

class TrainLine {
    constructor(id) {
        this.full_station_list = [];
        this.track_list = [];
        this.lone_station_list = [];
        this.used_station_list = [];
        this.hatching_angle = Math.PI * 2 * rng.nextFloat();
        this.hatching_distance = 0.1 + 0.5 * id / Math.max(1, line_count-1);
    }
    
    setStationList(station_list) {
        this.full_station_list = station_list;
        this.lone_station_list = Array.from({length: this.full_station_list.length}, (_,id) => id);
    }
    
    isDone() {
        return this.track_list.length >= this.full_station_list.length - 1;
    }

    doIteration() {
        var i1 = -1, i2 = -1;
        if (this.track_list.length < 1) {
            i1 = (rng.nextFloat() * this.full_station_list.length) | 0;
            i2 = this.findClosest(i1);
        } else if (this.used_station_list.length > 0 && this.lone_station_list.length > 0) {
            var min_dist = 10000;
            for (var i=0; i<this.used_station_list.length; i++) {
                if (this.countConnections(this.used_station_list[i]) > 1) continue;
                if (this.full_station_list[this.used_station_list[i]].closest_index >= 0 && this.lone_station_list.indexOf(this.full_station_list[this.used_station_list[i]].closest_index) >= 0) {
                    i1 = this.used_station_list[i];
                    i2 = this.full_station_list[this.used_station_list[i]].closest_index;
                    const dist = this.distance(i1, i2);
                    min_dist = dist;
                } else {
                    for (var j=0; j<this.lone_station_list.length; j++) {
                        const dist = this.distance(this.used_station_list[i], this.lone_station_list[j]);
                        if (min_dist > dist) {
                            i1 = this.used_station_list[i];
                            i2 = this.lone_station_list[j];
                            this.full_station_list[i1].closest_index = i2;
                            min_dist = dist;
                        }
                    }
                }
            }
        }
        if (i1 >= 0 && i2 >= 0) {
            const new_track = new Track(i1, i2);
            new_track.draw(this.full_station_list, this.hatching_angle, this.hatching_distance);
            this.track_list.push(new_track);
    
            i = this.lone_station_list.indexOf(i1);
            if (i > -1) { this.lone_station_list.splice(i, 1); }
            i = this.lone_station_list.indexOf(i2);
            if (i > -1) { this.lone_station_list.splice(i, 1); }
            i = this.used_station_list.indexOf(i1);
            if (i == -1) { this.used_station_list.push(i1); }
            i = this.used_station_list.indexOf(i2);
            if (i == -1) { this.used_station_list.push(i2); }
        }
    }
    
    drawStations() {
        this.full_station_list.forEach(p => p.draw(this.hatching_angle, this.hatching_distance));
    }
    
    countConnections(index) {
        var count = 0;
        for (var i=0; i<this.track_list.length; i++) {
            if (this.track_list[i].i1 == index || this.track_list[i].i2 == index) {
                count++;
            }
        }
        return count;
    }

    findClosest(i1) {
        var i2 = -1;
        var min_dist = 10000;
        for (var i=0; i<this.full_station_list.length; i++) {
            if (i == i1) continue;
            var dist = this.distance(i1, i);
            if (min_dist > dist) {
                min_dist = dist;
                i2 = i;
            }
        }
        return i2;
    }

    distance(i1, i2) {
        return distance_stations(this.full_station_list[i1], this.full_station_list[i2]);
    }
    
}

function distance_stations(station1, station2) {
    return Math.hypot(station1.x - station2.x, station1.y - station2.y);
}

class Station {
    constructor(x, y) {
        this.x = x;
        this.y = y;
        this.closest_index = -1;
        this.pickName();
    }
    
    draw(hatching_angle, hatching_distance) {
        const astep = Math.PI * 2 / 20;
        var points = [], points2 = [];
        for (var a = 0; a <= Math.PI * 2; a += astep) {
            var px = this.x + hole_size * Math.cos(a);
            var py = this.y + hole_size * Math.sin(a);
            points.push([px, py]);
            var px2 = this.x + station_size * Math.cos(a);
            var py2 = this.y + station_size * Math.sin(a);
            points2.push([px2, py2]);
        }
        drawPoints(points);
        drawPoints(points2, hatching_angle, coded_stations ? hatching_distance : 0.2);

        if (show_names) {
            const text = new Text();
            const text_size = station_size / 30;
            turtle.jump(this.x + station_size * 0.8, this.y - station_size * 0.8);
            text.print(turtle, this.name, text_size);
        }
    }
    
    pickName() {
        if (available_first_words.length < 1) available_first_words = [...first_words];
        if (available_second_words.length < 1) available_second_words = [...second_words];
        const index1 = (rng.nextFloat() * available_first_words.length) | 0;
        const index2 = (rng.nextFloat() * available_second_words.length) | 0;
        const word1 = available_first_words[index1];
        const word2 = available_second_words[index2];
        this.name = `${word1} ${word2}`;
        available_first_words.splice(index1, 1);
        available_second_words.splice(index2, 1);
    }
}

function rotX(x, y, a) { return Math.cos(a) * x - Math.sin(a) * y; }
function rotY(x, y, a) { return Math.sin(a) * x + Math.cos(a) * y; }

class Track {
    constructor(i1, i2) {
        this.i1 = i1;
        this.i2 = i2;
    }
    
    length() {
        return distance(this.i1, this.i2);
    }
    
    split(station_list) {
        const list = [];
        const dx = station_list[this.i2].x - station_list[this.i1].x;
        const dy = station_list[this.i2].y - station_list[this.i1].y;
        const EPS = 0.001;
        if ((Math.abs(dx) > EPS) && (Math.abs(dy) > EPS) && (Math.abs(dx-dy) > EPS)) 
        {
            const x1 = station_list[this.i1].x;
            const y1 = station_list[this.i1].y;
            const x3 = station_list[this.i2].x;
            const y3 = station_list[this.i2].y;

            const adx = Math.abs(dx);
            const ady = Math.abs(dy);
            const dir = Math.sign(dx) *  Math.sign(dy);
            const x2 = (adx > ady) ? (x1 + dy * dir) : (x3);            
            const y2 = (ady > adx) ? (y1 + dx * dir) : (y3);            

            if (Math.hypot(x1-x2, y1-y2) > hole_size && Math.hypot(x2-x3, y2-y3) > hole_size) {
                list.push([x1, y1, x2, y2]);
                list.push([x2, y2, x3, y3]);
            }
        }

        if (list.length < 1) {
            list.push([station_list[this.i1].x, station_list[this.i1].y, station_list[this.i2].x, station_list[this.i2].y]);
        }

        return list;
    }
    
    draw(station_list, hatching_angle, hatching_distance) {
        const lines = this.split(station_list);
        for (var i=0; i<lines.length; i++) {
            var points = [];
            
            const len = Math.hypot(lines[i][0] - lines[i][2], lines[i][1] - lines[i][3]);
            const EPS = 0.0001;
            if (len < EPS) continue;

            var rx = [], ry = [];
            rx[0] = rotX(lines[i][0] - lines[i][2], lines[i][1] - lines[i][3], Math.PI/2) / len * track_size;
            ry[0] = rotY(lines[i][0] - lines[i][2], lines[i][1] - lines[i][3], Math.PI/2) / len * track_size;
            rx[1] = rx[0];
            ry[1] = ry[0];
            
            if (i > 0) {
                const len = Math.hypot(lines[i-1][0] - lines[i-1][2], lines[i-1][1] - lines[i-1][3]);
                if (len > EPS) {
                    const rx2 = rotX(lines[i-1][0] - lines[i-1][2], lines[i-1][1] - lines[i-1][3], Math.PI/2) / len * track_size;
                    const ry2 = rotY(lines[i-1][0] - lines[i-1][2], lines[i-1][1] - lines[i-1][3], Math.PI/2) / len * track_size;
                    rx[0] = (rx[0] + rx2) / 2;
                    ry[0] = (ry[0] + ry2) / 2;
                }
            }
            
            if (i < lines.length-1) {
                const len = Math.hypot(lines[i+1][0] - lines[i+1][2], lines[i+1][1] - lines[i+1][3]);
                if (len > EPS) {
                    const rx2 = rotX(lines[i+1][0] - lines[i+1][2], lines[i+1][1] - lines[i+1][3], Math.PI/2) / len * track_size;
                    const ry2 = rotY(lines[i+1][0] - lines[i+1][2], lines[i+1][1] - lines[i+1][3], Math.PI/2) / len * track_size;
                    rx[1] = (rx[1] + rx2) / 2;
                    ry[1] = (ry[1] + ry2) / 2;
                }
            }
            
            [0, 1].forEach(j => {
                points.push(   [lines[i][j*2+0] + rx[j], lines[i][j*2+1] + ry[j]]);
                points.unshift([lines[i][j*2+0] - rx[j], lines[i][j*2+1] - ry[j]]);
            });

            drawPoints(points, hatching_angle, hatching_distance);
        }
    }
    
    sameAs(e) {
        return (this.i1 == e.i1 && this.i2 == e.i2) || (this.i1 == e.i2 && this.i2 == e.i1);
    }
}

function drawPoints(points, hatching_angle = 0, hatching_distance = 0) {
    if (style == 0) {
        turtle.jump(points[points.length-1]);
        points.forEach(p=>turtle.goto(p));
    } else {
        const p1 = polygons.create();
        p1.addPoints(...points);
        if (hatching_distance) p1.addHatching(hatching_angle, hatching_distance);
        //p1.addOutline();
        polygons.draw(turtle, p1, true);
    }
}

// Random with seed
function RNG(t){return new class{constructor(t){this.m=2147483648,this.a=1103515245,this.c=12345,this.state=t||Math.floor(Math.random()*(this.m-1))}nextFloat(){return this.state=(this.a*this.state+this.c)%this.m,this.state/(this.m-1)}}(t)}

////////////////////////////////////////////////////////////////
// Polygon Clipping utility code - Created by Reinder Nijhoff 2019
// https://turtletoy.net/turtle/a5befa1f8d
////////////////////////////////////////////////////////////////
function Polygons(){const t=[],s=class{constructor(){this.cp=[],this.dp=[],this.aabb=[]}addPoints(...t){let s=1e5,e=-1e5,h=1e5,i=-1e5;(this.cp=[...this.cp,...t]).forEach(t=>{s=Math.min(s,t[0]),e=Math.max(e,t[0]),h=Math.min(h,t[1]),i=Math.max(i,t[1])}),this.aabb=[(s+e)/2,(h+i)/2,(e-s)/2,(i-h)/2]}addSegments(...t){t.forEach(t=>this.dp.push(t))}addOutline(){for(let t=0,s=this.cp.length;t<s;t++)this.dp.push(this.cp[t],this.cp[(t+1)%s])}draw(t){for(let s=0,e=this.dp.length;s<e;s+=2)t.jump(this.dp[s]),t.goto(this.dp[s+1])}addHatching(t,e){const h=new s;h.cp.push([-1e5,-1e5],[1e5,-1e5],[1e5,1e5],[-1e5,1e5]);const i=Math.sin(t)*e,n=Math.cos(t)*e,a=200*Math.sin(t),p=200*Math.cos(t);for(let t=.5;t<150/e;t++)h.dp.push([i*t+p,n*t-a],[i*t-p,n*t+a]),h.dp.push([-i*t+p,-n*t-a],[-i*t-p,-n*t+a]);h.boolean(this,!1),this.dp=[...this.dp,...h.dp]}inside(t){let s=0;for(let e=0,h=this.cp.length;e<h;e++)this.segment_intersect(t,[.1,-1e3],this.cp[e],this.cp[(e+1)%h])&&s++;return 1&s}boolean(t,s=!0){if(Math.abs(this.aabb[0]-t.aabb[0])-(t.aabb[2]+this.aabb[2])>=0&&Math.abs(this.aabb[1]-t.aabb[1])-(t.aabb[3]+this.aabb[3])>=0)return this.dp.length>0;const e=[];for(let h=0,i=this.dp.length;h<i;h+=2){const i=this.dp[h],n=this.dp[h+1],a=[];for(let s=0,e=t.cp.length;s<e;s++){const h=this.segment_intersect(i,n,t.cp[s],t.cp[(s+1)%e]);!1!==h&&a.push(h)}if(0===a.length)s===!t.inside(i)&&e.push(i,n);else{a.push(i,n);const h=n[0]-i[0],p=n[1]-i[1];a.sort((t,s)=>(t[0]-i[0])*h+(t[1]-i[1])*p-(s[0]-i[0])*h-(s[1]-i[1])*p);for(let h=0;h<a.length-1;h++)(a[h][0]-a[h+1][0])**2+(a[h][1]-a[h+1][1])**2>=.001&&s===!t.inside([(a[h][0]+a[h+1][0])/2,(a[h][1]+a[h+1][1])/2])&&e.push(a[h],a[h+1])}}return(this.dp=e).length>0}segment_intersect(t,s,e,h){const i=(h[1]-e[1])*(s[0]-t[0])-(h[0]-e[0])*(s[1]-t[1]);if(0===i)return!1;const n=((h[0]-e[0])*(t[1]-e[1])-(h[1]-e[1])*(t[0]-e[0]))/i,a=((s[0]-t[0])*(t[1]-e[1])-(s[1]-t[1])*(t[0]-e[0]))/i;return n>=0&&n<=1&&a>=0&&a<=1&&[t[0]+n*(s[0]-t[0]),t[1]+n*(s[1]-t[1])]}};return{list:()=>t,create:()=>new s,draw:(s,e,h=!0)=>{for(let s=0;s<t.length&&e.boolean(t[s]);s++);e.draw(s),h&&t.push(e)}}}


////////////////////////////////////////////////////////////////
// Text utility code. Created by Reinder Nijhoff 2019
// https://turtletoy.net/turtle/1713ddbe99
////////////////////////////////////////////////////////////////
function Text(){const s="br>eoj^jl<jqirjskrjq>brf^fe<n^ne>`ukZdz<qZjz<dgrg<cmqm>`thZhw<lZlw<qao_l^h^e_caccdeefggmiojpkqmqporlshsercp>^vs^as<f^h`hbgdeeceacaab_d^f^h_k`n`q_s^<olmmlolqnspsrrspsnqlol>]wtgtfsereqfphnmlpjrhsdsbraq`o`makbjifjekckaj_h^f_eaecffhimporqssstrtq>eoj`i_j^k_kajcid>cqnZl\\j_hcghglhqjulxnz>cqfZh\\j_lcmhmllqjuhxfz>brjdjp<egom<ogem>]wjajs<ajsj>fnkojpiojnkokqis>]wajsj>fnjniojpkojn>_usZaz>`ti^f_dbcgcjdofrisksnrpoqjqgpbn_k^i^>`tfbhak^ks>`tdcdbe`f_h^l^n_o`pbpdofmicsqs>`te^p^jfmfogphqkqmppnrkshserdqco>`tm^clrl<m^ms>`to^e^dgefhekenfphqkqmppnrkshserdqco>`tpao_l^j^g_ebdgdlepgrjsksnrppqmqlpingkfjfggeidl>`tq^gs<c^q^>`th^e_dadceegfkgnhpjqlqopqorlshserdqcocldjfhigmfoepcpao_l^h^>`tpeohmjjkikfjdhcecddaf_i^j^m_oapepjoomrjshserdp>fnjgihjikhjg<jniojpkojn>fnjgihjikhjg<kojpiojnkokqis>^vrabjrs>]wagsg<amsm>^vbarjbs>asdcdbe`f_h^l^n_o`pbpdofngjijl<jqirjskrjq>]xofndlcicgdfeehekfmhnknmmnk<icgefhfkgmhn<ocnknmpnrntluiugtdsbq`o_l^i^f_d`bbad`g`jambodqfrislsorqqrp<pcokompn>asj^bs<j^rs<elol>_tc^cs<c^l^o_p`qbqdpfoglh<chlhoipjqlqopqorlscs>`urcqao_m^i^g_eadccfckdnepgrismsorqprn>_tc^cs<c^j^m_oapcqfqkpnopmrjscs>`sd^ds<d^q^<dhlh<dsqs>`rd^ds<d^q^<dhlh>`urcqao_m^i^g_eadccfckdnepgrismsorqprnrk<mkrk>_uc^cs<q^qs<chqh>fnj^js>brn^nnmqlrjshsfreqdndl>_tc^cs<q^cl<hgqs>`qd^ds<dsps>^vb^bs<b^js<r^js<r^rs>_uc^cs<c^qs<q^qs>_uh^f_daccbfbkcndpfrhslsnrppqnrkrfqcpan_l^h^>_tc^cs<c^l^o_p`qbqepgohlici>_uh^f_daccbfbkcndpfrhslsnrppqnrkrfqcpan_l^h^<koqu>_tc^cs<c^l^o_p`qbqdpfoglhch<jhqs>`tqao_l^h^e_caccdeefggmiojpkqmqporlshsercp>brj^js<c^q^>_uc^cmdpfrisksnrppqmq^>asb^js<r^js>^v`^es<j^es<j^os<t^os>`tc^qs<q^cs>asb^jhjs<r^jh>`tq^cs<c^q^<csqs>cqgZgz<hZhz<gZnZ<gznz>cqc^qv>cqlZlz<mZmz<fZmZ<fzmz>brj\\bj<j\\rj>asazsz>fnkcieigjhkgjfig>atpeps<phnfleiegfehdkdmepgrislsnrpp>`sd^ds<dhffhekemfohpkpmopmrkshsfrdp>asphnfleiegfehdkdmepgrislsnrpp>atp^ps<phnfleiegfehdkdmepgrislsnrpp>asdkpkpiognfleiegfehdkdmepgrislsnrpp>eqo^m^k_jbjs<gene>atpepuoxnylzizgy<phnfleiegfehdkdmepgrislsnrpp>ate^es<eihfjemeofpips>fni^j_k^j]i^<jejs>eoj^k_l^k]j^<kekvjyhzfz>are^es<oeeo<ikps>fnj^js>[y_e_s<_ibfdegeifjijs<jimfoeretfuius>ateees<eihfjemeofpips>atiegfehdkdmepgrislsnrppqmqkphnfleie>`sdedz<dhffhekemfohpkpmopmrkshsfrdp>atpepz<phnfleiegfehdkdmepgrislsnrpp>cpgegs<gkhhjfleoe>bsphofleieffehfjhkmlompopporlsisfrep>eqj^jokrmsos<gene>ateeeofrhsksmrpo<peps>brdejs<pejs>_ubefs<jefs<jens<rens>bseeps<pees>brdejs<pejshwfydzcz>bspees<eepe<esps>cqlZj[i\\h^h`ibjckekgii<j[i]i_jakbldlfkhgjkllnlpkrjsiuiwjy<ikkmkojqirhthvixjylz>fnjZjz>cqhZj[k\\l^l`kbjcieigki<j[k]k_jaibhdhfihmjilhnhpirjskukwjy<kkimiojqkrltlvkxjyhz>^vamakbhdgfghhlknlplrksi<akbidhfhhillnmpmrlsisg>brb^bscsc^d^dsese^f^fsgsg^h^hsisi^j^jsksk^l^lsmsm^n^nsoso^p^psqsq^r^rs".split(">").map(s=>[s.charCodeAt(0)-106,s.charCodeAt(1)-106,s.substr(2).split("<").map(s=>{const e=[];for(let p=0;p<s.length;p+=2)e.push(s.substr(p,2).split("").map(s=>s.charCodeAt(0)-106));return e})]);return new class{print(e,p,j=1,h=0,r=1){e.radians();let f=[e.x(),e.y()],o=e.h(),i=f;p.split("").map(p=>{const c=p.charCodeAt(0)-32;if(c<0)f=i=this.rotAdd([0,48*j],i,o);else if(c>96)f=this.rotAdd([16*j,0],i,o);else{const p=s[c],i=p[0]*j,d=p[1]*j;p[2].map(s=>{e.up(),s.map(s=>{e.goto(this.rotAdd([(s[0]-s[1]*h)*j-i,s[1]*j],f,o)),e.down()})}),f=this.rotAdd([(d-i)*r,0],f,o)}})}rotAdd(s,e,p){return[Math.cos(p)*s[0]-Math.sin(p)*s[1]+e[0],Math.cos(p)*s[1]+Math.sin(p)*s[0]+e[1]]}}}