console.clear();
class Point {
constructor(id) {
this.pos = createVector(random(width), random(height));
this.id = id;
this.color = "rgba(255, 255, 255, 0.5)";
}
show() {
fill(this.color);
noStroke();
circle(this.pos.x, this.pos.y, 20);
const idText = this.id.toString();
fill(0);
text(
idText,
this.pos.x - textWidth(idText) / 2,
this.pos.y + textSize() / 2
);
}
constrain() {
if (this.pos.x < 60) {
this.pos.x = 60;
}
if (this.pos.x > width - 60) {
this.pos.x = width - 60;
}
if (this.pos.y < 60) {
this.pos.y = 60;
}
if (this.pos.y > height - 60) {
this.pos.y = height - 60;
}
}
}
function myBezierPoint(a, b, c, d, t) {
const t3 = t * t * t,
t2 = t * t,
f1 = -0.5 * t3 + t2 - 0.5 * t,
f2 = 1.5 * t3 - 2.5 * t2 + 1.0,
f3 = -1.5 * t3 + 2.0 * t2 + 0.5 * t,
f4 = 0.5 * t3 - 0.5 * t2;
return a * f1 + b * f2 + c * f3 + d * f4;
}
function indexMod(i, l) {
if (i < 0) {
return indexMod(l + i, l);
}
if (i >= l) {
return indexMod(i - l, l);
}
return i;
}
function threePointsAngle(center, A, B) {
const base = A.pos.copy().sub(center.pos);
const target = B.pos.copy().sub(center.pos);
const angle = base.angleBetween(target);
return angle;
}
function collideLineLine(A, B, C, D) {
const { x: x1, y: y1 } = A.pos;
const { x: x2, y: y2 } = B.pos;
const { x: x3, y: y3 } = C.pos;
const { x: x4, y: y4 } = D.pos;
// Avoid considering collision if one point is in common
if (A.id === C.id || A.id === D.id || B.id === C.id || B.id === D.id) {
return false;
}
// calculate the distance to intersection point
const uA =
((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) /
((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1));
const uB =
((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) /
((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1));
// if uA and uB are between 0-1, lines are colliding
if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {
return true;
}
return false;
}
class Terrain {
constructor() {
this.nbOfPoints = 9;
this.maxPush = 10;
this.pushCounter = 0;
this.reset();
}
reset() {
this.points = [];
for (let i = 0; i < this.nbOfPoints; i++) {
this.points.push(new Point(i));
this.points[i].constrain();
}
}
pushPoints() {
if (this.pushCounter > this.maxPush) {
this.pushCounter = 0;
return true;
}
this.pushCounter++;
let stable = true;
for (let i = 0; i < this.points.length; i++) {
for (let j = 0; j < this.points.length; j++) {
if (i === j) {
continue;
}
const a = this.points[i];
const b = this.points[j];
const distance = a.pos.copy().sub(b.pos);
if (distance.mag() < 150) {
a.pos.add(distance.copy().setMag(100).rotate(radians(15)));
a.pos.add(createVector(random(20), random(20)));
b.pos.sub(distance.copy().setMag(100).rotate(radians(15)));
a.pos.add(createVector(random(20), random(20)));
a.constrain();
b.constrain();
stable = false;
}
}
}
if (stable) {
this.pushCounter = 0;
}
// Just by safety is some point are too close remove one of them
let toBeRemoved = [];
for (let i = 0; i < this.points.length; i++) {
for (let j = 0; j < this.points.length; j++) {
const A = this.points[i];
const B = this.points[j];
if (A.id !== B.id && A.pos.dist(B.pos) < 40) {
toBeRemoved.push(A.id);
}
}
}
this.points = this.points.filter((p) => !toBeRemoved.includes(p.id));
return stable;
}
getLeftMostPoint() {
let leftMostPoint = this.points[0];
for (const point of this.points) {
if (point.pos.x < leftMostPoint.pos.x) {
leftMostPoint = point;
}
}
return leftMostPoint;
}
getDownMostPoint() {
let downMostPoint = this.points[0];
for (const point of this.points) {
if (point.pos.y > downMostPoint.pos.y) {
downMostPoint = point;
}
}
return downMostPoint;
}
getKNearest(point, points, k) {
const sortedByDistance = [...points]
.filter((p) => p.id !== point.id)
.sort((a, b) => {
return a.pos.dist(point.pos) - b.pos.dist(point.pos);
});
return sortedByDistance.splice(0, k);
}
getConcaveHull() {
// Largely inspired by https://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf
const downMostPoint = this.getDownMostPoint();
downMostPoint.color = "rgba(188, 198, 35, 0.5)";
const hull = [downMostPoint];
let remainingPoints = [...this.points].filter(
(p) => p.id !== downMostPoint.id
);
let guard = 0;
let K = 3;
let k = K;
//while (remainingPoints.length && guard < 10) {
while (
(hull.length < 2 || hull[0].id !== hull[hull.length - 1].id) &&
guard < 40
) {
guard++;
const current = hull[hull.length - 1];
if (hull.length === 4) {
remainingPoints.push(hull[0]);
}
// find the k nearest
const nearest = this.getKNearest(current, remainingPoints, k);
// sort the nearest neighbords by angle
nearest.sort((a, b) => {
const directionA = a.pos.copy().sub(current.pos).rotate(PI);
const directionB = b.pos.copy().sub(current.pos).rotate(PI);
return directionA.heading() - directionB.heading();
});
let placed = false;
let guard1 = 0;
let selected;
while (!placed && nearest.length && guard1 < 10) {
guard1++;
selected = nearest.pop();
if (hull.length < 2) {
placed = true;
continue;
}
let createCollision = false;
for (let i = 0; i < hull.length - 1; i++) {
const A = selected;
const B = hull[hull.length - 1];
const C = hull[i];
const D = hull[i + 1];
if (collideLineLine(A, B, C, D)) {
createCollision = true;
}
}
if (!createCollision) {
placed = true;
}
}
if (!selected) {
k++;
continue;
}
hull.push(selected);
remainingPoints = remainingPoints.filter(
(p) => p.id !== selected.id
);
}
this.concaveHull = hull;
}
getHull() {
// // S is the set of points
// // P will be the set of points which form the convex hull. Final set size is i.
// pointOnHull = leftmost point in S // which is guaranteed to be part of the CH(S)
// i := 0
// repeat
// P[i] := pointOnHull
// endpoint := S[0] // initial endpoint for a candidate edge on the hull
// for j from 0 to |S| do
// // endpoint == pointOnHull is a rare case and can happen only when j == 1 and a better endpoint has not yet been set for the loop
// if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint) then
// endpoint := S[j] // found greater left turn, update endpoint
// i := i + 1
// pointOnHull = endpoint
// until endpoint = P[0] // wrapped around to first hull point
const leftMostPoint = this.getLeftMostPoint();
leftMostPoint.color = "rgba(198, 35, 188, 0.5)";
const S = this.points;
const P = [];
let pointOnHull = leftMostPoint;
let i = 0;
let endpoint;
do {
P[i] = pointOnHull;
endpoint = S[0];
for (let j = 0; j < S.length; j++) {
const Sj = S[j];
const Pi = P[i];
const angle = threePointsAngle(Pi, endpoint, Sj);
if (endpoint.id === pointOnHull.id || angle < 0) {
endpoint = Sj;
}
}
i++;
pointOnHull = endpoint;
} while (endpoint.id !== P[0].id && i < 15);
P.push(P[0]);
this.convexHull = P;
}
generateBezierCurve(points, step) {
const curve = [];
for (let i = 0; i < points.length; i++) {
const a = points[indexMod(i - 1, points.length)];
const b = points[indexMod(i, points.length)];
const c = points[indexMod(i + 1, points.length)];
const d = points[indexMod(i + 2, points.length)];
const curvePoint = new Point(points.length);
(curvePoint.pos.x = myBezierPoint(
a.pos.x,
b.pos.x,
c.pos.x,
d.pos.x,
0.5
)),
(curvePoint.pos.y = myBezierPoint(
a.pos.y,
b.pos.y,
c.pos.y,
d.pos.y,
0.5
));
curve.push(points[indexMod(i)]);
curve.push(curvePoint);
}
if (!step || step === 0) {
curve.push(curve[0]);
return curve;
}
return this.generateBezierCurve(curve, step - 1);
}
getBezierConcaveHull() {
if (!this.concaveHull) {
throw new Error("can't generate bezier curve wihtout concave hull");
}
this.bezierConcaveHull = this.generateBezierCurve(
[...this.concaveHull].slice(0, -1),
3
);
}
getBezierConvexHull() {
if (!this.convexHull) {
throw new Error("can't generate bezier curve wihtout concave hull");
}
this.bezierConvexHull = this.generateBezierCurve(
[...this.convexHull].slice(0, -1),
3
);
}
show() {
for (const p of this.points) {
p.show();
}
/*
if (this.convexHull) {
stroke("rgba(198, 35, 188, 0.5)");
for (let i = 0; i < this.convexHull.length - 1; i++) {
const A = this.convexHull[i].pos;
const B = this.convexHull[i + 1].pos;
line(A.x, A.y, B.x, B.y);
}
}
*/
if (this.bezierConvexHull) {
stroke("rgba(198, 35, 188, 1)");
for (let i = 0; i < this.bezierConvexHull.length - 1; i++) {
const A = this.bezierConvexHull[i].pos;
const B = this.bezierConvexHull[i + 1].pos;
line(A.x, A.y, B.x, B.y);
ellipse(A.x, A.y, 2);
}
}
/*
if (this.concaveHull) {
stroke("rgba(188, 198, 35, 0.5)");
for (let i = 0; i < this.concaveHull.length - 1; i++) {
const A = this.concaveHull[i].pos;
const B = this.concaveHull[i + 1].pos;
line(A.x, A.y, B.x, B.y);
}
}
*/
if (this.bezierConcaveHull) {
stroke("rgba(188, 198, 35, 1)");
for (let i = 0; i < this.bezierConcaveHull.length - 1; i++) {
const A = this.bezierConcaveHull[i].pos;
const B = this.bezierConcaveHull[i + 1].pos;
line(A.x, A.y, B.x, B.y);
ellipse(A.x, A.y, 2);
}
}
}
}
class Track {
constructor(points, trackWidth) {
this.minAngle = radians(90);
const lefts = [];
const rights = [];
for (let i = 0; i < points.length - 1; i++) {
const anchor = points[i].pos;
const mover = points[i + 1].pos;
const left = mover
.copy()
.sub(anchor)
.rotate(PI / 2)
.setMag(20)
.add(anchor);
const right = mover
.copy()
.sub(anchor)
.rotate(-PI / 2)
.setMag(20)
.add(anchor);
//track.push(points[i].pos);
rights.push(right);
lefts.push(left);
}
this.right = [...rights, rights[0]];
this.left = [...lefts, lefts[0]];
this.track = [...points.map((p) => p.pos)];
}
smoothSide(list) {
let toRemove;
let currentMinAngle = radians(180);
for (let i = 1; i < list.length - 2; i++) {
const A = list[i - 1];
const center = list[i];
const B = list[i + 1];
const angle = Math.abs(
threePointsAngle({ pos: center }, { pos: A }, { pos: B })
);
if (angle < currentMinAngle) {
currentMinAngle = angle;
toRemove = i;
}
}
console.log(
currentMinAngle,
degrees(currentMinAngle),
"min",
this.minAngle,
degrees(this.minAngle)
);
if (currentMinAngle < this.minAngle) {
list.splice(toRemove, 1);
return false;
}
return true;
}
smoothTrack() {
let toRemove;
let currentMinAngle = radians(180);
for (let i = 1; i < this.track.length - 2; i++) {
const A = this.track[i - 1];
const center = this.track[i];
const B = this.track[i + 1];
const angle = Math.abs(
threePointsAngle({ pos: center }, { pos: A }, { pos: B })
);
if (angle < currentMinAngle) {
currentMinAngle = angle;
toRemove = i;
}
}
console.log(
currentMinAngle,
degrees(currentMinAngle),
"min",
this.minAngle,
degrees(this.minAngle)
);
//if (currentMinAngle < this.minAngle) {
if (currentMinAngle < radians(100)) {
this.left.splice(toRemove, 1);
this.track.splice(toRemove, 1);
this.right.splice(toRemove, 1);
return false;
}
return true;
}
smooth() {
const doneTrack = this.smoothTrack();
if (!doneTrack) {
return false;
}
const doneRight = this.smoothSide(this.left);
const doneLeft = this.smoothSide(this.right);
return doneRight && doneLeft;
}
show() {
stroke("rgba(19, 58, 216, 1)");
for (let i = 0; i < this.track.length - 1; i++) {
const A = this.track[i];
const B = this.track[i + 1];
line(A.x, A.y, B.x, B.y);
ellipse(A.x, A.y, 2);
}
stroke("green");
for (let i = 0; i < this.right.length - 1; i++) {
const A = this.right[i];
const B = this.right[i + 1];
line(A.x, A.y, B.x, B.y);
ellipse(A.x, A.y, 2);
}
stroke("red");
for (let i = 0; i < this.left.length - 1; i++) {
const A = this.left[i];
const B = this.left[i + 1];
line(A.x, A.y, B.x, B.y);
ellipse(A.x, A.y, 2);
}
}
}
function pushOrReset() {
const stable = terrain.pushPoints();
if (!stable) {
pushOrReset();
} else {
setTimeout(() => {
if (generate === EASY) {
terrain.getHull();
terrain.getBezierConvexHull();
track = new Track(terrain.bezierConvexHull, 10);
} else {
terrain.getConcaveHull();
terrain.getBezierConcaveHull();
track = new Track(terrain.bezierConcaveHull, 10);
}
const isSmooth = track.smooth();
const smoothLoop = setInterval(() => {
console.log("smooth again");
const isSmooth = track.smooth();
console.log("result isSmooth", isSmooth);
if (isSmooth) {
clearInterval(smoothLoop);
setTimeout(() => {
terrain.reset();
pushOrReset();
}, 5000);
}
}, 100);
}, 1000);
}
}
let terrain;
let track;
let select;
const HARD = "HARD";
const EASY = "EASY";
let generate = "HARD";
function setup() {
createCanvas(800, 800);
select = createSelect();
select.position(10, 10);
select.option(HARD);
select.option(EASY);
select.changed(() => {
generate = select.value();
});
terrain = new Terrain();
pushOrReset();
}
function draw() {
background(10);
//terrain.show();
if (track) {
track.show();
}
}
function keyPressed() {
if (keyCode === UP_ARROW) {
terrain.pushPoints();
}
if (keyCode === DOWN_ARROW) {
terrain.reset();
pushOrReset();
}
}
!
