c# - A*(A 星)算法不完全有效

Question

我正在尝试为大学作业实现 A 星搜索方法，所以我有点需要从头开始，但我在使其以正确的方式工作时遇到了一些麻烦。这是我的问题的图片:

如您所见，它确实找到了一条路径，但不是最简单的路径。

这是我的工具:

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是要检查的邻居节点。

我很感激任何帮助。谢谢。

Answer 1

因为你还没有发布你的全部代码，我不知道你在用你的节点做什么，但我能看到:

• 您没有更新 G。G 不是启发式，它是到达该节点的实际成本。又名:nextTile.G = currentTile.G + distanceBetween(currentTile,nextTile)
• 您只是将最佳选项添加到开放列表中。因此，您无需检查所有 4 个，而只需检查 1 个

我可以继续，但是您的整个算法根本不像 A* 那样工作。修复代码意味着完全重写它。

这个算法真的很简单。 pseudocode维基百科上的可以直接复制实现。看起来您在那里错过了几个步骤并且错误地实现了很多事情。