Veteran's Blog

只要懂得了原理，代码很容易理解。。。
map = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]];
mapH = map[0].length;
mapW = map.length;
tW = 20;
tH = 20;
d = 0;
for (var i = 0; i<mapH; i++) {
    for (var j = 0; j<mapW; j++) {
        _root.attachMovie("tile","w_"+i+"_"+j,i*mapH+j,{_x:20*j, _y:20*i});
        _root["w_"+i+"_"+j].gotoAndPlay(map[i][j]+1);
    }
}
_root.attachMovie("otil","otil",10001,{_x:80, _y:40});
startY = 2;
startX = 4;
path_array = new Array();
lostime.swapDepths(5000);
_root.onMouseDown = function() {
    ctime = getTimer();
    endY = Math.floor(_ymouse/20);
    endX = Math.floor(_xmouse/20);
    path_array = findPath(map, startY, startX, endY, endX);
    //trace(path_array)
    lost = getTimer()-ctime;
    for (var i = 0; i<path_array.length; i++) {
        _root.attachMovie("pathing","pathing"+i,i+10003,{_x:path_array[i][1]*20, _y:path_array[i][0]*20});
        _root["pathing"+i]._alpha = 10;
    }
};
//***************
mapStatus = new Array();
for (var i = 0; i<mapW; i++) {
    mapStatus[i] = new Array();
}
openslist = new Array();
dir = new Array();
dir[0] = new Array(0, 1);
dir[1] = new Array(1, 1);
dir[2] = new Array(1, 0);
dir[3] = new Array(1, -1);
dir[4] = new Array(0, -1);
dir[5] = new Array(-1, -1);
dir[6] = new Array(-1, 0);
dir[7] = new Array(-1, 1);
//***************
findPath = function (map, startY, startX, endY, endX) {
    insertList(startY,startX);
    while (openslist.length>0 && !isClosed(endY, endX)) {
        var nearPoint = searchList();
        nowY = openslist[nearPoint][0];
        nowX = openslist[nearPoint][1];
        deleteList(nowY,nowX);
        for (var k = 0; k<8; k++) {
            if (nowY+dir[k][0]>0 && nowX+dir[k][1]>0 && nowX+dir[k][1]<mapW && nowY+dir[k][0]<mapH) {
                if (map[nowY+dir[k][0]][nowX+dir[k][1]] == 0) {
                    if (!isClosed(nowY+dir[k][0], nowX+dir[k][1])) {
                        G = mapStatus[nowY][nowX].G+(nowX == nowX+dir[k][1] || nowY == nowY+dir[k][0] ? 10 : 14);
                        if (isOpen(nowY+dir[k][0], nowX+dir[k][1])) {
                            if (G<mapStatus[nowY+dir[k][0]][nowX+dir[k][1]].G) {
                                insertList(nowY+dir[k][0],nowX+dir[k][1],[nowY, nowX],G,undefined,true);
                            }
                        } else {
                            var H = Math.abs(nowY+dir[k][0]-endY)+Math.abs(nowX+dir[k][1]-endX)*10;
                            insertList(nowY+dir[k][0],nowX+dir[k][1],[nowY, nowX],G,H,false);
                        }
                    }
                }
            }
        }
    }
    var isfind = isClosed(endY, endX);
    if (isfind) {
        var path = new Array();
        nowY = endY;
        nowX = endX;
        while (nowY<>startY || nowX<>startX) {
            path.push([nowY, nowX]);
            newY = mapStatus[nowY][nowX].parent[0];
            newX = mapStatus[nowY][nowX].parent[1];
            nowY = newY;
            nowX = newX;
        }
        path.push([startY, startX]);
        return path;
    }
};
function isOpen(y, x) {
    return mapStatus[y][x].opens;
}
function isClosed(y, x) {
    return mapStatus[y][x].closed;
}
function insertList(y, x, parent, G, H, replace) {
    if (!replace) {
        openslist.push([y, x]);
        mapStatus[y][x] = {G:G, opens:true, closed:false};
    }
    mapStatus[y][x].parent = parent;
    mapStatus[y][x].G = G;
}
function deleteList(y, x) {
    var len = openslist.length;
    for (var i = 0; i<len; i++) {
        if (openslist[i][0] == y) {
            if (openslist[i][1] == x) {
                openslist.splice(i,1);
                break;
            }
        }
    }
    mapStatus[y][x].opens = false;
    mapStatus[y][x].closed = true;
}
function searchList() {
    var minimum = 999999;
    var indexFound = 0;
    var thisF = undefined;
    var thisSquare = undefined;
    var i = opensList.length;
    while (i-->0) {
        thisSquare = mapStatus[opensList[i][0]][opensList[i][1]];
        thisF = thisSquare.heuristic+thisSquare.movementCost;
        if (thisF<=minimum) {
            minimum = thisF;
            indexFound = i;
        }
    }
    return indexFound;
}


Flash 动画：