Algorithm A * (A) doesn't work exactly

I'm trying to implement a star search method for college jobs, so I need to do it from scratch, but I'm having trouble getting it working correctly. Here is a picture of my problem:

gray box = Start, Green = End, Yellow = path

As you can see, it finds a way, but not the easiest one.

Here's my tool:

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;
}

      

This is how I instantiate each node (I store it in a matrix):

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);
        }
    }
}

      

Ref code:

- node is a special class that contains "G" and "H" that I use the Manhattan formula to determine "x", "y", "BLOCK" or "NORMAL" (position availability)

- openNodes is the list where I put the correct nodes for the path

- closedNodes are the nodes that I checked, but have large "F" values;

- nodesToLook are neighboring nodes to check.

I appreciate any help. Thank.

+3


source to share


1 answer


Since you haven't posted all your code, I don't know what you are doing with your nodes, but I can see:

  • You are not upgrading G. G is not heuristic , it is the actual cost to reach that node. Aka:nextTile.G = currentTile.G + distanceBetween(currentTile,nextTile)

  • You add only the best option to the open list. So instead of checking all 4, you only check 1


I can go on, but your whole algorithm doesn't work like A *. Correcting your code means a complete rewrite.

The algorithm is very simple. pseudocode in wikipedia can be copied and implemented directly. You seem to have missed a couple of steps there and implemented a lot of things wrong.

+4


source







All Articles