On my second try with A* I managed to calculate all values needed for traceback. Also marked the starting cell with S, blocked with B and the goal cell with F.

http://s14.directupload.net/file/d/3307/gsiapr4r_png.htm

Now for the backtracking I would simply follow the cells with lowest G value, starting from goal cell. Here I would follow G=24 => G=10 => S.

As you can see this solution would create a path which is not valid because it leads throught a wall in this case.

This hangs together with corner cutting when calculating the values for a grid. As you can see here. One would backtrace: G=50 => G= 40 and here one would take G=20 next. This leads to the corner cutting.

http://s7.directupload.net/file/d/3307/9ffdp83z_png.htm

I think this issue occurs when calculating the values for each adjacent cell. Maybe I could avoid this if I set some restrictions when adding adjacent cells to the current cell?

public List<Cell> GetAdjacent(Cell _currentCell, List<Cell> _closedList, List<Cell> _gridList) { List<Cell> adjacentList = new List<Cell>(); List<Cell> gridList = _gridList; List<Cell> closedList = _closedList; Cell currentCell = _currentCell; foreach (Cell cell in gridList) { bool containedInClosedList = closedList.Any(c => c.id == cell.id); if (!cell.blocked && !containedInClosedList && ((cell.positionCR.X == currentCell.positionCR.X - 1 && cell.positionCR.Y == currentCell.positionCR.Y) || (cell.positionCR.X == currentCell.positionCR.X + 1 && cell.positionCR.Y == currentCell.positionCR.Y) || (cell.positionCR.X == currentCell.positionCR.X && cell.positionCR.Y == currentCell.positionCR.Y - 1) || (cell.positionCR.X == currentCell.positionCR.X && cell.positionCR.Y == currentCell.positionCR.Y + 1) || (cell.positionCR.X == currentCell.positionCR.X - 1 && cell.positionCR.Y == currentCell.positionCR.Y - 1) || (cell.positionCR.X == currentCell.positionCR.X - 1 && cell.positionCR.Y == currentCell.positionCR.Y + 1) || (cell.positionCR.X == currentCell.positionCR.X + 1 && cell.positionCR.Y == currentCell.positionCR.Y - 1) || (cell.positionCR.X == currentCell.positionCR.X + 1 && cell.positionCR.Y == currentCell.positionCR.Y + 1))) { adjacentList.Add(cell); } } return adjacentList; }

Could it also be a problem with the custom costs I defined? I took a G=10 for straight and G=14 for diagonal cells.

I think this is the last thing which stops me from finishing the algorithm, so I am looking forward for any help or constructive input.

Thanks in advance!