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:
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.
source to share
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.
source to share