主攻前文吴烜：JavaScript实现ZLOGO: 界面改进与速度可调的几个性能问题
在线演示: 圈3
源码仍在: program-in-chinese/quan3
之前是在绘制过程中计算每帧需要绘制的线段, 在尝试改进的过程中很快发现问题太多且不易测试. 接着在某早晨"醒悟"到应该而且可以在绘制前计算好每一帧的步进路径表. 不仅可以避免绘制卡顿问题, 还便于测试(因为是纯JS实现, 不需夹杂DOM操作). 于是通过如下递归代码实现了截取指定位置的路径表:
// 返回{截取部分: 路径表, 剩余部分: 路径表}
// 如果 开始位置 >= 终止位置, 返回{[], 所有}
function 截取路径表(路径表, 开始位置, 终止位置) {
if (开始位置 >= 终止位置) {
return {截取部分: [], 剩余部分: 路径表};
}
if (路径表.length == 0) {
return {截取部分: [], 剩余部分: []};
} else if (路径表.length == 1) {
return 截取路径(路径表[0], 开始位置, 终止位置);
} else {
var 段 = 路径表[0];
var 长度 = 段.长度;
if (开始位置 >= 长度) {
路径表.shift();
return 截取路径表(路径表, 开始位置 - 长度, 终止位置 - 长度);
} else if (开始位置 < 长度 && 终止位置 < 长度) {
var 前段 = 截取路径(路径表[0], 开始位置, 终止位置);
路径表.shift();
return {截取部分: 前段.截取部分, 剩余部分: 前段.剩余部分.concat(路径表)};
} else {
var 前段 = 截取路径(路径表[0], 开始位置, 长度);
路径表.shift();
var 后段 = 截取路径表(路径表, 0, 终止位置 - 长度);
return {截取部分: 前段.截取部分.concat(后段.截取部分), 剩余部分: 后段.剩余部分};
}
}
}原本为去掉路径表第一项, 使用了slice(), 测试时发现耗时接近O(n^3). 导致点击"运行"后的运算耗时在复杂时(比如>10000线段的图形)太长(停顿超过1秒)难以接受. 改为shift()后, 粗测不超过O(n^2), 暂未深入研究.
这里是获取每一帧的路径表(每帧前进的长度等于"速度"):
function 按步进拆分路径表(路径表, 速度) {
var 所有段 = [];
while (路径表.length > 0) {
var 拆分路径 = 截取路径表(路径表, 0, 速度);
所有段.push(拆分路径.截取部分);
路径表 = 拆分路径.剩余部分;
}
return 所有段;
}感觉已经达到可以让用户玩玩的程度. 接下来视反馈决定改进方向.
2019-01-23
