|
/* 方格数组，高9，宽12。数字0代表空缺位置，其他数字代表 每种图像块，同数字代表同种图像块，规定头尾数组所有元 素只能为0，各数组首尾元素只能为0，以构成一个矩形环绕 空位。用表达式map_ary[0~9][0~12]，可以访问这个矩阵的 所有元素。 */ /* 《连连看游戏核心算法》 尊重原创，引用请注明出处 欧阳赟 于2005年11月14日 E-Mail:ouyang.em@163.com 华东交大软件学院03届8班 */ var map_ary:Array = Array(); //// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2]; map_ary[0] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; map_ary[1] = [0, 1, 3, 4, 7, 7, 8, 9, 1, 6, 6, 2, 0]; map_ary[2] = [0, 3, 5, 6, 8, 8, 9, 2, 5, 7, 0, 7, 0]; map_ary[3] = [0, 4, 2, 6, 7, 5, 4, 3, 0, 0, 0, 2, 0]; map_ary[4] = [0, 7, 5, 9, 3, 8, 0, 8, 0, 5, 4, 5, 0]; map_ary[5] = [0, 5, 3, 4, 0, 0, 7, 5, 4, 2, 4, 2, 0]; map_ary[6] = [0, 1, 0, 3, 6, 0, 0, 6, 2, 4, 5, 6, 0]; map_ary[7] = [0, 6, 0, 0, 0, 7, 0, 4, 3, 8, 9, 4, 0]; map_ary[8] = [0, 2, 5, 6, 7, 4, 3, 9, 7, 9, 8, 1, 0]; map_ary[9] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; /* 排序方法函数，用于Array.sort()方法的调用。编写方法是 function 函数名(第一个元素，第二个元素):Number{如果第一个元素和第二个元素不换位置则返回-1;否则返回1;如果相等就返回0} 使用：数组名.sort(函数名); 下面的这个函数把数组元素的长度作为排序的依据，a.length大于b.length则换位。从而按照此方法排序后的数组是以元素长度升序排列的。 但首先必须确认从数组中取出的的元素具有.length属性，即元素要属于Array或者String,所以被排序的数组是一个嵌套数组。 因为路径集在算法构思时被定义为一个嵌套数组，它的元素是一条条路径，而路径由一个个点组成，一个点由两个坐标组成。 如： paths=[[[1,1],[1,2],[1,3]],[[2,1],[2,2]]] paths.length的值为2,即包含两条路径 paths[0].length的值为3，即第一条路径的长度是3，也即第一条路径包含3个点[1,1],[1,2],[1,3]。 如果要访问到最低层元素可以用类似表达式：paths[0][0][0] 值为1，意为第一条路径的第一个点的第一个坐标。 paths.sort(byLength)后较深层数据顺序不变，只改变paths第一层数据即路径的顺序。结果为：[[[2,1],[2,2]],[[1,1],[1,2],[1,3]]] */ function byLength(a:Array, b:Array):Number { if (a.length>b.length) { return 1; } else if (a.lengthvmax-i ? i : vmax-i); j++) { if (j == 0) { tmp_ary.push(sequence[i]); } else { if (sequence[i+j] != undefined) { tmp_ary.push(sequence[i+j]); } if (sequence[i-j] != undefined) { tmp_ary.push(sequence[i-j]); } } } return tmp_ary; } /* 下面函数的作用是判断路径是否被阻断(是否不全为0)，如果被阻断则返回值true，主函数将继续下一个搜索。 a是个数组用来接收一段路径。其他四个数字是例外的点，因为被判断的两个图块不可能是空缺的，但是 路径的两端包含着这两个点，传递这四个参数的目的是把它们当作是通的。 */ function ary_isBlocked(a:Array, x1:Number, y1:Number, x2:Number, y2:Number):Boolean { for (var m = 0; my1 ? y2 : y1); m++) { px_ary.push([0, m]); } for (m=(x1x1 ? x2 : x1); m++) { py_ary.push([m, 0]); } /* 如果两点不在同一列时启动px_ary纵向的遍历 */ if (y1 != y2) { /* 首先建立遍历序列 */ sequence_ary = create_sequence(x1, x2, xmax); for (var i = 0; i<=xmax; i++) { m = sequence_ary[i]; if (mx1) { tmp_ary = p1_x_ary.slice(x1, m); if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) { points_ary = new Array(); continue; } points_ary = points_ary.concat(tmp_ary); } if (y1=0; n--) { if (pot_isBlocked(m, px_ary[n][1], x1, y1, x2, y2)) { points_ary = new Array(); blocked = true; break; } else { blocked = false; } points_ary = points_ary.concat([[m, px_ary[n][1]]]); } if (blocked) { continue; } } if (mx2) { tmp_ary = p2_x_ary.slice(x2, m); tmp_ary.reverse(); if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) { points_ary = new Array(); continue; } points_ary = points_ary.concat(tmp_ary); } paths_ary.push(points_ary); points_ary = new Array(); if (isAll) { } else { break; } } } /* 如果两点不在同一列时启动py_ary横向的遍历 */ if (x1 != x2) { sequence_ary = create_sequence(y1, y2, ymax); for (i=0; i<=ymax; i++) { m = sequence_ary[i]; if (my1) { tmp_ary = p1_y_ary.slice(y1, m); if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) { points_ary = new Array(); continue; } points_ary = points_ary.concat(tmp_ary); } else if (y1 != y2) { continue; } if (x1=0; n--) { if (pot_isBlocked(py_ary[n][0], m, x1, y1, x2, y2)) { points_ary = new Array(); blocked = true; break; } else { blocked = false; } points_ary = points_ary.concat([[py_ary[n][0], m]]); } if (blocked) { continue; } } if (my2) { tmp_ary = p2_y_ary.slice(y2, m); tmp_ary.reverse(); if (ary_isBlocked(tmp_ary, x1, y1, x2, y2)) { points_ary = new Array(); continue; } points_ary = points_ary.concat(tmp_ary); } else if (y1 != y2) { points_ary = new Array(); continue; } paths_ary.push(points_ary); points_ary = new Array(); if (isAll) { } else { break; } } } if (isAll) { } else { /* 如果isAll为false，即只要求得最短路径。 将paths_ary进行排序以便确保最短路径在前面 */ paths_ary.sort(byLength); /* 返回排序后的第一条路经 */ return [paths_ary[0]] } return paths_ary; } }
|
