How to avoid cutting corners with A * pathfinding?

Question

In the second attempt with A *, I was able to calculate all the values ​​needed for tracking. Also marked is the starting cell with S, blocked B and the target cell with F.

Now for backtracking, I will just keep track of the cells with the lowest G value, starting from the target cell.

Here I would follow G = 24 => G = 10 => S.

As you can see, this solution would create a path that is invalid because in this case it leads through the wall.

This freezes along with corner cutting when calculating the values ​​for the grid. As you can see here. One could return: G = 50 => G = 40, and here one could take G = 20. This leads to an angular section.

I think this problem occurs when calculating values ​​for each adjacent cell. Maybe I could avoid this if I set some restrictions when adding neighboring 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 there also be problems with user charges that I have identified? I took G = 10 for straight and G = 14 for diagonal cells.

I think this is the last thing that prevents me from completing the algorithm, so I look forward to any help or constructive input.

Thanks in advance!

Answer 1

As Eric mentioned in the comments above, you can make a list with eight possible neighbors and check if they are valid. Valid here means not only checking to see if they are locked, but you must also check to see if angle reduction is allowed here.