A-Star algorithm produces too long path in certain situations.

Questions & Answers
1

Hi,

I have a problem with my A-Star implementation. It produces too long path in certain situations (see image)

[29283-a-star.jpg*|29283]

Here´s the code:

public function findPath(start:GameObject, dest:GameObject):ArrayList{
		if(this.traversed == null){
			return;
		}
		this.path = new ArrayList();
		var openList: ArrayList = new ArrayList();
		var closedList: ArrayList = new ArrayList();
		
		openList.Add(start);
		while((!closedList.Contains(dest))){
			if(openList.Count == 0){
				break;
			}
			var currentCell: GameObject = openList[0] as GameObject;
			var currentGridCell: GridCell = currentCell.GetComponent(GridCell);
			closedList.Add(currentCell);
			openList.Remove(currentCell);
			for(var i = 0; i < currentGridCell.neighbors.length; i++){
				var currentNeighbor:GameObject = currentGridCell.neighbors*;*

  •  		if(!closedList.Contains(currentNeighbor) && this.traversed.Contains(currentNeighbor) && currentNeighbor != null){*

  •  			var currentNeighborGridCell: GridCell = currentNeighbor.GetComponent(GridCell);*

  •  			currentNeighborGridCell.rating = this.rateGridCell(currentNeighbor, dest) + currentNeighborGridCell.moveCost;*

  •  			currentNeighborGridCell.predecessor = currentCell;*

  •  			openList.Add(currentNeighbor);*

  •  		}*

  •  	}*

  •  	openList.Sort(new RatingComparer());*

  •  }*

  •  if(closedList.Contains(dest)){*

  •  	path.Add(dest);*

  •  	dest.renderer.material.color.a = 1.0f;*

  •  	var gridCell: GridCell = dest.GetComponent(GridCell);*

  •  	while(gridCell.predecessor != null){*

  •  		path.Add(gridCell.predecessor);*

  •  		gridCell.predecessor.renderer.material.color.a = 1.0f;*

  •  		gridCell = gridCell.predecessor.GetComponent(GridCell);*

  •  	}*

  •  }*

  •  print(path.Count - 1);*

  •  return path;*

I tried with messing with the heuristic value (now it´s simply the manhattan distance), but it produced even worse paths or the problem occured in other situatons.
What´s wrong with my code?
Thanks in advance.
*

2

My understanding of A* is not perfect. But I would expect a check around line 19 to see if the rating of the current neighbour from this cell is better then the neighbours current rating. If so you need to run lines 21 to 24 again. Something like this:

for(var i = 0; i < currentGridCell.neighbors.length; i++){
    var currentNeighbor:GameObject = currentGridCell.neighbors*;*

if(currentNeighbor != null && !closedList.Contains(currentNeighbor)){
var tentativeRating = this.rateGridCell(currentNeighbor, dest) + currentNeighborGridCell.moveCost;
if((!openList.Contains(currentNeighbor) || (tentativeRating < currentNeighborGridCell.rating)){
var currentNeighborGridCell: GridCell = currentNeighbor.GetComponent(GridCell);
currentNeighborGridCell.rating = tentativeRating;
currentNeighborGridCell.predecessor = currentCell;
if(!openList.Contains(currentNeighbor){
openList.Add(currentNeighbor);
}
}
}
}
Try that out, or something similar. No promises though.