a*巡路算法问题

Creator 2.x
#1

Creator 版本号：1.4.2
运行时目标平台：模拟器
操作系统：windows

最近在研究a*巡路的算法，然后自己写了一个，不说废话，先上代码：
--------------------------------------分割线--------------------------------------------
//点对象
var aStarPos = cc.Class({
ctor:function() {
this.pos = cc.v2(0, 0); //所在位置
this.fPos = null; //父节点
this.g = 0; // 到起点的位置
this.h = 0; // 到终点的位置
this.f = 0; //g + h
}
});

//巡路参数
var gridRank = 0; //宽
var gridLine = 0; //高
var gridWidth = 0; //格子大小
var gridArray = []; //障碍数组
var isFour = true; //是否四方向

//设置巡路参数
window.aStar_setPatrolConfig = function(rank, line, width, _gridArray, _isFour) {
gridRank = rank;
gridLine = line;
gridWidth = width;
gridArray = _gridArray;
isFour = _isFour;
};

//A*巡路
window.aStar_partrolFunc = function(startPos, endPos) {
var openArray = []; //开启列表
var closeArray = []; //关闭列表
//起点对象
var startObj = new aStarPos();
startObj.pos = startPos;
startObj.fPos = null;
//添加到关闭数组
closeArray.push(startObj);
//开始检测
return aStar_checkPosition(startPos, endPos, startObj, openArray, closeArray);
};

//位置判断
window.aStar_checkPosition = function(startPos, endPos, starObj, openArray, closeArray) {
//检测点位置
var position = starObj.pos;
var arr = [];

//四方向巡路
if(true === isFour) {
    arr.push(cc.pAdd(position, cc.v2(-1, 0)));
    arr.push(cc.pAdd(position, cc.v2(1, 0)));
    arr.push(cc.pAdd(position, cc.v2(0, -1)));
    arr.push(cc.pAdd(position, cc.v2(0, 1)));
}
//八方向巡路
else {
    arr.push(cc.pAdd(position, cc.v2(-1, 0)));
    arr.push(cc.pAdd(position, cc.v2(1, 0)));
    arr.push(cc.pAdd(position, cc.v2(0, -1)));
    arr.push(cc.pAdd(position, cc.v2(0, 1)));
    arr.push(cc.pAdd(position, cc.v2(-1, -1)));
    arr.push(cc.pAdd(position, cc.v2(-1, 1)));
    arr.push(cc.pAdd(position, cc.v2(1, -1)));
    arr.push(cc.pAdd(position, cc.v2(1, 1)));
}

//判断各个方向
for(var i = 0; i < arr.length; i++) {
    //方向点
    var pos = arr[i];
    //越界处理
    if(pos.x < 0 || pos.x > gridRank || pos.y < 0 || pos.y > gridLine) {
        continue;
    }
    //障碍处理
    if(true === aStar_dealObstacle(pos)) {
        continue;
    }
    
    //判断是否在打开列表
    if(-1 !== aStar_getObj(pos, openArray)) {
        //取出在打开列表的对象
        var oldObj = aStar_getObj(pos, openArray);
        var objPos = oldObj.pos;
        //重新计算g值
        var newG = 0;
        if(true === isFour) {
            newG = (Math.abs(objPos.x - position.x) + Math.abs(objPos.y - position.y)) * gridWidth + starObj.g;
        }
        else {
            var g_x = Math.abs(pos.x - position.x) * gridWidth;
            var g_y = Math.abs(pos.y - position.y) * gridWidth;
            newG = Math.sqrt(g_x * g_x + g_y * g_y) + starObj.g;
        }
        
        //比较替换
        if(newG < oldObj.g) {
            oldObj.g = newG;
            oldObj.fPos = starObj;
        }
    }
    //创建新的
    else {
        //新对象
        var newObj = new aStarPos();
        newObj.pos = pos;
        
        //确定不在列表内
        if(false === aStar_isAloneArray(newObj, closeArray) && false === aStar_isAloneArray(newObj, openArray)) {
            //g、h
            var g = 0;
            var h = 0;
            //区分四方向、八方向
            if(true === isFour) {
                g = (Math.abs(pos.x - position.x) + Math.abs(pos.y - position.y)) * gridWidth + starObj.g;
                h = (Math.abs(pos.x - endPos.x) + Math.abs(pos.y - endPos.y)) * gridWidth;
            }
            else {
                var g_x = Math.abs(pos.x - position.x) * gridWidth;
                var g_y = Math.abs(pos.y - position.y) * gridWidth;
                g = Math.sqrt(g_x * g_x + g_y * g_y) + starObj.g;
                var h_x = Math.abs(pos.x - position.x) * gridWidth;
                var h_y = Math.abs(pos.y - position.y) * gridWidth;
                h = Math.sqrt(h_x * h_x + h_y * h_y);
            }
            
            newObj.fPos = starObj; //父节点
            //赋值
            newObj.g = g;
            newObj.h = h;
            newObj.f = g + h;
            openArray.push(newObj);
            if(pos.x === endPos.x && pos.y === endPos.y) {
                return newObj;
            }
        }
    }
}
//根据f值由低到高排序
openArray = aStar_bubbleSort(openArray);
//从开启列表zhong取出h最低的加入到关闭开启列表中列表
var _obj = openArray.pop();
//开启列表为空说明无路径
if(undefined === _obj) {
    return -1; //死路
}
closeArray.push(_obj);
//继续判断
return aStar_checkPosition(startPos, endPos, _obj, openArray, closeArray);

};

//从列表取出一个对象
window.aStar_getObj = function(pos, array) {
for(var i = 0; i < array.length; i++) {
var a = array[i];
if(a.pos.x === pos.x && a.pos.y === pos.y) {
return a;
}
}
return -1;
};

//判断对象是否在数组内
window.aStar_isAloneArray = function(obj, array) {
for(var i = 0; i < array.length; i++) {
var a = array[i];
if(a.pos.x === obj.pos.x && a.pos.y === obj.pos.y) {
return true;
}
}
return false;
};

//障碍物处理
window.aStar_dealObstacle = function(pos) {
if(1 === gridArray[pos.x][pos.y]) {
return true;
}
else {
return false;
}
};

//冒泡排序
window.aStar_bubbleSort = function(array) {
var i = array.length;
var j = 0;
var tempExchangVal = 0; //中间变量
while (i > 0) {
for (j = 0; j < i - 1; j++) {
if (array[j].f < array[j + 1].f) {
tempExchangVal = array[j];
array[j] = array[j + 1];
array[j + 1] = tempExchangVal;
}
}
i–;
}
return array;
};
--------------------------------------分割线--------------------------------------------

区分了四方向和八方向，经过测试发现一个问题，仅四方向出现，八方向正常，如图：红色为障碍，黄色为路径
四方向不是最短路径

八方向正常

不知道是哪里的问题

1赞