// Distance to path. Created by Reinder Nijhoff 2023 - @reindernijhoff
// The MIT License
//
// https://turtletoy.net/turtle/b8caf5b1f5
//
const pathInput = `M100,-80 C-120,-80 -120,0 0,0 C120,0 120,80 -100,80`; // type=path, Click here to redraw the path

const grid = 11; // min=5, max=50, step=1
const drawmode = 2;  // min=0, max=2, step=1, (Gradient, Curl, Flow field)
const radius = 1.3; // min=0.1, max=5, step=0.01
const maxPathLength = 50;  // min=1, max=100, step=0.1
const maxTries = 1000;
const precision = .75;
const eps = .01;

const path = Path(pathInput);
const turtle = new Turtle();
const pGrid  = new PoissonDiscGrid(radius);

function walk(i) {
    if (drawmode <= 1) {
        const x = i % grid;
        const y = i / grid | 0;
        
        const p = [(x+1) * 200 / (grid+1) - 100, (y+1) * 200 / (grid+1) - 100];
        
        const d = path.distance(p);
        const dx = (path.distance([p[0]+eps, p[1]]) - d)/eps;
        const dy = (path.distance([p[0], p[1]+eps]) - d)/eps;
        
        if (drawmode == 0) {
            drawArrow(p, [dx, dy]);
        } else {
            drawArrow(p, [-dy, dx]);
        }
        return i < grid * grid - 1;
    } else {
        const p = turtle.pos();

        const curl = flowField(p);
        const dest = [p[0]+curl[0], p[1]+curl[1]];
        
        if (turtle.traveled < maxPathLength && Math.abs(dest[0]) < 110 && Math.abs(dest[1]) < 110 && pGrid.insert(dest)) {
            turtle.goto(dest);
            turtle.traveled += Math.hypot(curl[0], curl[1]);
        } else {
            turtle.traveled = 0;
            let r, i = 0;
            do { 
                r =[Math.random()*200-100, Math.random()*200-100];
                i ++;
            } while(!pGrid.insert(r) && i < maxTries);
            if (i >= maxTries) {
                return false;
            }
            turtle.jump(r);
        }
        return true;
    }
}

function drawArrow(p, dir) {
    dir = scale(dir, 100/grid);
    p   = add(p, scale(dir, -0.5));
    const end = add(p, dir);
    const hw  = lerp(p, end, .6);
    
    turtle.jump(p);
    turtle.goto(end);
    turtle.goto(add(hw, scale([dir[1], -dir[0]], .2)));
    turtle.jump(end);
    turtle.goto(add(hw, scale([-dir[1], dir[0]], .2)));
}

function flowField(p) {
    const [x, y] = p;
    
    const dx = (path.distance([x, y + eps]) - path.distance([x, y - eps]))/(2 * eps);
    const dy = (path.distance([x + eps, y]) - path.distance([x - eps, y]))/(2 * eps);
    
    const l = Math.hypot(dx, dy) / radius * .99;
    return [dx / l, -dy / l];	
}

function scale(a,b) { return [a[0]*b,a[1]*b]; }
function add(a,b) { return [a[0]+b[0],a[1]+b[1]]; }
function lerp(a,b,t) { return [a[0]*(1-t)+b[0]*t,a[1]*(1-t)+b[1]*t]; }

////////////////////////////////////////////////////////////////
// Poisson-Disc utility code. Created by Reinder Nijhoff 2019
// https://turtletoy.net/turtle/b5510898dc
////////////////////////////////////////////////////////////////
function PoissonDiscGrid(radius) {
    class PoissonDiscGrid {
        constructor(radius) {
            this.cellSize = 1/Math.sqrt(2)/radius;
            this.radius2 = radius*radius;
            this.cells = [];
        }
        insert(p) {
            const x = p[0]*this.cellSize|0, y=p[1]*this.cellSize|0;
            for (let xi = x-1; xi<=x+1; xi++) {
                for (let yi = y-1; yi<=y+1; yi++) {
                    const ps = this.cell(xi,yi);
                    for (let i=0; i<ps.length; i++) {
                        if ((ps[i][0]-p[0])**2 + (ps[i][1]-p[1])**2 < this.radius2) {
                            return false;
                        }
                    }
                }       
            }
            this.cell(x, y).push(p);
            return true;
        }
        cell(x,y) {
            const c = this.cells;
            return (c[x]?c[x]:c[x]=[])[y]?c[x][y]:c[x][y]=[];
        }
    }
    return new PoissonDiscGrid(radius);
}

////////////////////////////////////////////////////////////////
// Modified path utility code. Created by Reinder Nijhoff 2023
//
// Added a distance method
//
// Parses a single SVG path (only M, C and L statements are
// supported). The p-method will return
// [...position, ...derivative] for a normalized point t.
//
// https://turtletoy.net/turtle/46adb0ad70
////////////////////////////////////////////////////////////////
function Path(svg) {
    function lenSquare(a) { return a[0]**2 + a[1]**2; }
    function dot(a, b) { return a[0]*b[0]+a[1]*b[1]; }
    function distSegmentSquare(p, a, b ) {
    	const pa = [p[0]-a[0], p[1]-a[1]], ba = [b[0]-a[0], b[1]-a[1]];
	    const h = Math.max(0, Math.min(1, dot(pa,ba)/dot(ba,ba)));
	    return lenSquare( [pa[0] - ba[0]*h, pa[1] - ba[1]*h] );
    }
    
    class MoveTo {
        constructor(p) { this.p0 = p; }
        p(t, s) { return [...this.p0, 1, 0]; }
        length() { return 0; }
        distSquare(p, res) { return lenSquare([p[0]-this.p0[0], p[1]-this.p0[1]]); }
    }
    class LineTo {
        constructor(p0, p1) { this.p0 = p0, this.p1 = p1; }
        p(t, s = 1) {
            const nt = 1 - t, p0 = this.p0, p1 = this.p1;
            return [ 
                nt*p0[0] + t*p1[0],
                nt*p0[1] + t*p1[1],
                (p1[0] - p0[0]) * s,
                (p1[1] - p0[1]) * s,
            ];
        }
        length() { 
            const p0 = this.p0, p1 = this.p1;
            return Math.hypot(p0[0]-p1[0], p0[1]-p1[1]);
        }
        distSquare(p, res) {
            return distSegmentSquare(p, this.p0, this.p1);
        }
    }
    class BezierTo {
        constructor(p0, c0, c1, p1) { this.p0 = p0, this.c0 = c0, this.c1 = c1, this.p1 = p1; }
        p(t, s = 1) {
            const nt = 1 - t, p0 = this.p0, c0 = this.c0, c1 = this.c1, p1 = this.p1;
            return [ 
                nt*nt*nt*p0[0] + 3*t*nt*nt*c0[0] + 3*t*t*nt*c1[0] + t*t*t*p1[0],
                nt*nt*nt*p0[1] + 3*t*nt*nt*c0[1] + 3*t*t*nt*c1[1] + t*t*t*p1[1],
                (3*nt*nt*(c0[0]-p0[0]) + 6*t*nt*(c1[0]-c0[0]) + 3*t*t*(p1[0]-c1[0])) * s,
                (3*nt*nt*(c0[1]-p0[1]) + 6*t*nt*(c1[1]-c0[1]) + 3*t*t*(p1[1]-c1[1])) * s,
            ];
        }
        length() {
            return this._length || (
                this._length = Array.from({length:25}, (x, i) => this.p(i/25)).reduce( 
                    (a,c,i,v) => i > 0 ? a + Math.hypot(c[0]-v[i-1][0], c[1]-v[i-1][1]) : a, 0));
        }
        distSquare(p, res) {
            // super slow, probably better to use an analytical solution if exists
            const segments = Math.max(1, this.length()/res | 0);
            const p0 = this.p0, c0 = this.c0, c1 = this.c1, p1 = this.p1;
            
            let a = [...p0];
            let dist = 1e10;
            
            for (let i=1; i<=segments; i++) {
                const t = i/segments, nt = 1 - t;
                const b = [
                    nt*nt*nt*p0[0] + 3*t*nt*nt*c0[0] + 3*t*t*nt*c1[0] + t*t*t*p1[0],
                    nt*nt*nt*p0[1] + 3*t*nt*nt*c0[1] + 3*t*t*nt*c1[1] + t*t*t*p1[1]
                ];
                dist = Math.min(dist, distSegmentSquare(p, a, b));
                a = [...b];
            }
            return dist;
        }
    }
    class Path {
        constructor(svg) {
            this.segments = [];
            this.parsePath(svg);
        }
        parsePath(svg) {
            const t = svg.match(/([0-9.-]+|[MLC])/g);
            for (let s, i=0; i<t.length;) {
                switch (t[i++]) {
                    case 'M': this.add(new MoveTo(s=[t[i++],t[i++]]));
                              break;
                    case 'L': this.add(new LineTo(s, s=[t[i++],t[i++]]));
                              break;
                    case 'C': this.add(new BezierTo(s, [t[i++],t[i++]], [t[i++],t[i++]], s=[t[i++],t[i++]]));
                              break;
                    default:  i++;
                }
            }
        }
        add(segment) {
            this.segments.push(segment);
            this._length = 0;
        }
        length() {
            return this._length || (this._length = this.segments.reduce((a,c) => a + c.length(), 0));
        }
        p(t) {
            t = Math.max(Math.min(t, 1), 0) * this.length();
            for (let l=0, i=0, sl=0; i<this.segments.length; i++, l+=sl) {
                sl = this.segments[i].length();
                if (t > l && t <= l + sl) {
                    return this.segments[i].p((t-l)/sl, sl/this.length());
                }
            }
            return this.segments[Math.min(1, this.segments.length-1)].p(0);
        }
        distance(p, res = 3) {
            return Math.sqrt(this.segments.reduce((a,c) => Math.min(a, c.distSquare(p, res)), 1e10));
        }
    }
    return new Path(svg);
}