Pacman
The Pacman map as a quick demo of the Outliner utility .
The path is optimized for drawing with a plotter.
Log in to post a comment.
// LL 2021
const precision = 16; /// min=2 max=100 step=1
const thickness = 3; // min=1 max=3 step=1
const offset_x = 14, offset_y = 15.9;
const scale = 6;
Canvas.setpenopacity(1);
const turtle = new Turtle();
const map=[{r:0.5,p:[[-0.5,22.5],[-0.5,19.5],[2.5,19.5]]},{r:0.5,p:[[-0.5,28.5],[-0.5,25.5],[2.5,25.5]]},{r:0.5,p:[[-0.5,10.5],[-0.5,7.5],[2.5,7.5]]},{r:0.5,p:[[-0.5,4.5],[-0.5,1.5]]},{r:0.25,p:[[-.5,1],[13.2,1],[13.2,10],[8.2,10],[8.2,14],[13.2,14]]},{r:0.25,p:[[-.5,31],[13.2,31],[13.2,20],[8.2,20],[8.2,16],[13.2,16]]},{r:0.5,p:[[2.5,22.5],[5.5,22.5]]},{r:0.5,p:[[5.5,16.5],[5.5,19.5]]},{r:0.5,p:[[5.5,25.5],[5.5,28.5],[2.5,28.5],[10.5,28.5]]},{r:0.5,p:[[11.5,25.5],[12.8,25.5]]},{r:0.5,p:[[8.5,25.5],[8.5,22.5],[10.5,22.5]]},{r:0.5,p:[[5.5,7.5],[5.5,13.5],[5.5,10.5],[2.5,10.5]]},{r:0.5,p:[[8.5,7.5],[10.5,7.5]]},{r:0.2,p:[[1.,13.5],[3,13.5],[3,17],[-0.5,17]]},{r:0.501,p:[[2.5,3.5],[5.5,3.5],[5.5,4.5],[2.5,4.5],[2.5,3.5]]},{r:0.501,p:[[8.5,3.5],[10.5,3.5],[10.5,4.5],[8.5,4.5],[8.5,3.5]]}];
const food=[[[1,2],[12,2]],[[1,3],[1,5]],[[7,3],[7,5]],[[12,3]],[[12,5]],[[12,22]],[[1,22],[1,23]],[[5,15],[7,15]],[[0,6],[12,6]],[[4,7],[4,9]],[[1,9],[3,9]],[[1,10],[1,11]],[[0,12],[4,12]],[[7,7],[7,27]],[[12,7],[12,9]],[[8,9],[11,9]],[[4,13],[4,20]],[[1,21],[6,21]],[[8,21],[12,21]],[[10,24],[12,24]],[[8,27],[12,27]],[[12,28],[12,29]],[[0,30],[12,30]],[[0,24],[6,24]],[[4,25],[4,27]],[[1,27],[3,27]],[[1,28],[1,29]],[[10,25],[10,27]],[[0,18],[3,18]],];
const powerup=[[12,4],[12,23]];
var outliner;
console.clear();
function transform(point, dir) {
return [ (14 + dir * (point[0]+0.5) - offset_x) * scale, (point[1] - offset_y) * scale];
}
function walk(i, t) {
if (i==0) {
outliner = new Outliner(turtle, precision, thickness);
map.forEach(section => {
for (var dir=-1; dir<=1; dir+=2) {
for (var j=0; j<section.p.length-1; j++) {
const point1 = transform(section.p[j], dir);
const point2 = transform(section.p[j+1], dir);
const p1 = outliner.addPoint(point1, section.r*scale);
const p2 = outliner.addPoint(point2, section.r*scale);
outliner.addSegment(p1, p2);
}
}
});
food.forEach(group => {
for (var dir=-1; dir<=1; dir+=2) {
var x = group[0][0], y = group[0][1];
while (y <= group[group.length-1][1]) {
while (x <= group[group.length-1][0]) {
const point = transform([x, y], dir);
outliner.addPoint(point, 0.15*scale);
x++;
}
y++;
x = group[0][0];
}
}
});
powerup.forEach(p => {
for (var dir=-1; dir<=1; dir+=2) {
const point = transform(p, dir);
outliner.addPoint(point, 0.4*scale);
}
});
outliner.build();
}
// 5. Draw a little bit of the outlines in a loop until there is no more to draw
if (!outliner.drawNext()) return false;
return true;
}
/////////////////////////////////////////////////////////////////
// Outliner utility code - Created by Lionel Lemarie 2021
// https://turtletoy.net/turtle/a206296e80
/////////////////////////////////////////////////////////////////
function Outliner(tt_=turtle, precision_=20, thickness_=1) {
const timers = {}
const timer_list = [];
function startTimer(name) {
const now = performance.now();
if (!(name in timers)) {
timers[name] = [1, -now];
timer_list.push(name);
} else {
timers[name][0]++;
timers[name][1]-=now;
}
}
function stopTimer(name) {
const now = performance.now();
if (name in timers) {
timers[name][1]+=now;
}
}
function printTimers() {
function numberWithCommas(x) { return x.toString().replace(/\B(?=(\d{3})+(?!\d))/g, ","); }
timer_list.forEach(name => {
var elapsed = timers[name][1], count = timers[name][0], unit = "ms";
if (elapsed > 1000) { unit = "sec"; elapsed /= 1000; if (elapsed > 60) { unit = "min"; elapsed /= 60; } }
console.log(`Outliner: ${name} - calls: ${numberWithCommas(count)} - total: ${elapsed.toFixed(1)} ${unit}`);
});
}
startTimer("Total time");
const lines_to_draw = [];
const figure_points = [];
const figure_segments = [];
const epsilon = 0.0001;
function createPointOutline(point) {
const step = 1 / precision_;
for (var a=0; a<1; a+=step) {
const x0 = point[0] + point[2] * Math.cos(a * Math.PI * 2);
const y0 = point[1] + point[2] * Math.sin(a * Math.PI * 2);
const x1 = point[0] + point[2] * Math.cos((a+step) * Math.PI * 2);
const y1 = point[1] + point[2] * Math.sin((a+step) * Math.PI * 2);
addLine([ [x0, y0], [x1, y1] ]);
}
}
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; }
function createSegmentOutline(segment) {
const l = Math.hypot(segment[1][0]-segment[0][0], segment[1][1]-segment[0][1]);
if (l < epsilon) return [];
var px11 = (segment[0][0] + segment[0][2] * rotX(segment[0][0] - segment[1][0], segment[0][1] - segment[1][1], -0.5 * Math.PI) / l);
var py11 = (segment[0][1] + segment[0][2] * rotY(segment[0][0] - segment[1][0], segment[0][1] - segment[1][1], -0.5 * Math.PI) / l);
var px12 = (segment[0][0] + segment[0][2] * rotX(segment[0][0] - segment[1][0], segment[0][1] - segment[1][1], 0.5 * Math.PI) / l);
var py12 = (segment[0][1] + segment[0][2] * rotY(segment[0][0] - segment[1][0], segment[0][1] - segment[1][1], 0.5 * Math.PI) / l);
var px21 = (segment[1][0] + segment[1][2] * rotX(segment[1][0] - segment[0][0], segment[1][1] - segment[0][1], -0.5 * Math.PI) / l);
var py21 = (segment[1][1] + segment[1][2] * rotY(segment[1][0] - segment[0][0], segment[1][1] - segment[0][1], -0.5 * Math.PI) / l);
var px22 = (segment[1][0] + segment[1][2] * rotX(segment[1][0] - segment[0][0], segment[1][1] - segment[0][1], 0.5 * Math.PI) / l);
var py22 = (segment[1][1] + segment[1][2] * rotY(segment[1][0] - segment[0][0], segment[1][1] - segment[0][1], 0.5 * Math.PI) / l);
addSubDivLine([[px11, py11], [px22, py22]]);
addSubDivLine([[px12, py12], [px21, py21]]);
}
function addSubDivLine(line) {
const step = 1 / precision_;
for (t=0; t<(1-epsilon); t+=step) {
const x1 = line[0][0] + (line[1][0]-line[0][0]) * t;
const y1 = line[0][1] + (line[1][1]-line[0][1]) * t;
const x2 = line[0][0] + (line[1][0]-line[0][0]) * (t+step);
const y2 = line[0][1] + (line[1][1]-line[0][1]) * (t+step);
addLine([[x1, y1], [x2, y2]]);
}
}
const binSize = 1;
const bins = {};
function point_key(point) {
return Math.floor(point[1]/binSize) * 100000 + Math.floor(point[0]/binSize);
}
function getBinListForPoint(point) {
var bin_list = [];
const key0 = point_key(point);
if (key0 in bins) bin_list.push(bins[key0]);
var found_good = false;
bin_list.forEach(bin => bin.forEach(index => found_good |= !inBlacklist(index)));
if (!found_good) {
bin_list = [];
const search_radius = 2;
for (var y=-search_radius; y<=search_radius+0.1; y+=1) {
for (var x=-search_radius; x<=search_radius+0.1; x+=1) {
if (x==0 && y==0) continue;
const key = point_key([point[0]+x*binSize, point[1]+y*binSize]);
if (key in bins) bin_list.push(bins[key]);
}
}
}
return bin_list;
}
function getBinListForLine(line) {
const bin_list = [];
const key0 = point_key(line[0]);
if (key0 in bins) bin_list.push(bins[key0]);
const key1 = point_key(line[1]);
if (key1 in bins) bin_list.push(bins[key1]);
return bin_list;
}
function addToBin(line, index) {
for (var i=0; i<2; i++) {
const key = point_key(line[i]);
if (!(key in bins)) bins[key] = [];
bins[key].push(index);
}
}
function checkOverlap(line1, line2) {
const distance00 = distance2(line1[0], line2[0]);
const distance01 = distance2(line1[0], line2[1]);
const distance10 = distance2(line1[1], line2[0]);
const distance11 = distance2(line1[1], line2[1]);
const value = ! ( ((distance00 > epsilon) || (distance11 > epsilon)) && ((distance01 > epsilon) || (distance10 > epsilon)) );
return value;
}
function addLine(line) {
startTimer("addLine");
var ok_to_add = true;
startTimer(`addLine - figure_points ${figure_points.length}`);
for (var i=0; i<figure_points.length && ok_to_add; i++) {
const dist0 = distance2(line[0], figure_points[i]) * (1+epsilon);
const dist1 = distance2(line[1], figure_points[i]) * (1+epsilon);
ok_to_add &= dist0 > (figure_points[i][2]**2);
ok_to_add &= dist1 > (figure_points[i][2]**2);
}
stopTimer(`addLine - figure_points ${figure_points.length}`);
startTimer(`addLine - figure_segments ${figure_segments.length}`);
for (var i=0; i<figure_segments.length && ok_to_add; i++) {
const segment = [0,1].map(si => figure_points[figure_segments[i][si]]);
ok_to_add &= !pointInSegment(line[0], segment) && !pointInSegment(line[1], segment);
}
stopTimer(`addLine - figure_segments ${figure_segments.length}`);
getBinListForLine(line).forEach(bin => {
for (var i=0; i<bin.length && ok_to_add; i++) {
ok_to_add &= !checkOverlap(line, lines_to_draw[bin[i]]);
}
});
if (ok_to_add) {
addToBin(line, lines_to_draw.length);
lines_to_draw.push(line);
}
stopTimer("addLine");
}
function distance2(point1, point2) {
const dist2 = (point1[0]-point2[0]) * (point1[0]-point2[0]) + (point1[1]-point2[1]) * (point1[1]-point2[1]);
return dist2;
}
function distanceToSegmentFactor(point, segment) {
var l2 = distance2(segment[0], segment[1]);
if (l2 < epsilon) return 0;
var t = ((point[0] - segment[0][0]) * (segment[1][0] - segment[0][0]) + (point[1] - segment[0][1]) * (segment[1][1] - segment[0][1])) / l2;
t = Math.max(0, Math.min(1, t));
return t;
}
function distance2ToSegmentWithFactor(point, segment, t) {
const dist2 = distance2(point, [segment[0][0] + t * (segment[1][0] - segment[0][0]), segment[0][1] + t * (segment[1][1] - segment[0][1])]);
return dist2;
}
function pointInSegment(point, segment) {
const t = distanceToSegmentFactor(point, segment);
const radius = segment[0][2] * (1-t) + segment[1][2] * t;
const inside = distance2ToSegmentWithFactor(point, segment, t) < radius*radius*(1-epsilon);
return inside;
}
function fillGaps() {
const dangling_points = [];
for (var i1=0; i1<lines_to_draw.length; i1++) {
for (var j1=0; j1<2; j1++) {
var found_close = false;
getBinListForPoint(lines_to_draw[i1][j1]).forEach(bin => {
var closest_point = [];
var closest_distance = NaN;
for (var i2=0; i2<bin.length; i2++) {
if (checkOverlap(lines_to_draw[i1], lines_to_draw[bin[i2]])) continue;
for (var j2=0; j2<2; j2++) {
const dist2 = distance2(lines_to_draw[i1][j1], lines_to_draw[bin[i2]][j2]);
if (isNaN(closest_distance) || dist2 < closest_distance) {
closest_distance = dist2;
closest_point = lines_to_draw[bin[i2]][j2];
}
}
}
if (!isNaN(closest_distance) && closest_distance < epsilon) {
found_close = true;
}
});
if (!found_close) dangling_points.push(lines_to_draw[i1][j1]);
}
}
const extra_lines = [];
while (dangling_points.length > 1) {
const point1 = dangling_points.shift();
var closest_index = -1;
var closest_distance = NaN;
for (var i=0; i<dangling_points.length; i++) {
const dist2 = distance2(dangling_points[i], point1);
if (closest_index < 0 || dist2 < closest_distance) {
closest_distance = dist2;
closest_index = i;
}
}
if (closest_index >= 0 && closest_distance < 30) {
const point2 = dangling_points[closest_index];
dangling_points.splice(closest_index, 1);
extra_lines.push([point1, point2]);
}
}
extra_lines.forEach(l => { addToBin(l, lines_to_draw.length); lines_to_draw.push(l); });
}
const blacklist = [];
var blacklist_count = 0;
function inBlacklist(index) {
while (blacklist.length <= index) blacklist.push(false);
const value = blacklist[index];
return value;
}
function addToBlacklist(index) {
while (blacklist.length <= index) blacklist.push(false);
blacklist[index] = true;
blacklist_count++;
}
function drawNextLine() {
startTimer("drawNextLine");
if (lines_to_draw.length == 0) return false;
const position = tt_.position();
var closest_distance = 1000000;
var closest_line_index = -1;
var closest_point_index = -1;
startTimer("drawNextLine - bins");
getBinListForPoint(position).forEach(bin => {
for (var i=0; i<bin.length; i++) {
if (inBlacklist(bin[i])) continue;
for (var j=0; j<2; j++) {
const dist2 = distance2(position, lines_to_draw[bin[i]][j]);
if (closest_line_index < 0 || dist2 < closest_distance) {
closest_distance = dist2;
closest_line_index = bin[i];
closest_point_index = j;
}
}
}
});
stopTimer("drawNextLine - bins");
if (closest_line_index < 0) {
startTimer("drawNextLine - all");
for (var i=0; i<lines_to_draw.length && closest_distance > 1; i++) {
if (inBlacklist(i)) continue;
for (var j=0; j<2; j++) {
const dist2 = distance2(position, lines_to_draw[i][j]);
if (closest_line_index < 0 || dist2 < closest_distance) {
closest_distance = dist2;
closest_line_index = i;
closest_point_index = j;
}
}
}
stopTimer("drawNextLine - all");
}
if (closest_line_index < 0) {
startTimer("drawNextLine - last restort");
closest_line_index = 0;
closest_point_index = 0;
closest_distance = 1;
while (inBlacklist(closest_line_index)) closest_line_index++;
stopTimer("drawNextLine - last restort");
}
if (closest_distance > 0.21) {
tt_.jump(lines_to_draw[closest_line_index][closest_point_index]);
}
tt_.down();
tt_.goto(lines_to_draw[closest_line_index][1-closest_point_index]);
addToBlacklist(closest_line_index);
stopTimer("drawNextLine");
const more_to_do = lines_to_draw.length - blacklist_count > 0;
if (!more_to_do) {
stopTimer("Total time");
printTimers();
}
return more_to_do;
}
function applyThickness() {
const original_count = lines_to_draw.length;
const offset = 0.2;
for (var ty=0; ty<thickness; ty++) {
for (var tx=0; tx<thickness; tx++) {
if (tx==0 && ty==0) continue;
for (var i=0; i<original_count; i++) {
const line = lines_to_draw[i].map(p => [p[0]-tx*offset, p[1]-ty*offset, p[2]]);
addToBin(line, lines_to_draw.length);
lines_to_draw.push(line);
}
}
}
}
function buildOutline() {
startTimer("buildOutline");
for (var i=0; i<figure_points.length; i++) {
createPointOutline(figure_points[i]);
}
for (var i=0; i<figure_segments.length; i++) {
const segment = [0,1].map(si => figure_points[figure_segments[i][si]]);
createSegmentOutline(segment);
}
fillGaps();
applyThickness();
stopTimer("buildOutline");
}
function newPoint(point, radius) {
figure_points.push([point[0], point[1], radius]);
return figure_points.length - 1;
}
function newSegment(index1, index2) {
figure_segments.push([index1, index2]);
return figure_segments.length - 1;
}
return {
addPoint: (point, radius) => newPoint(point, radius),
addSegment: (index1, index2) => newSegment(index1, index2),
addPoints: (point_list) => point_list.forEach(p => newPoint(p[0], p[1])),
addSegments: (segment_list) => segment_list.forEach(s => newSegment(s[0], s[1])),
build: () => buildOutline(),
drawNext: () => drawNextLine(),
unsortedLines: lines_to_draw
};
}