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_p
                    map_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;
}