为什么我的小规模 A* 路径脚本会跳过所有内容？
Why is my small scale A* pathing script skipping everything?
我正在为 7x7 方格网格上的游戏编写 A* 路径脚本，玩家始终位于中间（方格 24）。零作为视觉对象添加，它实际上是一个数组，而不是 7x7 二维数组。
[00,01,02,03,04,05,06]
[07,08,09,10,11,12,13]
[14,15,16,17,18,19,20]
[21,22,23,24,25,26,27]
[28,29,30,31,32,33,34]
[35,36,37,38,39,40,41]
[42,43,44,45,46,47,48]
该游戏是服务器驱动的，因此玩家使用相对坐标。这意味着，如果玩家移动，tile[0] 就会改变。简而言之，玩家将始终从中间的第 24 块牌开始移动。网格是硬编码的，但如果我 post 公开它，我会稍微更改代码；没问题。
该函数应该有一个目的地，并找到从 24 号地块到那个方块的良好路径，但它实际上做了什么return“未定义”。
如果我输入 24 我希望游戏输出这样的数组
[18,12,6]
代码如下：
z = 0;
function pathTo(goal){
var createPath = function (goal){
var createNode = function(i){
this.id = i;
this.g = Infinity;
this.f = Infinity;
this.parent = null;
this.open = null;
};
this.nodes = Array(49);
for(i=0;i<this.nodes.length;i++){
this.nodes[i] = new createNode(i);
}
this.start = this.nodes[24];
this.start.g = 0;
this.currentNodeId = 24;
this.goal = this.nodes[goal];
this.bestPath = null;
};//end createPath
var getBestNeighbor = function(nodeId){
z++
if(z>50){throw z}debugger;
console.log(nodeId);
var getG = function(parentG){
//here you can check the map for water, sand, and ruins penalties
/*
default = 1
path = .9
water = 3
*/
return (parentG + 1);
};
var closeNode = function (node){
node.open = false;
};//end closeNode
var getF = function(startId,endId,g){
if(g>9){
throw g;
}
var startX = startId % 7;
var startY = (startId - startX) / 7;
var endX = endId % 7;
var endY = (endId - endX) / 7;
var h = Math.sqrt( Math.pow((startX - endX) , 2 ) + Math.pow(( startY - endY ), 2 ) );
console.log("Start.id:"+startId+"H:"+h+" Start.id.g:"+g);
return (h + g);
};//end getF
var tracePath = function(tracedNode){
path.bestPath = [];
while(tracedNode != path.start){
path.bestPath.unshift(tracedNode.id);
tracedNode = tracedNode.parent;
}
return path.bestPath;
};//end tracePath
var getNeighborNodeId = function(x,y,currentId){return currentId + (y*7) + x;};//end getNeighborNodeId
if(path.bestPath === null){
var neighborNode = {};
var bestNode = {f: Infinity};
if(nodeId == path.goal.id){//may need to pass path
return tracePath(path.nodes[nodeId]);
}else{
for(x=-1;x<=1;x++){
for(y=-1;y<=1;y++){
var nnId = getNeighborNodeId(x,y,nodeId);
if(nnId==24){debugger}
if( ( (x!=0) && (y!=0) ) ||( (nnId>=0) && (nnId<=48))){
var neighborNode = path.nodes[nnId];
if(neighborNode.open === null){ neighborNode.open = true; }
if(neighborNode.open === true ){//don't check closed neighbors
if(typeof neighborNode === "object"){
neighborNode.parent = path.nodes[nodeId]
debugger;
neighborNode.g = getG(neighborNode.parent.g);
neighborNode.f = getF(neighborNode.id , path.goal.id , neighborNode.g);
if( neighborNode.f < bestNode.f){
bestNode = neighborNode;
}//endif
}//endif
}//endif Note: if the node isn't null or true, it's false.
}
}//endfor
}//endfor - Note: Here we should have the best neighbor
if(bestNode.f == Infinity){
closeNode(path.nodes[nodeId]);//need escape for no possible path
return;
}else{
//bestNode.parent = path.nodes[nodeId];
path.currentNodeId = bestNode.id;
getBestNeighbor(bestNode.id);
}//endelse
}//endelse
}//endif
};//end getBestNeighbor
var path = new createPath(goal);
while(path.bestPath === null){
getBestNeighbor(path.currentNodeId);
}//end while
return path.bestPath;
}//end pathTo
console.log(pathTo(41)); //testing with 6
和一个 JSFiddle link：https://jsfiddle.net/jb4xtf3h/
这是我第一次不只是到处打全局变量，所以它可能有一个我不熟悉的范围问题。
很可能我的问题出在 getNeighborId 函数中；我不认为我有任何声明好的节点的父节点。
问题是它去了 NW 3 次而不是 NE 3 次。这可能意味着我在 getBestNeighbor 函数中有一个错误，我将 -1 读为 1。
而且我认为我没有正确地转义递归函数。
出于某种原因，当我输入 41 时，它变得非常混乱。这要么与我如何设置 G 和 H 有关，它们通常在 A* 中用于记录在这条路径上行驶的距离和估计的剩余距离。特别是 G 数是错误的，因为它出于某种原因采取了错误的步骤。
这是工作代码。我没有实现墙壁或任何东西，但我确实展示了你会在哪里做。您需要做的就是在开始寻路之前关闭所有作为墙的节点，如果您希望 AI“知道”避免水或沙子，您可以分配移动惩罚。
我实际上无法确定一个问题，但一个主要问题是声明的方式：
if( ( (x!=0) && (y!=0) ) ||( (nnId>=0) && (nnId<=48))){
已更改为：
if( ( !(x==0 && y==0) && ( nnId>=0 && nnId<=48))){
此行的目的是防止搜索您站在 x,y = (0,0) 上的图块，并确保您要查看的邻居在网格上（7x7 网格有49 个方格，编号为 0-48)
我想说的是“如果 X 和 Y 都不为零”显然这实际上使它与 or 语句相同，所以如果任何一个方块为 0，它就会跳过它和需要它的方块 space 遇到了问题，因为有几个方向不起作用。
如果有人需要一个很好的简单路径脚本，我希望对他们有所帮助我非常努力地使代码可读，我不是世界上最强大的编码员，但我认为一个 100 行的工作 A* 脚本很容易理解。如果您正在阅读本文并且不熟悉 A* 路径，您可能需要知道的是
H 是您的启发值，它是对从图块剩余距离的估计。在此代码中，它位于路径对象 path.nodes[array#].h
下
G 是您到目前为止移动到那个方块的距离 path.nodes[array#].g。
F 只是将 h+g 加到总值上。 This pseudocode on Wikipedia帮我写的
var z = 0;
function pathTo(goal){
var createPath = function (goal){
var createNode = function(i){
this.id = i;
this.g = Infinity;
this.f = Infinity;
this.parent = null;
this.open = null;
};
this.nodes = Array(49);
for(i=0;i<this.nodes.length;i++){
this.nodes[i] = new createNode(i);
}
this.start = this.nodes[24];
this.start.g = 0;
this.currentNodeId = 24;
this.goal = this.nodes[goal];
this.bestPath = null;
};//end createPath
var path = new createPath(goal);
var getBestNeighbor = function(nodeId){
var getG = function(parentG){
//here you can check the map for water, sand, and ruins penalties
/*
default = 1
path = .9
water = 3
*/
return (parentG + 1);
};
var closeNode = function (node){
node.open = false;
};//end closeNode
var getF = function(startId,endId,g){
var startX = startId % 7;
var startY = (startId - startX) / 7;
var endX = endId % 7;
var endY = (endId - endX) / 7;
var h = Math.sqrt( Math.pow((startX - endX) , 2 ) + Math.pow(( startY - endY ), 2 ) );
return (h + g);
};//end getF
var tracePath = function(tracedNode){
path.bestPath = [];
while(tracedNode != path.start){
path.bestPath.unshift(tracedNode.id);
tracedNode = tracedNode.parent;
}
return path.bestPath;
};//end tracePath
var getNeighborNodeId = function(x,y,currentId){return currentId + (y*7) + x;};//end getNeighborNodeId
debugger;
z++
if(z>50){throw z}
if(path.bestPath === null){
var neighborNode = {};
var bestNode = {f: Infinity};
if(nodeId == path.goal.id){//may need to pass path
return tracePath(path.nodes[nodeId]);
}else{
for(y=-1;y<=1;y++){
for(x=-1;x<=1;x++){
var nnId = getNeighborNodeId(x,y,nodeId);
if( ( !(x==0 && y==0) && ( nnId>=0 && nnId<=48))){
var neighborNode = path.nodes[nnId];
if(path.nodes[nodeId].parent!=neighborNode){
if(neighborNode.open === null){ neighborNode.open = true; }
if(neighborNode.open === true ){//don't check closed neighbors
if(typeof neighborNode === "object"){
neighborNode.parent = path.nodes[nodeId]
neighborNode.g = getG(neighborNode.parent.g);
neighborNode.f = getF(neighborNode.id , path.goal.id , neighborNode.g);
if( neighborNode.f < bestNode.f){
bestNode = neighborNode;
}//endif
}//endif
}
}//endif Note: if the node isn't null or true, it's false.
}
}//endfor
}//endfor - Note: Here we should have the best neighbor
if(bestNode.f >= 50){
closeNode(path.nodes[nodeId]);//need escape for no possible path
return;
}else{
path.currentNodeId = bestNode.id;
getBestNeighbor(bestNode.id);
}//endelse
}//endelse
}//endif
};//end getBestNeighbor
while(path.bestPath === null){
getBestNeighbor(path.currentNodeId);
}//end while
return path.bestPath;
}//end pathTo
myPath = pathTo(41); //testing with 6
console.log("path2:"+myPath);
我正在为 7x7 方格网格上的游戏编写 A* 路径脚本，玩家始终位于中间（方格 24）。零作为视觉对象添加，它实际上是一个数组，而不是 7x7 二维数组。
[00,01,02,03,04,05,06]
[07,08,09,10,11,12,13]
[14,15,16,17,18,19,20]
[21,22,23,24,25,26,27]
[28,29,30,31,32,33,34]
[35,36,37,38,39,40,41]
[42,43,44,45,46,47,48]
该游戏是服务器驱动的，因此玩家使用相对坐标。这意味着，如果玩家移动，tile[0] 就会改变。简而言之，玩家将始终从中间的第 24 块牌开始移动。网格是硬编码的，但如果我 post 公开它，我会稍微更改代码；没问题。
该函数应该有一个目的地，并找到从 24 号地块到那个方块的良好路径，但它实际上做了什么return“未定义”。
如果我输入 24 我希望游戏输出这样的数组
[18,12,6]
代码如下：
z = 0;
function pathTo(goal){
var createPath = function (goal){
var createNode = function(i){
this.id = i;
this.g = Infinity;
this.f = Infinity;
this.parent = null;
this.open = null;
};
this.nodes = Array(49);
for(i=0;i<this.nodes.length;i++){
this.nodes[i] = new createNode(i);
}
this.start = this.nodes[24];
this.start.g = 0;
this.currentNodeId = 24;
this.goal = this.nodes[goal];
this.bestPath = null;
};//end createPath
var getBestNeighbor = function(nodeId){
z++
if(z>50){throw z}debugger;
console.log(nodeId);
var getG = function(parentG){
//here you can check the map for water, sand, and ruins penalties
/*
default = 1
path = .9
water = 3
*/
return (parentG + 1);
};
var closeNode = function (node){
node.open = false;
};//end closeNode
var getF = function(startId,endId,g){
if(g>9){
throw g;
}
var startX = startId % 7;
var startY = (startId - startX) / 7;
var endX = endId % 7;
var endY = (endId - endX) / 7;
var h = Math.sqrt( Math.pow((startX - endX) , 2 ) + Math.pow(( startY - endY ), 2 ) );
console.log("Start.id:"+startId+"H:"+h+" Start.id.g:"+g);
return (h + g);
};//end getF
var tracePath = function(tracedNode){
path.bestPath = [];
while(tracedNode != path.start){
path.bestPath.unshift(tracedNode.id);
tracedNode = tracedNode.parent;
}
return path.bestPath;
};//end tracePath
var getNeighborNodeId = function(x,y,currentId){return currentId + (y*7) + x;};//end getNeighborNodeId
if(path.bestPath === null){
var neighborNode = {};
var bestNode = {f: Infinity};
if(nodeId == path.goal.id){//may need to pass path
return tracePath(path.nodes[nodeId]);
}else{
for(x=-1;x<=1;x++){
for(y=-1;y<=1;y++){
var nnId = getNeighborNodeId(x,y,nodeId);
if(nnId==24){debugger}
if( ( (x!=0) && (y!=0) ) ||( (nnId>=0) && (nnId<=48))){
var neighborNode = path.nodes[nnId];
if(neighborNode.open === null){ neighborNode.open = true; }
if(neighborNode.open === true ){//don't check closed neighbors
if(typeof neighborNode === "object"){
neighborNode.parent = path.nodes[nodeId]
debugger;
neighborNode.g = getG(neighborNode.parent.g);
neighborNode.f = getF(neighborNode.id , path.goal.id , neighborNode.g);
if( neighborNode.f < bestNode.f){
bestNode = neighborNode;
}//endif
}//endif
}//endif Note: if the node isn't null or true, it's false.
}
}//endfor
}//endfor - Note: Here we should have the best neighbor
if(bestNode.f == Infinity){
closeNode(path.nodes[nodeId]);//need escape for no possible path
return;
}else{
//bestNode.parent = path.nodes[nodeId];
path.currentNodeId = bestNode.id;
getBestNeighbor(bestNode.id);
}//endelse
}//endelse
}//endif
};//end getBestNeighbor
var path = new createPath(goal);
while(path.bestPath === null){
getBestNeighbor(path.currentNodeId);
}//end while
return path.bestPath;
}//end pathTo
console.log(pathTo(41)); //testing with 6
和一个 JSFiddle link：https://jsfiddle.net/jb4xtf3h/
这是我第一次不只是到处打全局变量，所以它可能有一个我不熟悉的范围问题。
很可能我的问题出在 getNeighborId 函数中；我不认为我有任何声明好的节点的父节点。
问题是它去了 NW 3 次而不是 NE 3 次。这可能意味着我在 getBestNeighbor 函数中有一个错误，我将 -1 读为 1。
而且我认为我没有正确地转义递归函数。
出于某种原因，当我输入 41 时，它变得非常混乱。这要么与我如何设置 G 和 H 有关，它们通常在 A* 中用于记录在这条路径上行驶的距离和估计的剩余距离。特别是 G 数是错误的，因为它出于某种原因采取了错误的步骤。
这是工作代码。我没有实现墙壁或任何东西，但我确实展示了你会在哪里做。您需要做的就是在开始寻路之前关闭所有作为墙的节点，如果您希望 AI“知道”避免水或沙子，您可以分配移动惩罚。
我实际上无法确定一个问题，但一个主要问题是声明的方式：
if( ( (x!=0) && (y!=0) ) ||( (nnId>=0) && (nnId<=48))){
已更改为：
if( ( !(x==0 && y==0) && ( nnId>=0 && nnId<=48))){
此行的目的是防止搜索您站在 x,y = (0,0) 上的图块，并确保您要查看的邻居在网格上（7x7 网格有49 个方格，编号为 0-48)
我想说的是“如果 X 和 Y 都不为零”显然这实际上使它与 or 语句相同，所以如果任何一个方块为 0，它就会跳过它和需要它的方块 space 遇到了问题，因为有几个方向不起作用。
如果有人需要一个很好的简单路径脚本，我希望对他们有所帮助我非常努力地使代码可读，我不是世界上最强大的编码员，但我认为一个 100 行的工作 A* 脚本很容易理解。如果您正在阅读本文并且不熟悉 A* 路径，您可能需要知道的是
H 是您的启发值，它是对从图块剩余距离的估计。在此代码中，它位于路径对象 path.nodes[array#].h
G 是您到目前为止移动到那个方块的距离 path.nodes[array#].g。
F 只是将 h+g 加到总值上。 This pseudocode on Wikipedia帮我写的
var z = 0;
function pathTo(goal){
var createPath = function (goal){
var createNode = function(i){
this.id = i;
this.g = Infinity;
this.f = Infinity;
this.parent = null;
this.open = null;
};
this.nodes = Array(49);
for(i=0;i<this.nodes.length;i++){
this.nodes[i] = new createNode(i);
}
this.start = this.nodes[24];
this.start.g = 0;
this.currentNodeId = 24;
this.goal = this.nodes[goal];
this.bestPath = null;
};//end createPath
var path = new createPath(goal);
var getBestNeighbor = function(nodeId){
var getG = function(parentG){
//here you can check the map for water, sand, and ruins penalties
/*
default = 1
path = .9
water = 3
*/
return (parentG + 1);
};
var closeNode = function (node){
node.open = false;
};//end closeNode
var getF = function(startId,endId,g){
var startX = startId % 7;
var startY = (startId - startX) / 7;
var endX = endId % 7;
var endY = (endId - endX) / 7;
var h = Math.sqrt( Math.pow((startX - endX) , 2 ) + Math.pow(( startY - endY ), 2 ) );
return (h + g);
};//end getF
var tracePath = function(tracedNode){
path.bestPath = [];
while(tracedNode != path.start){
path.bestPath.unshift(tracedNode.id);
tracedNode = tracedNode.parent;
}
return path.bestPath;
};//end tracePath
var getNeighborNodeId = function(x,y,currentId){return currentId + (y*7) + x;};//end getNeighborNodeId
debugger;
z++
if(z>50){throw z}
if(path.bestPath === null){
var neighborNode = {};
var bestNode = {f: Infinity};
if(nodeId == path.goal.id){//may need to pass path
return tracePath(path.nodes[nodeId]);
}else{
for(y=-1;y<=1;y++){
for(x=-1;x<=1;x++){
var nnId = getNeighborNodeId(x,y,nodeId);
if( ( !(x==0 && y==0) && ( nnId>=0 && nnId<=48))){
var neighborNode = path.nodes[nnId];
if(path.nodes[nodeId].parent!=neighborNode){
if(neighborNode.open === null){ neighborNode.open = true; }
if(neighborNode.open === true ){//don't check closed neighbors
if(typeof neighborNode === "object"){
neighborNode.parent = path.nodes[nodeId]
neighborNode.g = getG(neighborNode.parent.g);
neighborNode.f = getF(neighborNode.id , path.goal.id , neighborNode.g);
if( neighborNode.f < bestNode.f){
bestNode = neighborNode;
}//endif
}//endif
}
}//endif Note: if the node isn't null or true, it's false.
}
}//endfor
}//endfor - Note: Here we should have the best neighbor
if(bestNode.f >= 50){
closeNode(path.nodes[nodeId]);//need escape for no possible path
return;
}else{
path.currentNodeId = bestNode.id;
getBestNeighbor(bestNode.id);
}//endelse
}//endelse
}//endif
};//end getBestNeighbor
while(path.bestPath === null){
getBestNeighbor(path.currentNodeId);
}//end while
return path.bestPath;
}//end pathTo
myPath = pathTo(41); //testing with 6
console.log("path2:"+myPath);