深度遍历迷宫用html5 canvas来得到遍历动画(希望可以兼容不支持async, await, Promise特性的浏览器)
来源：5-5 迷宫问题与回溯法
甲骨文_0001
2017-09-27
<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title></title>
<style type="text/css">
body{margin:0;overflow:hidden;}
</style>
</head>
<body>
<canvas id="canvas"></canvas>
<script type="text/javascript">
let canvas = document.getElementById('canvas');
let gd = canvas.getContext('2d');
canvas.width = window.innerWidth;
canvas.height = window.innerHeight;
let dirs = [ [0, -1], [1, 0], [0, 1], [-1, 0] ];
function ajax(){
return new Promise(resolve=>{
let xhr = new XMLHttpRequest();
xhr.open('GET', './map.txt', true); // 本文件是map.html, 在它身边要map.txt，就要项目里的地图数据文件...
xhr.onload = function(){
let str = xhr.responseText;
let arr = str.split(/\r\n|\r/);
resolve(arr);
};
xhr.send();
});
}
ajax()
.then( arr=>{
let rowcol = arr.shift();
let row = rowcol.trim().split(/\s+/)[0];
let col = rowcol.trim().split(/\s+/)[1];
let map = [];
let visited = [];
let path = [];
let entranceR = 1, entranceC = 0, exitR = 99, exitC = 100;
for( let r = 0; r < row; r ++ ){
map[r] = [];
visited[r] = [];
path[r] = [];
for( let c = 0; c < col; c ++ ){
if( arr[r][c] == '#' ){
map[r][c] = 1;
}else{
map[r][c] = 0;
}
visited[r][c] = false;
path[r][c] = false;
}
} // for r
draw();
go(entranceR, entranceC).then( data=>{
draw();
} );
// 通过Async函数配合Await来模拟Thread.sleep()
async function go(r, c){
if( r == exitR && c == exitC ){
return true;
}
visited[r][c] = true;
path[r][c] = true;
await timeout();
draw();
for( let i = 0; i < dirs.length; i ++ ){
let cc = c + dirs[i][0], rr = r + dirs[i][1];
if( inRange( rr, cc ) && (map[rr][cc] == 0) && !visited[rr][cc] ){
if(await go(rr, cc)){
return true;
}
}
}// for i
path[r][c] = false;
await timeout();
draw();
return false;
}
function timeout(){
return new Promise( resolve=>{
setTimeout( ()=>{
resolve();
}, 20 );
} );
}
function inRange(r, c){
if( r >= 0 && r < row && c >= 0 && c < col ){
return true;
}
return false;
}
function draw(){
canvas.width = canvas.width;
let size = 10;
let scale = canvas.height / ( size * row );
let offsetX = (canvas.width - col * size) / 2;
gd.translate( offsetX, 0 );
gd.scale(scale, scale);
for( let r = 0; r < row; r ++ ){
for( let c = 0; c < col; c ++ ){
if( map[r][c] == 1 ){
gd.fillStyle = 'lightblue';
}else{
gd.fillStyle = 'white';
}
if( path[r][c] ){
gd.fillStyle = 'yellow';
}
gd.fillRect( c * size, r * size, size, size );
}
}
}
} );
</script>
</body>
</html>
///// ?: 波波老师，如果不通过async,await来实现遍历绘制动画，仍然通过最原生的javascript来实现，能不能给我们一个参考的实现方式(非常想知道~~~~)，谢谢你>_<
1回答
-
liuyubobobo
2017-09-27
如果是H5的方式使用递归确实不方便必须改成非递归。总体和之前向你提及的排序算法可视化一样。在每一帧执行的动作都是
修改数据() 渲染数据()
其中修改数据部分就是运行算法的一部分。这里如果要展现算法的内部动画过程我们就需要把算法本身的执行过程拆解开。在修改数据的时候大体是这样的
function 修改数据(): 读取当前算法执行状态 根据当前算法执行状态继续执行一步 // 真正的修改数据 保存当前算法执行状态留给下一次使用
这里的关键就是我们需要把算法的执行过程封装起来可以保存和读取。在执行算法的时候我们是根据自己封装的算法状态继续进行算法的。
举个简单的例子对于一个遍历一次寻找最大值的算法假设每次遍历到一个元素都要显示一下。我们包装的算法结构就要包括
所有元素 data; 元素个数 N 当前找到的最大值 tempMax 当前找到的最大值索引 tempMaxIndex 当前搜索的索引i
我们每次只需要看一下i+1所在位置相应的更新tempMax tempMaxIndex和i就好了。在这种体系下算法的执行过程不再有for循环其实for循环影藏在了时间的流逝中。我们只需要保存好算法的执行过程在每一个tick做该做的事情就好了。
当然这个问题比较简单对于更复杂的算法希望你能理解这个思路自己想一想怎么封装这个“算法结构”
这样做的缺点是整个算法表达发生了很大的改变。因为这个课程本身还是重视算法本身的表达的根本上还是讲解算法的课程不是产品化算法动画的课程所以我强调的重点还是的算法运行思路。如果你能将每个算法的运行都转换成我上面描述的方式相信你是真正的理解了这些算法已经可以将这些算法的表达玩弄于鼓掌之中了
122017-09-27
相似问题