A*（A星）算法并非完全起作用。

Question

A*（A星）算法并非完全起作用。

c#unity-game-engineartificial-intelligencea-star

3

我正在尝试为我的大学作业实现A星搜索算法，因此我需要从头开始编写代码。但是我在让它正确工作方面遇到了一些困难。这是我问题的图片：灰色框=起点，绿色=终点，黄色=path

如您所见，它确实找到了路径，但不是最容易的路径。

这是我的实现方式：

public List<node> updateAstar(){
    //clear all the lists
    openedNodes.Clear();
    closedNodes.Clear();
    nodesToLook.Clear();
    //check if starpos and endpos are okay
    if(startPos!=null && endPos!=null){
        float F;
        node currentNote=Grid.getNodeAtPos(startPos);

        openedNodes.Add(currentNote);
        int i = 0;
        int size = 100;
        while(currentNote.type!=tilesType.END){
            if(i<=size){ //debugging purpose. prevent infinite loop 
                nodesToLook.Clear();
                foreach(node nearNode in currentNote.getNearestTiles()){
                    if(closedNodes.Find(r => ((r.pos.x==nearNode.pos.x)&&(r.pos.y==nearNode.pos.y)))==null){
                        nodesToLook.Add(nearNode);
                    }
                }

                float bestValue=float.PositiveInfinity;
                node bestNode=new node();

                foreach(node lookingNode in nodesToLook){
                    //check if current node is not on the closed list
                    if((closedNodes.Find(r => ((r.pos.x==lookingNode.pos.x)&&(r.pos.y==lookingNode.pos.y)))==null)
                        &&(openedNodes.Find(r => ((r.pos.x==lookingNode.pos.x)&&(r.pos.y==lookingNode.pos.y)))==null) 
                        && lookingNode.type!=tilesType.BLOCK){
                        //calculate F=G+H

                        //assume path number is 0 for the question purpose
                        F=lookingNode.G[pathNumber]+lookingNode.H[pathNumber];
                        if(F<bestValue){
                            bestValue=F;
                            bestNode=lookingNode;
                        }else
                            closedNodes.Add(lookingNode);
                    }
                }
                openedNodes.Add(bestNode);
                currentNote=bestNode;
                i++;
            }else{
                Debug.Log("Error getting better path");
                break;
            }
        }
    }else Debug.Log("Current path does not have an startpos nor endpos");
    return openedNodes;
}

如何实例化每个节点（我将其保存在矩阵中）：

coordinate posAux=new coordinate();
this.myNodes=new node[columnNumber,lineNumber];
this.lineNumber=lineNumber;
this.columnNumber=columnNumber;
for(int y=0;y<lineNumber;y++){                      // Y Desce = linhas
    for(int x=0; x<columnNumber; x++){               // X vai pro lado = colunas
        //create a node based on matrix position
        posAux.Set(x, y);
        tilesType type;
        node current=new node(posAux);
        //update up and left nodes
        //"nodeDireita" means rightNode and "nodeEsquerda" means left node
        if(x-1>=0){                 
            current.nodeEsquerda=myNodes[x-1, y];
            myNodes[x-1, y].nodeDireita=current;
        }             
        if(y-1>=0){
            current.nodeAcima=myNodes[x, y-1];
            current.nodeAcima.nodeAbaixo=current;
        }

        //UNity stuff to set type of node visually based on what object is in it
        Collider[] colliders;
        if((colliders = Physics.OverlapSphere(coordinate.gridToUnity(posAux), 3f)).Length >0){
            foreach(Collider collider in colliders){
                objScript obj = collider.gameObject.GetComponent<objScript>();
                current.type=obj.type;
                if(current.type==tilesType.START){
                    path Path = new path (obj.pos, obj.posEnd, this);
                    addPath (Path); 
                    Path.numeroPath=paths.IndexOf(Path);
                }
            }
        }
        myNodes[x,y]=current;
    }
}   
//adicionar vetor[] para H e G com numero de paths nos nodes
//create a vector for multiple paths in each node
int numeroPaths = paths.Count;
for (int y = 0; y < lineNumber; y++) {
    for (int x = 0; x < columnNumber; x++) { 
        myNodes [x, y].H=new float[numeroPaths];
        myNodes [x, y].G=new float[numeroPaths];
    }
}
//adicionar Heuristica e G para cada node em cada path
//calculate heuristic and G for each node in each path
foreach (path Path in paths) {
    coordinate start=Path.startPos, end=Path.endPos;
    int numeroPath=paths.IndexOf(Path);

    for (int y = 0; y < lineNumber; y++) {
        for (int x = 0; x < columnNumber; x++) { 
            coordinate pos = myNodes [x, y].pos;
            //G e H as manhattan distance

            /*Mathf.Sqrt(Mathf.Pow((start.x - pos.x), 2) + Mathf.Pow((start.y - pos.y), 2)); euclidian-does not apply x.x */
            myNodes [x, y].H[numeroPath]=Mathf.Abs(pos.x-end.x) + Mathf.Abs(pos.y-end.y);
            myNodes [x, y].G[numeroPath]=Mathf.Abs(start.x-pos.x) + Mathf.Abs(start.y-pos.y);
        }
    }
}

代码引用：

--node 是一个自定义类，它包含“G”和“H”值。我使用曼哈顿公式来定义“x”，“y”，“BLOCK”或“NORMAL”（该位置的可用性）。

--openedNodes 是我将正确路径的节点放入的列表。

--closedNodes 是我检查过但具有较大“F”值的节点；

--nodesToLook 是要检查的相邻节点。

感谢任何帮助。谢谢。

- markus

1

你是否需要自己实现这个功能？对于我的毕业项目，我只需要引用这个作为dll，然后只需要一行代码就可以实现。 - Sayse

2

只是一个快速的提示：你应该使用HashSet而不是List（更快）甚至是Bit数组。 - Random Dev

我们能在哪里看到完整的源代码吗？现在它非常难以阅读（需要进行重构），如果我能够调试，我可能会找到罪魁祸首...例如：你的 G 或 H 可能有缺陷，但我们看不到方法，而且你处理打开/关闭/访问集合的方式看起来有点奇怪。 - Random Dev

1

首先，您混淆了开放列表和关闭列表。开放列表包含最终需要检查的节点，而关闭列表包含不再需要检查的节点（因为它们不能通过更短的路径到达）。那么，如何计算节点的 G 和 H 值？我没有看到任何成本更新（这是算法的核心部分）。您对列表的处理总体上有些笨拙。例如，您实际上不需要 nodesToLook。相反，直接将节点添加到开放列表中，或者如果它们已经在该列表中，则更新其成本。 - Nico Schertler

乍一看，你的启发式算法要么错误地预测了路径，要么仅将一个最佳邻居添加到PQ中而非全部。 - cerkiewny

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DoXicK · Accepted Answer

由于你没有发布你的整个代码，我完全不知道你对节点做了什么，但是我能看到的是：

你没有更新G的值。G不是一种启发式算法，它是到达该节点的实际代价。即：nextTile.G = currentTile.G + distanceBetween(currentTile,nextTile)
你只添加最佳选项到开放列表中，所以你只检查了其中1个，而不是所有4个。

我还可以继续说下去，但是你的整个算法根本不像A*。修复你的代码意味着需要彻底重写它。

这个算法真的很简单。维基百科上的伪代码可以直接复制实现。你可能错过了几个步骤，实现了很多错误的东西。