一个JS版寻路的实现

js版的寻路的测试

path
get_v8: function (x_inc, y_inc) {if (x_inc == 0) {if (y_inc < 0) {return [[0, -1], [-1, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [1, 1], [0, 1]];} else if (y_inc > 0) {return [[0, 1], [-1, 1], [1, 1], [-1, 0], [1, 0], [-1, -1], [1, -1], [0, -1]];}}if (y_inc == 0) {if (x_inc < 0) {return [[-1, 0], [-1, -1], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 1], [1, 0]];} else if (x_inc > 0) {return [[1, 0], [1, -1], [1, 1], [0, -1], [0, 1], [-1, -1], [-1, 1], [-1, 0]];}}if ((x_inc == 1) && (y_inc == 1)) {return [[1, 1], [1, 0], [0, 1], [1, -1], [-1, 1], [0, -1], [-1, 0], [-1, -1]];}if ((x_inc == -1) && (y_inc == -1)) {return [[-1, -1], [-1, 0], [0, -1], [-1, 1], [1, -1], [0, 1], [1, 0], [1, 1]];}if ((x_inc == 1) && (y_inc == -1)) {return [[1, -1], [0, -1], [1, 0], [-1, -1], [1, 1], [-1, 0], [0, 1], [-1, 1]];}if ((x_inc == -1) && (y_inc == 1)) {return [[-1, 1], [0, 1], [-1, 0], [1, 1], [-1, -1], [1, 0], [0, -1], [1, -1]];}
},
is_line_path: function (path, i1, i2, map_data) {if (path[i1].col == path[i2].col) {for (var i = i1; i <= i2; i++) {if (map_data.data[path[i].row][path[i1].col] < 1)return false;}return true;}if (path[i1].row == path[i2].row) {for (var i = i1; i <= i2; i++) {if (map_data.data[path[i1].row][path[i].col] < 1)return false;}return true;}return false;
},
smooth_path: function (path, map_data) {for (var k = path.length - 1; k > 0; k--) {var x2 = path[k].col;var y2 = path[k].row;var i_line = -1;for (var i = k - 1; i >= 0; i--) {if ((path[i].col == x2) || (path[i].row == y2)) {if (this.is_line_path(path, i, k, map_data)) {i_line = i;}}}if (i_line >= 0) {if (path[i_line].col == x2) {for (var i = i_line; i <= k; i++) {path[i].col = x2;}}if (path[i_line].row == y2) {for (var i = i_line; i <= k; i++) {path[i].row = y2;}}}}return path;
},
get_path: function (pos1, pos2, map_data) {var pos_from = pos1;var pos_to = this.get_pos_canto(pos2, map_data);var rows = map_data.rows;var cols = map_data.cols;if (map_data.pt) {} else {map_data.pt = [];for (var row = 0; row < rows; row++) {var p = [];for (var col = 0; col < cols; col++) {p.push([0, 0]);}map_data.pt.push(p);}}for (var row = 0; row < rows; row++) {for (var col = 0; col < cols; col++) {if (map_data.data[row][col] >= 1) {map_data.data[row][col] = 1;}}}var v8 = [[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]];var v = v8;var pt = [];var x_p;var y_p;var x;var y;var x_inc;var y_inc;var xy;var is_end = false;var pt_tmp = [];pt.push(pos_from);var path = [];map_data.data[pos_from.row][pos_from.col] = 2;map_data.pt[pos_from.row][pos_from.col] = [0, 0];var maxd = Math.sqrt(map_data.cols * map_data.cols + map_data.rows * map_data.rows);for (var d = 3; d < maxd * 8; d++) {pt_tmp = [];for (var i = 0; i < pt.length; i++) {var x_p = pt[i].col;var y_p = pt[i].row;if (x_p <= 0)continue;if (x_p >= cols)continue;if (y_p <= 0)continue;if (y_p >= rows)continue;if (d > 3) {xy = map_data.pt[y_p][x_p];x_inc = x_p - xy[0];y_inc = y_p - xy[1];v = this.get_v8(x_inc, y_inc);}for (k = 0; k < v.length; k++) {x = x_p + v[k][0];y = y_p + v[k][1];if ((map_data.data[y][x] == 1)) {if (map_data.data[y][x] == 1) {pt_tmp.push({ col: x, row: y });}map_data.data[y][x] = d;map_data.pt[y][x][0] = x_pmap_data.pt[y][x][1] = y_p;if ((x == pos_to.col) && (y == pos_to.row)) {var tmp = [];for (var m = 0; m < d; m++) {xy = map_data.pt[y][x];x = xy[0];y = xy[1];if ((x > 0) && (y > 0)) {tmp.push({ col: x, row: y });}else {break;}}path.push(pos_from);for (var m = tmp.length - 1; m >= 0; m--) {path.push(tmp[m]);}path.push(pos_to);is_end = true;break;}}}if (is_end) {break;}}if (is_end) {break;}pt = pt_tmp;}return this.smooth_path(path, map_data);
},
get_pos_canto: function (pos, map_data) {if (map_data.data[pos.row][pos.col] >= 1) {return pos;}var x1 = 0;var x2 = 0;var y1 = 0;var y2 = 0;var maxd = Math.sqrt(map_data.cols * map_data.cols + map_data.rows * map_data.rows);for (var d = 1; d < maxd; d++) {x1 = pos.col - d;x2 = pos.col + d;y1 = pos.row - d;y2 = pos.row + d;if (x1 < 0) x1 = 0;if (x2 >= map_data.cols) x2 = map_data.cols - 1;if (y1 < 0) y1 = 0;if (y2 >= map_data.rows) y2 = map_data.rows - 1;for (var x = x1; x <= x2; x++) {if (map_data.data[y1][x] >= 1)return { col: x, row: y1 }if (map_data.data[y2][x] >= 1)return { col: x, row: y2 }}for (var y = y1; y <= y2; y++) {if (map_data.data[y][x1] >= 1)return { col: x1, row: y }if (map_data.data[y][x2] >= 1)return { col: x2, row: y }}} return null;
}